Referential transparency

Last updated

In analytic philosophy and computer science, referential transparency and referential opacity are properties of linguistic constructions, [1] and by extension of languages. A linguistic construction is called referentially transparent when for any expression built from it, replacing a subexpression with another one that denotes the same value [2] does not change the value of the expression. [3] [4] Otherwise, it is called referentially opaque. Each expression built from a referentially opaque linguistic construction states something about a subexpression, whereas each expression built from a referentially transparent linguistic construction states something not about a subexpression, meaning that the subexpressions are ‘transparent’ to the expression, acting merely as ‘references’ to something else. [5] For example, the linguistic construction ‘_ was wise’ is referentially transparent (e.g., Socrates was wise is equivalent to The founder of Western philosophy was wise) but ‘_ said _’ is referentially opaque (e.g., Xenophon said ‘Socrates was wise’ is not equivalent to Xenophon said ‘The founder of Western philosophy was wise’).

Contents

Referential transparency depends on the values associated to expressions, that is on the semantics of the language. So, both declarative languages and imperative languages can be referentially transparent or referentially opaque, according to the semantics they are given.

The importance of referential transparency is that it allows the programmer and the compiler to reason about program behavior as a rewrite system. This can help in proving correctness, simplifying an algorithm, assisting in modifying code without breaking it, or optimizing code by means of memoization, common subexpression elimination, lazy evaluation, or parallelization.

History

The concept originated in Alfred North Whitehead and Bertrand Russell's Principia Mathematica (1910–1913): [5]

A proposition as the vehicle or truth or falsehood is a particular occurrence, while a proposition considered factually is a class of similar occurrences. It is the proposition considered factually that occurs in such statements as “A believes p“ and “p is about A.”

Of course it is possible to make statements about the particular fact “Socrates is Greek.” We may say how many centimetres long it is; we may say it is black; and so on. But these are not the statements that a philosopher or logician is tempted to make.

When an assertion occurs, it is made by means of a particular fact, which is an instance of the proposition asserted. But this particular fact is, so to speak, “transparent”; nothing is said about it, but by means of it something is said about something else. It is this “transparent” quality that belongs to propositions as they occur in truth-functions. This belongs to p when p is asserted, but not when we say “p is true.”

It was adopted in analytic philosophy in Willard Van Orman Quine's Word and Object (1960): [3]

When a singular term is used in a sentence purely to specify its object, and the sentence is true of the object, then certainly the sentence will stay true when any other singular term is substituted that designates the same object. Here we have a criterion for what may be called purely referential position: the position must be subject to the substitutivity of identity.

[…]

Referential transparency has to do with constructions (§ 11); modes of containment, more specifically, of singular terms or sentences in singular terms or sentences. I call a mode of containment φ referentially transparent if, whenever an occurrence of a singular term t is purely referential in a term or sentence ψ(t), it is purely referential also in the containing term or sentence φ(ψ(t)).

The term appeared in its contemporary computer science usage in the discussion of variables in programming languages in Christopher Strachey's seminal set of lecture notes Fundamental Concepts in Programming Languages (1967): [4]

One of the most useful properties of expressions is that called by Quine [4] referential transparency. In essence this means that if we wish to find the value of an expression which contains a sub-expression, the only thing we need to know about the sub-expression is its value. Any other features of the sub-expression, such as its internal structure, the number and nature of its components, the order in which they are evaluated or the colour of the ink in which they are written, are irrelevant to the value of the main expression.

Formal definitions

There are three fundamental properties concerning substitutivity in formal languages: referential transparency, definiteness, and unfoldability. [6]

Let’s denote syntactic equivalence with ≡ and semantic equivalence with =.

Referential transparency

A position is defined by a sequence of natural numbers. The empty sequence is denoted by ε and the sequence constructor by ‘.’.

Example. — Position 2.1 in the expression (+ (∗e1e1) (∗e2e2)) is the place occupied by the first occurrence of e2.

Expression ewith expression e′inserted at position p is denoted by e[e′/p] and defined by

e[e′/ε] ≡ e′
e[e′/i.p] ≡ <Ω e1 … ei[e′/p] … en> if e ≡ <Ω e1 … ei … en> else undefined, for all operators Ω and expressions e1, …, en.

Example. — If e ≡ (+ (∗e1e1) (∗e2e2)) then e[e3/2.1] ≡ (+ (∗e1e1) (∗e3e2)).

Position p is purely referential in expression e is defined by

e1 = e2 implies e[e1/p] = e[e2/p], for all expressions e1, e2.

In other words, a position is purely referential in an expression if and only if it is subject to the substitutivity of equals. ε is purely referential in all expressions.

Operator Ω is referentially transparent in place i is defined by

p is purely referential in ei implies i.p is purely referential in e ≡ <Ω e1 … ei … en>, for all positions p and expressions e1, …, en.

Otherwise Ω is referentially opaque in place i.

An operator is referentially transparent is defined by it is referentially transparent in all places. Otherwise it is referentially opaque.

A formal language is referentially transparent is defined by all its operators are referentially transparent. Otherwise it is referentially opaque.

Example. — The ‘_ lives in _’ operator is referentially transparent:

She lives in London.

Indeed, the second position is purely referential in the assertion because substituting The capital of the United Kingdom for London does not change the value of the assertion. The first position is also purely referential for the same substitutivity reason.

Example. — The ‘_ contains _’ and quote operators are referentially opaque:

‘London’ contains six letters.

Indeed, the first position is not purely referential in the statement because substituting The capital of the United Kingdom for London changes the value of the statement and the quotation. So in the first position, the ‘_ contains _’ and quote operators destroy the relation between an expression and the value that it denotes.

Example. — The ‘_ refers to _’ operator is referentially transparent, despite the referential opacity of the quote operator:

‘London’ refers to the largest city of the United Kingdom.

Indeed, the first position is purely referential in the statement, though it is not in the quotation, because substituting The capital of the United Kingdom for London does not change the value of the statement. So in the first position, the ‘_ refers to _’ operator restores the relation between an expression and the value that it denotes. The second position is also purely referential for the same substitutivity reason.

Definiteness

A formal language is definite is defined by all the occurrences of a variable within its scope denote the same value.

Example. — Mathematics is definite:

3x2 + 2x + 17.

Indeed, the two occurrences of x denote the same value.

Unfoldability

A formal language is unfoldable is defined by all expressions are β-reducible.

Example. — The lambda calculus is unfoldable:

((λx.x + 1) 3).

Indeed, ((λx.x + 1) 3) = (x + 1)[3/x].

Relations between the properties

Referential transparency, definiteness, and unfoldability are independent. Definiteness implies unfoldability only for deterministic languages. Non-deterministic languages cannot have definiteness and unfoldability at the same time.

See also

Related Research Articles

In grammar, a noun is a word that represents a concrete or abstract thing, such as living creatures, places, actions, qualities, states of existence, and ideas. A noun may serve as an object or subject within a phrase, clause, or sentence.

In linguistics and related fields, pragmatics is the study of how context contributes to meaning. The field of study evaluates how human language is utilized in social interactions, as well as the relationship between the interpreter and the interpreted. Linguists who specialize in pragmatics are called pragmaticians. The field has been represented since 1986 by the International Pragmatics Association (IPrA).

A proposition is a central concept in the philosophy of language, semantics, logic, and related fields, often characterized as the primary bearer of truth or falsity. Propositions are also often characterized as being the kind of thing that declarative sentences denote. For instance the sentence "The sky is blue" denotes the proposition that the sky is blue. However, crucially, propositions are not themselves linguistic expressions. For instance, the English sentence "Snow is white" denotes the same proposition as the German sentence "Schnee ist weiß" even though the two sentences are not the same. Similarly, propositions can also be characterized as the objects of belief and other propositional attitudes. For instance if one believes that the sky is blue, what one believes is the proposition that the sky is blue. A proposition can also be thought of as a kind of idea: Collins Dictionary has a definition for proposition as "a statement or an idea that people can consider or discuss whether it is true."

Curry is a declarative programming language, an implementation of the functional logic programming paradigm, and based on the Haskell language. It merges elements of functional and logic programming, including constraint programming integration.

In formal semantics and philosophy of language, a definite description is a denoting phrase in the form of "the X" where X is a noun-phrase or a singular common noun. The definite description is proper if X applies to a unique individual or object. For example: "the first person in space" and "the 42nd President of the United States of America", are proper. The definite descriptions "the person in space" and "the Senator from Ohio" are improper because the noun phrase X applies to more than one thing, and the definite descriptions "the first man on Mars" and "the Senator from Washington D.C." are improper because X applies to nothing. Improper descriptions raise some difficult questions about the law of excluded middle, denotation, modality, and mental content.

In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: the input and output of a truth function are all truth values; a truth function will always output exactly one truth value, and inputting the same truth value(s) will always output the same truth value. The typical example is in propositional logic, wherein a compound statement is constructed using individual statements connected by logical connectives; if the truth value of the compound statement is entirely determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and any logical connectives used are said to be truth functional.

Short-circuit evaluation, minimal evaluation, or McCarthy evaluation is the semantics of some Boolean operators in some programming languages in which the second argument is executed or evaluated only if the first argument does not suffice to determine the value of the expression: when the first argument of the AND function evaluates to false, the overall value must be false; and when the first argument of the OR function evaluates to true, the overall value must be true.

The theory of descriptions is the philosopher Bertrand Russell's most significant contribution to the philosophy of language. It is also known as Russell's theory of descriptions. In short, Russell argued that the syntactic form of descriptions is misleading, as it does not correlate their logical and/or semantic architecture. While descriptions may seem like fairly uncontroversial phrases, Russell argued that providing a satisfactory analysis of the linguistic and logical properties of a description is vital to clarity in important philosophical debates, particularly in semantic arguments, epistemology and metaphysical elements.

In semiotics, linguistics, anthropology, and philosophy of language, indexicality is the phenomenon of a sign pointing to some element in the context in which it occurs. A sign that signifies indexically is called an index or, in philosophy, an indexical.

David Benjamin Kaplan is an American philosopher. He is the Hans Reichenbach Professor of Scientific Philosophy at the UCLA Department of Philosophy. His philosophical work focuses on the philosophy of language, logic, metaphysics, epistemology and the philosophy of Frege and Russell. He is best known for his work on demonstratives, propositions, and reference in intensional contexts. He was elected a Fellow of the American Academy of Arts & Sciences in 1983 and a Corresponding Fellow of the British Academy in 2007.

In any of several fields of study that treat the use of signs — for example, in linguistics, logic, mathematics, semantics, semiotics, and philosophy of language — an extensional context is a syntactic environment in which a sub-sentential expression e can be replaced by an expression with the same extension and without affecting the truth-value of the sentence as a whole. Extensional contexts are contrasted with opaque contexts where truth-preserving substitutions are not possible.

An opaque context or referentially opaque context is a linguistic context in which it is not always possible to substitute "co-referential" expressions without altering the truth of sentences. The expressions involved are usually grammatically singular terms. So, substitution of co-referential expressions into an opaque context does not always preserve truth. For example, "Lois believes x is a hero" is an opaque context because "Lois believes Superman is a hero" is true while "Lois believes Clark Kent is a hero" is false, even though 'Superman' and 'Clark Kent' are co-referential expressions.

"On Denoting" is an essay by Bertrand Russell. It was published in the philosophy journal Mind in 1905. In it, Russell introduces and advocates his theory of denoting phrases, according to which definite descriptions and other "denoting phrases ... never have any meaning in themselves, but every proposition in whose verbal expression they occur has a meaning." This theory later became the basis for Russell's descriptivism with regard to proper names, and his view that proper names are "disguised" or "abbreviated" definite descriptions.

A truth-bearer is an entity that is said to be either true or false and nothing else. The thesis that some things are true while others are false has led to different theories about the nature of these entities. Since there is divergence of opinion on the matter, the term truth-bearer is used to be neutral among the various theories. Truth-bearer candidates include propositions, sentences, sentence-tokens, statements, beliefs, thoughts, intuitions, utterances, and judgements but different authors exclude one or more of these, deny their existence, argue that they are true only in a derivative sense, assert or assume that the terms are synonymous, or seek to avoid addressing their distinction or do not clarify it.

In computer science and recursion theory the McCarthy Formalism (1963) of computer scientist John McCarthy clarifies the notion of recursive functions by use of the IF-THEN-ELSE construction common to computer science, together with four of the operators of primitive recursive functions: zero, successor, equality of numbers and composition. The conditional operator replaces both primitive recursion and the mu-operator.

Refal "is a functional programming language oriented toward symbolic computations", including "string processing, language translation, [and] artificial intelligence". It is one of the oldest members of this family, first conceived of in 1966 as a theoretical tool, with the first implementation appearing in 1968. Refal was intended to combine mathematical simplicity with practicality for writing large and sophisticated programs.

<i>Word and Object</i> 1960 book by Willard Van Orman Quine

Word and Object is a 1960 work by the philosopher Willard Van Orman Quine, in which the author expands upon the line of thought of his earlier writings in From a Logical Point of View (1953), and reformulates some of his earlier arguments, such as his attack in "Two Dogmas of Empiricism" on the analytic–synthetic distinction. The thought experiment of radical translation and the accompanying notion of indeterminacy of translation are original to Word and Object, which is Quine's most famous book.

Salva congruitate is a Latin scholastic term in logic, which means "without becoming ill-formed", salva meaning rescue, salvation, welfare and congruitate meaning combine, coincide, agree. Salva Congruitate is used in logic to mean that two terms may be substituted for each other while preserving grammaticality in all contexts.

Q0 is Peter Andrews' formulation of the simply-typed lambda calculus, and provides a foundation for mathematics comparable to first-order logic plus set theory. It is a form of higher-order logic and closely related to the logics of the HOL theorem prover family.

In computer science, having value semantics means for an object that only its value counts, not its identity. Immutable objects have value semantics trivially, and in the presence of mutation, an object with value semantics can only be uniquely-referenced at any point in a program.

References

  1. ↑ A linguistic construction (also called mode of containment, context, or operator) is an expression with holes.
  2. ↑ Here a value is the denotation (also called meaning, object, or referent) of an expression, not the result of the evaluation process.
  3. 1 2 Quine, Willard Van Orman (1960). Word and Object (1st ed.). Cambridge, Massachusetts: MIT Press. p. 144. ISBN   978-0-262-17001-7.
  4. 1 2 Strachey, Christopher (1967). Fundamental Concepts in Programming Languages (Technical report). Lecture notes for the International Summer School in Computer Programming at Copenhagen. Also: Strachey, Christopher (2000). "Fundamental Concepts in Programming Languages". Higher-Order and Symbolic Computation. 13 (1–2): 11–49. doi:10.1023/A:1010000313106. S2CID   14124601.
  5. 1 2 Whitehead, Alfred North; Russell, Bertrand (1927). Principia Mathematica. Vol. 1 (2nd ed.). Cambridge: Cambridge University Press. p. 665. ISBN   978-0-521-06791-1.
  6. ↑ Søndergaard, Harald; Sestoft, Peter (1990). "Referential Transparency, Definiteness and Unfoldability" (PDF). Acta Informatica. 27 (6): 505–517. doi:10.1007/bf00277387.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.