Lazy Realization

January 2, 2016

Support for using realized? with lazy sequences has landed in ClojureScript.

What kind of new fun can we have with this capability?




Fun

First, let's say we have a lazy sequence. Here's one representing the factors for each natural number:

(def factors 
  (map (fn [n]
         (filter (fn [x] 
                   (zero? (rem n x)))
           (range 1 (inc n))))
    (rest (range))))

This sequence looks like 

((1) (1 2) (1 3) (1 2 4) (1 5) ...)

Even though the def defines an infinite sequence, defining it at the REPL simply results in the var #'factors being returned, but with none of the factors yet being calculated.

You can verify this: (realized? factors) yields false.

If you evaluate (first factors), you will get (1). After doing this, (realized? factors) will yield true which means that the first item has been realized. And you can confirm that only the first item has been realized: (realized? (rest factors)) yields false.

Now, let's say we do something like, (take 4 factors), causing the next 3 items of this infinite sequence to be calculated and cached. A function like the following (due to Alan Malloy) can be used to calculate how much of the infinite sequence has been realized:

(defn realized-length [xs] 
  (loop [n 0 xs xs] 
    (if (realized? xs) 
      (recur (inc n) (rest xs)) 
      n)))

With this, (realized-length factors) produces the desired result of 4.

Implementation

Adding support for realized? for lazy sequences was relatively easy in ClojureScript. At its core, realized? simply needs its argument to be of a type that satisfies cljs.core/IPending. This involves providing an implementation for its -realized? method.

In ClojureScript, lazy sequences are implemented by a LazySeq deftype with a fn field which is used to realize the value. After this fn has been used, it is set to nil (it is marked as ^:mutable), and, via this side effect, we can deduce that the value has been realized.

This strategy is in fact analogous to the one used in Delay—the type that underlies the delay function—and its existing support for realized? in ClojureScript.

The implementation landed for realized? for LazySeq simply mimics the approach used for Delay, checking to see if the fn mutable field has been set to nil in the inline IPending implementation in the LazySeq deftype:

IPending
(-realized? [x]
  (not fn))

That's all there is to it!

Tags: ClojureScript