[plt-scheme] Lazy Evaluation -- Even Streams

This is the result of a discussion I had with Phil who is working on
his streams SRFI (he's not on this list so I CCd him).

The beginning of all this is in the "How to add laziness to a strict
language without even being odd" paper.  The main idea they present,
and that Phil used following that, is that an even lazy data structure
should always be a delayed object, instead of the standard cons of
something and a promise which cause off-by-one errors since they
always require evaluation of one extra object.  The solution is to
always use functions that do this:

  (define (foo ...)
    (delay (force ...random-code...)))

which is what Phil used for a `stream-define' macro that translates to
this kind of a definition.  But I think that this could be improved
even further.  The standard solution follows the basic philosophy that
the random-code is something that uses the arguments to compute a new
stream value -- which is always a promise, but this computation itself
needs to be lazy which is why the body is wrapped in a `delay'.  The
next thing to see is that if we leave it this way, we will have a
promise containing a promise which is no longer a stream as defined,
so the contents of the delay is further wrapped in a `force'.

The complexity which I think is easy to get rid of, is that the actual
body (random-code in the above) still needs to know what arguments are
streams and use only stream functions with them.  What I'd want
instead, is to magically know what arguments are lazy and force them
before using them.  This means that the random-code will have to
handle standard Scheme objects, like lists in the stream example.  In
other words, the original solution strips a promise level on the
result of the computation which handles lazy objects, and the new
solution strips a promise level from input values on entry and delays
the result which was achieved using simple strict code -- resulting in
functions that look even more similar to their strict equivalents
since they use the same functions.  This can be implemented by
wrapping the body in code that will bind any argument variable v to
(maybe-force v) where `maybe-force' is:

  (define (maybe-force x) (if (promise? x) (force x) x))

which should work reasonably well if all lazy inputs are promises
which you'd expect them to be.  But there is another problem
introduced by this approach -- some of the arguments might not be
needed for the computation so you don't want to force them.  The
solution for this is to use a syntax binding that will bind every
input variable `v' to the *syntax* `(maybe-force v)'.  This is simple
using my `letsubst' thing from Swindle, resulting in this macro to
create such bindings for a possibly dotted list of arguments:

  (define-syntax force-args
    (syntax-rules ()
      ((force-args "REV" (arg ...) (a . rest) body0 body1 ...)
       (force-args "REV" (arg ... a) rest body0 body1 ...))
      ((force-args "REV" (arg ...) () body0 body1 ...)
       (force-args "DONE" (arg ...) body0 body1 ...))
      ((force-args "REV" (arg ...) rest body0 body1 ...)
       (force-args "DONE-R" (arg ...) rest body0 body1 ...))
      ((force-args "DONE" (arg ...) body0 body1 ...)
       (letsubst ((arg (maybe-force arg)) ...)
         body0 body1 ...))
      ((force-args "DONE-R" (arg ...) rest body0 body1 ...)
       (letsubst ((arg (maybe-force arg)) ...
                  (rest (map maybe-force rest)))
         body0 body1 ...))
      ((force-args args body0 body1 ...)
       (force-args "REV" () args body0 body1 ...))))

which can be be used to make the final syntax bits: `strict-lambda',
which is like a normal `lambda' except it forces things as above.
`strict-define' uses that for defining a named function.  `strictify'
turns a normal function to a strict one (I don't know if it's useful
for anything), and `strict' is a convenient shorthand for
maybe-forcing stuff -- either value, or applying a function of forced
values.  It's a syntax only for symmetry with `lazy' below, and its
usage will be cleared below.  Then there are `lazy' versions of all
this which are wrapped in a `delay'.  This is the code:

  (define-syntax strict-lambda
    (syntax-rules ()
      ((strict-lambda args body0 body1 ...)
       (lambda args (force-args args body0 body1 ...)))))
  (define-syntax strict-define
    (syntax-rules ()
      ((strict-define (name . args) body0 body1 ...)
       (define name (strict-lambda args body0 body1 ...)))))
  (define (strictify func)
    (strict-lambda args (apply func args)))
  (define-syntax strict ; doesn't need to be a macro
    (syntax-rules (:)
      ((strict : val)      (maybe-force val))
      ((strict func x ...) (func (maybe-force x) ...))))

  (define-syntax lazy-lambda
    (syntax-rules ()
      ((lazy-lambda args body0 body1 ...)
       (lambda args (delay (force-args args body0 body1 ...))))))
  (define-syntax lazy-define
    (syntax-rules ()
      ((lazy-define (name . args) body0 body1 ...)
       (define name (lazy-lambda args body0 body1 ...)))))
  (define (lazify func)
    (lazy-lambda args (apply func args)))
  (define-syntax lazy
    (syntax-rules (:)
      ((lazy : val)      (delay val))
      ((lazy func x ...) (delay (func x ...)))))

Now, implementing even streams with this is very simple, and doesn't
even require a special syntax...

* instead of stream-null, you use (lazy : '()), but (delay '()) would
  do just as well.  Repeating what I said above, the goal is for
  stream functions to be written as if they operate on normal pairs,
  the inputs get forced, and the output gets delayed.  This is why
  (delay '()) is the same as stream-null.

* instead of (stream-null? x), you use (strict null? x), this will
  call null?, after forcing x (if its a promise).

* The same goes for all functions that take something from the lazy
  world into the normal one, some examples are (strict pair? x),
  (strict car x), (strict cdr x).  But (strict cadr x) won't work
  since we're handling lazy *pairs* -- there is no way to force the
  cdr of the stream automatically, so all functionality relies only on
  Scheme pairs.  But note that force is conditional, so a
  `list->stream' becomes redundant -- you could just delay the list,
  or even use it as is which will work the same.

* As for a lazy constructor -- instead of (lazy-cons x y), all you
  need is (lazy cons x y) which is simple enough to not even requiring
  an additional macro.  But you rarely need this, since you'll usually
  create streams in a lazy function (which will be delayed
  automatically), or for streams that are literally specified, you
  just use them.

So the quick summary is that lazy functions operate completely in the
lazy side, strict functions work from the lazy to the strict side, and
you don't need functions that go from the strict to the lazy since it
is automatically a subset of it, but `lazy' is a nice thing to have
when you want to have delayed computations to build your stuff.

To show how this works, I go back to the "reference problem" from the
above paper.  First, I have stream-map, which I called lazy-map since I
consider this to be a generically lazy thing:

  (lazy-define (lazy-map func list)
    (if (null? list)
      '()
      (cons (func (car list)) (lazy-map func (cdr list)))))

As you can see there is no difference between this and a simple
recursive map...

`countdown' (an infinite stream counting down from a number) is also
very simple, just like an equivalent simple version (except that such
a version would never halt):

  (lazy-define (countdown n)
    (cons n (countdown (- n 1))))

`cutoff' (returning a list of the first n elements from a stream) is
again defined as if it is a normal function.  It is defined as a
strict function because it returns a value to the real world.  Note
that here we don't want to evaluate the `list' argument if n is zero
which will work since it is bound to a "symbol macro".

  (strict-define (cutoff n list)
    (if (or (zero? n) (null? list))
      '()
      (cons (car list) (cutoff (- n 1) (cdr list)))))

And finally, the following works as expected (not raising the error
that would occur with an odd stream):

  (define (12div n) (/ 12 n))
  (cutoff 4 (lazy-map 12div (countdown 4)))

There is no promise-level problem, everything is kept at a single
delay level, the same as with the standard implementation.  To see
this, I did the following:

  (cutoff 4 (lazy cons (delay 1)
                       (lazy cons (delay 2)
                                  (lazy cons (delay 3)
                                             (lazy : '())))))

and the expected result was a list of the three promises.  The only
level problem is if you want a strict argument to hold a promise
value, but I can't think of any realistic example for that.

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!