Referential Transparency and Interchangeability

Being had spent hours trying to grasp referential transparency, I am finally inclined to regard this concept as confusing one rather than helpful. But maybe the problem is me…

Usually referential transparency is mentioned with regard to a function which can be replaced with another function by a compiler with the aim of incresing effectivenes in some way (let’s restricted ourselves to "functions" in common programming languages sense here).

So what’s the condition to be met to make possible this "replacement"? Let’s consider the line given by cody:

Referential transparency is an operational notion: it describes what happens when you evaluate a same piece of code (typically a function) several times, namely, the return value is the same. In particular, the evaluation context can generally be ignored when considering the operational semantics of a referentially transparent language.

In other words, if a couple of functions always return the same value for the same argument(s), so they are interchangeable (and if they both do not affect "external world" (have no side effects) – otherwise it is supposed a compiler will not able to make the replacement).

Question #1: Is the concept of referential transparency only applicable to pure functions? If so, why is it?

For example, in terms of some logical system (let’s refer this to a specification of some type of compiler or programming language, etc.) these two pretty non-pure functions can be considered interchangeable:

function DoSmthOdd1 (x) {    launchSpaceX(); //a side effect   var sum = K + x; // K is an external variable   return sum; }  function DoSmthOdd2 (x) {   var sum = x + K;   launchSpaceX();    return sum; } 

Our logical system is not interested in the order an expression written by a programmer and it does not get frightened when an external variable is used "in the same (specified) way", so the compiler can replace DoSmthOdd1 with DoSmthOdd2. In the other hand, the very same logical system prescribes that the compiler must not replace two pure functions (of kind of "the same argument – the same return value") if they have different algorithm complexity (for e. g.).

Let’s deem function equality to be interchangeability of two or more functions (= possibility to be replaced with each other) within the framework of a logical system. Then:

Question #2: Is referential transparency another word for conveing meaning of function equality (interchangeability) and with the only possible "the same argument – the same value" rule at that?

The issue is function equality is a binary relationship whereas referential transparency pretends to be an unary one. I can give an example of pure function (pure per se), but what is a (non-)referentially transparent function (if we consider it per se without making a comparsion with other functions)?

There is an example in the Expert Systems: Principles and Programming by Giarratano, Riley:

sum := f(x) + x; // f(x) changes the value of x passed by reference 

The authors claim this function to be a non-rf because

  • Depending on how the compiler is written value of x might be the original value if it was saved on a stack, or the new value if x was not saved.
  • If one compiler evaluates expressions right to left while another evaluates left to right. In this case, f(x) + x would not evaluate the same as x + f(x) on different compilers.

But wait… all the above is just comparsion of different logical systems ("compilers"). In standard algebra f(x) + x and x + f(x) are equivalent and interchangeable but in the specification of our compiler they are not. So why do we need this analogy at all?

Question #3: Is it true that a function is referentially transparent if it can be replaced in the same way how it can be done in algebra?