Referential transparency (other)
   HOME

TheInfoList



OR:

In
analytic philosophy Analytic philosophy is a branch and tradition of philosophy using analysis, popular in the Western world and particularly the Anglosphere, which began around the turn of the 20th century in the contemporary era in the United Kingdom, United Sta ...
and computer science, referential transparency and referential opacity are properties of linguistic constructions, 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 valueHere a value is the denotation (also called meaning, object, or referent) of an expression, not the result of the evaluation process. does not change the value of the expression. Also: 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. 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’''). Referential transparency depends on the values associated to expressions, that is on the semantics of the language. So, both
declarative language In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow. Many languages that a ...
s and
imperative language In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program c ...
s 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 A computer programmer, sometimes referred to as a software developer, a software engineer, a programmer or a coder, is a person who creates computer programs — often for larger computer software. A programmer is someone who writes/creates ...
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 In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...
, common subexpression elimination, lazy evaluation, or parallelization.


History

The concept originated in
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher. He is best known as the defining figure of the philosophical school known as process philosophy, which today has found applicat ...
and Bertrand Russell's '' Principia Mathematica'' (1910–1913):
A proposition as the vehicle of 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):
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 is purely referential in a term or sentence , it is purely referential also in the containing term or sentence .
The term appeared in its contemporary computer science usage in the discussion of
variable Variable may refer to: * Variable (computer science), a symbolic name associated with a value and whose associated value may be changed * Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
s in programming languages in
Christopher Strachey Christopher S. Strachey (; 16 November 1916 – 18 May 1975) was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design and computer time-sharing.F. J. Corbató, et al., ...
's seminal set of lecture notes ''
Fundamental Concepts in Programming Languages ''Fundamental Concepts in Programming Languages'' were an influential set of lecture notes written by Christopher Strachey for the International Summer School in Computer Programming at Copenhagen in August, 1967. It introduced much programming l ...
'' (1967):
One of the most useful properties of expressions is that called by Quine ''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. 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 is the place occupied by the first occurrence of . Expression ''with'' expression ''inserted at'' position is denoted by and defined by : : if else undefined, for all operators and expressions . ''Example.'' — If then . Position is ''purely referential'' in expression is defined by : implies , for all expressions . 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 is defined by : is purely referential in implies is purely referential in , for all positions and expressions . Otherwise is ''referentially opaque'' in place . 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: : . Indeed, the two occurrences of denote the same value.


Unfoldability

A formal language is ''unfoldable'' is defined by all expressions are β-reducible. ''Example.'' — The
lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
is unfoldable: : . Indeed, .


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

*
Liskov substitution principle The Liskov substitution principle (LSP) is a particular definition of a subtyping relation, called strong behavioral subtyping, that was initially introduced by Barbara Liskov in a 1988 conference keynote address titled ''Data abstraction and h ...
*
Rewrite rule In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or redu ...


References

{{reflist


External links

* http://userpage.fu-berlin.de/~ram/pub/pub_jf47ht81Ht/referential_transparency * https://stackoverflow.com/a/9859966/655289 b
Prof. Uday Reddy
(University of Birmingham) * http://okmij.org/ftp/Computation/PrincipiaMathematica.txt Programming language theory