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 <ccs...@post.harvard.edu> wrote: > Henning Thielemann <lemm...@henning-thielemann.de> wrote in article > <pine.gso.4.56.0802080908310.12...@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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Regards, Paul Liu Yale Haskell Group http://www.haskell.org/yale _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe