Is my understanding of "referential transparency" with mutable classes correct?

Question

From the book of "Functional programming in scala", I see the definition of "referential transparent" of an expression:

An expression e is referentially transparent if, for all programs p, all occurrences of e in p can be replaced by the result of evaluating e without affecting the meaning of p.

I have some code examples that I'm not sure if they are referentially transparent or not.

I will use scala.collection.mutable.StringBuilder in the examples which is a mutable class

1.

val x = new StringBuilder("Hello")

println(x.length)
println(x.length)

Suppose the code here is the whole and complete code that uses x.

Can I say expression x is a referential transparent expression?

If I change all x with its value new StringBuilder("Hello"), the observable behavior of the program is not changed:

val x = new StringBuilder("Hello")

println(new StringBuilder("Hello").length)
println(new StringBuilder("Hello").length)

2.

val x = new StringBuilder("Hello")
val y = x.append("aaa")

Suppose the code here is the whole and complete code that uses x and y.

Can I say y is referential transparent because it's not used at all in the program?

3.

def getTheClassName(n:Int):String = {
  val x = new StringBuilder("hello")
  for(int i=0;i<n;i++) {
    x.append("world")
  }
  return x.getClass.getName
}

Can I say the x is referential transparent? Because no matter how I replace it with its value, the return value will not changed.

PS: Maybe the main problem is that I don't understand what does for all programs p mean, does it mean the existing complete code? Or any possible code that may be added?

Answer 1

It means for any possible program p you might write containing that expression. Properly this should be defined with respect to a language, or a set of possible programs. So your x is referentially transparent in the language in which the only valid program is the one you wrote. Your y is referentially transparent in the subset of Scala in which you're not allowed to call .append on a StringBuilder. But these are not particularly interesting languages to talk about.

Most of the time, when people talk about a "referentially transparent" expression, they (implicitly) mean with respect to something like the Scalazzi safe subset of Scala, which is general enough to express (all?) useful Scala programs in, but safe enough to reason about. Because of course if you're allowed to call e.g. System.identityHashCode(), most allegedly "referentially transparent" expressions actually aren't.

Of course the most important definition is the operational one; what is "referentially transparent" ultimately depends on what you want to use it for. One important use case is for compiler/library optimizations: we wouldn't want a compiler to perform the replacement you gave in your example 1, because for most programs this "optimization" would change the meaning of the program. But we are happy for the compiler to optimize our programs by inlining immutable constants, because our programs "shouldn't" depend on what the identityHashCode of a particular constant is.

Answer 2

As I understand expression 'e' is referentially transparent, is it's referentially transparent for all possible programs 'p'.

It can be "referential transparent-like" for concrete program 'p', but if you can write another program 'px' that will violate "replace rule", it means expression is not referential transparent.

  import scala.collection.mutable

  val b = new mutable.StringBuilder("Hello")
  def e = b.length

  def p0 = {
    val l1 = e
    val l2 = e
    l1 + l2
  }

  def p1 = {
    val l1 = e
    b.append("World")
    val l2 = e
    l1 + l2
  }

It it's possible to build program 'p' that will violate " e in p can be replaced by the result of evaluating e" - it means that 'e' is not referential transparent. With mutable state it's very easy to build this program.

In p0 we can say that e is referential transparent, but p1 easily breaks it.