[Haskell-cafe] Re: I love purity, but it's killing me.

[Paul L]

Let-expression in the EDSL indeed solves the sharing problem, but only
partially.
Recursion appears when you have a leaf node pointing back to the root
node or another branch and forming a cyclic graph in the data
structure. It is often desirable to recover cyclic sharing when
showing/reading/interpretating EDSL programs.

One possible solution is to further introduce a fixed point data
constructor, a Rec or even LetRec to explicitly capture cycles. But
then you still incur much overheads interpreting them, and syntax wise
it just gets more and more complicated to the point that turning the
EDSL into a DSL (or even a preprocessor with your own lexer and
parser) becomes more attractive.

Another alternative is to express the EDSL as Monad/MonadFix, or
Arrows/ArrowLoop. There are still interpretive overheads, but at the
very least they could help with the syntax.

The tagless paper is really nice, but I doubt it offers solutions to
the (cyclic) sharing problem.


On 2/13/08, Chung-chieh Shan <ccshan at post.harvard.edu> wrote:
> Henning Thielemann <lemming at henning-thielemann.de> wrote in article
> <Pine.GSO.4.56.0802080908310.12174 at haydn.informatik.uni-halle.de> in
> gmane.comp.lang.haskell.cafe:
>> It seems to become a FAQ. I think all DSLs suffer from the same problems:
>> sharing and recursion. I've used wrappers for CSound, SuperCollider,
>> MetaPost, they all have these problems.
>
> What do you mean by the "recursion" problem?
>
> Sometimes (or perhaps even often), sharing in an EDSL can be expressed
> in two ways.  First, to reuse a -value- in the embedded language, you
> could introduce a "let" construct in the embedded language.
>
>     let_ expr body = body expr
>
> Second, to reuse an -expression- in the embedded language, if your
> interpreter is compositional (here by "interpreter" I include a
> compiler, and by "compositional" I mean a fold), then you can represent
> an embedded expression simply as its interpretation.
>
>     add x y = x + y
>     let expr = add x y in add expr expr
>
> Jacques Carette, Oleg Kiselyov, and I have been exploring this "final"
> representation.  http://okmij.org/ftp/Computation/tagless-typed.html
>
> --
> Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
> I am a signature virus. Put me in your signature.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


-- 
Regards,
Paul Liu

Yale Haskell Group
http://www.haskell.org/yale