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

So far we’ve covered flat data structures, reading flat data structures, creating data structures, creating a numeric tower, working with multiple occurrences of a match in the list, and changing our functions to work with nested lists.

In this chapter we’re driving towards our metacircular interpreter by starting to look at evaluating numerical values. So we’ll look at building an expression, breaking it down into operators and operands, and then handling it and returning a result. So let’s get started!

First we’re going to test with a test function to see if the S-expression passed in is a valid numeric expression that we can evaluate. We’re going to call this function numbered. But first we’ll expand Clojure’s definition of number? – so it can return a null for an invalid expression as we expect

;we need to define number_? to handle true/false
(def number_?
  (fn [a]
    (cond
      (null? a) false
      (number? a) true
      true false)))

(println (number_? 3))
;//=> true
(println (number_? 'a))
;//=> false

So now let’s do numbered to test for S-expressions that we can evaluate as a numeric expression.

(def numbered?
  (fn [aexp]
    (cond
      (atom? aexp) (number_? aexp)
      (= (first (rest aexp)) '+)
         (and
           (numbered? (first aexp))
           (numbered? (first (rest (rest aexp)))))
      (= (first (rest aexp)) '*)
         (and
           (numbered? (first aexp))
           (numbered? (first (rest (rest aexp)))))
      (= (first (rest aexp)) 'exp)
         (and
           (numbered? (first aexp))
           (numbered? (first (rest (rest aexp)))))
      true false)))

(println (numbered? '(a b c)))
;//=> false
(println (numbered? '(3 + (4 * 5))))
;//=> true
(println (numbered? '(3 a (4 * 5))))
;//=> false

Ok – so can we simplify numbered? Yes:

(def numbered?
  (fn [aexp]
    (cond
      (atom? aexp) (number_? aexp)
      true (and
             (numbered? (first aexp))
             (numbered? (first (rest (rest aexp))))))))

(println (numbered? '(a b c)))
;//=> false
(println (numbered? '(3 + (4 * 5))))
;//=> true
(println (numbered? '(3 a (4 * 5))))
;//=> true

Hmm – notice that the final expression became true in this version, but was false in the previous? That’s an assumption we’re making with this new version – that we know already this is an arithmetic expression. One might think this defeats the purpose of this function. I digress.

Now we’ll look at the Eight Commandment. This states that you recur on all subparts that are of the same nature including:
– On all sublists of a list
– On all the subexpressions of a representation of an arithmetic expression.
The big idea is that we’re starting to make a distinction between code and data. We’re saying that data functions recur on data, and code functions recur on code.

Now you’ll remember the infamous function eval from many languages – especially LISP. We’ll start writing the first version of eval for our metacircular interpreter starting with a basic version that just looks at arithmetic expressions. We’ll call it value:

(use 'clojure.math.numeric-tower)
; note use of new primitive expt

(def value
  (fn [aexp]
    (cond
      (number_? aexp) aexp
      (= (first (rest aexp)) '+) (+ (value (first aexp)) (value (first (rest (rest aexp)))))
      (= (first (rest aexp)) '*) (* (value (first aexp)) (value (first (rest (rest aexp)))))
      (= (first (rest aexp)) 'exp) (expt (value (first aexp)) (value (first (rest (rest aexp))))))))

(println (value '(1 + 1)))
;//=> 2
(println (value '(2 + 2)))
;//=> 4
(println (value '(3 exp 3)))
;//=> 27
(println (value '(4 b 4)))
;//=> nil

Now we’re going to take the function above and move from prefix to infix – just to illustrate how trivial the distinction is from an implementation point of view

(def value
  (fn [aexp]
    (cond
      (number_? aexp) aexp
      (= (first  aexp) '+) (+ (value (rest aexp)) (value  (rest (rest aexp))))
      (= (first (rest aexp)) '*) (* (value (first aexp)) (value (first (rest (rest aexp)))))
      (= (first (rest aexp)) 'exp) (expt (value (first aexp)) (value (first (rest (rest aexp))))))))

Now in my view that was a little silly. The book included a non-working version of value just to illustrate a violation of the Eighth Commandment. Let’s get on with it.

Now we’ll extract out helper functions to get the subexpressions and the operator

(def first-sub-exp
  (fn [aexp]
    (first (rest aexp))))

(def second-sub-exp
  (fn [aexp]
    (first (rest (rest aexp)))))

(def operator
  (fn [aexp]
    (first aexp)))

(def value
  (fn [aexp]
    (cond
      (number_? aexp) aexp
      (= (operator aexp) '+) (+ (value (first-sub-exp aexp)) (value  (second-sub-exp aexp)))
      (= (operator aexp) '*) (* (value (first-sub-exp aexp)) (value (second-sub-exp aexp)))
      (= (operator aexp) 'exp) (expt (value (first-sub-exp aexp)) (value (second-sub-exp aexp))))))

(println (value '(+ 1 1)))
;//=> 2
(println (value '(* 2 2)))
;//=> 4
(println (value '(exp 3 3)))
;//=> 27
(println (value '(b 4 4)))
;//=> nil

Cool – now – just to illustrate the power of abstraction by functions – we’ll switch back from prefix to infix functions.

(def first-sub-exp
  (fn [aexp]
    (first  aexp)))

(def operator
  (fn [aexp]
    (first (rest aexp))))

(println (value '(1 + 1)))
;//=> 2
(println (value '(2 * 2)))
;//=> 4
(println (value '(3 exp 3)))
;//=> 27
(println (value '(4 b 4)))

Time for another Commandment – The Ninth Commandment States Use helper functions to abstract from representations. Part of this is the java concept of eclipse’s extract method. Part of it is the power this gives you to change the function across the whole application and have it impact many parts of the system – ie a wide-ranging refactor.

Now we’re testing for null?. Although we had to write our own helper method for this in Chapter 1 – now as part of implementing the metacircular interpreter – we’re re-implementing it in terms of other functions so keep our api minimal.

;This is what we had
(def null?
  (fn [a]
    (or
      (nil? a)
      (= () a))))

;This is what they're proposing
(def null?
  (fn [s]
    (and
      (atom? s)
      (= s '()))))

Now it turns out this fails the conversion from Scheme to Clojure. We get the big idea. We’ll just move on.

Now we’re going to build our own numeric system out of parenthesis – again, just to make the implementation of our metacircular interpreter more pure and easier to implement. This is significant because we’re going to build up our own number representation out of parentheses – admittedly a strange exercise – but going to prove that we can do maths in a lisp implemented in itself.

We’ll start with zero?:

(def zero_?
  (fn [n]
    (null? n)))

(println (zero_? '()))
;//=>true
(println (zero_? 0))
;=>false

Ok – maybe that didn’t make sense – let’s give a few examples. So now zero is (), one is (()), and two is (()()).
Let’s do some operations on our new numeric representation – we’ll start with a new definition of add1.

(def add1
  (fn [n]
    (cons '() n)))

(println (add1 '()))
;//=>(()) ie 1
(println (add1 '(())))
;//=> (() ()) ie 2

Now let’s do sub1:

(def sub1
  (fn [n]
    (rest n)))

(println (sub1 '(()())))
;//=>(()) ie 1
(println (sub1 '(())))
;//=>() ie 0
(println (sub1 '()))
;//=> () unfortunately with our implementation sub1 of zero returns zero

Now we’ll reimplement our plus function:

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

(println (+_ '() '()))
;//=> ()
;//  zero plus zero is zero
(println (+_ '(()) '(())))
;//=> (()()) ie 1 plus 1 is 2

Now we’ll test for valid numbers in our new scheme by rewriting our function number?:

(def number_?
  (fn [n]
    (cond
      (null? n) true
      true (and
             (null? (first n))
             (number_? (rest n))))))

(println (number_? '() ))
;//=>true
(println (number_? '(()) ))
;//=>true
(println (number_? '((())) ))
;//=>false
(println (number_? '(()()) ))
;//=>true

You can see it running here.

Conclusion:
Why is this chapter called shadows? I haven’t figured that out. Perhaps it is a shadow of things to come.

Here we’ve started on the journey of the metacircular interpreter by writing an evaluator for arithmetic expressions. The only primitive we added was expt.

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