[PRL] referential transparency

[David Herman]

In the context of the same conversation, I've heard one person claim 
that even with monads, Haskell still doesn't have referential 
transparency because of IO, and another claim that monads allow Haskell 
to preserve referential transparency. What I didn't hear was anyone 
actually give a definition of referential transparency or a 
justification of their claim.

Is there a formal definition of referential transparency? What is it?

Informally, I've heard it described as being able to "substitute equals 
with equals," meaning, IIUC, that two equivalent terms can be used 
interchangeably in any context without any observable difference in 
program behavior. But this depends on your particular equivalence 
relation, right? If you choose term equality as your equivalence 
relation, then any language is referentially transparent, no?

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.

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.

Thanks,
Dave