Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer
    
Great answer. The key is that there must not exist any program where you'd be able to tell the difference. In addition to effects observable within programs, this also includes things like I/O. So if you changed mutating a global for printing a message to stdout, it still wouldn't be referentially transparent. Conversely you can have side effects; they just can't be observable. If you memoized the results, there would be no program that could tell the difference. So it wouldn't be pure, but it would be referentially transparent. It may not be thread-safe though! –  Doval Mar 30 at 20:10
1  
@Doval: right. In my second example, it's a matter of abstraction. foo as a black box is RT. But its implementation clearly isn't, and you run into all the same problems that you run into when not writing RT code. Like, as you mentioned, thread-safety. It's just that the "universe" is much smaller, and so the scope of the side-effects is not that big. The problem with side-effects is that they make reasoning about programs essentially non-local. In my second example, the world is much smaller, so "non-local" is less of a problem. –  Jörg W Mittag Mar 30 at 20:13

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.