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

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 wrote:

Henning Thielemann wrote in article 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Regards, Paul Liu Yale Haskell Group http://www.haskell.org/yale