How to Be Lazy

Before we get to laziness, we first need to delve into recursion as an approach to enumerating sequences of values.

Functional programs make great use of recursive definitions. A recursive definition consists of two parts:

• A basis, which explicitly enumerates some members of the sequence
• An induction, which provides rules for combining members of the sequence to produce additional members

Our challenge in this section is converting a recursive definition into working code. You might do this in several ways:

• A simple recursion, using a function that calls itself in some way to implement the induction step.

• A tail recursion, using a function calling itself only at the tail end of its execution. Tail recursion enables an important optimization.

• A lazy sequence that eliminates actual recursion and calculates a value later, when it’s needed.

Choosing the right approach is important. Implementing a recursive definition poorly can lead to code that performs terribly, consumes all available stack and fails, consumes all available heap and fails, or does all of these. In Clojure, being lazy is often the right approach.

We’ll explore all of these approaches by applying them to the Fibonacci numbers. Named for the Italian mathematician Leonardo (Fibonacci) of Pisa (c.1170--c.1250), the Fibonacci numbers were actually known to Indian mathematicians as far back as 200 BC. The Fibonacci numbers have many interesting properties, and they crop up again and again in algorithms, data structures, and even biology.^[24] The Fibonaccis have a very simple recursive definition:

• Basis: F₀, the zeroth Fibonacci number, is zero. F₁, the first Fibonacci number, is one.

• Induction: For n > 1, F_n equals F_n-1 + F_n-2.

Using this definition, the first 10 Fibonacci numbers are as follows:

Let’s begin by implementing the Fibonaccis using a simple recursion. The following Clojure function will return the nth Fibonacci number:

Lines 4 and 5 define the basis, and line 6 defines the induction. The implementation is recursive because stack-consuming-fibo calls itself on lines 6 and 7.

Test that stack-consuming-fibo works correctly for small values of n:

Good so far, but there’s a problem calculating larger Fibonacci numbers such as F_1000000:

Because of the recursion, each call to stack-consuming-fibo for n > 1 begets two more calls to stack-consuming-fibo. At the JVM level, these calls are translated into method calls, each of which allocates a data structure called a stack frame.^[25]

The stack-consuming-fibo creates a depth of stack frames proportional to n, which quickly exhausts the JVM stack and causes the StackOverflowError shown earlier. (It also creates a total number of stack frames that’s exponential in n, so its performance is terrible even when the stack does not overflow.)

Clojure function calls are designated as stack-consuming because they allocate stack frames that use up stack space. In Clojure, you should almost always avoid stack-consuming recursion as shown in stack-consuming-fibo.

Tail Recursion

Functional programs can solve the stack-usage problem with tail recursion. A tail-recursive function is still defined recursively, but the recursion must come at the tail, that is, at an expression that’s a return value of the function. Languages can then perform tail-call optimization (TCO), converting tail recursions into iterations that don’t consume the stack.

The stack-consuming-fibo definition of Fibonacci is not tail recursive, because it calls add (+) after both calls to stack-consuming-fibo. To make fibo tail recursive, you must create a function whose arguments carry enough information to move the induction forward, without any extra “after” work (like an addition) that would push the recursion out of the tail position. For fibo, such a function needs to know two Fibonacci numbers, plus an ordinal n that can count down to zero as new Fibonaccis are calculated. You can write tail-fibo as follows:

Line 2 introduces the letfn macro:

letfn is like let but is dedicated to creating local functions. Each function declared in a letfn can call itself or any other function in the same letfn block. Line 3 declares that fib has three arguments: the current Fibonacci, the next Fibonacci, and the number n of steps remaining.

Line 5 returns current when there are no steps remaining, and line 6 continues the calculation, decrementing the remaining steps by one. Finally, line 7 kicks off the recursion with the basis values 0 and 1, plus the ordinal n of the Fibonacci we’re looking for.

tail-fibo works for small values of n:

But although it’s tail recursive, it still fails for large n:

The problem here is the JVM. While functional languages such as Scheme or Haskell perform TCO, the JVM doesn’t perform this optimization. The absence of TCO is unfortunate but not a showstopper for functional programs.

Clojure provides several pragmatic workarounds: explicit self-recursion with recur, lazy sequences, and explicit mutual recursion with trampoline. We’ll discuss the first two here and defer the discussion of trampoline, which is a more advanced feature, until later in the chapter.

Self-recursion with recur

One special (and common) case of recursion that can be optimized away on the JVM is self-recursion. Fortunately, the tail-fibo is an example: it calls itself directly, not through some series of intermediate functions.

In Clojure, you can convert a function that tail-calls itself into an explicit self-recursion with recur. Using this approach, convert tail-fibo into recur-fibo:

The critical difference between tail-fibo and recur-fibo is on line 7, where recur replaces the call to fib.

The recur-fibo won’t consume stack as it calculates Fibonacci numbers and can calculate F_n for large n if you have the patience:

The complete value of F_1000000 is included in the sample code at output/f-1000000.

The recur-fibo calculates one Fibonacci number. But what if you want several? Calling recur-fibo multiple times would be wasteful, since none of the work from any call to recur-fibo is cached for the next call. But how many values should be cached? Which ones? These choices should be made by the caller of the function, not the implementer.

Ideally, you’d define sequences with an API that makes no reference to the specific range that a particular client cares about and then let clients pull the range they want with take and drop. This is exactly what lazy sequences provide.

Lazy Sequences

Lazy sequences are constructed using the macro lazy-seq:

A lazy-seq invokes its body only when needed, that is, when seq is called directly or indirectly. lazy-seq then caches the result for subsequent calls. You can use lazy-seq to define a lazy Fibonacci series as follows:

On line 3, the zero-argument body returns the concatenation of the basis values [0 1] and then calls the two-argument body to calculate the rest of the values. On line 5, the two-argument body calculates the next value n in the series, and on line 7 it conses n onto the rest of the values.

The key is line 6, which makes its body lazy. Without this, the recursive call to lazy-seq-fibo on line 7 would happen immediately, and lazy-seq-fibo would recurse until it blew the stack. This illustrates the general pattern: wrap the recursive part of a function body with lazy-seq to replace recursion with laziness.

lazy-seq-fibo works for small values:

lazy-seq-fibo also works for large values. Use (rem ... 1000) to print only the last three digits of the one millionth Fibonacci number:

The lazy-seq-fibo approach follows guideline #3, using laziness to implement an infinite sequence. But as is often the case, you don’t need to explicitly call lazy-seq yourself. By guideline #5, you can reuse existing sequence library functions that return lazy sequences. Consider this use of iterate:

The iterate begins with the first pair of Fibonacci numbers: [0 1]. Working by pairs, it then calculates the Fibonaccis by carrying along just enough information (two values) to calculate the next value.

The Fibonaccis are simply the first value of each pair. They can be extracted by calling map first over the entire sequence, leading to the following definition of fibo suggested by Christophe Grand:

fibo returns a lazy sequence because it builds on map and iterate, which also return lazy sequences. fibo is also simple. fibo is the shortest implementation we’ve seen so far. But if you’re accustomed to writing imperative, looping code, correctly choosing fibo over other approaches may not seem simple at all! Learning to think recursively, lazily, and within the JVM’s limitations on recursion—all at the same time—can be intimidating. Let the guidelines help you. The Fibonacci numbers are infinite: guideline #3 correctly predicts that the right approach in Clojure will be a lazy sequence, and guideline #5 lets the existing sequence functions do most of the work.

Lazy definitions consume some stack and heap. But they don’t consume resources proportional to the size of an entire (possibly infinite!) sequence. Instead, you choose how many resources to consume when you traverse the sequence. If you want the one millionth Fibonacci number, you can get it from fibo, without having to consume stack or heap space for all the previous values.

There’s no such thing as a free lunch. But with lazy sequences, you can have an infinite menu and pay only for the menu items you’re eating at a given moment. When writing Clojure programs, you should prefer lazy sequences over loop/recur for any sequence that varies in size and for any large sequence.

Coming to Realization

Lazy sequences consume significant resources only as they are realized, that is, when a portion of the sequence is actually instantiated in memory. Clojure works hard to be lazy and avoid realizing sequences until it’s absolutely necessary. For example, take returns a lazy sequence and does no realization at all. You can see this by creating a var to hold, say, the first billion Fibonacci numbers:

The creation of lots-o-fibs returns almost immediately, because it does almost nothing. If you ever call a function that needs to actually use some values in lots-o-fibs, Clojure will calculate them. Even then, it’ll do only what’s necessary. For example, the following will return the 100th Fibonacci number from lots-o-fibs, without calculating the millions of other numbers that lots-o-fibs promises to provide:

Most sequence functions return lazy sequences. If you aren’t sure whether a function returns a lazy sequence, the function’s documentation string typically will tell you the answer:

The REPL, however, is not lazy. The printer used by the REPL will, by default, print the entirety of a collection. That’s why we stuffed the first billion Fibonaccis into lots-o-fibs, instead of evaluating them at the REPL. Don’t enter the following at the REPL:

If you enter the previous expression, the printer will attempt to print a billion Fibonacci numbers, realizing the entire collection as it goes. You’ll probably get bored and exit the REPL before Clojure runs out of memory.

As a convenience for working with lazy sequences, you can configure how many items the printer will print by setting the value of *print-length*:

For collections with more than 10 items, the printer will now print only the first 10 followed by an ellipsis. So, you can safely print a billion fibos:

Or even all the fibos:

Lazy sequences are wonderful. They do only what’s needed, and for the most part, you don’t have to worry about them. If you ever want to force a sequence to be fully realized, you can use either doall or dorun, discussed in ​Lazy and Infinite Sequences​.

Losing Your Head

There’s one last thing to consider when working with lazy sequences. Lazy sequences let you define a large (possibly infinite) sequence and then work with a small part of that sequence in memory at a given moment. This clever ploy will fail if you (or some API) unintentionally hold a reference to the part of the sequence you no longer care about.

The most common way this can happen is if you accidentally hold the head (first item) of a sequence. In the examples in previous sections, each variant of the Fibonacci numbers was defined as a function returning a sequence, not the sequence itself.

You could define the sequence directly as a top-level var:

This definition uses lazy-cat, which is like concat except that the arguments are evaluated only when needed. This is a very pretty definition, in that it defines the recursion by mapping a sum over (each element of the Fibonaccis) and (each element of the rest of the Fibonaccis).

head-fibo works great for small Fibonacci numbers:

but not so well for huge ones:

The problem is that the top-level var head-fibo holds the head of the collection. This prevents the garbage collector from reclaiming elements of the sequence after you’ve moved past those elements. So, any part of the Fibonacci sequence that you actually use gets cached for the life of the value referenced by head-fibo, which is likely to be the life of the program.

Unless you want to cache a sequence as you traverse it, you must be careful not to keep a reference to the head of the sequence. As the head-fibo example demonstrates, you should normally expose lazy sequences as a function that returns the sequence, not as a var that contains the sequence. If a caller of your function wants an explicit cache, the caller can always create its own var. With lazy sequences, losing your head is often a good idea.