Skip to content
Abstract UI reconciliation library
Branch: master
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
clj Allow revaluate to be called with new args May 13, 2019
kt extract rt to separate maven project; add some kotlin api draft Dec 27, 2018
rt Allow revaluate to be called with new args May 13, 2019
LICENSE license Oct 6, 2017
README.md README Stateful thunks & Bottom-up reevaluation May 14, 2019

README.md

Incremental computations

Imagine this function:

(defn f [x y z]
  (+ x (* y z)))

What happens when we call it? Let’s add some logging:

(defn + [a b] (println "[calc]" a "+" b "=" (clojure.core/+ a b)) (clojure.core/+ a b))
(defn * [a b] (println "[calc]" a "*" b "=" (clojure.core/* a b)) (clojure.core/* a b))

If we call it, we get what we expect:

user=> (f 1 2 3)
[calc] 2 * 3 = 6
[calc] 1 + 6 = 7
7

If we call it again, all calculations will be redone:

user=> (f 1 2 3)
[calc] 2 * 3 = 6
[calc] 1 + 6 = 7
7

What if + and * were actually quite expensive to compute? In that case we would want to cache them, if we can. Ideally, if we call f repeatedly, nothing should happen at all:

user=> (f 1 2 3)
7

If we change arguments, we expect that only parts that absolutely need re-evaluation will be called:

user=> (f 4 2 3)
[calc] 4 + 6 = 10
10

Notice that multiplication wasn’t called because the arguments didn’t change.

Another elimination should kick in if multiplication arguments change but the result stays the same (notice no addition):

user=> (f 4 3 2)
[calc] 3 * 2 = 6
10

Adding incrementality

Noria does exactly that: given a deep call tree, it ensures that on subsequent runs only the absolutely necessary parts of computation will be re-calculated.

Let’s rewrite out function using Noria’s -< macro:

(require '[noria :as n])

(defn g [x y z]
  (n/-< + x @(n/-< * y z)))

We’ll need a helper function that will remember the last state of the evaluation in a var.

(def dag nil)

(defn evaluate [fun & args]
  (let [[dag' _ res] (n/evaluate dag fun args)]
    (alter-var-root #'dag (constantly dag'))
    res))

Note that there’s no magic or any global state in the Noria itself. Both dag and evaluate here are just convenience functions for us to remember previous state of calculations in the REPL. In your program, feel free to store that in an atom, component, database, global var or any other way that best suits you.

Another important note is that all Noria macros (-<, -<<, thunks, derefs etc) will only work in a context of n/evaluate. E.g., if you try to call g directly:

user=> (g 1 2 3)
Execution error (NullPointerException) at noria.NoriaRT/reconcile (NoriaRT.java:294).
null

Ok, let’s see if our caching works:

=> (evaluate g 1 2 3)
[calc] 2 * 3 = 6
[calc] 1 + 6 = 7
7
=> (evaluate g 1 2 3)
7
=> (evaluate g 4 2 3)
[calc] 4 + 6 = 10
10
=> (evaluate g 4 3 2)
[calc] 3 * 2 = 6
10
=> (evaluate g 4 3 2) 
10

As you can see multiplication is only called when y or z change, and addition is only called if x or the result of the multiplication is change.

How does it work?

The magical -< macro that you’ve seen above does two things:

  1. It calls your function and wraps its return value in a Thunk. Thunk is a reference, very much like Clojure’s atoms. All you need to know about it is that you can deref it to get to the value: (f 1 2 3) === @(n/-< f 1 2 3).
  2. It caches the returned Thunk by the call site. That means that on subsequent calculations, when calculation reaches the same place in a code via the same call path, Noria will have access to the previous Thunk value. That gives Noria a chance to compare old and new arguments and decide whether computation should be re-run.

We can inspect the state of the call graph after evaluation happen:

user=> (evaluate g 1 2 3)
[calc] 2 * 3 = 6
[calc] 1 + 6 = 7
7
user=> (for [entry (.-values (:noria/graph dag))
             :let [id    (.-key entry)
                   calc  (.-value entry)
                   sv    (.-stateAndValue calc)
                   state (.-state sv)
                   value (.-value sv)]]
         {:id id, :state state, :value value, :args (.-arg calc)})
({:id 0,  :state #:noria{:id 0, :arg (1 2 3), :value 7},  :value 7,  :args (1 2 3)}
 {:id 1,  :state #:noria{:id 1, :arg [2 3], :value 6},    :value 6,  :args [2 3]  }
 {:id 2,  :state #:noria{:id 2, :arg [1 6], :value 7},    :value 7,  :args [1 6]  })

Thunk with id 0 corresponds to the top-level f call. Thunk #1 is the multiplication, and thunk #2 is an addition. As you can see Noria carefully stored all the arguments, return values and identities of each call.

The -< actually lets you hook into the process of re-evaluation. First argument to -< doesn’t have to be a function, but can be any object implementing reconciler protocol (ThunkDef). Noria already has implementation for Clojure functions:

(extend-protocol ThunkDef
  clojure.lang.AFn
  (up-to-date? [this state old-args new-args] (= old-args new-args))
  (compute [this state args]
    [state (apply this args)])
  (changed? [this old-val new-val] (not= old-val new-val))
  (destroy! [this state]))

We can implement our own reconciler to better understand what’s going on:

(defrecord LoggingFnReconciler [op fun]
  noria.thunks/ThunkDef
  (up-to-date? [_ state old-args new-args]
    (let [res (= old-args new-args)]
      (println (format "(up-to-date? %s %s %s) => %s ;; thunk %s" op old-args new-args res (:noria/id state)))
      res))
  (compute [_ ^Object state ^Object args]
    (let [res (apply fun args)]
      (println (format "(compute %s %s) => %s ;; thunk %s" op args res (:noria/id state)))
      [state res]))
  (changed? [_ old-value new-value]
    (let [res (not= old-value new-value)]
      (println (format "(changed? %s %s %s) => %s" op old-value new-value res))
      res))
  (destroy! [_ state]
    (println (format "(destroy! %s) ;; thunk %s" op (:noria/id state)))))

(def r+ (LoggingFnReconciler. "+" clojure.core/+))
(def r* (LoggingFnReconciler. "*" clojure.core/*))

(defn h [x y z]
  (n/-< r+ x @(n/-< r* y z)))

Let’s try evaluating h and see what happens:

user=> (alter-var-root #'dag (constantly nil))
nil

user=> (evaluate h 1 2 3)
(compute * [2 3]) => 6 ;; thunk 1
(changed? * null 6) => true
(compute + [1 6]) => 7 ;; thunk 2
(changed? + null 7) => true
7

user=> (evaluate h 1 3 2)
(up-to-date? * [2 3] [3 2]) => false ;; thunk 1
(compute * [3 2]) => 6 ;; thunk 1
(changed? * 6 6) => false
(up-to-date? + [1 6] [1 6]) => true ;; thunk 2
7

user=> (evaluate h 4 3 2)
(up-to-date? * [3 2] [3 2]) => true ;; thunk 1
(up-to-date? + [1 6] [4 6]) => false ;; thunk 2
(compute + [4 6]) => 10 ;; thunk 2
(changed? + 7 10) => true
10

Notice how Noria carefully checks if function arguments has changed (to see if it needs to call .compute) and if result value has changed (to see if dependent calculations need to be triggered).

Let’s write one more function to see how Noria handles changes in a call graph (when different branches of the code gets evaluated based on conditions):

user=> (def r- (LoggingFnReconciler. "-" clojure.core/-))
#'user/r-

user=> (defn i [bool x y]
         (if bool
           (n/-< r- x y)
           (n/-< r- y x)))
#'user/i

user=> (alter-var-root #'dag (constantly nil))
nil

user=> (evaluate i true 1 2)
(compute - [1 2]) => -1 ;; thunk 1
(changed? - null -1) => true
-1

user=> (evaluate i false 1 2)
(compute - [2 1]) => 1 ;; thunk 2
(changed? - null 1) => true
(destroy! -) ;; thunk 1
1

You can see, even though we used the same reconciler for both branches, Noria actually distingueshed between two branches and created separate thunks for each. It also garbage collected first thunk after it was not reinstantiated on a second invocation (thus the destroy! call).

Stateful thunks

One use of Noria is just to cache expensive calculations. As long as your functions are pure and side-effect-free, default function reconciler would work just fine. But where’s fun in that?

Noria is actually pretty good at keeping stateful objects at the -< call sites and managing their lifecycle. If you have a stateful tree that needs updating over time, implement convenient callbacks like add/update/remove nodes in place and let Noria figure out when and how to call them and store the intermediate state.

Imagine following reconciler:

(defrecord DOMNode [tagName]
  noria.thunks/ThunkDef
  (up-to-date? [this state old-args new-args] (= old-args new-args))
  (changed? [this old-val new-val] (not= old-val new-val))
  (compute [_ ^Object state ^Object args]
    (if-some [node (:noria/value state)]
      ;; update
      (let [[attrs & children] args
            [old-attrs & old-children] (:noria/attrs state)]
        ;; update old-attrs -> attrs
        ;; update old-children -> children
        [state node])
      ;; create
      (let [node (js/document.createElement tagName)
            [attrs & children] args]
        (doseq [[k v] attrs]
          (.setAttribute node k v))
        (doseq [child children
                :let [childNode (cond
                                  (string? child) (js/Text. child)
                                  (instance? noria.thunks/ThunkDef child) @child)]]
          (.appendChild node childNode))
        [state node])))
  ;; remove
  (destroy! [_ state]
    (.remove (:noria/value state))))

Because Noria tracks where and when thunks appear/update/disappear, we can hook into reconciler lifecycle to do side effects we need to update the tree. The DOMNode reconciler above, combined with Noria’s -< macro, implement Virtual DOM paradigm. Yes, it’s that simple. This is how it can be used:

(def *clicks (atom 0))

(def div (DOMNode. "div"))
(def span (DOMNode. "span"))

(defn header [text]
  (-< span {"className" "header"} text))

(defn vdom-app []
  (-< div {"id" "app"}
    (header "Clicker app")
    (-< div {}
      (-< span {} "Clicks count" @*clicks))))

;; initial mount
(js/document.documentElement.appendChild (evaluate vdom-app))

;; redraw: only minimal necessary nodes update
(swap! *clicks inc)
(js/document.documentElement.appendChild (evaluate vdom-app))

Note: Noria is JVM-only at the moment, so code above would not compile under CLJS. It’s there to give you the idea of how Noria can be used.

Bottom-up reevaluation

In the example above you might’ve noticed that full reevaluation from the top might be unnecessary if it’s only *clicks that changed. In the ideal world, we would want to specifically update the latest span and touch nothing more. We would prefer to not even go through vdom-app body at all!

In Noria, this is possible through the :dirty-set option to n/evaluate. If you track your components’ data dependencies yourself, you can figure out which thunks to update and Noria will take care of the rest. This is a bit trickier to set up, but it has a potential to be much more efficient in the real world.

(def *dirty-set (atom #{}))

(def RefReconciler
  (reify noria.thunks/ThunkDef
    (up-to-date? [this state old-args new-args] (= @(first old-args) @(first new-args)))
    (changed? [this old-val new-val] (not= old-val new-val))
    (compute [_ ^Object state ^Object args]
      (let [[*ref] args
            id     (:noria/id state)]
        (println (format "(compute ref) => %s ;; thunk %s" @*ref id))
        (add-watch *ref id (fn [_ _ old new] (swap! *dirty-set conj id)))
        [state @*ref]))
    (destroy! [_ state]
      (let [[*ref] (:noria/args state)
            id     (:noria/id state)]
        (remove-watch *ref id)))))

(defn evaluate-dirty [fun]
  (let [dirty-set @*dirty-set
        _         (reset! *dirty-set #{})
        [dag' _ res] (n/evaluate dag fun [] :dirty-set dirty-set)]
    (alter-var-root #'dag (constantly dag'))
    res))

Now define a “dirty” test function that does not take any arguments and reads its state from atom instead:

(def rstr (LoggingFnReconciler. "str"
            (fn [& args]
              (apply str (map n/deref-or-value args)))))

(def *clicks (atom 0))

(defn j []
  (n/-< rstr "Clicked " (n/-< RefReconciler *clicks) " times"))

Let’s see how a thunks will behave when evaluation starts from the dirty set:

user=> (alter-var-root #'dag (constantly nil))
nil

user=> (evaluate-dirty j)
(compute ref) => 0 ;; thunk 1
(compute str ["Clicked " [Thunk#1] " times"]) => Clicked 0 times ;; thunk 2
(changed? str null Clicked 0 times) => true
"Clicked 0 times"

user=> (evaluate-dirty j)
"Clicked 0 times"

(swap! *clicks inc)
1

user=> @*dirty-set 
#{1}

user=> (evaluate-dirty j)
(compute ref) => 1 ;; thunk 1
(compute str ["Clicked " [Thunk#1] " times"]) => Clicked 1 times ;; thunk 2
(changed? str null Clicked 1 times) => true
"Clicked 1 times"

Note how compute starts directly from the deeps of RefReconciler and then bubbles up all the way until the return value. In this particular case it doesn’t really matter, since it triggers all calculations anyway. But if our calculation was a DOM tree for example, dirty set update might just update a single node deep down in the DOM tree and stop change propagation right there because DOM node reference does not change.

You can’t perform that action at this time.