[ACCEPTED]-Purity vs Referential transparency-purely-functional

If I gather in one place any three theorists 21 of my acquaintance, at least two of them 20 disagree on the meaning of the term "referential 19 transparency." And when I was a young 18 student, a mentor of mine gave me a paper 17 explaining that even if you consider only 16 the professional literature, the phrase 15 "referentially transparent" is used to mean 14 at least three different things. (Unfortunately 13 that paper is somewhere in a box of reprints 12 that have yet to be scanned. I searched 11 Google Scholar for it but I had no success.)

I 10 cannot inform you, but I can advise you to 9 give up: Because even the tiny cadre of 8 pointy-headed language theorists can't agree 7 on what it means, the term "referentially 6 transparent" is not useful. So don't use it.

P.S. On 5 any topic to do with the semantics of programming 4 languages, Wikipedia is unreliable. I have 3 given up trying to fix it; the Wikipedian 2 process seems to regard change and popular 1 voting over stability and accuracy.

All pure functions are necessarily referentially 20 transparent. Since, by definition, they 19 cannot access anything other than what they 18 are passed, their result must be fully determined 17 by their arguments.

However, it is possible 16 to have referentially transparent functions 15 which are not pure. I can write a function 14 which is given an int i, then generates a 13 random number r, subtracts r from itself and 12 places it in s, then returns i - s. Clearly this 11 function is impure, because it is generating 10 random numbers. However, it is referentially 9 transparent. In this case, the example is 8 silly and contrived. However, in, e.g., Haskell, the 7 id function is of type a - > a whereas my stupidId function 6 would be of type a -> IO a indicating that it makes 5 use of side effects. When a programmer can 4 guarantee through means of an external proof 3 that their function is actually referentially 2 transparent, then they can use unsafePerformIO to strip 1 the IO back away from the type.

I'm somewhat unsure of the answer I give 30 here, but surely somebody will point us 29 in some direction. :-)

"Purity" is generally 28 considered to mean "lack of side-effects". An 27 expression is said to be pure if its evaluation 26 lacks side-effects. What's a side-effect 25 then? In a purely functional language, side-effect 24 is anything that doesn't go by the simple 23 beta-rule (the rule that to evaluate function 22 application is the same as to substitute 21 actual parameter for all free occurrences 20 of the formal parameter).

For example, in 19 a functional language with linear (or uniqueness, this 18 distinction shouldn't bother at this moment) types 17 some (controlled) mutation is allowed.

So 16 I guess we have sorted out what "purity" and 15 "side-effects" might be.

Referential transparency 14 (according to the Wikipedia article you 13 cited) means that variable can be replaced 12 by the expression it denotes (abbreviates, stands 11 for) without changing the meaning of the 10 program at hand (btw, this is also a hard 9 question to tackle, and I won't attempt 8 to do so here). So, "purity" and "referential 7 transparency" are indeed different things: "purity" is 6 a property of some expression roughly means 5 "doesn't produce side-effects when executed" whereas 4 "referential transparency" is a property 3 relating variable and expression that it 2 stands for and means "variable can be replaced 1 with what it denotes".

Hopefully this helps.

These slides from one ACCU2015 talk have a great summary on the topic of referential 20 transparency.

From one of the slides:

A language 19 is referentially transparent if (a) every 18 subexpression can be replaced by any other that’s 17 equal to it in value and (b) all occurrences 16 of an expression within a given context 15 yield the same value.

You can have, for 14 instance, a function that logs its computation 13 to the program standard output (so, it won't 12 be a pure function), but you can replace 11 calls for this function by a similar function 10 that doesn't log its computation. Therefore, this 9 function have the referential transparency property. But... the 8 above definition is about languages, not 7 expressions, as the slides emphasize.

[...] it's 6 the same as if it were pure in the first 5 place, isn't it?

From the definitions we 4 have, no, it is not.

Is there a simpler way 3 to understand the differences between a 2 pure expression and a referentially transparent 1 one, if any?

Try the slides I mentioned above.

I'll quote John Mitchell Concept in programming language. He defines pure 29 functional language has to pass declarative 28 language test which is free from side-effects or lack of side effects.

"Within 27 the scope of specific deceleration of x1,...,xn 26 , all occurrence of an expression e containing 25 only variables x1,...,xn have the same value."

In 24 linguistics a name or noun phrase is considered 23 referentially transparent if it may be replaced 22 with the another noun phrase with same referent 21 without changing the meaning of the sentence 20 it contains.

Which in 1st case holds but 19 in 2nd case it gets too weird.

Case 1: "I 18 saw Walter get into his new car."

And if 17 Walter own a Centro then we could replace 16 that in the given sentence as:

"I saw 15 Walter get into his Centro"

Contrary to first 14 :

Case #2 : He was called William Rufus because of his 13 read beard.

Rufus means somewhat red and 12 reference was to William IV of England.

"He 11 was called William IV because of his read beard." looks 10 too awkward.

Traditional way to say is, a 9 language is referentially transparent if 8 we may replace one expression with another 7 of equal value anywhere in the program without 6 changing the meaning of the program.

So, referential 5 transparency is a property of pure functional 4 language. And if your program is free from 3 side effects then this property will hold.

So 2 give it up is awesome advice but get it 1 on might also look good in this context.

Let's start with a question: is this snippet 36 of Haskell pure?

next   :: IORef Int -> IO Int
next r =  do i <- readIORef v
             writeIORef (i + 1)
             return i

• boring answer: we don't 35 know - the monadic IO type and its assortment 34 of primitives, FFI calls, et al are deemed to be abstract.

• alternate 33 answer: yes - next is merely a composition of 32 inactive IO actions. Those actions can only 31 [legitimately] occur if next is called from main :: IO () but by the 30 time that happens, main (and subsequently next) will 29 be semantically outside Haskell.

So what 28 about this snippet of Haskell:

next   :: STRef Int -> IO Int
next r =  do i <- readSTRef v
             writeSTRef (i + 1)
             return i

Does the alternate 27 answer carry across?

• modified answer: [...] - next is merely a composition of inactive IO ST actions. Those actions can only [legitimately] occur if next is called from main :: IO () but by the time that happens, main (and subsequently next)[?!] will be outside Haskell, semantically.

...what if next is part 26 of an ST action called by
runST :: (forall s . ST s a) -> a ...?

t = runST $ runX

runX = do ...
          i <- next v
          ...

That alternate 25 answer won't work here - runX never semantically 24 "goes outside". If t is evaluated, then
next :: STRef Int -> ST Int 23 - and all the effects it relies on - will 22 happen "inside Haskell".

If "purity" means 21 "no effects" ("side" or 20 otherwise!) then t is impure.

But we can still 19 use equational reasoning with t:

t + 2*t^2

and:

let x = t in x + 2*x^2

would be equivalent expressions 18 - referential transparency is preserved.

So 17 purity and referential transparency are 16 different:

• purity: the property that an expression 15 makes no use of effects;

• referential transparency: the property that 14 an expression always has the same value 13 in the same environment.

_{Despite all that, don't expect the Haskell website to be updated any time soon - Haskell's evaluation mechanism is actually non-strict, but the term "lazy" lingers on...}

...you're not convinced? Alright, consider 12 a simple primitive e.g. for adding Int values:

primPlusInt :: Int -> Int -> Int

Let's 11 contemplate how primPlusInt x y would be evaluated:

1. if x isn't already evaluated, then evaluate and overwrite y with its result;
2. if y isn't already evaluated, then evaluate and overwrite y with its result;
3. Extract the primitive value (of type Int# in GHC) from x;
4. Extract the primitive value from y;
5. Overwrite an unused memory location (or CPU register) with the primitive result of adding the two primitive values from steps 3 and 4;
6. Overwrite the application primPlusInt x y with the final (Int) result, using the primitive result from step 5.

...that's 10 four assignments overwrites, at least - there would 9 be more if the evaluations in steps 1 and 8 2 occur, not to mention the possibility 7 of garbage collection, thread scheduling, etc. As 6 with runX, all of those effects happen "inside 5 Haskell". It is the inescapable consequence 4 of running a program - functional or otherwise 3 - on top of a machinery so intrinsically based on mutable state.

But 2 - just like t earlier - primPlusInt [if correctly implemented] is also referentially 1 transparent.

Pure functions are those that return the 31 same value on every call, and do not have 30 side effects.

Referential transparency means 29 that you can replace a bound variable with 28 its value and still receive the same output.

Both pure and referentially transparent:

def f1(x):
    t1 = 3 * x
    t2 = 6
    return t1 + t2

Why is this pure?

Because 27 it is a function of only the input x and 26 has no side-effects.

Why is this referentially transparent?

You could replace t1 and 25 t2 in f1 with their respective right hand sides 24 in the return statement, as follows

def f2(x):
    return 3 * x + 6

and f2 will still 23 always return the same result as f1 in every 22 case.

Pure, but not referentially transparent:

Let's modify f1 as follows:

def f3(x):
    t1 = 3 * x
    t2 = 6
    x = 10
    return t1 + t2

Let us try 21 the same trick again by replacing t1 and t2 with 20 their right hand sides, and see if it is 19 an equivalent definition of f3.

def f4(x):
    x = 10
    return 3 * x + 6

We can easily 18 observe that f3 and f4 are not equivalent on 17 replacing variables with their right hand 16 sides / values. f3(1) would return 9 and f4(1) would 15 return 36.

Referentially transparent, but not pure:

Simply modifying f1 to receive a 14 non-local value of x, as follows:

def f5:
    global x
    t1 = 3 * x
    t2 = 6
    return t1 + t2

Performing 13 the same replacement exercise from before 12 shows that f5 is still referentially transparent. However, it 11 is not pure because it is not a function 10 of only the arguments passed to it.

Observing 9 carefully, the reason we lose referential 8 transparency moving from f3 to f4 is that x is 7 modified. In the general case, making a 6 variable final (or those familiar with Scala, using 5 vals instead of vars) and using immutable objects 4 can help keep a function referentially transparent. This 3 makes them more like variables in the algebraic or 2 mathematical sense, thus lending themselves better to 1 formal verification.