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.

Monoids, not monads

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])
(require '[monads.macors :as mm])

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

(defmacro p-do [bindings expr]
  `(monads.macros/do parser ~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
    m/Monad
    (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.

Jim Duey 19 October 2013
blog comments powered by Disqus