[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
Sat Feb 16 05:59:38 EST 2008

Hi Oleg,

at the possible risk of straying from Tom's original problem, consider
the following generator that could conceivably occur in practice:

> sklansky f [] = []
> sklansky f [x] = [x]
> sklansky f xs = left' ++ [ f (last left') r | r <- right' ]
>   where
>     (left, right) = splitAt (length xs `div` 2) xs
>     left' = sklansky f left
>     right' = sklansky f right
> test_sklansky n = runState sk exmap0
>   where
>     sk = sequence (Prelude.map unA (sklansky add xs))
>     xs = Prelude.map (variable . show) [1..n]

(Example due to Chalmers folk, Mary Sheeran and Emil Axelsson;
sklanksy is similar to scanl1, but contains more parallelism.)

If a 128-bit processor were being developed, sklansky could reasonably
be passed 128 elements,

  *Main> test_sklansky 128    -- on an AMD64 2200
  (3.71 secs, 296129440 bytes)

and could form part of a larger expression, and be called several
times.  So I think this is close to a real situation where CSE is not
practical.  But like you say, a human would not write such a humungous
expression by hand; hand-written expressions may therefore be ideal
for crunching by your CSE method.

Still, we might like to write generators like sklansky.  Hope is
offered by the new "let_" construct, but it's not clear how to use it
in this case. The problem is that sklansky is a function over lists of
expressions rather than single expressions, and the "let_" construct
can only bind single expressions and return single expressions.  To
write sklansky using your approach, it seems (to me) that the DSL's
expression type needs to be extended to support lists.  Will this not
be complicated and introduce notational inconvenience?  (In an earlier
post, I outlined a method for embedding algebraic data types in
Haskell, and it does have some notational burden.)


More information about the Haskell-Cafe mailing list