Sieve of Eratosthenes

Using channels to generate a sequence of prime numbers is an example often seen in presentations about CSP and channels. Below is an example in Clojure(Script) that filters out non-prime values using a naive implementation. Continue reading for a vastly improved version:

(defn chan-of-primes-naive []
  (let [ints (chan)
        primes (chan)]
    (go-loop [n 2]
      (>! ints n)
      (recur (inc n)))
    (go-loop [cur-ch ints]
      (let [prime (<! cur-ch)
            new-ch (chan 1 (filter #(not= 0 (mod % prime))))]
        (>! primes prime)
        (pipe cur-ch new-ch)
        (recur new-ch)))
    primes))

The previous code works, but notice that it doesn't take advantage of the composability of transducers. To do that, within our main go-loop we can create a new channel of integers that begins with the previous prime number and has a transducer that combines the new prime filter with the previous filter (using the standard comp function), like this:

(defn chan-of-ints [xform start-n]
  (let [ints (chan 1 xform)]
    (go-loop [n start-n]
      (>! ints n)
      (recur (inc n)))
    ints))

(defn chan-of-primes []
  (let [primes (chan)]
    (go-loop [cur-xf (map identity)
              cur-ch (chan-of-ints cur-xf 2)]
      (let [prime  (<! cur-ch)
            new-xf (comp cur-xf (filter #(not= 0 (mod % prime))))
            new-ch (chan-of-ints new-xf prime)]
        (>! primes prime)
        (recur new-xf new-ch)))
    primes))

Notice how this version, which recursively composes a new transducer, also avoids the need to pipe values from the previous channel to the new channel. To see the difference this makes in performance you can do some simple timings from a REPL using code like the following:

(defn consume [n ch]
  (dorun (repeatedly n #(<!! ch))))

(time (consume 2000 (chan-of-primes-naive)))
(time (consume 2000 (chan-of-primes)))