[racket] iterative lazy space-safe or not?

From: Eli Barzilay (eli at barzilay.org)
Date: Wed Nov 17 13:05:14 EST 2010

6 minutes ago, Keiko Nakata wrote:
> From: Eli Barzilay <eli at barzilay.org>
> > > But the penalty is incurred only when an exception is raised
> > > during the initialization; am I correct? I.e, if the
> > > initialization is successful, no cost is incurred due to this.
> > 
> > It's when the promise is forced (the important part).
> Hmm... I did not know installing exception handlers costs.  But at
> any rate, I do not think I'll be willing to give up this semantics
> of memorizing exceptional behavior.

I probably wouldn't mind giving it up, but the problems that it leads
to tend to be much more significant in the lazy language.

There are still cases where the naive version is applicable.  A recent
example is Hari's purely functional data structure code -- he uses
promises extensively, but in that context there's no need to worry
about exceptions or deal with multiple values, and IIRC, he doesn't
even need the benefits of composable promises.  So I made up a small
naive implementation to be used instead of the usual promises, and the
result was a significant boost.  (I don't remember the numbers

The bottom line is that the cost should be there, but there's still
place for a simple and faster version.  I'd like to have that as part
of the core too, but I didn't think of a good way to incorporate it,

> > > Will you explain how/why it is fragile?  It looks conceptually
> > > simple.
> > 
> > Well, there were several problems that lead to memory leaks, which
> > means that it's hard to know about them, and it's hard to catch
> > them (I often resort to debugging with a process monitor).  The
> > code itself has a number of subtle details that are important and
> > easy to mess.
> It's well-thought-out rather than fragile, I would say :)
> Simplicity never means easy for me.

:)  In this case it certainly isn't...

> > > You rewrite
> > >
> > > let rec x = y, y = M  in E[x]
> > >
> > > into
> > >
> > > let rec x = M, y = x in E[x]
> > >
> > > The two graphs must be extensionally equivalent.
> > 
> > (The racket code is not doing any rewrites, so I don't see how
> > that's related.)
> I thought this is roughly what the implementation does: In the first
> term x points to y and y points to M, in the second, x points to M
> and y points to x.  (You kind of swap the pointers; so if y is not
> free in M nor E[x], it can be garbage-collected immediately.)

Ah yes -- that's the core thing in the mechanics of forcing composable
promises, but as you said above, this simplicity is not easy to

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!

Posted on the users mailing list.