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

From: jerzy.karczmarczuk at info.unicaen.fr (jerzy.karczmarczuk at info.unicaen.fr)
Date: Mon Oct 15 18:27:34 EDT 2007

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

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, but I wanted to see
the gory details. If you demand to print integs, you get 

(0 . #<promise:?>)
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. Now, (caddr
integs gives 2, and integs becomes 

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

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

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

Jerzy Karczmarczuk 

Posted on the users mailing list.