Tue Oct 19 10:35:32 CEST 2010

Pure functional programming and object identity

One of the most difficult ideas to let go I find object Identity.  It
pops up in my expression to SSA conversion code that needs to process
code as a graph.  The usual imperative approach (is this node "x" ?)
don't seem to work very well.

Semantically there is no problem: equality is well defined.  Identity
isn't necessary for that.  However, identity makes it easier to
_implement_ equality.  There I think I still need some experience to
see how this would be handled correctly.

( Obscure maybe : )

This seems to be a representation problem.  Representing a graph as a
list of named nodes makes implementation of equality trivial and O(1).
However, mapping an original expression to a dictionary does require a
full traversal.  The problem is to keep dictionaries in sync: node
names are _centralized_ data.  I.e. combining 2 expressions needs a
merge of dictionaries, and they might have different names for the
same nodes.