A Lazy Fibonacci Adventure in Clojure

Tracing Fibonacci Steps with Macros

Introduction

The Fibonacci sequence—0, 1, 1, 2, 3, 5, 8, ...—is a staple in computer science, famously explored in Structure and Interpretation of Computer Programs (SICP) to illustrate computational processes (Section 1.2). In Clojure, a modern Lisp dialect, we implemented it lazily with lazy-cat. But its self-referential nature—building itself from itself—felt mysterious. How does (map + lazy-fibb (rest lazy-fibb)) generate the sequence? To answer this, we crafted a macro, trace-map-add, to reveal each addition step-by-step, connecting Clojure’s laziness to SICP’s process insights.

The Lazy Fibonacci

We began with a compact definition:

Clojure code:

(def lazy-fibb
  (lazy-cat [0 1]
            (map + lazy-fibb (rest lazy-fibb))))

Running (take 20 lazy-fibb) yields (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181). The idea:

• [0 1] seeds the sequence.

• (rest lazy-fibb) shifts it to (1 1 2 3 ...).

• map + pairs lazy-fibb with (rest lazy-fibb)—e.g., 0+1=1, 1+1=2, 1+2=3—and lazy-cat stitches it together.

• The result is a lazy sequence, computed on demand.

Elegant, but opaque. How does lazy-fibb use itself before it’s fully formed?

Peeling Back the Layers

Clojure’s lazy-cat embodies laziness—elements emerge only when requested, hinting at SICP’s stream-like processes (Chapter 3). Unlike a recursive (defn fib [n] (if (<= n 2) n (+ (fib (- n 1)) (fib (- n 2))))), which grows exponentially, this should be linear. Yet, (take 5 lazy-fibb) giving (0 1 1 2 3) didn’t explain how. To see inside, we wrote a tracing macro:

Clojure macro and code:

(defmacro trace-map-add [seq1 seq2]
  `(map (fn [[x# idx#] [y# _#]]
          (let [result# (+ x# y#)]
            (println (str "Step " idx# ": Adding " x# " from " '~seq1 "[" idx# "] and " y# " from " '~seq2 "[" idx# "] to get " result#))
            result#))
        (map vector ~seq1 (range))
        (map vector ~seq2 (range))))

(def lazy-fibb
  (lazy-cat [0 1]
            (trace-map-add lazy-fibb (rest lazy-fibb))))

Now, (take 20 lazy-fibb) reveals:

(take 20 lazy-fibb)
Step 0: Adding 0 from lazy-fibb[0] and 1 from (rest lazy-fibb)[0] to get 1

Step 1: Adding 1 from lazy-fibb[1] and 1 from (rest lazy-fibb)[1] to get 2

Step 2: Adding 1 from lazy-fibb[2] and 2 from (rest lazy-fibb)[2] to get 3

Step 3: Adding 2 from lazy-fibb[3] and 3 from (rest lazy-fibb)[3] to get 5

Step 4: Adding 3 from lazy-fibb[4] and 5 from (rest lazy-fibb)[4] to get 8

Step 5: Adding 5 from lazy-fibb[5] and 8 from (rest lazy-fibb)[5] to get 13

Step 6: Adding 8 from lazy-fibb[6] and 13 from (rest lazy-fibb)[6] to get 21

Step 7: Adding 13 from lazy-fibb[7] and 21 from (rest lazy-fibb)[7] to get 34

Step 8: Adding 21 from lazy-fibb[8] and 34 from (rest lazy-fibb)[8] to get 55

Step 9: Adding 34 from lazy-fibb[9] and 55 from (rest lazy-fibb)[9] to get 89

Step 10: Adding 55 from lazy-fibb[10] and 89 from (rest lazy-fibb)[10] to get 144

Step 11: Adding 89 from lazy-fibb[11] and 144 from (rest lazy-fibb)[11] to get 233

Step 12: Adding 144 from lazy-fibb[12] and 233 from (rest lazy-fibb)[12] to get 377

Step 13: Adding 233 from lazy-fibb[13] and 377 from (rest lazy-fibb)[13] to get 610

Step 14: Adding 377 from lazy-fibb[14] and 610 from (rest lazy-fibb)[14] to get 987

Step 15: Adding 610 from lazy-fibb[15] and 987 from (rest lazy-fibb)[15] to get 1597

Step 16: Adding 987 from lazy-fibb[16] and 1597 from (rest lazy-fibb)[16] to get 2584

Step 17: Adding 1597 from lazy-fibb[17] and 2584 from (rest lazy-fibb)[17] to get 4181

Result: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181).

What We Discovered

1. Lazy Pairing:

   • lazy-fibb: (0 1 1 2 3 5 8 13 21...).

   • (rest lazy-fibb): (1 1 2 3 5 8 13 21...).

   • map + aligns them: 0+1, 1+1, 1+2, ...—a sliding window over the sequence as it grows.

2. Sequence, Not Vector:

   • Despite [0 1], lazy-cat produces a LazySeq, not a vector. Laziness enables infinity, aligning with SICP’s process focus over static structures.

3. Macro Clarity:

   • By tagging elements with (range), trace-map-add shows lazy-fibb[n] + (rest lazy-fibb)[n], mirroring Fibonacci’s f(n) = f(n-1) + f(n-2) after [0 1].

4. Process Efficiency:

   • This isn’t tree recursion (O(2^n)) or stateful iteration (O(n)). It’s a lazy, linear process—O(n) for nth, leveraging the sequence’s own growth.

Conclusion

The trace-map-add macro turned lazy-fibb’s black box into a transparent story: from (0 1), it lazily appends sums of its own elements, offset by one. Questions—why not a vector? how does it self-build?—dissolved with each traced step. Rooted in SICP’s Section 1.2, this experiment showcased Clojure’s lazy evaluation as a fresh take on classic problems. Next, we might explore SICP’s logarithmic Fibonacci (Exercise 1.19) with the same lens. For now, we’ve decoded a lazy dance, one addition at a time.