[r6rs-discuss] [Formal] Delayed evaluation

From: AndrevanTonder <andre>
Date: Mon Oct 30 09:00:08 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
   expression

      (lazy <expression>)

   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?)
       (lazy
         (let ((head (car (force s)))
               (tail (cdr (force s))))
           (if (p? head)
               (delay (cons head (stream-filter tail p?)))
               (stream-filter tail p?)))))

   the computation

     (car (force (stream-filter (from 0)
                                (lambda (m) (= m 100000000)))))
              ==> 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)))
     (loop)

   will run forever in bounded space. If (lazy ---) were replaced
   by (delay (force ---)), the amount of memory required would
   grow without bound.

========================================================================

Andre
Received on Mon Oct 30 2006 - 08:56:38 UTC