2021-04-30

Lately, I have been exploring lazy programming in Scheme. I think the subject is
really interesting, and I wish to show this with the blog post you are currently
reading. The inspiration for my little excursion into the wacky land of lazy
programming comes from my encounters with Haskell, and its lazy nature. This is
particularily true with lists in Haskell, which makes for a good starting point.

To my surprise Scheme already features primitives for lazyness in the language.
These are the the `delay` and `force` functions. To make any (!) expression
lazy, you simply wrap it with a delay clause like so:

    (delay (+ 2 2))
    => #[promise 12 (unevaluated)]

This will evaluate to something Scheme calls a "promise". To get the value of a
promise, you evaluate it inside a force clause like so:

    (force (delay (+ 2 2)))
    => 4

If your Scheme system does not come with these procedures, it is trivial to
implement them. Here's a definition of delay:

    (define-syntax delay
      (syntax-rules ()
        ((delay expr)
         (lambda () expr))))

It has to be a macro since it shouldn't evaluate its argument.

With this definition, force is also incredibly easy to define.

    (define (force delayed) (delayed))

Yeah, it's just evaluating that delayed function.

Now, let us get on with the lists! My lazy list model consists of a value
cons'ed onto a promise which when evaluated will produce a value, consed onto a
promise, etc. Let me visualise it for you with an example. A list of the numbers
1 to 3 would look like the following:

    (cons 1 (delay (cons 2 (delay (cons 3 (delay '()))))))

In practice, this is really just a pair of a value and a promise, but it is
really a lazy list of values. Because of the structure, we do not need the empty
list to close the list, like other strict lists in Scheme. Because of our
abstraction, it is therefore possible to create infinite lists. However, I am
getting ahead of myself.

Typing that long sequence is quite tedious. Let us create a function to create a
lazy range of values. This is my implementation:

    (define (range low high)
       (if (= low high)
           '()
           (cons low (delay (range (+ 1 low) high)))))

Now, this function creates a lazy list of values from low to high, including
low. An ideal version would create an infinite list if the high argument is
omitted from the evaluation. Optional arguments can be implemented portably
with a case-lambda:

    (define range
      (case-lambda
        ((low) (cons low (delay (range (+ 1 low)))))
        ((low high) (if (= low high)
                        '()
                        (cons low (delay (range (+ 1 low) high)))))))

Right! Now we can create lists of any size, including infinite ones! However, we
still do not have any method of extracting these values in a nice manner. To
build more complex functions for doing this, let us first define the essential
car and cdr functions:

    (define (lazy-car lst)
      (car lst))

    (define (lazy-cdr lst)
      (force (cdr lst)))

As you can see, taking the car of a lazy list is exactly the same as any
ordinary list since the first element of a lazy list is a value. To get the cdr
of the lazy list, we generate the rest of the list (which is actually just one
more value and its accompanying promise).

The final essential function is not really essential at all, but I find it quite
useful. It is a function which given a lazy list will produce a normal strict
one. This is useful for inspecting the values of the list after applying various
operations to it, as we are unable to see the values of a lazy list otherwise.

Here is one implementation of it:

    (define (force-list lst)
      (if (null? lst)
          '()
          (cons (lazy-car lst)
                (force-list (lazy-cdr lst)))))

Now we can generate a lazy list with range and view the resulting list with
force-list. Oh, and a word of caution: If you attempt to pass an infinite list
to force-list, it will never terminate, since it will generate the rest of the
values forever. Let us try it out:

    (force-list (range 1 10))
    => (1 2 3 4 5 6 7 8 9)

Great! Let us write some utility functions.

The first one will be take, which given a lazy list will extract the first n
elements and create a new lazy list with those elements in it.

    (define (take lst n)
      (if (zero? n)
          '()
          (cons (lazy-car lst)
                (delay (take (lazy-cdr lst) (- n 1))))))

Let us try it out by taking the first 5 elements of an infinite list, starting
at 10:

    (force-list (take (range 10) 5))
    => (10 11 12 13 14)

Another interesting function would be a lazy filter which removes all elements
of the lazy list which does not evaluate to true given a predicate function.
It is defined here as lazy-filter rather than simply filter to avoid naming
conflicts.

    (define (lazy-filter pred lst)
      (cond
       ((null? lst) '())
       ((pred (lazy-car lst)) (cons (lazy-car lst)
                                    (delay (lazy-filter pred (lazy-cdr lst)))))
       (else (lazy-filter pred (lazy-cdr lst)))))

Let us try it out by taking the first 5 even numbers, starting at 1:

    (force-list (take (lazy-filter even? (range 1))
                      5))
    => (2 4 6 8 10)

Now we can achieve the same as Haskell list comprehensions. The above example in
Haskell would be written as:

    take 5 [ x | x <- [1..], even x ]

And just for completeness sake, let us implement a map equivalent for our lazy lists.

    (define (lazy-map f lst)
      (cond
       ((null? lst) '())
       (else (cons (f (lazy-car lst))
                   (delay (lazy-map f (lazy-cdr lst)))))))

I hope this introduction to lazy programming in Scheme has made you interested in the
topic. There are still many essential functions missing, like the folds, so I might
make a new post in the future discussing further functions and other interesting points
with this way of programming.

built with sh(1) and cat(1)