Grinding Some Coffee

After having a look at Arne's writeup of what he calls "Coffee Grinders", I thought I'd add a few small comments.

The people saying it's a state machine aren't wrong, of course, because — strictly speaking — it is a kind of state machine, but this doesn't really tell us very much about the pattern because almost everything is a state machine.

If I were trying to explain this idea, I might start from fold (akareduce). As a reminder, the simplest recursive definition of the reducefunction is:

(defn our-reduce [f init xs]

  (if (seq xs) 

    (our-reduce f (f init (first xs)) (rest xs))

    init))

This allows us to do the canonical example:

(our-reduce + 0 [1 2 3])

There's a common pattern when writing more complex reductions where one reduces over a sequence of functions while passing state in the accumulator:

(our-reduce (fn [a f] (f a))

  {:counter 0}

  [#(update % :counter inc)

   #(update % :counter inc)])

This ability to use this sort of pattern is one of the reasons that reduceis universal over the class of recursive functions on sequences. This makes it easy, as above, to replicate Arne's first Coffee Grinder example which is as follows:

(defn run [{:keys [queue] :as ctx}]

  (if-let [[step & next-queue] (seq queue)]

    (recur (step (assoc ctx :queue next-queue)))

    ctx))

(run {:counter 0

      :queue [#(update % :counter inc)

              #(update % :counter inc)]})

However, we cannot use reduce to perform his second example:

(run {:counter 0

      :queue [(fn [ctx]

                (update ctx

                        :queue

                        concat

                        (for [i (range 10)]

                          #(update % :counter + i))))]})

This is because we cannot mutate the sequence over which we are reducing from within the reducing function. For that, we would need a different version of reduce that looks for the sequence in the accumulator and thus can update it at any step. Note that the definition for this is very similar to the one above for our-reduce:

(defn grind [state]

  (if (seq (:queue state))

    (grind ((first (:queue state)) (update state :queue rest)))

    state))

Which allows us to run Arne's other examples because it's just his run function by another name:

(grind {:counter 0

        :queue [(fn [ctx]

                  (update ctx

                          :queue

                          concat

                          (for [i (range 10)]

                            #(update % :counter + i))))]})

(Note that in Clojure one would always, as Arne has done, use recur rather than named recursion because Clojure doesn't have tail call optimization. I just happen to prefer the way named recursion reads in examples.)

All of this is to say that the Coffee Grinder pattern is really a particular use of the general pattern of recursive functions, in this case operating on a self-modifiable queue. This sort of things pops up all the time in many programming situations and should definitely be a part of your toolkit!

As an additional historical aside, if we were to build a system using several of these recursive state processors and regard the operations that arrive in each queue as "messages", we would arrive at something very close to Smalltalk-style object orientation. If those queues were each being serviced on their own thread, we would converge on something very like the Actor model. All of these things were discovered around the same time in the early 1970s by Carl Hewitt, Alan Kay, and Sussman/Steele. 😊

Libraries

{:deps

 {org.clojure/clojure {:mvn/version "1.10.0"}

  org.clojure/tools.deps.alpha

  {:git/url "https://github.com/clojure/tools.deps.alpha.git"

   :sha "f6c080bd0049211021ea59e516d1785b08302515"}

  compliment {:mvn/version "0.3.9"}}}