Relations between different functional programming notions

Question

I understand different notions of functional programming by itself: side effects, immutability, pure functions, referential transparency. But I can't connect them together in my head. For example, I have the following questions:

1. What is the relation between ref. transparency and immutability. Does one implies the other?

2. Sometimes side effects and immutability is used interchangeably. Is it correct?

Answer 1

This question requires some especially nit-picky answers, since it's about defining common vocabulary.

First, a function is a kind of mathematical relation between a "domain" of inputs and a "range" (or codomain) of outputs. Every input produces an unambiguous output. For example, the integer addition function + accepts input in the domain Int x Int and produces outputs in the range Int.

object Ex0 {
  def +(x: Int, y: Int): Int = x + y
}

Given any values for x and y, clearly + will always produce the same result. This is a function. If the compiler were extra clever, it could insert code to cache the results of this function for each pair of inputs, and perform a cache lookup as an optimization. That's clearly safe here.

The problem is that in software, the term "function" has been somewhat abused: although functions accept arguments and return values as declared in their signature, they can also read and write to some external context. For example:

class Ex1 {
  def +(x: Int): Int = x + Random.nextInt
}

We can't think of this as a mathematical function anymore, because for a given value of x, + can produce different results (depending on a random value, which doesn't appear anywhere in +'s signature). The result of + can not be safely cached as described above. So now we have a vocabulary problem, which we solve by saying that Ex0.+ is pure, and Ex1.+ isn't.

Okay, since we've now accepted some degree of impurity, we need to define what kind of impurity we're talking about! In this case, we've said the difference is that we can cache Ex0.+'s results associated with its inputs x and y, and that we can't cache Ex1.+'s results associated with its input x. The term we use to describe cacheability (or, more properly, substitutability of a function call with its output) is referential transparency.

All pure functions are referentially transparent, but some referentially transparent functions aren't pure. For example:

object Ex2 {
  var lastResult: Int
  def +(x: Int, y: Int): Int = {
    lastResult = x + y
    lastResult
  }
}

Here we're not reading from any external context, and the value produced by Ex2.+ for any inputs x and y will always be cacheable, as in Ex0. This is referentially transparent, but it does have a side effect, which is to store the last value computed by the function. Somebody else can come along later and grab lastResult, which will give them some sneaky insight into what's been happening with Ex2.+!

A side note: you can also argue that Ex2.+ is not referentially transparent, because although caching is safe with respect to the function's result, the side effect is silently ignored in the case of a cache "hit." In other words, introducing a cache changes the program's meaning, if the side effect is important (hence Norman Ramsey's comment)! If you prefer this definition, then a function must be pure in order to be referentially transparent.

Now, one thing to observe here is that if we call Ex2.+ twice or more in a row with the same inputs, lastResult will not change. The side effect of invoking the method n times is equivalent to the side effect of invoking the method only once, and so we say that Ex2.+ is idempotent. We could change it:

object Ex3 {
  var history: Seq[Int]
  def +(x: Int, y: Int): Int = {
    result = x + y
    history = history :+ result
    result
  }
}

Now, each time we call Ex3.+, the history changes, so the function is no longer idempotent.

Okay, a recap so far: a pure function is one that neither reads from nor writes to any external context. It is both referentially transparent and side effect free. A function that reads from some external context is no longer referentially transparent, whereas a function that writes to some external context is no longer free of side effects. And finally, a function which when called multiple times with the same input has the same side effect as calling it only once, is called idempotent. Note that a function with no side effects, such as a pure function, is also idempotent!

So how does mutability and immutability play into all this? Well, look back at Ex2 and Ex3. They introduce mutable vars. The side effects of Ex2.+ and Ex3.+ is to mutate their respective vars! So mutability and side effects go hand-in-hand; a function that operates only on immutable data must be side effect free. It might still not be pure (that is, it might not be referentially transparent), but at least it will not produce side effects.

A logical follow-up question to this might be: "what are the benefits of a pure functional style?" The answer to that question is more involved ;)