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)