Sun Jul 10 14:48:29 CEST 2011

Referential transparency and object identity

An expression e of a program p is referentially transparent[1] if and
only if e can be replaced with its evaluated result without affecting
the behavior of p.

This is a very strong requirement and completely destroys the ability
to use object identity.  From [2]:

    Identity is a property that an object may contain aspects
    that are not visible in its interface.

These "aspects" might simply be references by other objects, as the
just the act of referencing already creates a "hidden" relationship
between the pointing objects.  This relationship cannot be expressed
by any value that would substitute the object.

An interesting application of this is that while it is possible to
recover input->output dependency information for Haskell functions of
the Num class through abstract interpretation, it is impossible to
recover _internal_ sharing information from a Haskell program by
observing just the input->output behaviour of that program.  Here
"sharing" refers to bindings defined by `let' and `where' forms that
have more than one reference, thus producing a dependency graph
instead of a tree.  In short: values do not encode who they are used

In the presence of sharing, the output of such an abstract
interpretation will be a tree with duplicate nodes.  With careful
input prepration, external input nodes can be unified using equality
in a straightforward way, but internal nodes need to be "scanned"
based only on structural equivalence of their dependency graph that
traces back to the input nodes.  This is really just common
subexpression elimination and has not much to do with the original

[1] http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
[2] http://en.wikipedia.org/wiki/Identity_(object-oriented_programming)