[Haskell-cafe] I love purity, but it's killing me.

[Matthew Naylor]

Hi,

(Warning: longish message!)

There is some concern, and rightly so, that observable sharing is
dangerous, and that your Haskell program will explode if you use it,
and perhaps even that anyone who uses it is "dirty" and should be sent
to matron's for a good scrubbing!  However, when used "safely", it is
not a hack, nor even dirty, but a nice, simple solution to an
otherwise nasty problem.  Below I define what I mean by "safely".

First consider the circumstances under which obserevable sharing is
useful.  Typically we have some Haskell function "f" that produces a
symbolic representation of an expression.  For whatever reason, we'd
like to *generate a program* that computes the value of this
expression, rather that computing it in Haskell.  For example, in
Lava, we want to generate a VHDL program so that the expression can be
computed on, say, an FPGA.  In Tom's case, he wants to generate a C
program to compute the expression.  All perfectly reasonable, and in
my opinion, a very powerfull way to use Haskell.

Now recall that referential transparency lets you replace equals with
equals without changing the *value produced* by a program.  Note that
it says nothing about preserving *runtime behaviour*.  Sharing, for
example, may be lost.  So if you do equational reasoning on function
"f" (above), and loose some sharing, then you can only expect that the
same sharing will also be also lost in the generated program.  As long
as the generated program computes the same result as it did before,
referential transparency will be, overall, preserved; it would only be
lost intermediately.  This is what I mean by "safe".

Now, there remains the concern that Haskell's semantics does not
enforce sharing.  A Haskell compiler is free to change the sharing a
program at a whim, unknowingly to the programmer who may be relying on
it in for an efficient program.  However, to my knowledge, it is an
unwritten rule of Haskell compilers that sharing *is* preserved, and
that they do perform *graph* reduction.  Clean, a similar language to
Haskell, indeed has a semantics based on graphs.  So I don't believe
Haskell being non-strict (not necessarily lazy) is a good reason for
not using observable sharing.  Though I do feel better when I compile
without -O. :-)

Finally, when I say "observable sharing", I don't necessarily mean it
as defined by Koen Claessen and David Sands.  I simply mean the use of
unsafePerformIO to detect sharing, whether or not this is done by an
"eq" predicate on Refs. (I say this because I think there are simpler
ways to detect sharing, though these will probably not have the nice
semantic properties of observable sharing.)

Sorry for the somewhat long exposition. :-)

Matt.