Can referentially transparent functions have side effects?

Question

I read everywhere that referential transparency and side-effects are mutually exclusive for all functions, however, what about the case in which a function changes some state that has no effect on its outputs. For example:

global_variable = 0

def foo(a,b):
    global_variable += 2
    return a + b

# Other code ...

Now, if you call this function, it seems to fit the standard definition of referential transparency while it also changes state and thus has side-effects.

With that in mind, I wonder, do I misunderstand referential transparency or the even the idea of a side-effect? Is it correct to say that the function foo is both referentially transparent and has side-effects?

To an extent, I feel that it is counter-productive to expand the definition of referential transparency with the condition that side-effects with no effect on the return value of a function still excludes functions from being considered referentially transparent.

Answer 1

Referential Transparency means that you can replace an expression with the result of evaluating that expression everywhere in the program without changing the result of the program.

So, take the following program:

a = foo(1, 2) + foo(1, 2)
b = a + global_variable

Referential Transparency says that I can replace every occurrence of foo(1, 2) with the result of evaluating foo(1, 2) (i.e. 3) without changing the meaning of the program. So, this program must have the exact same result as the preceding program:

a = 3 + 3
b = a + global_variable

But it doesn't. The first program has a = 6 and b = 10 the second program has a = b = 6. Therefore, foo is not Referentially Transparent.

In fact, we can simplify the program even more, I just wanted to demonstrate what "everywhere in the program means":

foo(1, 2)

must be the same as

3

but the values of global_variable in both programs are different.

Note that a complex expression can be Referentially Transparent when viewed as a black box even if its constituent parts aren't.

For example:

def foo(a, b)
  static mutable_cache
  if not mutable_cache.has_key?([a, b])
    mutable_cache[[a, b]] = a + b
  end
  return mutable_cache[[a, b]]
end

foo uses a mutable data structure to cache the results of the incredibly expensive operation of adding two integers. Even though that clearly is not RT, the function viewed as a black box is: I can replace foo(1, 2) with 3 everywhere without changing the result of the program as a whole. The side-effects are contained within foo. This is sometimes called externally pure. This is common in Scala, for example. The standard library favors referentially transparent interfaces, but sometimes the (hidden) implementation uses mutation under the hood.

Answer 2

In your example, the variable global_variable is not referentially transparent, because its value is being mutated – we cannot arbitrarily exchange global_variable with 0 in the program.

While the function foo does have side effects, it could also be argued that it's a pure function because the return value is solely dependent on the function arguments. However, this is not a contradiction: foo is not a function in the mathematical sense, but more like a procedure (which is executed solely for side effects).

So the question is what exactly you mean by “referential transparency”:

• A name is interchangeable with the definition it has been bound to:

  Then yes, foo would be referentially transparent because inlining the function will not change the program behavior.

• An expression is interchangeable with the value of that expression:

  Then no, because substituting foo(x, y) with x + y does not maintain all side effects of the foo procedure.