[plt-scheme] Space/time behaviour of Lazy Scheme

On Oct 16, jerzy.karczmarczuk at info.unicaen.fr wrote:
> Probably this is a question addressed to ELi Barzilay... 
> 
> Since I suffer from a disease called co-recursivity, I tried to
> implement some of my favourite Haskell algorithms in lazy
> Scheme. For example, the list of *all* non-negative integers:
> 
> (define ones (cons 1 ones)) 
> 
> (define (add u v) (map (lambda (x y) (+ x y)) u v))
> (define integs (cons 0 (add ones integs))) 

(Shorter version:

  (define integs (cons 0 (map + ones integs)))
)


> There is nothing wrong with that. Of course, the lazy module is not
> exactly the same as the lazy semantics in Haskell or in Clean,

What differences do you see?


> but I wanted to see the gory details. If you demand to print integs,
> you get
> 
> (0 . #<promise:?>)

This is known -- and that's one place where the Lazy Scheme language
level is different than the Haskell repl (at least what I've seen in
Hugs).  (But this is not a change in the sematics.)

The thing is that all values are promises, and it's only the repl
interaction that forces them.  The question is what kind of force
should be used.  The Lazy Scheme language uses `!' (which is basically
iterating `force' as many times as needed to get to a non-promise
value) -- so you always see a value when you type expressions on the
repl.  (Modulo additional pending fixes on my todo queue.)  But the
`!' doesn't go into the results to force their contents.  This is why
you see the promise.

In the Lazy Scheme version that I use in my class I use `!!' as the
default top-level force.  This version does go through the structure
of the value and forces everything in it.  That's fine for a class,
but in the general case I think that it's better to leave the question
of "how much force to use" to you.  For example, if the default force
was `!!', then the above would blow up just like you expect it to.
(In my class we use the provided `take' for that.)


> After evaluating (cadr integs), which is 1, the same query gives 
> 
> (0 . #<promise!(#<promise!1> . #<promise:...cts/lazy/lazy.ss:508:47>)>) 
> 
> so, the promises have been partly evaluated and substituted.

Yes -- these promises print out in a way that shows their value, if
they were forced.  (These are not MzScheme's promises -- it's closer
to the definition in srfi-45.)


> Now, (caddr integs gives 2, and integs becomes
> 
> (0 . #<promise!(#<promise!1> . #<promise!(#<promise!2> . 
> #<promise:...cts/lazy/lazy.ss:508:47>)>)>) 
> 
> I will spare you the result when the fourth element is evaluated, the list
> grows somewhat. But, after the evaluation of the fifth element, something
> strange happens. I typed
> integs 
> 
> ... and I am still waiting. An infinite loop, or what. Why? The algorithm
> doesn't seem even to be exponential. So, before I try to dig inside all
> this, perhaps somebody has an answer? Thanks. 

I evaluated `(take 10 integs)', then looked at `integs' and saw
something like this:

  (0
   .
   #<promise!(#<promise!1>
              .
              #<promise!(#<promise!2>
                         .
                         #<promise!(#<promise!3>
                                    .
                                    #<promise!(#<promise!4>
                                    ...

So my guess is that the printout can be very consuming -- and perhaps
there is some problem when the nesting becomes too deep?  (In any
case, this is not a problem of the lazy language...)

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