In Chapter 14, you learned that your programs can be simpler and cleaner when built with clean, math-like functions. These functions always return the same result, which depends solely on the arguments passed into them. When you rely only on these types of functions, you are using the functional programming style.
However, when we used the functional programming style to create the Dice of Doom game in Chapter 15, a problem became evident: If your functions rely entirely on the arguments passed into them, the stuff that you need to pass into them often becomes huge.
In the Dice of Doom game, we pass around the game-tree variable, which holds all the possible future states of the game board. This is a truly massive structure, even on a measly 3-by-3 board! So while the game’s current design makes our code very simple and elegant, it doesn’t appear to scale well to larger game boards, which would have exponentially larger game trees. The only way we could conceivably maintain our elegant code while allowing more complex games on larger boards is to make our program smart enough not to look at every conceivable move right from the start of the game. Is this possible? Yes, it is possible, using a feature called lazy evaluation. In this chapter, we’ll employ lazy evaluation to create an improved version of Dice of Doom.
With lazy evaluation, we can still create our entire game tree in a single place in our code—at the beginning of our game. However, we use some clever tricks so that some branches of our game tree are hidden in clouds:
The branches of the game tree are still declared right from the start. However, we don’t bother doing all the actual calculations for the branches in clouds, as we would do when we create a “real” branch. This is the lazy part of lazy evaluation.
Instead, we wait to see if anyone “looks” at a cloudy branch. The moment this happens, POOF!, we create a real branch of our game tree at that spot:
This means that these branches in the game tree are created only if some part of the code happens to look at them. If the player never chooses a particular move in the game, and the AI never decides to contemplate it, our program will lazily avoid the calculations needed to figure out what the given branch actually looks like.
Some languages, such as Haskell and Clojure Lisp, contain support for lazy evaluation as part of the core of the language. In fact, Clojure encourages its use and clearly demonstrates how useful it is for functional programming. However, the ANSI Common Lisp standard does not contain any similar feature for such lazy evaluation. Fortunately, with Common Lisp’s powerful macro system, we can easily add this feature to the language ourselves!
The most basic commands for lazy evaluation we’re going to create are lazy and force. The lazy command will be a wrapper you can put around a piece of code, telling Lisp that you would like the code to be evaluated in a lazy way, like this:
> (lazy (+ 1 2))
#<FUNCTION ...>As you can see, the computer does not try to calculate the value of 1 plus 2. Instead, it simply returns a function. To get the actual result of the calculation, we must call our other basic lazy evaluation command on a lazy value:
> (force (lazy (+ 1 2)))
3The important thing is that the calculation was performed, but not when the lazy value was created—only when it was forced. To see that this is the case, let’s look at a more complex example:
>
(defun add (a b)(princ "I am adding now")(+ a b))ADD>
(defparameter *foo* (lazy (add 1 2)))*FOO*>
(force *foo*)I am adding now 3
Here, we’ve created our own add function, which, as a side effect, prints a message to the console showing when the addition is happening . Next, we lazily add two numbers with our function and store the result in the variable *foo* . So far, we know the addition hasn’t actually happened, since the message “I am adding now” has not yet appeared.
Then we force our variable . By forcing the value, the calculation is actually performed, and the result of 3 is returned. You can see that the addition took place when we forced the lazy value, since our message was also printed in the console .
Here is the code for a simple implementation of lazy:
(lambda ()
(unless ,forced
(setf ,value (progn ,@body))
(setf ,forced t))
,value))))
We implement lazy by declaring a macro . This macro will require two variables in the code it generates. We need to declare these as gensym names , as discussed in Chapter 16. Next, we begin generating the code that the macro will output (note the backquote at the beginning of this line).
At the top of the code generated by the macro is a declaration for two local variables, using the gensym names we created . The first variable tells us whether this lazy value has been forced yet . If it is nil, the value can hide in a cloud. If the variable is true, the value is no longer hidden in a cloud, because it has been forced.
Once the value has been calculated through a call to force, we store the resulting value in another variable, though initially this value isn’t used and is set to nil . When our lazy macro is called, we want it to return a function, which can be called at a later time to force our lazy value to return a result. Therefore, we declare a lambda function next .
Remember that any local variables declared outside this lambda function will be captured by the function as a closure. This means that the local variables above will persist between subsequent calls of the lambda function. Why does this matter? Well, once the cloud goes POOF!, we have completed all the work to calculate a value, and we don’t want to do it again when the lazy value is forced and checked again multiple times in the future. We can avoid this by remembering the value after the first force here between calls.
When our lazy value is forced (by calling the lambda function we created), the first question we must ask ourselves is whether it has been forced already or is still hidden behind the cloud . For a value that has not yet been forced, we go POOF! and perform the lazy calculation , and save it as our value. We also mark it as having been forced . Now the cloud has been destroyed.
Once the cloud is gone, we can simply return our calculated value . This may have been just calculated, or it may already exist from a previous call to force.
Unlike the (admittedly mind-bending) code for the lazy macro, the force function is super-simple. All it does is call the lambda function created by lazy:
(defun force (lazy-value) (funcall lazy-value))
We now have a fully functional set of primitive lazy evaluation commands. Many different types of sophisticated tools could be built on top of these simple lazy and force commands.
We will now employ our new commands to build a library for lazy lists, based loosely on their implementation in Clojure. (In Clojure, lazy lists are referred to as lazy sequences.)
Since the fundamental command for working with Lisp lists is the cons command, you shouldn’t be surprised that the first command we create for working with lazy lists is the lazy-cons command:
(defmacro lazy-cons (a d) `(lazy (cons ,a ,d)))
This macro emulates the behavior of cons, except that the result is wrapped in the lazy macro. To accompany lazy-cons, we’ll also create lazy-car and lazy-cdr commands:
(defun lazy-car (x) (car (force x))) (defun lazy-cdr (x) (cdr (force x)))
All these functions do is force the lazy value and then call car and cdr, respectively. Let’s try using these new commands:
(defparameter *foo* (lazy-cons 4 7))*FOO*(lazy-car *foo*)4(lazy-cdr *foo*)7
As you can see, we can use lazy-cons exactly as we would use cons . Then we can take apart a lazy cons in the same way we would take apart a cons .
So far, it looks like our lazy list functions aren’t any different from the standard cons, car, and cdr functions. However, we can actually use them to perform some pretty amazing feats. Consider, for instance, the following definition:
(defparameter *integers*
Here, we’ve used the lazy-cons command to declare something impossible: a variable that holds a list of all positive integers! We do this by creating a local function f , which we then call recursively to build an infinite chain of lazy-conses, using an ever-increasing number n . Once we’ve declared this seemingly impossible *integers* variable, we can use it just as you might expect:
>(lazy-car *integers*)1 >(lazy-car (lazy-cdr *integers*))2 >(lazy-car (lazy-cdr (lazy-cdr *integers*)))3
As long as we stick to using only our lazy- commands, we can pull whatever we want out of our infinite list of integers, forcing more and more numbers from *integers* on an as-needed basis.
Since not all lists are infinite (as is the list of positive integers), we’ll also need to have a concept of a lazy-nil to terminate a list. Similarly, we need a lazy-null function that we can use to check if we’ve reached the end of a list, just as the null function can be used to check for the end of a regular list.
(defun lazy-nil () (lazy nil)) (defun lazy-null (x) (not (force x)))
Now that we have all the basic building blocks for working with lazy lists, let’s create some useful functions for our library.
One obvious thing we would want to be able to do is convert a regular list into a lazy list. The make-lazy function allows us to do this:
(defun make-lazy (lst)
As the make-lazy function clearly shows, writing lazy list library functions is sort of like writing zen koans. The only way to understand them is to stare at them for a long time. The English language doesn’t have appropriate words for clearly explaining functions like make-lazy.
In broad terms, make-lazy uses recursion to travel across the list , and then wraps each cons in a call to the lazy macro . However, to get the full meaning of this function (and the other remaining functions in our lazy library), you’ll just have to try to think carefully about what lazy and force really mean, and meditate a bit over each function. Luckily, once our little lazy list library is complete, it will hide most of the strangeness of lazy evaluation.
Just as we wrote the make-lazy function to convert regular lists to lazy lists, we can create some functions to do the reverse—convert lazy lists into regular ones. The take and take-all functions allow us to do this.
The reason we want two different commands for going from lazy to regular lists is that, unlike regular lists, lazy lists can be infinite. Therefore, it is useful to have an additional command that lets us take just a specified number of items from the list. The take function accepts an extra argument n that indicates just how many values we want to take . If we just want all values, we can call the take-all function . Of course, this function cannot be used on infinite lists—taking all items from an infinite list would lead to an infinite loop.
Let’s try out our new lazy list conversion functions:
(take 10 *integers*)(1 2 3 4 5 6 7 8 9 10)(take 10 (make-lazy '(q w e r t y u i o p a s d f)))(Q W E R T Y U I O P) >(take-all (make-lazy '(q w e r t y u i o p a s d f)))
As you would expect, if we take the first 10 integers off the list of all positive integers, we just get the numbers 1 through 10 as a result . The take function can also be used on a finite list we’ve created by calling make-lazy . However, if a list is finite, we can use the simpler take-all function and just get a regular list of all items in the lazy list .
We also want to be able to map and search across lazy lists. Here are some functions to allow that:
(defun lazy-mapcar (fun lst)
(lazy (unless (lazy-null lst)
(cons (funcall fun (lazy-car lst))
(lazy-mapcar fun (lazy-cdr lst))))))
(defun lazy-mapcan (fun lst)
(labels ((f (lst-cur)
(if (lazy-null lst-cur)
(force (lazy-mapcan fun (lazy-cdr lst)))
(cons (lazy-car lst-cur) (lazy (f (lazy-cdr lst-cur)))))))
(lazy (unless (lazy-null lst)
(f (funcall fun (lazy-car lst)))))))
(defun lazy-find-if (fun lst)
(unless (lazy-null lst)
(let ((x (lazy-car lst)))
(if (funcall fun x)
x
(lazy-find-if fun (lazy-cdr lst))))))
(defun lazy-nth (n lst)
(if (zerop n)
(lazy-car lst)
(lazy-nth (1- n) (lazy-cdr lst))))These functions are analogous to the functions mapcar, mapcan, find-if, and nth. The only difference is that they accept and return lazy lists. This means that instead of using null, car, and cdr, they use the lazy versions of these functions (lazy-null, lazy-car, and lazy-cdr) that we just created.
Using these functions is pretty straightforward:
(take 10 (lazy-mapcar #'sqrt *integers*))(1 1.4142135 1.7320508 2 2.236068 2.4494898 2.6457512 2.828427 3 3.1622777)(take 10 (lazy-mapcan (lambda (x)(if (evenp x)(make-lazy (list x))(lazy-nil)))*integers*))(2 4 6 8 10 12 14 16 18 20)(lazy-find-if #'oddp (make-lazy '(2 4 6 7 8 10)))7(lazy-nth 4 (make-lazy '(a b c d e f g)))E
Calling lazy-mapcar to map the square root function across the positive integers gives us a lazy list of the square roots of the positive integers. The first 10 are shown . Next, we call lazy-mapcan and check if each positive integer is even. If it is, we return a lazy list of the numbers . If it isn’t, we return the lazy empty list . The result is that we’ve filtered out all the even numbers from our lazy list of integers. We can use lazy-find-if to find the first odd number in a lazy list . In this case, the number was 7. Finally, we can use lazy-nth to pick a number out of a specific location in a lazy list .
We have now written an entire, if rather simple, lazy list library. Place all the functions we’ve written so far in this chapter in a file named lazy.lisp (or simply download that file from http://landoflisp.com/).
Now, you’re going to see that lazy lists allow us to greatly boost the power of our Dice of Doom game engine!