Difference between revisions of "Referential transparency"

From HaskellWiki
Jump to: navigation, search
m (Informal definition replaced)
m (Reference to Quine's book added)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 
[[Category:Glossary]]
 
[[Category:Glossary]]
Referential transparency is an oft-touted property of ([[Pure|pure]]) functional languages, which makes it easier to reason about the behavior of programs. While there is no single formal definition[[#notes|[1]]], a concise one is given by F. Warren Burton[[#notes|[2]]]:
+
Referential transparency is an oft-touted property of ([[Pure|pure]]) functional languages, which makes it easier to reason about the behavior of programs. As there is no single formal definition[[#notes|[1]]], the one Christopher Strachey[[#notes|[2]]] used to introduce the term into the study of programming languages will have to suffice:
  
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
Referential transparency, the property that an expression always has the same value in the same environment, is central to the mathematical foundation for functional programs.
+
One of the most useful properties of expressions is that called by Quine[[#notes|[3]]] 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.
 
</div>
 
</div>
  
 
Side effects like (uncontrolled) imperative update break this desirable property. C and ML are languages with constructs that are not referentially transparent.
 
Side effects like (uncontrolled) imperative update break this desirable property. C and ML are languages with constructs that are not referentially transparent.
  
As an example, consider the following program[[#notes|[3][4]]] in Standard ML:
+
As an example, consider the following program[[#notes|[4][5]]] in Standard ML:
 
<pre>
 
<pre>
 
  puts "h"; puts "a"; puts "h"; puts "a"
 
  puts "h"; puts "a"; puts "h"; puts "a"
Line 39: Line 39:
 
[1] Wolfram Kahl provides a [https://www.cas.mcmaster.ca/~kahl/reftrans.html USENET post by Tom DeBoni] containing a summary of various definitions for referential transparency.
 
[1] Wolfram Kahl provides a [https://www.cas.mcmaster.ca/~kahl/reftrans.html USENET post by Tom DeBoni] containing a summary of various definitions for referential transparency.
  
[2] From [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages], ''The Computer Journal'', 31(3):243--247, January 1988.
+
[2] From [https://classes.cs.uoregon.edu/14S/cis607pl/Papers/fundamental-1967.pdf Fundamental Concepts in Programming Languages], 1967 (page 9 of 39).
  
[3] This example is based on one from pages 4-5 of 33, in [https://homepages.inf.ed.ac.uk/wadler/ Philip Wadler]'s  [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.3579&rep=rep1&type=pdf How to Declare an Imperative], ''ACM Computing Surveys'', 29(3):240--263, September 1997.
+
[3] [https://archive.org/details/in.ernet.dli.2015.52908 Word and Object], by Willard Van Ormond Quine (page 163 of 314).
  
[4] where <code>puts</code> can be defined as <code>fun puts s = TextIO.output(TextIO.stdOut, s);</code>
+
[4] This example is based on one from pages 4-5 of 33, in [https://homepages.inf.ed.ac.uk/wadler/ Philip Wadler]'s [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.3579&rep=rep1&type=pdf How to Declare an Imperative], ''ACM Computing Surveys'', 29(3):240--263, September 1997.
  
[5] There is some debate about whether the imprecisely-defined semantics of <code>Int</code> breaks referential transparency. For instance, <code>even (maxBound :: Int)</code> may be <code>True</code> in some contexts and <code>False</code> in others. Another example is <code>System.Info.os :: String</code>.
+
[5] where <code>puts</code> can be defined as <code>fun puts s = TextIO.output(TextIO.stdOut, s);</code>  
  
[6] One perspective is that Haskell is not just one language (plus <code>Prelude</code>), but a family of languages, parameterized by a collection of implementation-dependent parameters.
+
[6] There is some debate about whether the imprecisely-defined semantics of <code>Int</code> breaks referential transparency. For instance, <code>even (maxBound :: Int)</code> may be <code>True</code> in some contexts and <code>False</code> in others. Another example is <code>System.Info.os :: String</code>.
 +
 
 +
[7] One perspective is that Haskell is not just one language (plus <code>Prelude</code>), but a family of languages, parameterized by a collection of implementation-dependent parameters.
 
Each such language is referentially transparent, even if the collection as a whole might not be.
 
Each such language is referentially transparent, even if the collection as a whole might not be.
 
Some people are satisfied with this situation and others are not.
 
Some people are satisfied with this situation and others are not.

Latest revision as of 07:59, 22 February 2022

Referential transparency is an oft-touted property of (pure) functional languages, which makes it easier to reason about the behavior of programs. As there is no single formal definition[1], the one Christopher Strachey[2] used to introduce the term into the study of programming languages will have to suffice:

One of the most useful properties of expressions is that called by Quine[3] 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.

Side effects like (uncontrolled) imperative update break this desirable property. C and ML are languages with constructs that are not referentially transparent.

As an example, consider the following program[4][5] in Standard ML:

 puts "h"; puts "a"; puts "h"; puts "a"

which prints "haha". In an attempt to factor out the repetition, we write

let val x = (puts "h"; puts "a")
in  x; x end

but now the laugh is on us, because "ha" is only printed once. The reason is that puts's side effect is only realized when x gets bound, so we should have written

let fun x () = (puts "h"; puts "a")
in  x (); x () end

Haskell's monadic I/O system distinguishes between values and actions like the puts procedure above. So we do indeed have that

putStr "h" >> putStr "a" >> putStr "h" >> putStr "a"

is equivalent to

let x = putStr "h" >> putStr "a"
in  x >> x

Notes:

[1] Wolfram Kahl provides a USENET post by Tom DeBoni containing a summary of various definitions for referential transparency.

[2] From Fundamental Concepts in Programming Languages, 1967 (page 9 of 39).

[3] Word and Object, by Willard Van Ormond Quine (page 163 of 314).

[4] This example is based on one from pages 4-5 of 33, in Philip Wadler's How to Declare an Imperative, ACM Computing Surveys, 29(3):240--263, September 1997.

[5] where puts can be defined as fun puts s = TextIO.output(TextIO.stdOut, s);

[6] There is some debate about whether the imprecisely-defined semantics of Int breaks referential transparency. For instance, even (maxBound :: Int) may be True in some contexts and False in others. Another example is System.Info.os :: String.

[7] One perspective is that Haskell is not just one language (plus Prelude), but a family of languages, parameterized by a collection of implementation-dependent parameters. Each such language is referentially transparent, even if the collection as a whole might not be. Some people are satisfied with this situation and others are not.