scalafunctional-programmingscala-catsreferential-transparencycats-effect

Can a function operating upon mutable data structure be referentially transparent?


I'm working on an network application and designed the following trait to read files from remote machines:

trait ReadFileAlg[F[_], Dataset[_], Context]{
  def read(path: String, ctx: Context): F[Dataset[String]]
}

final class NetworkContext{
  private var fileDescriptor: Int = _
  private var inputStream: InputStream = _
  //etc
}

final class ReadFromRemoteHost[F[_]: Sync] extends ReadFileAlg[F, List, NetworkContext]{
  override def read(path: String, ctx: NetworkContext): F[List[String]] = Sync[F].delay(
    //read data from the remote host
  )
}

The problem I see here is that the implementation accepts NetworkContext as a paramenter which is mutable and contains fields like fileDescriptor which is related to a network connection.

Is this function read referentially transparent?

I think yes, because the function itself does not provide direct access to a mutable state (it is under Sync[F].delay) even though it accepts mutable data structure as an argument.


Solution

  • IMO, the semantics of read are

    "When you apply me I am pure, however when you run me I have a side-effect."

    Some say this is a kind of sleight of hand:

    ...we simply declare that a function returning an IO type may have arbitrary effects without going into detail in how these come about. The scheme has two consequences: First, the type of a function tells you whether it is referentially transparent or has side-effects when run.

    For example, consider the following object with mutable state

    object Foo {
      var x = 42
    }
    
    def f(foo: Foo.type): Int = foo.x
    

    We can confirm f is not referentially transparent because

    assert(f(Foo) == 42) // OK
    assert(f(Foo) == 42) // OK
    ...
    Foo.x = -11
    ...
    assert(f(Foo) == 42) // boom! Expression f(Foo) suddenly means something else
    

    However re-implementing f to "suspend" the effect

    def f(foo: Foo.type): IO[Int] = IO(foo.x)
    

    which is similar to

    def f(foo: Foo.type): Unit => Int = _ => foo.x
    

    then

    magicalAssert(f(Foo) == (_ => foo.x)) // OK
    magicalAssert(f(Foo) == (_ => foo.x)) // OK
    ...
    Foo.x = -11
    ...
    magicalAssert(f(Foo) == (_ => foo.x)) // Still OK! Expression f(Foo) did not change meaning
    

    Here magical assert is like human brain and does not suffer from halting problem so is able to deduce equality of function behaviour, that is, applying f evaluates to value (_ => foo.x) which is indeed always equal to value (_ => foo.x) even though at some point Foo.x was mutated to -11.

    However, running f's effect we have

    assert(f(Foo)() == 42) // OK
    assert(f(Foo)() == 42) // OK
    ...
    Foo.x = -11
    ...
    assert(f(Foo)() == 42) // boom! expression f(Foo)() suddenly means something else
    

    (Note how we are simulating IO.run via extra parentheses in f(Foo)())

    Hence expression f(Foo) is referentially transparent, however expression f(Foo)() is not.