[Haskell-cafe] pointers for EDSL design

[Dominique Devriese]

John, Oleg,

2010/10/9  <oleg at okmij.org>:
>> So here's a very simple expression:
>>
>> t1 = let v = sigGen (cnst 1) in outs v v
>>
>> which is what led to my question.  I'm binding the sigGen to 'v' to
>> introduce sharing at the meta-level.  Would it be better to introduce
>> support for this in the dsl?
>
> Often this is not a question of preference but that of
> necessity. Sharing at the meta-level may help the generator, but it
> does _not_ translate into the sharing at the object level. In the
> generated code, the code for 'sigGen (cnst 1)' shall be
> duplicated. It could be that two csound blocks must share the same
> signal source, to receive samples in parallel. Meta-level sharing
> (Haskell's let) would not do. We need a construct for an object-level
> let, for example
>
>  t1 = let_ (SigGen (cnst 1)) (\v -> outs v v)

An alternative approach to model sharing at the object level is the
technique I use for modelling context-free grammars in my PADL 2011
paper "Explicitly Recursive Grammar Combinators" [1] (just got
acceptance notification this morning!). The idea is basically that you make the
sharing in the object-level expression explicit by modelling all
your terms as the results of one big recursive function and then
opening up the recursion. Using ideas from the Multirec generic
programming library and some recent Haskell type system extensions
(most importantly GADTs and type families), you can do this in a
well-typed way for sets of mutually recursive object-level
expressions.

In this case, you would get something like the following (written
without any understanding of your problem domain, so sorry if I
interpret stuff wrong here ;) ):

data I1
data T1
data CircuitNode ix where
   I1 :: CircuitNode I1
   T1 :: CircuitNode T1

myCircuit self I1 = sigGen (cnst 1)
myCircuit self T1 = outs (self I1) (self I1)

With a type class such as RecProductionRule in my paper, you can then
even get rid of the self argument and get something like this:

myCircuit I1 = sigGen (cnst 1)
myCircuit T1 = outs (ref I1) (ref I1)

The main advantage is that this approach extends to circuits with
mutually recursive nodes, but contrary to simple meta-level sharing,
allows you to observe and manipulate the recursive structure of the
circuit. Oh, and it stays properly typed. More info in the paper and
the accompanying technical report [2].

cheers
Dominique

Footnotes:
[1]  http://people.cs.kuleuven.be/~dominique.devriese/permanent/cfgc-submitted-PADL.pdf
[2]  http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW594.abs.html