[racket] iterative lazy space-safe or not?

From: Eli Barzilay (eli at barzilay.org)
Date: Wed Nov 17 15:59:28 EST 2010

Two hours ago, Keiko Nakata wrote:
> > > 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.
> 
> What do you mean by "the problems that it leads to tend to be much
> more significant in the lazy language"?  You have other concerns
> than the language semantics for memorizing exceptions?

Well, think about `delay' as it's used in most Scheme implementations:
you use it in specific contexts where usually you know in advance that
you're not worried about exceptions -- if an exception always
indicates a bug, then it doesn't matter that forcing some promise
throws an exception, and a later force doesn't -- either way it's a
bug that you need to resolve, and when the bug is gone you're back
into "don't care about exceptions" mode.

But if you want to implement a lazy language, then the perspective
changes, and you certainly want that consistent behavior.  Same as
racket itself -- if exceptions *always* indicate a bug in your code
then there's no real need for making up the machinery to capture them
etc, you can get away with reporting the problem and then segfault
your way out of the process.


> > 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 can perfectly believe that there are situations where you want
> lazys and other situations where you only need delays.  For me, I'd
> need delays for initializing recursive bindings, but truely lazy
> algorithms benefit from lazys.

I certainly agree with that.  In fact, one thing I did to that end is
get a discount for `lazy' promises by not dealing with multiple
values.  Having `delay' too means that I can make *that* deal with
multiple values while regaining some performance for the composable
promises.

But a bit more than that, I made `lazy' promises usable as the end
points also, which means that you can use them too -- provided that
you don't need multiple values.  In fact, I think that in general
using `lazy' is better since it composes -- it's in perfect analogy to
tail calls: it's true that you don't always need them, but by getting
them wherever possible "good things happen", including situations
where you didn't realize that you need it.  So if you're using `delay'
you're making sure that promises don't compose, whereas a consistent
use of `lazy' will give you that when needed.


> Optimizing Java compilers perform exception analysis to optimize
> non-exception-raising code. I guess you could do the same, if you
> like; no?

Definitely -- and the same goes for multiple values too, and probably
even detecting when it's fine to replace a `delay' with a `lazy'.  The
problem is getting that analysis, and at the level of the current
implementation there's no way for the macros to do it.  At least
there's no simple way, short of turning it into a compiler.

If there was a way for me to expand the delayed code then pull out
properties from it like "does no side-effects" then things could work
out better.  Perhaps this will happen eventually, possibly via typed
racket.

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


Posted on the users mailing list.