Referential Transparency

This is a property of programming constructs, which is enforced by some (but not all) FunctionalProgrammingLanguages.

In a referentially transparent program, a function/method invocation can be freely replaced with its return value without changing the program's semantics. In a referentially transparent language, the following two constructs have identical semantics (Haskell/ML syntax):

  let y = f x in y + y
and
  f x + f x 

Obviously, this is only true when the only thing the function f does is simply compute a value. That is, f is independent of temporal context and has no SideEffects. If f does depend on something that changes temporally, then f(5) now might not equal f(5) later. If the computation of f does have effects, then computing it twice would have very different semantics than computing it once. FunctionalProgramming advocates programming without effects because this makes the program referentially transparent.

The main advantage of referential transparency is that it makes it much easier to reason about programs, and to apply program transformations... including optimizations and partial evaluations at compile-time (since if a computation has no side-effects, then it doesn't matter whether you calculate it now or later).


Q: If a whole program has the property of ReferentialTransparency, then -- if I didn't misunderstand the above definition -- the whole set of expressions that makes up this program can be evaluated to / replaced by a single value. Does this mean that all such a program can ever do is compute a value, i.e. you can't write an interactive application in a language that enforces ReferentialTransparency?

A1: A standard REP loop is not (as a whole) referentially transparent even if every individual evaluation it performs is referentially transparent. This is because the input to the REP loop is not wholly determined by the output of the REP loop and past input. Other inputs are involved that cannot be referenced... such as the state of mind of the user on the opposite side of the REP loop. This applies to usefully interactive systems in general... and, in this sense, it is not possible to 'write' an interactive system in a language that enforces ReferentialTransparency.

A2: That said, a program-description is a value. Fundamentally, it doesn't matter whether you view it as a finite sequence of bits in RAM or on the HDD or as a sequence of higher-level sub-program descriptors... a program-description is still a value. Thus, while a language that enforces referential transparency can have any single definition reduced to a value, that single value can constitute any application that can be described... including an interactive one.

A3: Further, all programming systems are more than just a language. In fact, any programming system must be constituted by three parts: a language, a writer of that language (who expresses intent), and a reader of that language (who acts upon the expressed intent). At the lowest levels, the writers are compilers of assembly and the readers are CPUs, but above that you can have an arbitrary number of language layers each with a writer and reader.

For many languages that enforce ReferentialTransparency, the default reader produces an REP-loop (useful for debugging). In this case, the 'intent' behind, for example, 'define fib(N) = (...)' is interpreted to be: 'from now on, calculate and print the value of fib(x) whenever I see it on the read-loop'. However, transforming a program-description into a big REP loop is just one possible interpretation of intent.

Another reader might take the approach: (1) look for 'define main = (...)' which must be a function that accepts string input and produces (string-output,fn_continue) where fn_continue has the same type as main. (2) Utilize this function as an application by accepting input from a second user, processing it, printing the output string, and holding onto fn_continue as the new 'main'. This is, essentially, what is utilized in Haskell.

... And yet another reader might: (1) look for 'define prog = '(...)'' where prog must be an array of integers, (2) load prog as a sequence of machine characters into executable memory, (3) set CPU's process-counter to the first byte. In fact, this reader isn't at all far removed from how a modern OS loads 'executable' files, though it's rather primitive (no relocatable code, sections, etc.).

It's worth noting that changing the reader does not change the language. The written expression of the language and (importantly) all type-safety constraints and enforced characteristics of that language are the same in every case. Thus, if the language enforces ReferentialTransparency, it is still being enforced.

It's also worth noting that a program-description in C or C++ also constitute values and are also subject to all this sort of interpretation (though for C/C++ the only real variation in readers is in choosing which language or object-file or executable-file format into which to compile).

OTOH, any time you expect a particular interpretation by a reader, you're no longer performing FunctionalProgramming. You are, instead, performing functional meta-programming for an imperative language. Your 'command' in an imperative language is the intent you express to the reader (regardless of how it is expressed)... but this command is independent of ReferentialTransparency within the language.

ReferentialTransparency requires only that definitions be wholly independent of communications context (including temporal context)... f(5) now = f(5) later, no matter what... and that their computation produce no intentional effects. And this will be true if f itself does not depend on receiving a communication and does not depend on anything else that depends on communication actions.


A: No, because this "single value" can represent the program's interactive behavior (for example, by giving a sequence of output actions as a function of the sequence of input events).

A2: The "set of operations that makes up a program" defines a value. But, this value can be a function, that takes an input and returns an output. Let's consider the following program (in Haskell)

  fac 0 = 1
  fac n = n * fac (n-1)

It defines a value (fac), which is a function. When fac is given a specific value (3) it denotes another value (6). The "interactivity" you need can be achieved by supplying the needed values to your program. -- Alex

A3: The question does not take into account that fact that every program or function has input. Having ReferentialTransparency means that only the input determines the output. No state changes of global variables can influence the result of a function. If f(5) = 17 then f(5) will always equal 17 regardless of the values of other "variables".


What is a Purely Functional Language? Amr Sabry (1998) http://citeseer.ist.psu.edu/sabry98what.html
I don't get the interactive stuff. Interactive means that the process will ask data to the user, and that data cannot be determined in advance. Therefore, the askTheQuestionAndGetTheResultBack function might return two different results even though it is supplied twice with the same parameters. An interactive process is, by design, something that uses SideEffect programming. -- PhilippeDetournay

By 'SideEffect' programming, I assume you mean intentional 'side'-effects... which, more accurately, is IntentionalEffect? programming. When an effect exists by design, I think you'd agree that it's hardly a "side" effect. Every communication, and therefore every computation, has SideEffects... time costs, energy consumption, etc. that you'd make go away if you could. Best you can do is mitigate and control them to some degree. Anyhow, I agree with you. Interactive programming (which occurs between two agents) is largely incompatible with referential transparency as it is presented above. I'm adding my own answer, above, to counterbalance those answers initially offered by FunctionalWeenies.


CategoryFunctionalProgramming
See also: FunctionalProgrammingLanguages for more detailed discussion.

EditText of this page (last edited July 9, 2010) or FindPage with title or text search