Interpreting lambda calculus is neither cheap or efficient, otherwise we wouldn't all be using compilers :-) By "interpretive overhead" of adding Let/Rec/LetRec to an object language I mean the need to introduce variables, scoping, and environment (mapping variables to either values or structures they bind to) during interpretations, which are otherwise not needed in the object language. I can't show you how I can do better because I don't have a solution. The open question is whether there exists such a solution that's both elegant and efficient at maintain proper sharing in the object language. We certainly can get rid of all interpretive overheads by either having a "tagless" interpreter (as in Oleg and Shan's paper), or by direct compilation. But so far I don't see how a tagless interpreter could handle sharing when it can't be distinguished in the host language. One would argue that the overhead of variables (and the environment associated with them) can be avoided by having a higher order syntax, but that has its own problem. Let me illustrate with a data structure that uses higher order Rec. data C a = Val a | ... | Rec (C a -> C a) val :: C a -> a val (Val x) = x val ... val (Rec f) = val (fix f) where fix f = f (fix f) update :: C a -> C a update (val x) = ... update ... update (Rec f) = Rec (\x -> ...) The problem is right there in the creation of a new closure during update (Rec f). Haskell would not evaluate under lambda, and repeated updates will inevitably result in space and time leaks. -- Regards, Paul Liu Yale Haskell Group http://www.haskell.org/yale On 6/6/09, Chung-chieh Shan <ccshan@post.harvard.edu> wrote:
On 2009-05-27T03:58:58-0400, Paul L wrote:
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,
I don't understand this criticism -- what interpretive overhead do you mean? Certainly the Rec/LetRec encoding is pretty efficient for one object language with cycles, namely the lambda calculus with Rec or LetRec. :)
One concrete way for you to explain what interpretive overhead you mean, if it's not too much trouble, might be to compare a Rec/LetRec encoding of a particular object language to another encoding that does not have the interpretive overhead you mean and is therefore more efficient.
-- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We want our revolution, and we want it now! -- Marat/Sade We want our revolution, and we'll take it at such time as you've gotten around to delivering it -- Haskell programmer