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

[Matthew Naylor]

Hello again,

since Oleg presented an approach to the sharing problem that works on
acyclic graphs, I may as well mention an alternative, pure, standard
Haskell solution which is to express the fork points in the circuit
(or expression), i.e. the points at which an expression is duplicated.
You need to introduce a fork primitive:

  fork :: Bit -> (Bit, Bit)

or

  fork :: Exp -> (Exp, Exp)

This fits quite naturally in the context of circuit description, and I
called it "expressible sharing".  Under some mild restrictions, it
even works on cyclic graphs.  In particular, it works nicely for
regular circuits.  The "tricky" example I mentioned earlier would be
written:

  tricky 0 = constant 0
  tricky d = add e0 e1
    where
      (e0, e1) = fork (tricky (d-1))

However, in the end I admitted defeat and decided I preferred
observable sharing!

Matt.