Implementing SICP-style streams in Clojure

Many people approaching a new language, particularly a new Lisp, often explore the new language by attempting to implement examples and exercises from canonical Lisp texts. Paul Graham’s On Lisp, Peter Siebel’s Practical Common Lisp, and Abelson and Sussman’s SICP are ususal suspects. I’m not going to attempt any large-scale “translation” of SICP into Clojure, but I do think the section 3.5, on streams, sheds a lot of light on the lazy sequences in the new language.

A stream is a sequence of elements that may be evaluated and used one at a time, rather than evaluating the entire sequence. SICP formulates them as delayed lists, but in Clojure anything that can implement first and rest may be abstracted as a sequence. And whereas in MIT Scheme you need macros, or your own evaluator with special forms, to achieve this delaying behavior, Clojure gives it to you by default.

Here’s a great example from SICP, an implementation of the Sieve of Eratosthenes, an algorithm for finding prime numbers in order:

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

(stream-ref primes 50)
233

Here is (one way) to do it in Clojure:

(def intstream (iterate inc 2))

(defn sieve [stream]
  (lazy-cons (first stream)
             (sieve (filter #(not (zero? (rem % (first stream))))
                    (rest stream)))))

(def primes (sieve intstream)
(nth primes 50)
233

The lovely thing about streams is that you can describe them very simply: an expression that evaluates to the first item and an expression that generates the next item is all you need. The Clojure expression (iterate inc 2) produces such a stream, with 2 as the first expression and a function that applies the increment function to produce the rest. We don’t have to specify a mechanism for generating (or caching) expressions as we need them. It’s taken care of under the hood. So our code has the simplicity that comes from using straight-forward sequences. This is one of the hallmarks of beautiful code, and beautiful functional code in particular: when you read the code you see clearly how the process is solving the problem. There’s very little noise in the way of the signal.

My sieve function is very naive. I’m writing it with virtually no knowledge of how Clojure executes it in Java. You begin to get an idea when you macroexpand the lazy-cons expression inside sieve:

(new clojure.lang.LazyCons
  (clojure.core/fn ([] (first stream))
                   ([G__1131] (sieve (filter
                                       (fn* [p1__1130]
                                            (not (zero? (rem p1__1130 (first stream)))))
                                       (rest stream))))))

This suggests that there’s a LazyCons class defined in clojure.lang with a one-argument constructor. Sure enough:

package clojure.lang;
final public class LazyCons extends ASeq{
final private static ISeq sentinel = new Cons(null, null);
IFn f;
Object _first;
ISeq _rest;
public LazyCons(IFn f){
    this.f = f;
    this._first = sentinel;
    this._rest = sentinel;
}
...

I’m going to stop at this point in the rabbit hole. This gives you an idea of how Clojure becomes java. I’m hoping to post more about streams and sequences as well as more about how Clojure ticks. It’s time for me to dust off my very dusty java skills.