[Haskell-cafe] Designing DSL with explicit sharing [was: I love purity, but it's killing me]

[Matthew Naylor]

Hi Oleg,

it's not immediately clear (to me at least) how efficient your method
will be in "practice".  Any method based on common sub-expression
elimination surely must inspect every node in the flattened graph.  In
the worst case, an acyclic graph containing n nodes could have 2^n
nodes when flattened to a tree:

  tricky 0 = constant 0
  tricky d = add g g
    where
      g = tricky (d-1)

Of course, in "practice" the worst case may not occur.  Also, my
mental model is big circuits, which may be different to yours and
Tom's.

(Sorry if I'm just pointing out the obvious.)

Matt.