This is the fourth Chapter of a series of posts about porting The Little Schemer to Clojure. You may wish to read the intro.

You’ll notice that in the first three chapters, we introduced lists [Ch1], then we pulled things out of lists [Ch2], and then we built lists [Ch3]. The bigger principle of the book is to be able to operate on data structures with a minimal set of primitives using the power of recursion and lambdas.

Now we’re driving at the meta-circular interpreter with these principles. We also want to be able to do mathematical operations, and yet still keep a minimal number of primitives. Interestingly enough, we’ll just use equals, add1 and sub1 and build up to multiplication, division and exponents. So let’s get started!

Our first function is +_ (plus) – we’re going to define it terms of add1 and sub1. (We’ll rename the functions with an _ suffix so they don’t clash with the existing clojure definitions of + and zero?

(def zero_?
  (fn [n]
    (= 0 n)))

(def add1
  (fn [n]
    (+ 1 n)))

(def sub1
  (fn [n]
    (- n 1)))

(def +_
  (fn [n m]
    (cond
      (zero_? m) n
      true (add1 (+ n (sub1 m))))))

(println (+_ 1 2))

Now this is kind of frustrating. Why bother doing all this recursion for an operation that is already built into the CPU? Especially when you limit yourself to integers anyway?

This is about making you think about numeric implementations. Part of it is that LISPs generally implement their own ‘numeric tower’ – you can see what fresh thinking has done for Clojure’s ability to handle numbers – particularly irrational fractions.

The other reason is the purity of the metacircular interpreter that you’ll build – you’ll literally be able to count the number of primitives required to build it and have no holes. (There is an assumption that recursion is cheap.)

Our next function is – (minus) which is quite similar to the above:

(def -_
  (fn [n m]
    (cond
      (zero_? m) n
      true (sub1 (- n (sub1 m))))))

(println (-_ 2 1))

From here we extend our concept of the lat (a List-ATom) – being a non-nested list of atoms. We extend it to what the book calls a vec, which is a non-nested list of integers.

From here we arrive at [The Fourth Commandment]. This states When recurring on a list of atoms, lat, or a vec, ask two questions about them, and use (cdr lat) or (cdr vec) for the natural recursion.

It then goes on to apply this to lists of numbers as well. It goes on: When recurring on a number, n, ask two questions, and use (sub1 n) for the natural recursion.

Now we get to the addvec function. This is really like a sum function from sql land:

(def addvec
  (fn [vec]
    (cond
      (empty? vec) 0
      true (+_ (first vec) (addvec (rest vec))))))

(println (addvec '(1 2 3)))

Next we look at the multiply function *_.

(def *_
  (fn [n m]
    (cond
      (zero_? m) 0
      true (+_ n (*_ n (sub1 m))))))

(println (*_ 4 5))

Again – we’ve built this in terms of our existing primitives.

Now we get onto The Fifth Commandment. I know these could come across as boring and self-righteous. On the other hand, if you write recursive code from scratch (and don’t rely on a library to do it for you) you want to have absolute confidence that it will run and terminate as you expect. These Commandments give you that confidence.

The Fifth Commandment states: When building a value with +_ (plus), always use 0 for the value of the terminating line, for adding 0 does not change the value of an addition.

It goes on to say: when building a value with *_(multiply), always use 1 for the value of the terminating line, for multiplying by 1 does not change the value of a multiplication.

It then finishes with: when building a value with cons, always consider () for the value of the terminating line.

Now we’ll look at vec+. The big idea is to be able to add two lists of numbers matching each corresponding element in the sum operation. This has uses in matrix operations:

(def vec+
  (fn [vec1 vec2]
    (cond
      (empty? vec1) vec2
      (empty? vec2) vec1
      true (cons (+_ (first vec1) (first vec2))
             (vec+
               (rest vec1) (rest vec2))))))

(println (vec+ '(1 2 3) '(4 5 6)))

Now we’ll look at >_(greater than). We’ll define it in terms of our primitives.

(def >_
  (fn [n m]
    (cond
      (zero_? n) false
      (zero_? m) true
      true (>_ (sub1 n) (sub1 m)))))

(println (>_ 10 1))
(println (>_ 1 10))

We’ll reuse this for less-than. It actually turns out remarkably similar:

(def <_
  (fn [n m]
    (cond
      (zero_? m) false
      (zero_? n) true
      true (<_ (sub1 n) (sub1 m)))))

(println (>_ 10 1))
(println (>_ 1 10))

Next we’ll define equals:

 
(def =_   
  (fn [n m]     
    (cond       
      (>_ n m) false
      (<_ n m) false      
      true true)))

(println "=_")
(println (=_ 1 10))
(println (=_ 10 1))
(println (=_ 10 10))

Next we’ll look at exponents:

(def exp
  (fn [n m]
    (cond
      (zero_? m) 1
      true (*_ n (exp n (sub1 m))))))

(println (exp 2 3))

Now we’ll start using our numbers functions on atoms and lats – this gets used in our metacircular evaluator later. First we’ll start with length:

(def length
  (fn [lat]
    (cond
      (empty? lat) 0
      true (add1 (length (rest lat))))))

(println (length '(pasta with pesto and mushrooms)))

Now we’re going to write a function pick to get an item out of a list using an index.

(def pick
  (fn [n lat]
    (cond
      (empty? lat) '()
      (zero_? (sub1 n)) (first lat)
      true (pick (sub1 n) (rest lat)))))

(println (pick  3 '(pasta with pesto and mushrooms)))

Now we’re going to extend this to remove an indexed item from a list using rempick:

(def rempick
  (fn [n lat]
    (cond
      (empty? lat) '()
      (zero_? (sub1 n)) (rest lat)
      true (cons (first lat)
             (rempick
               (sub1 n) (rest lat))))))

(println (rempick  2 '(pasta with pesto and mushrooms)))

Now we’re going to write a function to strip all the numbers out of a list. We’ll cheat a little bit, as we’ll introduce a new primitive function number?. We’ll call our strip function no-nums.

(def no-nums
  (fn [lat]
    (cond
      (empty? lat) '()
      true (cond
             (number? (first lat)) (no-nums (rest lat))
             true (cons (first lat)
                    (no-nums (rest lat)))))))

(println (no-nums  '(1 potato 2 potato 3 potato 4)))

This time we’ll flip it over – and write a function to strip out all the non-numbers from the list:

(def all-nums
  (fn [lat]
    (cond
      (empty? lat) '()
      true (cond
             (number? (first lat)) (cons (first lat) (all-nums (rest lat)))
             true (all-nums (rest lat))))))

(println (all-nums  '(1 potato 2 potato 3 potato 4)))

Our final function eqan? is our first building block towards rewriting the equals function in terms of our own primitives. This function will get us about half way there:

(def eqan?
  (fn [a1 a2]
    (cond
      (number? a1)
        (cond
          (number? a2) (=_ a1 a2)
          true false)
      (number? a2) false
      true (= a1 a2))))

(println (eqan?  1 10))
(println (eqan?  10 1))
(println (eqan?  10 10))
(println (eqan?  'a 'b))
(println (eqan?  'a 'a))

Conclusion
This chapter we’ve introduced two new primtives add1 and sub1 – and used them along with all our existing primitives to build all the functions above.

In total our primitives so far are: atom?, null?, first, rest, cond, fn, def, empty?, =, cons, add1 and sub1. These are all the functions (and those in the chapters to come) that we’ll need to implement to get our metacircular interpreter working.