World Library  
Flag as Inappropriate
Email this Article

Referential transparency

Article Id: WHEBN0000026526
Reproduction Date:

Title: Referential transparency  
Author: World Heritage Encyclopedia
Language: English
Subject: Programming language theory, Liskov substitution principle
Collection: Programming Language Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Referential transparency

Referential transparency and referential opacity are properties of parts of computer programs. 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). The opposite term is referential opacity.

While in mathematics all function applications are referentially transparent, in programming this is not always the case. 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.

Referential transparency is one of the principles of functional programming; only referentially transparent functions can be memoized (transformed into equivalent functions which cache results). Some programming languages provide means to guarantee referential transparency. Some functional programming languages enforce referential transparency for all functions.

As referential transparency requires the same results for a given set of inputs at any point in time, a referentially transparent expression is therefore deterministic.

Contents

  • History 1
  • Examples and counterexamples 2
  • Contrast to imperative programming 3
  • Another example 4
  • See also 5
  • References 6
  • External links 7

History

The concept (although not the term) seems to have originated in Alfred North Whitehead and Bertrand Russel's Principia Mathematica (1910–13). It was adopted in analytical philosophy by Willard Van Orman Quine in Word and Object (1960):

A mode of containment φ is 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 usage, in the discussion of variables in programming languages, in Christopher Strachey's seminal set of lecture notes Fundamental Concepts in Programming Languages (1967). The lecture notes referenced Quine's Word and Object in the bibliography.

Examples and counterexamples

If all functions involved in the expression are pure functions, then the expression is referentially transparent. Also, some impure functions can be included in the expression if their values are discarded and their side effects are insignificant.

Consider a function that returns the input from some source. In pseudocode, a call to this function might be GetInput(Source) where Source might identify a particular disk file, the keyboard, etc. Even with identical values of Source, the successive return values will be different. Therefore, function GetInput() is neither deterministic nor referentially transparent.

A more subtle example is that of a function that has a free variable, i.e., depends on some input that is not explicitly passed as a parameter. This is then resolved according to name binding rules to a non-local variable, such as a global variable, a variable in the current execution environment (for dynamic binding), or a variable in a closure (for static binding). Since this variable can be altered without changing the values passed as parameter, the results of subsequent calls to the function may differ even if the parameters are identical. However, in pure functional programming, destructive assignment is not allowed, and thus if the free variable is statically bound to a value, the function is still referentially transparent, as neither the non-local variable nor its value can change, due to static binding and immutability, respectively.

Arithmetic operations are referentially transparent: 5*5 can be replaced by 25, for instance. In fact, all functions in the mathematical sense are referentially transparent: sin(x) is transparent, since it will always give the same result for each particular x.

Assignments are not transparent. For instance, the C expression x = x + 1 changes the value assigned to the variable x. Assuming x initially has value 10, two consecutive evaluations of the expression yield, respectively, 11 and 12. Clearly, replacing x = x + 1 with either 11 or 12 gives a program with different meaning, and so the expression is not referentially transparent. However, calling a function such as int plusone(int x) {return x+1;} is transparent, as it will not implicitly change the input x and thus has no such side effects.

today() is not transparent, as if you evaluate it and replace it by its value (say, "Jan 1, 2001"), you don't get the same result as you will if you run it tomorrow. This is because it depends on a state (the time).

In languages with no side-effects, like Haskell, we can substitute equals for equals because f(x) = f(x) for every value of x. This does not hold for languages with side-effects.

Contrast to imperative programming

If the substitution of an expression with its value is valid only at a certain point in the execution of the program, then the expression is not referentially transparent. The definition and ordering of these sequence points are the theoretical foundation of imperative programming, and part of the semantics of an imperative programming language.

However, because a referentially transparent expression can be evaluated at any time, it is not necessary to define sequence points nor any guarantee of the order of evaluation at all. Programming done without these considerations is called purely functional programming.

One advantage of writing code in a referentially transparent style is that given an intelligent compiler, static code analysis is easier and better code-improving transformations are possible automatically. For example, when programming in C, there will be a performance penalty for including a call to an expensive function inside a loop, even if the function call could be moved outside of the loop without changing the results of the program. The programmer would be forced to perform manual code motion of the call, possibly at the expense of source code readability. However, if the compiler is able to determine that the function call is referentially transparent, it can perform this transformation automatically.

The primary disadvantage of languages that enforce referential transparency is that they make the expression of operations that naturally fit a sequence-of-steps imperative programming style more awkward and less concise. Such languages often incorporate mechanisms to make these tasks easier while retaining the purely functional quality of the language, such as definite clause grammars and monads.

With referential transparency, no distinction is made nor difference recognized between a reference to a thing and the corresponding thing itself. Without referential transparency, such difference can be easily made and utilized in programs.

Another example

As an example, let's use two functions, one which is referentially opaque, and the other which is referentially transparent:

 globalValue = 0;

 integer function rq(integer x)
 begin
   globalValue = globalValue + 1;
   return x + globalValue;
 end

 integer function rt(integer x)
 begin
   return x + 1;
 end

The function rt is referentially transparent, which means that rt(x) = rt(y) if x = y. For instance, rt(6) = 6 + 1 = 7, rt(4) = 4 + 1 = 5, and so on. However, we can't say any such thing for rq because it uses a global variable that it modifies.

The referential opacity of rq makes reasoning about programs more difficult. For example, say we wish to reason about the following statement:

integer p = rq(x) + rq(y) * (rq(x) - rq(x));

One may be tempted to simplify this statement to:

integer p = rq(x) + rq(y) * (0);
integer p = rq(x) + 0;
integer p = rq(x);

However, this will not work for rq() because each occurrence of rq(x) evaluates to a different value. Remember that the return value of rq is based on a global value that isn't passed in and which gets modified on each call to rq. This means that mathematical identities such as x - x = 0 no longer hold.

Such mathematical identities will hold for referentially transparent functions such as rt.

However, a more sophisticated analysis can be used to simplify the statement to:

integer a = globalValue; integer p = x + a + 1 + (y + a + 2) * (x + a + 3 - (x + a + 4)); globalValue = globalValue + 4;
integer a = globalValue; integer p = x + a + 1 + (y + a + 2) * (x + a + 3 - x - a - 4)); globalValue = globalValue + 4;
integer a = globalValue; integer p = x + a + 1 + (y + a + 2) * -1; globalValue = globalValue + 4;
integer a = globalValue; integer p = x + a + 1 - y - a - 2; globalValue = globalValue + 4;
integer p = x - y - 1; globalValue = globalValue + 4;

This takes more steps and requires a degree of insight into the code infeasible for compiler optimization.

Therefore, referential transparency allows us to reason about our code which will lead to more robust programs, the possibility of finding bugs that we couldn't hope to find by testing, and the possibility of seeing opportunities for optimization.

See also

References

External links

  • http://userpage.fu-berlin.de/~ram/pub/pub_jf47ht81Ht/referential_transparency
  • http://stackoverflow.com/a/9859966/655289 by Prof. Uday Reddy (University of Birmingham)
  • http://okmij.org/ftp/Computation/PrincipiaMathematica.txt
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.