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

From: jerzy.karczmarczuk at info.unicaen.fr (jerzy.karczmarczuk at info.unicaen.fr)
Date: Tue Oct 16 12:13:15 EDT 2007

Eli Barzilay kindly answers my question about lazy Scheme : 

> (Shorter version: 
>   (define integs (cons 0 (map + ones integs)))
> )

Sure, I had just that map by hand... 

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

You answered yourself. There is no immediate replacement of the thunk
(promise) by the result in *all* circumstances. But this wasn't my grief,
although the question about the space/time complexity of the system
remains an interesting question. I accept, of course what you say here,
and your comment about bangBang. 

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

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

Eli, I am not "accusing" the semantics of the language of anything. I just
want to know what happens. Sorry, but your 'take' answer is not sufficient,
your take is also lazy. If you *don't* evaluate caddr or whatever of
integs, execute (take 10 integs), an then ask: integs, you'll get 

(0 . #<promise:?>) 

But, please, ask for "4": (cadr (cdddr integs)), as I did, and then try to
print the result of integs. After several minutes I see only that CPU heats
(under Windows). 

Jerzy Karczmarczuk 

Posted on the users mailing list.