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

[Paul L]

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 at 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
>