全部文章

What is referential transparency in essence?

Introduction

Referential transparency is a fundamental concept of functional programming, but its real meaning is obscure, especially to newcomers. This article delves into this concept, trying to the reveal its very essence.

In the following, we sometimes also use RT as a shorthand for referential transparency.

Referential tranparent expression

First of all, we need to clarify the context of discussion, as much of obscurity arise from the lack of or unclear context. When we say something is referential transparent, it must be an expression. Someone take it for granted, because they think in functional programming way, where expression is a first class citizen. However, this is not true for most programmers that get used to procedural programming languages. For a long time, I do not understand RT because I come up with a Java statement, and ask myself what is a RT version of it.

Definition: An expression in a program, is referential transparent if it may be replaced by its value (or anything having the same value) without changing the program behaviors.

Examples

  1. Below is a simple scala program
val a = {
    println("hi"); 1
}
a + a

When this program runs, it will print “hi” once, and the final result is a + a = 2.

In addition, if we replace a with its value, the program becomes

({ println("hi"); 1}) + ({println("hi"); 1})

This program prints “hi” twice run it runs. Its behavior is different to the original one. Thus, a is not referential transparent.

  1. The expression a in the following program is referential transparent.
val a = 1
a + a

If we replace a by its value 1, the behaviors of the program are the same.

Theorems

  1. A referential transparent expression cannot have any side effects.

Short proof: give example 1 as a counter example.

Referential transparency FTW

Suppose we are functional programming advocates, and we believe in writing pure code for the win, how do we achieve that goal?

It turns out that, the heart of the problems is side effect handling. In any realworld programs, we have to deal with side effect, like printing as previous example shows. Fortunately, there are already solutions to this problem. That is effect libraries in Scala, and the built-in IO monad in Haskell.

Let us take Cats effect library as an example, and rewrite example 1 into a referential transparent version.

import cats.effect._
val a = IO {
    println("hi"); 1
}
val b = for {
    x <- a
    y <- a
} yield x + y
b.unsafeRunSync()

The main difference is the introduction of IO. Just like any other effect library, IO wraps any expressions that may contain side effect into a pure value. Its signature is as below.

object IO {
    def apply[A](body: => A): IO[A]
}

Since a is of type IO[Int] now, we cannot use the + operator any more. Instead, we build a new effect value b from a. For demonstration purpose, we invoke the unsafeRunSync method to trigger running the effect.

Now it is easy to verify that a is referential transparent.

How does effect libraries work?

An effect type (and value) is introduced, that can wrap an expression with side effect into a referential transparent expression. Aforementioned IO type is such an example. But how does such wrapping work? It sounds like a magic, isn’t it?

The key is, an effect value is actually lazily evaluated computation. Thus, a value of type IO[Int] represents a computation that, when run, will do some work (having side effects), and finally produce an Int as the result. In this regard, IO[A] is equivalent to () => A.

type IO[A] = () => A

Proposition

Any expression of the type () => A is referential transparent.

Location independence

Recall that in example 1, the side effect arises from println("hi"). Furthermore, the signature of println is the following.

def println(s: String) => Unit

In other words, the expression println("hi") is eagerly evaluated. This difference makes me suspect that RT is related to eagerness of expression.

If one expression has side effects and is eagerly evaluated, then its behavior depends on the location of the expression in the program. Otherwise, when an expression is lazily evaluated, its effect occurs deterministically regardless of its location, thus you can move it anywhere, aka referential transparent.

To help you understand the statements, let me give an example. This program prints a before b.

println("a")
println("b")

If we want to reuse println("b"), and give it a name (reference) like the following

val stm = println("b")
println("a")
stm

This program prints “b” before “a”. Because the expression println("b") is eagerly evaluated, moving it around or replacing it by a reference may alter its behavior, depending on its final location.

On the other hand, what happen if println is lazily evaluated?

def printAction(s: String) = () => println(s)
val a = printAction("a")
val b = printAction("b")
a()
b()

In this case, expression a and b can be in any order, and the program behaviors keep the same. Surprise, we make a and b referential transparent without any effect library.

Therefore, referential transparency is equivalent to location independence.

Explicit (expression) dependency

In procedural programming languages, a program is a sequence of statements (instructions). Consequently, the order of statements matters a lot. On the other hand, in functional programming languages, a program is a lambda expression. Thus, expression order is irrelevant to its semantics.

In real life, things come in order most of the time. Say we want to print a then b, we do this in procedural language like this.

println("a")
println("b")

As we can see, we do not specify the order of execution, rather it is implicitly defined (as code order).

To achieve the same thing in functional programming, we write something like the following.

val a = IO{println("a")}
val b = IO{println("b")}
for {
    _ <- a
    _ <- b
} yield ()

The for expression actually desugars to a.flatMap(_ => b). Note the flatMap call, it explicitly encodes the order (dependency) of a and b.

In conclusion, referential transparency = location independence = explicit (expression) dependency

Benefits of RT

  • Local reasoning
  • Easy code refactoring
  • Explicit value dependency

Drawbacks of RT

  • Deep learning curve
  • Viral IO boilerplate
  • Performance overhead

Conclusion

I think explicit dependency captures the essence of referential transparency. Because the expression dependency is explicit, it is easier to reason about the logic, and safer to refactor code. Also because of this explicitness, we have to write more code to express it.

After learning the very essence of RT, I will embrace this elegant concept, but I won’t force myself to write referential transparent program in real world application.

發表於2019年12月8日