[PRL] referential transparency

[Carl Eastlund]

On Mon, 30 Aug 2004 23:50:37 -0400, David Herman <dherman at ccs.neu.edu> wrote:
> 
> Another explanation I've heard is that a function, when called with the
> same argument, always returns the same result. With this definition any
> function in the IO monad is certainly not referentially transparent.

This is the definition (or explanation, because I think it's a
consequence of a more formal definition) I've heard and the one I
can/will address.

I think the Haskell IO monad is referentially transparent by this
definition.  For instance, the function hGetChar :: Handle -> IO Char.
 What does this do?  Given a file handle, it produces an IO Char, or a
computation with IO state threaded through it that produces a Char. 
Put another way, hGetChar :: Handle -> IOState -> IOState * Char.  For
a given Handle as input, hGetChar will in fact always produce the same
computation; for a given Handle and IOState, hGetChar will always
produce the same new state and Char.  Hence, I'd call it referentially
transparent.

> The most plausible definition I've seen is that you can substitute any
> subexpression with the value it converges to without making an
> observable change in the program. So Scheme is not r.t. because you
> can't replace the following expression:
> 
>      (begin (set! x 1) 10)
> 
> with 10, because there exist contexts that can distinguish the two
> terms. Again, I believe this means Haskell does not have referential
> transparency within the IO monad.

Sure it does.  The key to remember with monads like IO is that the
application of a function (such as hGetChar) does not actually update
state (such as reading IO) - only the application of some function
that "kicks off" a monad computation can do that.  For instance, the
State monad is kicked off by giving it an initial state, and the IO
monad is kicked off at the top level outside the programmer's control
(presumably by giving it an initial IO state).

So I think when you keep in mind that monads are (or can be)
implemented functionally - by passing state rather than updating it -
it becomes clear that they really are referentially transparent by
this simple definition.  Other definitions, when someone points out
which one(s) are proper, hopefully follow similarly.

I hope that makes almost as much sense outside my head as it did inside.

--Carl