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

Matthew Naylor mfn-haskell-cafe at cs.york.ac.uk
Wed Feb 13 09:27:30 EST 2008


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.


More information about the Haskell-Cafe mailing list