Build An Arrow

Last time, I discussed the arrow abstraction in an abstract way. Let’s get down to brass tacks and build an actual arrow for core.logic.

Real code

In the course of working at ViaSat (which is a great place to work. If you like what I write, you’d love to work here. (‘here’ being relative since we’re a totally remote team)), we had some problems that were ideally suited for an arrow based solution. So we wrote an arrows library and we’re releasing now. The code is here.

Start with the monad

I said earlier that core.logic uses a sophisticated monad to do backtracking in the search tree and also interleave the results from the various branches. And in earlier posts, I showed that it was possible to replace that monad with others to get various behaviors. So the first thing we’re going to do is use one of the simplest monads as our logic monad.

(def logic-m vector)

Now to put a value into our logic monad, we just call logic-m with that value and we get a monadic value back.

(logic-m s)
=> [s]

And in core.logic, the values inside our logic monad will always be substitutions.

Parallel branches

To recap, the minimum requirement an arrows must satisfy is to provide three functions; arr, seq and nth. The arrows library defines a protocol for this.

(defprotocol Arrow
  (arrow-arr [_ f])
  (arrow-seq [p ps])
  (arrow-nth [p n]))

The arrow-nth function lets you build parallel arrows, but each branch would actually be executed sequentially. If there’s a more effecient parallel implementation that your arrow can express, there’s an additional protocol you can satisfy.

(defprotocol ArrowPar
  (arrow-par [p ps]))

From monad to arrow

So how do we use our logic monad to build our arrow? First, some boilerplate:

(deftype logic-arr [fun meta-data]
  clojure.lang.IDeref
  (deref [_]
    [fun meta-data])

  clojure.lang.IMeta
  (meta [_]
    meta-data)

  clojure.lang.IFn
  (invoke [_ x]
    (fun x))

    ...

  )

All this does is define a type for our logic arrow. Remember that an arrow value is just a function with some associated meta-data. Now it would be possible to just use plain Clojure functions for this. But we’re going to need to dispatch on the type of the arrow value, so a deftype is called for. And for the constructor, we just give it a function and a hash-map of meta data. So we need those three protocols implemented so we can do something with it.

Now we add the arrow protocol definitions. First up, arrow-arr:

  a/Arrow
  (arrow-arr [_ f]
    (logic-arr. (comp logic-m f)
                {}))

Remember that the arr function takes a function of one argument and lifts it into the arrow (uses it to build an arrow value in a specific arrow). For the logic-arrow, this just means taking the output of f and wrapping it in the logic monad. This is done by composing f with logic-m. This function is just implemented for completeness sake, we don’t actually use it in core.logic.

Sequential composition

Next up is sequential composition of arrow values. Since they’re just functions, we want to link them together so that the output of each function is fed into the input of the next one. But with the monadic effect being taken into account. To do this, realize that each of the arrow values are actually monadic functions in the logic monad. That is, they are functions that take a single value and produce a monadic value. Linking monadic functions together is done with bind. As a reminder, say we have two monadic functions, f and g that we want to link together. You do that like this:

(def f-g (fn [x]
            (m/bind (f x) g))

Then if you wanted to add h at the end of the chain:

(def f-g-h (fn [x]
              (m/bind (f-g x) h)))

The basic form for each link in the chain of functions is the same, so there’s a handy function in monads.core to do this. And we’ll use it to implement sequential composition of our logic arrow.

  (arrow-seq [p ps]
    (logic-arr. (m/chain (cons p ps))
                {}))

This takes a list of arrow values and produces an arrow value that has the effect of executing each given arrow value in sequence. The input to the composed arrow value is passed to the first arrow value, with the resulting output passed to the next one and so on.

The real magic of arrows lies in how the meta data is used in composing arrow values. But I want to get the basic functionality out of the way before tackling that subject, so I’ll leave the meta data empty for now.

Parallel composition

For our logic arrow, we’re going to skip the arrow-nth protocol and only implement arrow-par because we’re only interested in implementing truly parallel branches.

To properly implement the arrow-par function, you have to remember that it must accept a number of arrow values and produce an arrow value that executes them in parallel. Furthermore, the composed arrow value must accept as input a vector of values that is of the same length as the number of arrow values given originally.

Again, remember that an arrow value is a monadic function. And since our logic monad happens to implement the MonadZero protocol, that means we can use monadic plus to combine monadic values. So we pass each value in the input list to it’s corresponding arrow value (monadic function) which gives us a list of monadic values. And then we pass that list to plus and we’re done.

  (arrow-par [p ps]
    (logic-arr. (fn [ss]
                  (m/plus (map #(%1 %2) ps ss)))
                {}))

And that’s the basic function portion of our arrow. Next time, the fun begins.

Jim Duey 16 October 2013
blog comments powered by Disqus