By Claudiu


2008-10-17 01:27:53 8 Comments

What does the term referential transparency mean? I've heard it described as "it means you can replace equals with equals" but this seems like an inadequate explanation.

13 comments

@Can 2019-07-13 09:17:07

Referential transparency can be simply stated as:

  • An expression always evaluating to the same result in any context [1],
  • A function, if given the same parameters twice, must produce the same result twice [2].

For example, the programming language Haskell is a pure functional language; meaning that it is referentially transparent.

@Uday Reddy 2012-03-25 12:03:24

The term "referential transparency" comes from analytical philosophy, the branch of philosophy that analyzes natural language constructs, statements and arguments based on the methods of logic and mathematics. In other words, it is the closest subject outside computer science to what we call programming language semantics. The philosopher Willard Quine was responsible for initiating the concept of referential transparency, but it was also implicit in the approaches of Bertrand Russell and Alfred Whitehead.

At its core, "referential transparency" is a very simple and clear idea. The term "referent" is used in analytical philosophy to talk about the thing that an expression refers to. It is roughly the same as what we mean by "meaning" or "denotation" in programming language semantics. Using Andrew Birkett's example (blog post), the term "the capital of Scotland" refers to the city of Edinburgh. That is a straightforward example of a "referent".

A context in a sentence is "referentially transparent" if replacing a term in that context by another term that refers to the same entity doesn't alter the meaning. For example

The Scottish Parliament meets in the capital of Scotland.

means the same as

The Scottish Parliament meets in Edinburgh.

So the context "The Scottish Parliament meets in ..." is a referentially transparent context. We can replace "the capital of Scotland" with "Edinburgh" without altering the meaning. To put another way, the context only cares about what the term refers to and nothing else. That is the sense in which the context is "referentially transparent."

On the other hand, in the sentence,

Edinburgh has been the capital of Scotland since 1999.

we can't do such a replacement. If we did, we would get "Edinburgh has been Edinburgh since 1999", which is a nutty thing to say, and doesn't convey the same meaning as the original sentence. So, it would seem that the context "Edinburgh has been ... since 1999" is referentially opaque (the opposite of referentially transparent). It apparently cares about something more than what the term refers to. What is it?

Things such as "the capital of Scotland" are called definite terms and they gave no lean amount of head ache to logicians and philosophers for a long time. Russell and Quine sorted them out saying that they are not actually "referential", i.e., it is a mistake to think that the above examples are used to refer to entities. The right way to understand "Edinburgh has been the capital of Scotland since 1999" is to say

Scotland has had a capital since 1999 and that capital is Edinburgh.

This sentence cannot be transformed to a nutty one. Problem solved! The point of Quine was to say that natural language is messy, or at least complicated, because it is made to be convenient for practical use, but philosophers and logicians should bring clarity by understanding them in the right way. Referential transparency is a tool to be used for bringing such clarity of meaning.

What does all this have to do with programming? Not very much, actually. As we said, referential transparency is a tool to be used in understanding language, i.e., in assigning meaning. Christopher Strachey, who founded the field of programming language semantics, used it in his study of meaning. His foundational paper "Fundamental concepts in programming languages" is available on the web. It is a beautiful paper and everybody can read and understand it. So, please do so. You will be much enlightened. He introduces the term "referential transparency" in this paragraph:

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.

The use of "in essence" suggests that Strachey is paraphrasing it in order to explain it in simple terms. Functional programmers seem to understand this paragraph in their own way. There are 9 other occurrences of "referential transparency" in the paper, but they don't seem to bother about any of the others. In fact, the whole paper of Strachey is devoted to explaining the meaning of imperative programming languages. But, today, functional programmers claim that imperative programming languages are not referentially transparent. Strachey would be turning in his grave.

We can salvage the situation. We said that natural language is "messy, or at least complicated" because it is made to be convenient for practical use. Programming languages are the same way. They are "messy, or at least complicated" because they are made to be convenient for practical use. That does not mean that they need to confuse us. They just have to be understood the right way, using a meta language that is referentially transparent so that we have clarity of meaning. In the paper I cited, Strachey does exactly that. He explains the meaning of imperative programming languages by breaking them down into elementary concepts, never losing clarity anywhere. An important part of his analysis is to point out that expressions in programming languages have two kinds of "values", called l-values and r-values. Before Strachey's paper, this was not understood and confusion reigned supreme. Today, the definition of C mentions it routinely and every C programmer understands the distinction. (Whether the programmers in other languages understand it equally well is hard to say.)

Both Quine and Strachey were concerned with the meaning of language constructions that involve some form of context-dependence. For example, our example "Edinburgh has been the capital of Scotland since 1999" signifies the fact that "capital of Scotland" depends on the time at which it is being considered. Such context-dependence is a reality, both in natural languages and programming languages. Even in functional programming, free and bound variables are to be interpreted with respect to the context in which they appear in. Context dependence of any kind blocks referential transparency in some way or the other. If you try to understand the meaning of terms without regard to the contexts they depend on, you would again end up with confusion. Quine was concerned with the meaning of modal logic. He held that modal logic was referentially opaque and it should be cleaned up by translating it into a referentially transparent framework (e.g., by regarding necessity as provability). He largely lost this debate. Logicians and philosophers alike found Kripke's possible world semantics to be perfectly adequate. Similar situation also reigns with imperative programming. State-dependence explained by Strachey and store-dependence explained by Reynolds (in a manner similar to Kripke's possible world semantics) are perfectly adequate. Functional programmers don't know much of this research. Their ideas on referential transparency are to be taken with a large grain of salt.

[Additional note: The examples above illustrate that a simple phrase such as "capital of Scotland" has multiple levels of meaning. At one level, we might be talking about the capital at the current time. At another level, we might talking about all possible capitals that Scotland might have had through the course of time. We can "zoom into" a particular context and "zoom out" to span all contexts quite easily in normal practice. The efficiency of natural language makes use of our ability to do so. Imperative programming languages are efficient in very much the same way. We can use a variable x on the right hand side of an assignment (the r-value) to talk about its value in a particular state. Or, we might talk about its l-value which spans all states. People are rarely confused by such things. However, they may or may not be able to precisely explain all the layers of meaning inherent in language constructs. All such layers of meaning are not necessarily 'obvious' and it is a matter of science to study them properly. However, the inarticulacy of ordinary people to explain such layered meanings doesn't imply that they are confused about them.]

A separate "postscript" below relates this discussion to the concerns of functional and imperative programming.

@Ryan Culpepper 2012-03-25 12:47:12

Great explanation. I think the extension of "referentially transparent" to languages and functions can roughly be translated as "All expression contexts in the language (or all argument contexts for the function, respectively) are referentially transparent with respect to the 'obvious' extensional notion of equality."

@Uday Reddy 2012-03-25 14:23:19

Thanks, but I don't hold that there is an 'obvious' extensional notion of equality. When I said the "capital of Scotland" refers to the city of Edinburgh, you didn't think twice about it. But when I started talking about "since 1999", you suddenly became aware that there is time involved. So, the extensional notion of equality can be quite subtle and it is formalized by programming language researchers. People that want to have a perfect understanding of the extensional equality need to learn the fruits of that research. It may not at all be 'obvious'.

@sclv 2012-07-26 23:56:35

Fantastic answer! I got a great deal out of this. I'd love any references you may have on the history of referential transparency in analytic philosophy, or on the history analytic philosophy as it pertains to computer science more generally.

@Conal 2012-07-27 00:25:52

Fantastic! A welcome relief to popular misconceptions about RT, e.g., tying it to functions. Or defining via replacing an expression with its value (as on Wikipedia)--oddly so since expressions and values are different kinds of things. Perhaps one place where people go wrong in considering RT-ness of imperative languages is to assume that these "values" are simple things like numbers rather than more complex things like functions from a store.

@Uday Reddy 2012-07-27 19:37:02

@sclv Quine's "Word and Object," which is cited by Strachey in his paper, has a chapter called "vagaries of reference," which deals with the issue. Many other articles of Quine also deal with the issues of reference. If you are interested in reading more about the analysis of referential transparency, you might enjoy reading Sondergaard and Sestoft: Referential transparency, definiteness and unfoldability.

@Uday Reddy 2012-07-28 07:47:49

@sclv As for the broader impact of analytical philosophy on Computer Science, I should say that Computer Science, as we know it, was founded by Godel, Church, Kleene and Turing. These people were logicians and they were well-versed in both the mathematical and philosophical aspects of logic, in particular the traditions of Peano, Frege, Russell, Whitehead, Carnap and Quine. The early pioneers of modern Computer Science knew the connections. But the rapid growth of Computer Science has severed them. We need to get back to them.

@Uday Reddy 2012-07-28 07:54:11

@sclv Logic is traditionally construed as the science of consequence. But I think it is a broader. It is the science of information. Quine, I see as the first one that who brought forth the broader view. "Word and object" is an analysis of the information content of natural language statements. However, neither philosophers nor mathematicians have ever taken an active interest in computations, which is quite perplexing, given how central computation has been for civilization and science from time immemorial. We need to find ways to get them interested.

@Uday Reddy 2012-07-29 09:29:08

@Conal: My feeling is that there is indeed some tenuous correspondence between Quine-Strachey notions of referential transparency and the present day functional programmers' notion. But the nature of this correspondence is not sufficiently clear in my mind to articulate it well at this point. I will continue to think about it.

@Uday Reddy 2012-07-31 13:05:09

@Conal: I have added a new answer that amplifies your point. It will probably be at the bottom of the page.

@Maggyero 2018-07-13 11:51:38

Great answer. But I find your answer on Reddit much clearer: reddit.com/r/haskell/comments/xgq27/…

@Philip Schwarz 2018-12-09 09:59:03

I found the definition of referential transparency in the book "Structure and Implementation of Computer Programs" (the Wizard Book) useful because it is complemented by an explanation of how referential transparency is violated by introducing the assignment operation. Check out the following slide deck I made about the subject: https://www.slideshare.net/pjschwarz/introducing-assignment-invalidates-the-substitution-model-of-evaluation-and-violates-referential-transparency-as-explained-in-sicp-the-wizard-book

@Brian R. Bondy 2008-10-17 01:39:57

Referential transparency, a term commonly used in functional programming, means that given a function and an input value, you will always receive the same output. That is to say there is no external state used in the function.

Here is an example of a referential transparent function:

int plusOne(int x)
{
  return x+1;
}

With a referential transparent function, given an input and a function, you could replace it with a value instead of calling the function. So instead of calling plusOne with a parameter of 5, we could just replace that with 6.

Another good example is mathematics in general. In mathematics given a function and an input value, it will always map to the same output value. f(x) = x + 1. Therefore functions in mathematics are referentially transparent.

This concept is important to researchers because it means that when you have a referentially transparent function, it lends itself to easy automatic parallelization and caching.

Referential transparency is used always in functional languages like Haskell.

--

In contrast there is the concept of referential opaqueness. This means the opposite. Calling the function may not always produce the same output.

//global G
int G = 10;

int plusG(int x)
{//G can be modified externally returning different values.
  return x + G;
}

Another example, is a member function in an object oriented programming language. Member functions commonly operate on its member variables and therefore would be referential opaque. Member functions though can of course be referentially transparent.

Yet another example is a function that reads from a text file and prints the output. This external text file could change at any time so the function would be referentially opaque.

@Jonathan Arkell 2008-10-17 04:51:13

Just a heads up, it is possible to have a fully referentially transparent object, with referentially transparent member functions. See okmij.org/ftp/Scheme/oop-in-fp.txt

@Jonathan Arkell 2008-10-17 04:53:25

And here is the code that is being talked about in that article: okmij.org/ftp/Scheme/pure-oo-system.scm

@Brian R. Bondy 2008-10-17 12:14:47

In the case of a fully referentially transparent class, you would probably have all member functions static.

@Claudiu 2009-04-26 23:14:10

Good links! lots of people conflate object-oriented with imperative. They are orthogonal to each other.

@Conal 2012-08-01 00:49:34

What you're talking about here is not referential transparency, though it's commonly referred to as such. See Uday's two answers and the comments on them. In particular, what you call the "output" is not the denotation. If you replaced "plusG 3" with any other expression having the same value/denotation, you would indeed get a program with the same meaning, so RT does hold in imperative languages. The expression "3+10" or "13" do not have the same meaning as "plusG 3", because meaning in imperative languages is a function of the "store" (state).

@Gaurav 2015-02-11 10:00:43

I just read an article on side effects and changing of state and have got an intuition that it has something to do with RT. Could you please add a note on it?

@Pacerier 2015-03-06 03:36:33

@JonathanArkell, Code link is down.............................

@Pedro Lourenço 2018-01-07 20:17:12

Upvoted for finally stating the true definition by example I was looking for: code.

@philipxy 2018-02-28 22:23:26

@PedroLourenço But this answer is wrong, echoing a common misconception, see UdayReddy's (correct) answers & comments. Also Conal's.

@user5998940 2016-02-29 17:45:32

The following answer I hope adds to and qualifies the controversial 1st and 3rd answers.

Let us grant that an expression denotes or refers to some referent. However, a question is whether these referents can be encoded isomorphically as part of expressions themselves, calling such expressions 'values'. For example, literal number values are a subset of the set of arithmetic expressions, truth values are a subset of the set of boolean expressions, etc. The idea is to evaluate an expression to its value (if it has one). So the word 'value' may refer to a denotation or to a distinguished element of the set of expressions. But if there is an isomorphism (a bijection) between the referent and the value we can say they are the same thing. (This said, one must be careful to define the referents and the isomorphism, as proven by the field of denotational semantics. To put an example mentioned by replies to the 3rd answer, the algebraic data type definition data Nat = Zero | Suc Nat does not correspond as expected to the set of natural numbers.)

Let us write E[·] for an expression with a hole, also known in some quarters as a 'context'. Two context examples for C-like expressions are [·]+1 and [·]++.

Let us write [[·]] for the function that takes an expression (with no hole) and delivers its meaning (referent, denotation, etc.) in some meaning-providing universe. (I'm borrowing notation from the field of denotational semantics.)

Let us adapt Quine's definition somewhat formally as follows: a context E[·] is referentially transparent iff given any two expressions E1 and E2 (no holes there) such that [[E1]] = [[E2]] (i.e. the expressions denote/refer-to the same referent) then it is the case that [[E[E1]]] = [[E[E2]]] (i.e. filling-in the hole with either E1 or E2 results in expressions that also denote the same referent).

Leibniz's rule of substituting equals for equals is typically expressed as 'if E1 = E2 then E[E1] = E[E2]', which says that E[·] is a function. A function (or for that matter a program computing the function) is a mapping from a source to a target so that there is at most one target element for each source element. Non-deterministic functions are misnomers, they are either relations, functions delivering sets, etc. If in Leibniz's rule the equality = is denotational then the double-brackets are simply taken for granted and elided. So a referentially transparent context is a function. And Leibniz's rule is the main ingredient of equational reasoning, so equational reasoning is definitely related to referential transparency.

Although [[·]] is a function from expressions to denotations, it could be a function from expressions to 'values' understood as a restricted subset of expressions, and [[·]] can be understood as evaluation.

Now, if E1 is an expression and E2 is a value we have what I think is meant by most people when defining referential transparency in terms of expressions, values, and evaluation. But as illustrated by the 1st and 3rd answers in this page, this is an inacurate definition.

The problem with contexts such as [·]++ is not the side effect, but that its value is not defined in C isomorphically to its meaning. Functions are not values (well, pointers to functions are) whereas in functional programming languages they are. Landin, Strachey, and the pioneers of denotational semantics were quite clever in using functional worlds to provide meaning.

For imperative C-like languages we can (roughly) provide semantics to expressions using the function [[·]] : Expression -> (State -> State x Value).

Value is a subset of Expression. State contains pairs (identifier,value). The semantic function takes an expression and delivers as its meaning a function from the current state to the pair with the updated state and a value. For example, [[x]] is the function from the current state to the pair whose first component is the current state and whose second component is the value of x. In contrast, [[x++]] is the function from the current state to the pair whose first component is a state in which the value of x is incremented, and whose second component is that very value. In this sense, the context [·]++ is referentially transparent iff it satisfies the definition given above.

I think functional programmers are entitled to use referential transparency in the sense that they naturally recover [[·]] as a function from expressions to values. Functions are first-class values and the state can also be a value, not a denotation. The state monad is (in part) a clean mechanism for passing (or threading) the state.

@philipxy 2018-02-28 22:42:25

Presumably the "1st" & "3rd" answers are UdayReddy's "March 25" & "postscript" answers, respectively. Ordinals are not a good way to refer to answers in SO. Not only can votes & acceptances change over time but there are multiple selectable orderings.

@chrisdornan 2012-07-27 00:40:25

For those in need of a concise explanation I will hazard one (but read the disclosure below).

Referential transparency in a programming language promotes equational reasoning -- the more referential transparency you have the easier it is to do equational reasoning. E.g. with a (pseudo) function definition,

f x = x + x,

the ease with which you can (safely) replace f(foo) with foo + foo in the scope of this definition, without having too many constraints on where you can perform this reduction, is a good indication of how much referential transparency your programming language has.

For example if foo were x++ in the C programming sense then you could not perform this reduction safely (which is to say, if you were to perform this reduction you would't end up with the same program that you started with).

In practical programming languages you won't see perfect referential transparency but functional programmers care about it more than most (cf Haskell, where it is a core objective).

(Full disclosure: I am a functional programmer so by the top answer you should take this explanation with a grain of salt.)

@Uday Reddy 2012-07-31 13:02:18

I have no problem with languages facilitating equational reasoning. But I would contest that it has anything to do with "referential transparency" as classically defined. Secondly, as a practical programmer, I think equational reasoning is overrated. The reasoning that is important in practice has to do with pre-conditions, post-conditions, invariants and data abstraction. For people that rely on such reasoning techniques, side effects don't seem to matter much. So, while I agree with you that side effects in expressions are a bad idea, they don't seem to represent a killer argument.

@chrisdornan 2012-07-31 18:44:12

@UdayReddy your initial discussion of classical RT seemed to boil down to equational reasoning, in other words, answering the question 'What changes can I make to this sentence or phrase while preserving its meaning'. E.g., can I replace "the capital of Scotland" with Edinburgh throughout this phrase and preserve its meaning. This makes sense to a logician as we often try to understand things by seeing how they change or not under transformation; if you are trying to make formal sense of something it has obvious advantages.

@chrisdornan 2012-07-31 18:57:07

@UdayReddy I think some of the confusion surrounding RT stems from the great emphasis functional programmer's have placed on referential transparency while being neglected by other fields in computer science with the result that many FP assumptions have 'leaked' into most people's understanding of RT. The debate around your original answer has highlighted this for me.

@chrisdornan 2012-07-31 19:09:58

@UdayReddy That said I don't accept your underlying thesis which smells of overreach.

@chrisdornan 2012-07-31 19:10:34

@UdayReddy Just because functional programmers have chosen a particular method of dialing up the referential transparency in their programs (eliminating side effects and developing a sophisticated and powerful algebra of programs), or have some practitioners that probably don't understand referential transparency as well as they think they do, doesn't mean that functional programming languages are failing to increase referential transparency or that functional language programmers and compiler writers aren't exploiting this increase in formal tractability to many good ends.

@chrisdornan 2012-07-31 19:50:10

@UdayReddy Further if equational reasoning is accepted as a valid means of achieving referential transparency (and I have yet to understand why it wouldn't be so) then of course the Haskell monadic method of expressing I/O is an entirely coherent method of expressing affective programs without compromising RT. All of the usual transformations available to 'pure' code can be applied in the same way to pure code; the programmers (can) and the tools (do) make heavy use of this fact.

@Conal 2012-08-01 01:01:07

Chris: Uday pointed out that Strachey eliminated the problem of referential opacity in programming language semantics, particularly for imperative languages. So functional programmers can't be "dialing up the referential transparency in their programs". As a concrete example, Haskell IO is no help with RT exactly because no RT help is needed.

@Uday Reddy 2012-08-01 15:41:33

@chrisdornan: Sorry for my first comment above. I myself had difficulty making out what I was trying to say in the first two sentences :-( But, here is an explanation. Consider a two-level or multi-level staging calculus. Each staging operator is referentially opaque. It is in fact, a quotation operator. However, you can do equational reasoning within each stage perfectly fine. So, each referentially opaque operator set up boundaries for equational reasoning. But you still have equational reasoning within those boundaries.

@Uday Reddy 2012-08-01 15:48:38

@chrisdomain: Moreover, very few people would want to be referential transparency-purists so as to banish such staging operators. Those operators are extremely useful. Programming without them by doing staging manually would be tedious, error-prone and ugly. And, doing staging manually wouldn't buy you any more equational reasoning than what you had earlier. So, prohibiting good programming devices in the purist pursuit of equational reasoning would be like cutting off your nose to spite your face.

@Uday Reddy 2012-08-01 15:56:26

@chrisdomain: On the other hand, I would heartily agree with you that using side-effecting "expressions" like x++ is a misguided practice. What you gain in terms of convenience is trivial. But, what you lose in terms of equational reasoning (or even other forms of logical reasoning) is considerable. If you ever see any of my papers, you will find me using imperative languages where expressions don't have side effects, such as Reynolds's Idealized Algol. In fact, read-only expressions represent a favorite research problem of mine. Pity that Haskell doesn't have such things!

@chrisdornan 2012-08-01 17:37:33

@Conal I think you are claiming too much. If it were really so that Strachey had eliminated the problem of referential opacity in programming language semantics then every programming language for which we could write a denotational semantics (i.e, every programming language) would be equally referentially transparent which would beg the question. I don't think Uday is saying this but accepts that some programming constructions (e.g., assignment operators embedded in expressions) reduce the referential transparency of a program. (I am sure I will be quickly corrected here if necessary.)

@chrisdornan 2012-08-01 17:49:32

@UdayReddy: it might be helpful if I try to outline your argument, which seems to be this. Functional programmers have somewhat colonized the term referential transparency and are assigning it a narrower meaning than the classical definition, leading to two unfortunate results: (i) a general confusion as to what 'referential transparency' means (as can be seen in the Wikipedia article and perhaps here) and (ii) to the extent that the colonization and confusion have succeeded, this is blocking off other potentially interesting ways of increasing the referential transparency of programs.

@chrisdornan 2012-08-01 17:54:50

@UdayReddy I get the sense that you regard this confusion as unfortunate as (as you see it) functional programmers have adopted an unfortunately restrictive discipline, putting beyond their reach many useful programming constructions, all seemingly in pursuit of an overly-narrow concept of referential transparency.

@Uday Reddy 2012-08-01 18:38:20

@chrisdornan 2012-08-01 18:41:44

@UdayReddy That said, I do think that the FPers have achieved something quite remarkable. I am not new to this, first learning Miranda and tracking the development of Haskell from the earliest reports (which used stream and continuation I/O). I am at the moment writing a dynamic scheduler in Haskell for preparing media for a media server with a view to distributing it over many nodes for scalability. This is a real-world application and my first serious foray into using the Haskell concurrency mechanisms. I am amazed at how easy it is to derive a clean design more-or-less from the types.

@Anuradha 2012-08-02 05:43:53

  1. Denotational-semantics is based on modelling languages by building domains that constitute denotable values.
  2. Functional Programmers use the term value to describe the convergence of a computation based on the rewrite rules of the language ie. its operational semantics.

In 1 there is a clarity of two languages in question:

  • the one being modelled, the object language
  • the language of modelling, the meta language

In 2, thanks to the closeness of the object and metalanguages, they can be confused.

As a language implementer, I find that I need to constantly remember this distinction.

So Prof. Reddy may I paraphrase you thus :-)

In the contexts of functional programming and semantics, the term Referential Transparency is not referentially transparent.

@Uday Reddy 2012-08-02 17:51:08

Ha ha. Thanks for the explanation. The problem is also that functional programmers act as if they have a general notion of "referential transparency" that is applicable to all programming languages. But this is dependent on their notion of "value," which may or may not make sense for other languages. To claim a general theory of "referential transparency," they need to produce a general theory "value". That is missing so far.

@Uday Reddy 2012-07-31 12:35:05

[This is a postscript to my answer from March 25, in an effort to bring the discussion closer to the concerns of functional/imperative programming.]

The functional programmers' idea of referential transparency seems to differ from the standard notion in three ways:

  • Whereas the philosophers/logicians use terms like "reference", "denotation", "designatum" and "bedeutung" (Frege's German term), functional programmers use the term "value". (This is not entirely their doing. I notice that Landin, Strachey and their descendants also used the term "value" to talk about reference/denotation. It may be just a terminological simplification that Landin and Strachey introduced, but it seems to make a big difference when used in a naive way.)

  • Functional programmers seem to believe that these "values" exist within the programming language, not outside. In doing this, they differ from both the philosophers and the programming language semanticists.

  • They seem to believe that these "values" are supposed to be obtained by evaluation.

For example, the Wikipedia article on referential transparency says, this morning:

An expression is said to be referentially transparent if it can be replaced with its value without changing the behavior of a program (in other words, yielding a program that has the same effects and output on the same input).

This is completely at variance with what the philosophers/logicians say. They say that a context is referential or referentially transparent if an expression in that context can be replaced by another expression that refers to the same thing (a coreferential expression). Who are these philosophers/logicians? They include Frege, Russell, Whitehead, Carnap, Quine, Church and countless others. Each one of them is a towering figure. The combined intellectual power of these logicians is earth-shattering to say the least. All of them are unanimous in the position that referents/denotations exist outside the formal language and expressions within the language can only talk about them. So, all that one can do within the language is to replace one expression by another expression that refers to the same entity. The referents/denotations themselves do not exist within the language. Why do the functional programmers deviate from this well-established tradition?

One might presume that the programming language semanticists might have misled them. But, they didn't.

Landin:

(a) each expression has a nesting subexpression structure, (b) each subexpression denotes something (usually a number, truth value or numerical function), (c) the thing an expression denotes, i.e., its "value", depends only on the values of its sub- expressions, not on other properties of them. [Added emphasis]

Stoy:

The only thing that matters about an expression is its value, and any subexpression can be replaced by any other equal in value [Added emphasis]. Moreover, the value of an expression is, within certain limits, the same whenever it occurs".

Bird and Wadler:

the value of an expression depends only on the the values of its constituent expressions (if any) and these subexpressions may be replaced freely by others possessing the same value [Added emphasis].

So, in retrospect, the efforts of Landin and Strachey to simplify the terminology by replacing "reference"/"denotation" with "value" might have been injudicious. As soon as one hears of a "value", there is a temptation to think of an evaluation process that leads to it. It is equally tempting to think of whatever the evaluation produces as the "value", even though it might be quite clear that that is not the denotation. That is what I gather to have happened to the concept of "referential transparency" in the eyes of functional programmers. But the "value" that was being spoken of by the early semanticists is not the result of an evaluation or the output of a function or any such thing. It is the denotation of the term.

Once we understand the so-called "value" of an expression ("reference" or "denotation" in classical philosophers' discourse) as a complex mathematical/conceptual object, all kinds of possibilities open up.

  • Strachey interpreted variables in imperative programming languages as L-values, as mentioned in my March 25 answer, which is a sophisticated conceptual object that does not have a direct representation within the syntax of a programming language.
  • He also interpreted commands in such languages as state-to-state functions, another instance of a complex mathematical object that is not a "value" within the syntax.
  • Even a side-effecting function call in C has a well-defined "value" as a state transformer that maps states to pairs of states and values (the so-called "monad" in functional programmers' terminology).

The reluctance of functional programmers to call such languages "referentially transparent" merely implies that they are reluctant to admit such complex mathematical/conceptual objects as "values". On the other hand, they seem perfectly willing to call a state transformer a "value" when it is put in their own favourite syntax and dressed up with a buzz word like "monad". I have to say that they are being entirely inconsistent, even if we grant it to them that their idea of "referential transparency" has some coherence.

A bit of history might throw some light on how these confusions came into being. The period between 1962 to 1967 was a very intensive one for Christopher Strachey. Between 1962-65, he took a part-time job as a research assistant with Maurice Wilkes to design and implement the programming language that came to be known as CPL. This was an imperative programming language but was meant to have powerful functional programming language capabilities as well. Landin, who was an employee of Strachey in his consultancy company, had a huge influence on Strachey's view of programming languages. In the landmark 1965 paper "Next 700 programming languages", Landin unabashedly promotes functional programming languages (calling them denotative languages) and describes imperative programming languages as their "antithesis". In the ensuing discussion, we find Strachey raising doubts on Landin's strong position.

... DLs form a subset of all languages. They are an interesting subset, but one which is inconvenient to use unless you are used to it. We need them because at the moment we don't know how to construct proofs with languages which include imperatives and jumps. [Added emphasis]

In 1965, Strachey took the position of a Reader at Oxford and seems to have worked essentially full-time on developing a theory of imperatives and jumps. By 1967, he was ready with a theory, which he taught in his course on "Fundamental concepts in programming languages" in a Copenhagen summer school. The lecture notes were supposed to have been published but "unfortunately, because of dilatory editing, the proceedings never materialized; like much of Strachey’s work at Oxford, however, the paper had an influential private circulation." (Martin Campbell-Kelly)

The difficulty of obtaining Strachey's writings could have led to the confusions being propagated, with people relying on secondary sources and hearsay. But, now that "Fundamental concepts" is readily available on the web, there is no need to resort to guess work. We should read it and make up our own mind as to what Strachey meant. In particular:

  • In section 3.2, he deals with "expressions" where he talks about "R-value referential transparency".
  • His section 3.3 deals with "commands" where he talks about "L-value referential transparency".
  • In section 3.4.5, he talks about "functions and routines" and declares that "any departure of R-value referential transparency in a R-value context should either be eliminated by decomposing the expression into several commands and simpler expressions, or, if this turns out to be difficult, the subject of a comment."

Any talk of "referential transparency" without understanding the distinction between L-values, R-values and other complex objects that populate the imperative programmer's conceptual universe is fundamentally mistaken.

@applicative 2012-07-31 16:37:01

There doesn't seem to be anything in these accusations. If the referent of "3" in Haskell were thought to be 'in the language', what would the referent be, except "3", but 3 == "3" doesn't even typecheck, much less express the ambient alleged confusion. Nothing is more unrelenting about enforcing the use/mention distinction than the type system. You did manage to find a defective sentence in the Wikipedia.

@applicative 2012-07-31 16:47:05

Why don't L-values 'have a direct representation in the syntax of the language'? Curious kind of thing or value or denominatum -- you can't refer to it directly, but only with curly brackets? You can do it in a publication, but not in a programming language... Is this a good thing? Are we missing something if we use a language without this indirect reference to values that can't be referred to directly?

@Conal 2012-07-31 17:02:10

Thanks again, Uday! I think you nailed the confusion between values within and outside of the language. However, as applicative demonstrates, those terms are also misleading, since the values "within the language" aren't really within in that they're not syntax, though they sometimes have syntactic counterparts (like "3" for 3). I think we need a better term for these "within" values, which you refer to as "obtained by evaluation", to distinguish them from denotations.

@applicative 2012-07-31 17:24:48

Note that with data Nat = Z | S Nat the class of 'reduced expressions' is isomorphic to N. Thus a 'confusion' of the reduced expressions of Nat with the numbers in N would be unusually harmless, even if, contra Uday R. it in fact only happens en passant in Wikipedia articles.

@Conal 2012-07-31 17:28:51

I think it's worth emphasizing that confusing these two notions of "value" (evaluations vs denotations) misleads functional programmers in their criticism of imperative languages, where the gap between notions is large.

@Conal 2012-07-31 17:33:15

i.e., the evaluation notion leads to the conclusion that imperative languages are not RT, while the denotation notion does not.

@sclv 2012-07-31 18:28:25

Conal: the "within" values are "closed terms in normal form"? i.e. the "naive" functional approach is nearly completely syntactic, while the "naive" imperative approach is nearly completely operational...

@applicative 2012-07-31 21:42:42

The suggestion that 'functional programmers' depart from the mighty tradition of Frege, Russell, Church, Quine etc etc. by mistaking e.g. the number of planets, viz, 8, for an expression in their preferred programming language is of course a mere troll. What surprises the reader is that anyone could think that anyone could think that anyone could think it...

@Conal 2012-07-31 22:10:39

applicative: No, the "within" values are not "closed terms in normal form". They're semantic (values) not syntactic (terms), as I mentioned above in recommending "evaluations" vs "denotations" instead of "values within the language" vs "... without ...". No need to bring in the notions of reduction or normal forms. When denotations are more complex than evaluations, as in imperative programming. Not "8" vs 8, but rather 8 vs an imperative denotation (including store & nondeterminism).

@Uday Reddy 2012-07-31 22:13:26

@applicative: Why don't L-values have a direct representation in the syntax of the language? Because they don't need to. The programmer says "I want a new L-value", and the system gives her one. She calls it 'x' and moves on. It would be a terrible idea to have constants representing L-values because they would tie you down to particular memory layouts and force you to do your own memory management. A high-level programming language is meant to liberate you from such details.

@Uday Reddy 2012-07-31 22:25:16

@sclv It does not particularly matter what the "within" values are. The point is that functional programmers seem to want all "values" to be within the language. For example, when they say "x++ evaluates to 2, but you can't replace x++ by 2" or some such equivalent complaint, they are limiting their imagination of what 'x++' can be. The idea that 'x++' could be an abstract state transformer doesn't seem to occur to them. If it did, they would see right away that 'x++' as a state transformer is quite different from 2. No surprise that you can't replace it.

@Uday Reddy 2012-07-31 22:30:19

@applicative: You are quite right that 'concept' wasn't a good term in my first answer. I felt uneasy about using it because Quine is quite particular that 'concepts' are incoherent. But my English fails me in coming up with a better term. 'Entity', perhaps?

@Tom Crockett 2012-07-31 22:48:46

Once we have perceived that statements in an imperative programming language denote state-transforming partial functions, it seems foolish to regard "the capital of Scotland" as denoting Edinburgh, rather than a partial function which transforms dates into cities.

@Tom Crockett 2012-07-31 22:50:39

It seems to me that once you've really fully nailed down the denotational semantics of a language, it can't help but be referentially transparent. So this seems tantamount to saying that the term is not useful with regard to programming languages.

@applicative 2012-07-31 22:51:38

@conal I am concerned only with the claim that 'functional programmers' depart from the ancient wisdom taught us by the Frege, ... , Quine. This I consider this and the consequent remarks an injustice. Since UR's only evidence for this extremely grave charge is a typical use/mention confusion of the sort human beings make every few minutes that he finds in a Wikipedia article.

@applicative 2012-07-31 23:03:59

@petolom yes this was the solution arrived at by Frege in the 1880's -- e.g. in Grundlagen section 47 ('the population of Berlin ... is a function of time' -- and not a 'variable number') and accepted by almost everyone since. The topic of 'referential transparency' raised by Quine has nothing to do with that topic which he like almost everyone considered totally closed, and it is not one of Quine's examples -- these are quotation and belief contexts.

@Uday Reddy 2012-07-31 23:09:06

@pelotom: That is well put. "Once you've fully nailed down the denotational semantics of a language, it can't help but be referentially transparent." Strachey was quite clear that a particular way of defining the semantics, way back in the 60's, was not referentially transparent. Once he found a referentially transparent semantics, i.e., a proper denotational semantics, the problem was solved!

@Daniel Pratt 2012-07-31 23:20:07

So it seems like folks are in the habit of using a term to mean something materially different than what other folks meant when they used that term in the past. To which I say: Welcome to the English language.

@Uday Reddy 2012-07-31 23:27:15

@applicative: I understand that you find an injustice, as you say. But I don't understand why. This is not a "use/mention confusion". If anybody talks about replacing a term by a "value", it immediately implies that the "value" itself is a term. But, the "values" that Frege etc. talk about (using their own terminology) are not terms. So, there is a fundamental type mismatch. It cannot be squared. If you can square it, then go ahead and add your own answer to the original question. That is how this forum works!

@applicative 2012-08-01 00:27:39

A use/mention confusion in the jargon of Quine is the confusion of a term with what it denotes, so yes, you are accusing 'functional programmers' generally of systematic use/mention confusion -- and affirming that they thus depart from the mighty tradition that distinguished these things. This is of course properly the tradition of the human race, not a peculiarity of [Frege,...,Quine]. But your evidence for the 'functional programmers' stunning and cretinous &c. departure from the obvious is one line from a Wikipedia article.

@Uday Reddy 2012-08-01 00:36:56

@applicative: That is not what I normally mean by use/mention confusion. But never mind. So, your belief is that functional programmers know what terms mean as denotations, but prefer to talk about those denotations as if they were terms? If so, what do they think is the denotation of "x++" in C? What is supposed to be its "value"? And, why do they say that they can't replace "x++" by its "value"?

@applicative 2012-08-01 00:39:25

It is not 'semantics' that are referentially opaque or transparent, but contexts in which expressions appear, eg quotation contexts, belief contexts, etc. Quine was well aware that a language could be reformed so that all contexts are referential, and this was a desideratum. His first example is the elimination of quotation in favor or references to ... lists of characters (Word and Object, 143). He speaks of the transparency thus acquired in this trivial case as an advantage of 'spelling' over 'quotation'. The provision of a semantics does nothing to affect transparency or opacity.

@Conal 2012-08-01 00:40:04

applicative: You're upset about Uday giving only one example of confusions about RT? There are several examples in upvoted answers and comments on this very StackOverflow page, particularly when applied to imperative languages. For instance, "In contrast there is the concept of referential opaqueness. This means the opposite. Calling the function may not always produce the same output." Note that the "output" is not the denotation, hence the erroneous conclusion that RT fails. I've seen this confusion many times in #haskell IRC.

@Uday Reddy 2012-08-01 01:23:01

@applicative: On Word and Object, p. 142, you find a notion of "purely referential" and, by implication, an admission that a context might be partly referential. In a well-intentioned formal language, such partial referentiality can be squeezed out by a good semantics so that all contexts then appear referential. That is what I take Strachey to have done. You will perhaps benefit from actually reading his paper, if you are really interested in this topic.

@applicative 2012-08-01 01:52:50

It is clear that for Quine quotation and belief contexts are simply not transparent and no amount of semantical theorizing or Stracheyization (mutatis mutandis) can ever change this. In the case of quotation it is easy to change the language though, and he shows how to do it, following Tarski, using a symbol for 'concatenation' (sc. cons) and names of characters. That this different form of representation is superior he takes to be obvious. Of course you can use the words "opaque context" differently if you like, but you were proposing not to.

@applicative 2012-08-01 05:40:22

I am baffled by your emphasis on x++. Various devices can be used to represent this 'operation' even in Haskell. Here (hpaste.org/72420) is a suitably dim example using STRef. In it (++) is made itself to denote a single definite 'entity', which ghci informs us is a single one of infinitely many values of the type STRef s Int -> ST s (). 'functional programmers' isolate things of this type all the time, I don't think 'they' think they are impossible, incoherent; if anyone says they are, they should study a little Haskell or a few more standard libraries.

@Marcin 2012-08-01 12:54:21

@UdayReddy I think your knowledge of programming languages is not as good as you think it is. Variables have a first-class existence as symbols in common lisp (making for explicit l-values), and I understand that it is possible to pass l-values as first-class objects in perl also.

@Uday Reddy 2012-08-01 12:55:07

@DanielPratt: I think I am open to terms changing meaning. But I wish somebody sets down clearly what has changed, why it has changed, what the relationship is to the old meaning, and what are the consequences of the new meaning. It would also be useful to know how and when the change has been made.

@Uday Reddy 2012-08-01 12:58:06

@Marcin. I am sorry, but I don't understand what point you are making. Notice that I never said anything about "first-class values" in my answer or in the discussion.

@Daniel Pratt 2012-08-01 13:50:23

@UdayReddy I will assume for the sake of argument (and also for the sake of not wanting to make a fool of myself) that you're correct about the classical definition of the term 'referential transparency'. Firstly, you yourself say that this definition is not particularly relevant to programming. (TBC)

@Daniel Pratt 2012-08-01 13:51:01

@UdayReddy Secondly, when functional programmers use the term 'referential transparency', they may do so in ignorance of the classical definition of that term, but the point they are making is a valid one, is it not? That point being that in some languages (e.g. Haskell) expressions that may exhibit 'side effects' (state changes, etc.) can be readily distinguished (by the facilities of the language itself) from those that may not. In every mainstream imperative language I know about, this is not the case.

@Marcin 2012-08-01 14:20:00

@UdayReddy You said "It would be a terrible idea to have constants representing L-values because they would tie you down to particular memory layouts and force you to do your own memory management." This is incorrect.

@Uday Reddy 2012-08-01 14:39:10

@DanielPratt: Yes, I did say that the classical definition is not particularly relevant to programming languages today (since their semantic issues have been sorted out in the 60's). But the new definition hasn't been stated anywhere, except on Wikipedia and StackExchange pages and they don't cite any sources either. At a minimum, a definition has to appear in a refereed publication so that we know that the test of rigour has been met and then we can take it seriously.

@Uday Reddy 2012-08-01 14:45:32

@DanielPratt: If side-effect-freedom is what functional programmers want to mean, then why do they call it "referential transparency"? They can just call it "side-effect-freedom", which is a perfectly clear idea. Nobody on will need to ask on stackexchange what "side-effect-freedom" means. Where is the need to purloin grandiose classical terms that nobody seems to understand?

@Uday Reddy 2012-08-01 14:47:13

@Marcin: Having L-values as first-class values does not mean that there are constants of that kind, does it? If there are constants of that kind, I would appreciate pointers to the literature.

@Daniel Pratt 2012-08-01 14:50:20

@UdayReddy First of all, I don't even consider myself to be a 'functional programmer' so any definition I give you for any FP-related term should be taken with several grains of salt. Second, I really did not mean to say what is the definition of RT per se, just the most obvious consequence (to me, anyway) of a concept I think others have defined much better than I could.

@Marcin 2012-08-01 15:31:10

@UdayReddy You are positing a distinction without a difference. What is the difference between a value and a context?

@sclv 2012-08-01 16:03:27

This conversation has gone on way too long. There's some conversation on the haskell reddit if people want to continue it there, but SO is for questions and answers, not protracted discussions: reddit.com/r/haskell/comments/xgq27/…

@Uday Reddy 2012-08-01 16:05:53

@Marcin: You mean what is the difference between a value and a constant? A constant is a pre-defined symbol in the language, like 0 for integers. A "value" in the sense of Strachey is a mathematical entity. Values of type 'integer' are all the integers. Values of type 'integer -> integer' are all functions from integers to integers (module some technicalities). L-values of type, say 'var[integer]', are all the abstract locations that can hold integers.

@Marcin 2012-08-01 16:59:12

@UdayReddy So, lisp, for example, has constants (symbols) which represent l-values, contra your previous statement.

@Uday Reddy 2012-08-01 17:30:10

@Marcin Indeed the use of symbols as l-values depends on Lisp's dynamic binding mechanism, which irretrievably breaks referential transparency even in the classical sense. In fact, one might think of it as a symbolic version messing with "memory layouts," as I called them earlier. I am still not sure what your point is.

@Marcin 2012-08-01 20:05:13

@UdayReddy My point is that you have incorrectly stated that programming languages do not expose l-values, and incorrectly stated that such a feature requires manual memory management. You cannot simply declare that whatever you think is going on is equivalent to manual memory management. Incidentally, do you think that all lisps are dynamically scoped? Common lisp is lexically scoped (at least except in respect of special variables).

@Uday Reddy 2012-08-01 20:38:43

@Marcin If Common Lisp, which I haven't used, has a way of combining static scoping with symbolic l-values, then those symbols would not be constants would they? Every scope can have a symbol called "x" and each of them can have an associated l-value. So, then, "x" wouldn't stand for a fixed l-value.

@Uday Reddy 2012-08-01 20:45:09

@Marcin But I think you are a bit too focused on your particular issue, and perhaps missed the bigger picture of the argument. My initial point was that you can have values that are not represented as constants within the programming language, and I gave l-values as an example of those. In order to illustrate my point, I only need one language in which l-values don't have constants. I don't need to prove that every language doesn't have l-values as constants. Machine languages obviously have l-value constants. We all know that!

@Marcin 2012-08-02 12:17:43

@UdayReddy Given that you choose to redefine everything to mean just what you want it to mean, I see no point in discussing things with you further. In general, you have brought very little light to these issues, and much heat, by insisting on definitions developed for a different purpose.

@Zoran Pavlovic 2013-02-25 15:21:13

I have no idea why everyone keeps upvoting this guy's posts. I left this page with 15mins of wasted time reading some guy regurgitating definitions and writing essays, with his only backing being an appeal to authority (his so called "towering giants"). For all we know, he may be right. But for the most part, his comments are not constructive to this dicussion and solely revolve around definitions that were coined for a different field. Instead of using the definitions applicable to the field being discussed. Ironic, seeing as he went on and on about "context" in his original post.

@Ben Kovitz 2014-04-02 16:38:22

Here's a source for the common usage. Bertrand Meyer, Introduction to the Theory of Programming Languages (1990) p. 7: "Referential transparency…is the property, enjoyed by mathematical notation, of substitutivity of equals for equals: it holds if, whenever a=b, any property obtained from a true property by substituting b for a throughout is still true. … Programming languages…violate referential transparency if they permit side effects."

@Uday Reddy 2014-04-02 17:08:36

@BenKovitz. Thanks. I didn't know that Bertrand Meyer joined the party. Unfortunately, the discussion on p.7 doesn't explicate the "common usage." Rather it falls into the common fallacy. The definition of referential transparency he uses is the standard one. But his application of it is wrong. He says "f(z) = 1 in the sense that the call f(z) will return value 1," where "in the sense that" are weasel words. No sensible programmer on earth would accept that the expressions f(z) and 1 are equal. Since they are not equal, his definition of referential transparency doesn't apply.

@Didier A. 2015-10-13 18:20:25

I'm still a bit confused. Do imperative language assume "values" to basically be truth of the universe. Therefore the language simply seeks to reference that truth. And if you can have multiple way to reference that truth, each way is transparently referential? Or does it say that, given all inputs to the methods, even those that are obtained through sub-expressions, the output will be the same is referentially transparent? The latter would seem then to simply be a matter of arguing what is a real input.

@Uday Reddy 2015-10-22 16:05:36

@didibus Yes, values, or rather denotations, are the "truth of the universe" in your terminology. A language is referentially transparent if two program fragments that represent the same denotation (and hence "equivalent") can be exchanged for each other without affecting anything else. It is not the program fragments that are referentially transparent. Referential transparency is a property of the whole language which allows us to replace equivalent fragments by each other.

@rdm 2012-07-26 22:33:36

Note that this concept of "meaning" is something that happens in the mind of the observer. Thus, the same "reference" can mean different things to different people. So, for example, we have an Edinburgh disambiguation page in Wikipedia.

A related issue which can show up in the context of programming might be polymorphism.

And perhaps we should have a name for the special case of polymorphism (or perhaps even casting) where for our purposes the differing polymorphic cases are semantically equivalent (as opposed to just being similar. For example, the number 1 -- which might be represented using an integer type, or a complex type or any of a variety of other types -- can be treated polymorphically).

@Andrew Birkett 2010-02-25 14:03:03

If you're interested in the etymology (ie. why does this concept have this particular name), have a look at my blog post on the topic. The terminology comes from the philosopher/logician Quine.

@Draemon 2008-10-17 02:22:07

A referentially transparent function is one which only depends on its input.

@Kris 2014-05-03 23:59:00

Which is why it is hard in OO programming because objects have state.

@mdenton8 2014-08-19 01:37:21

@Kris unless your object is immutable, of course...

@mwolfe02 2016-06-10 16:55:04

So is it correct to say "referentially transparent" is identical to "deterministic" when describing functions? If not, what is the difference between the two terms?

@Evgeny A. 2019-01-02 17:07:03

This also sounds like a definition of a "pure" function.

@CMS 2008-10-17 01:39:24

An expression is referentially transparent if it can be replaced with its value, without changing the algorithm, yielding an algorithm that has the same effects and output on the same input.

@Barry Kelly 2008-10-17 01:36:39

A referentially transparent function is one which acts like a mathematical function; given the same inputs, it will always produce the same outputs. It implies that the state passed in is not modified, and that the function has no state of its own.

Related Questions

Sponsored Content

39 Answered Questions

6 Answered Questions

45 Answered Questions

[SOLVED] What is a monad?

22 Answered Questions

[SOLVED] What is a lambda (function)?

27 Answered Questions

[SOLVED] What is tail recursion?

12 Answered Questions

[SOLVED] What is Turing Complete?

15 Answered Questions

[SOLVED] Getting started with Haskell

13 Answered Questions

18 Answered Questions

1 Answered Questions

[SOLVED] Referential Transparency

Sponsored Content