[r6rs-discuss] [Formal] Delayed evaluation
andre at het.brown.edu
Mon Oct 30 08:56:38 EST 2006
Given the unnecessary complexity of the original formal comment, I have
given a little thought to finding a concise way "lazy" could be
described in r6rs, if there happens to be some interest in including it.
I think something like the following is short and would be quite manageable
for r6rs. The current explanations of delay and force can be unchanged, but
the example implementation would need to be dropped. As a result, the
resulting specification might even be shorter than the current one:
(lazy <expression>) syntax
The "lazy" construct is useful for expressing iterative call-by-need
computations that execute in constant space.
Apart from its behaviour with respect to space consumption, the
has the same meaning as
(delay (force <expression>)).
However, whereas forcing a chain of promises of the form
(delay (force (delay (force .......... (delay <expression>)))))
triggers a recursive computation that will use an amount of space
of order O(N), where N is the length of the chain, forcing a chain
of promises of the form
(lazy (lazy (lazy ................(delay <expression>))))
will execute in space of order O(1), since the reductions
(force (lazy <expression>)) --> (force <expression>)
are done iteratively.
Example: Given the definitions
(define (from n) (delay (cons n (from (+ n 1)))))
(define (stream-filter s p?)
(let ((head (car (force s)))
(tail (cdr (force s))))
(if (p? head)
(delay (cons head (stream-filter tail p?)))
(stream-filter tail p?)))))
(car (force (stream-filter (from 0)
(lambda (m) (= m 100000000)))))
will run in O(1) space. If (lazy ---) were replaced by
(delay (force ---)) in the definition of stream-filter, the
amount of memory required would instead be O(100000000).
Example: The following non-terminating computation
(define (loop) (lazy (loop)))
will run forever in bounded space. If (lazy ---) were replaced
by (delay (force ---)), the amount of memory required would
grow without bound.
More information about the r6rs-discuss