[plt-scheme] Space/time behaviour of Lazy Scheme
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> .
#<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.
Jerzy Karczmarczuk