# Squirrel!

This tweet from Pepijn de Vos distracted me from thinking about arrows, so I thought I’d do a quick post about concatenative programming in Clojure. As befitting a ‘Squirrel!’ post, this will be light on explanation and long on code. I banged this out at the repl, so the only code is what’s in this post.

I did Forth programming 20 years ago and always thought it was awesome. Getting to meet Chuck Moore at Strangeloop this year was great.

So how can you do a Forth in Clojure? While I thought of a way to use the state monad to do it, it occurred to me after thinking a little more that concatenative programming should be based on a monoid, not a monad or comonad. I’ve got a post on monoids in the works after I get done with arrows. But for now, simple function composition is a monoid with `identity` being the zero value and `comp` being monoidial addition.

### Forth

In forth, each function is called a word and the ‘:’ is used to define new words composed of previously defined words. So

``````: new-word 2 8 + ;
``````

defines a new word that first puts a literal 2 and then a literal 8 on the stack, then calls `+` to pop both of those off and pushes their sum, 10, back onto the stack.

You do flow control like this:

``````: new-word 4 = if "four" else "not four" then ;
``````

This word replaces the number on the top of the stack with “four” if it’s equal to 4 or “not four” otherwise.

### Clojure Forth

Implementing something like this in Clojure is pretty simple. The first step is to realize that `comp` will work for building the definitions of words. Each word function needs to take a stack as a parameter and return a stack as a result.

The second step is to think about how to define ‘:’. Firstly, a colon is a reserved symbol in Clojure, so I just used `d` for ‘define’ instead. And if `d` is going to be defining words, it needs to be a macro. And it has to parse the given definition to build a function composition correctly, taking into account control flow expressions.

### Parsing

We’ll start with code to parse word definitions first. I just happen to have a monadic parser laying around. It’s not even worth putting into a seperate library:

``````(require '[monads.core :as m])

(def parser (m/state-t m/maybe))

(defmacro p-do [bindings expr]

(defn optional [p]
(m/plus [p (parser nil)]))

(declare one-or-more)

(defn none-or-more [p]
(optional (one-or-more p)))

(defn one-or-more [p]
(p-do
[a p
as (none-or-more p)]
(cons a as)))

(def next-item
(reify
(do-result [_ v]
(parser v))
(bind [mv f]
(fn [input]
((f (first input)) (rest input))))))

(defn item-test [pred]
(p-do
[c next-item
:when (pred c)]
c))

(defn is-item [c]
(item-test #(= c %)))
``````

Rather than explain it, I’m just going to show how it’s used. Here’s how you parse word definitions:

``````(defn comp-exprs [exprs]
(if (= 1 (count exprs))
(first exprs)
(cons 'comp (reverse exprs))))
``````

If multiple expressions are given, build an a call to `comp` out of them. But just return the expression if there’s only one given.

``````(def keywords #{nil 'if 'else 'then})

(def word
(item-test #(not (contains? keywords %))))

(def sentence
(p-do
[words (one-or-more word)]
(comp-exprs words)))
``````

A word is any symbol that’s not a reserved word, while a `sentence` is just a sequence of one or more words.

``````(declare expr)

(def if-else-then
(p-do
[_ (is-item 'if)
true-clause expr
_ (is-item 'else)
false-clause expr
_ (is-item 'then)]
`(fn [s#]
(if (first s#)
(~true-clause (rest s#))
(~false-clause (rest s#))))))
``````

An `if`/`else`/`then` expression gets parsed into an anonymous function.

``````(def if-then
(p-do
[_ (is-item 'if)
true-clause expr
_ (is-item 'then)]
`(fn [s#]
(if (first s#)
(~true-clause (rest s#))
(rest s#)))))
``````

And so does an `if`/`then` expression.

``````(def expr
(p-do
[exprs (one-or-more
(m/plus [if-else-then
if-then
sentence]))]
(comp-exprs exprs)))
``````

And an `expr` is either `if`/`else`/`then`, `if`/`then` or a `sentence`.

We also need a way to put literals on the stack:

``````(defn lit [v]
(fn [s]
(cons v s)))
``````

If you wanted to get fancy, you could extend each of the literal types to implement the IFn interface so they would take a stack and push that value onto it.

``````(defn apply-to-stack [n f]
(fn [s]
(cons (apply f (take n s))
(drop n s))))
``````

This will come in handy to define some primitive words to work with.

``````(defmacro d [name & body]
`(def ~name ~(first @(expr body))))
``````

And that’s all there is to the definition of `d`.

Now to define a couple of primitives:

``````(defn dup [s]
(cons (first s) s))

(def + (apply-to-stack 2 clojure.core/+))

(def = (apply-to-stack 2 clojure.core/=))

(d a (lit 1) (lit 4) (lit 6) (lit 2) + +)

(d four? (lit 4) = if (lit "four") else (lit "not four") then)

(four? '(4 5 6))
=> ("four" 5 6)

(four? '(5 6 7))
=> ("not four" 6 7)
``````

And that’s how you can do concatenative programming in Clojure.

### But wait …

In the post Pepijn mentioned in his tweet, he talks about continuations and dataflow. You don’t have to just do simple functional composition in the above. By using a different monoid, you could do all kinds of interesting things. And datafow maps directly onto arrows, which I’ll get back to next time.

19 October 2013