[racket] iterative lazy space-safe or not?

10 minutes ago, Keiko Nakata wrote:
> Hi, 
> 
> > I don't have any concrete measurements.  The implementation is as
> > fast as I could make it, but it's still pretty slow -- for
> > example, when you compare it with a naive implementation.
> 
> Naive implementation --- do you mean non-composable promises
> (i.e. delays) or graph reductions (or STG or whatever)?

Plain delays, no exception catching, ignoring multiple values.


> > Most of the hit is due to doing the right thing wrt exceptions:
> > when there's an exception when a promise is forced, the exception
> > is stored as the "value" and will be re-raised when forced again.
> > For example, if you do this:
> > 
> >  (define a (delay (/ (random 2))))
> >  (force a)
> > 
> > and get an error, you should get an error for future forces too.
> 
> Yes. I believe this is right thing to do and I think (or want to
> think) that other languages, OCaml, Scala, F# or whatever, do the
> same.  (I'll have to check myself...)

I'll be interested in what you'd find out.


> 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).


> > > It's simple and works, which is nice; isn't it?
> > 
> > It's very fragile, and when it breaks it's very hard to find out
> > how to fix 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.
For example, one bug was:

      [(composable-promise? v) (force/composable v) (force v)]

there's an innocent looking extra `force' -- and in most cases there
was no problem with that (the bug was there for a while, and nobody
noticed).  It seems reasonable too -- the first force caches the
result so the second would just return the cached results.  The
problem is that the first `force/composable' is not called in tail
position, which caused a leak in a particular situation in the lazy
language.


> 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.)

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