Author Archives: admin

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.

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

The first function we look at is rember.

(def rember
  (fn [ a lat]
    (cond
      (null? lat) '()
      true (cond
        (= (first lat) a) (rest lat)
        true (cons (first lat)
          (rember
            a (rest lat)))))))

(println (rember 'banana '(apple banana orange)))

The big idea here is list construction. We’re applying the second commandment of the Little Lisper – use cons to build lists [sequences].

The next function we look at is firsts.

(def firsts
  (fn [l]
    (cond
      (null? l) '()
      true (cons (first (first l))
        (firsts (rest l))))))

(println (firsts '((large burger)(fries coke)(chocolate sundae))))

Here we also meet the Third Commandment of TLS. This states when building a list, describe the typical element, and then cons it onto the natural recursion. This goes back to the discussion on lat? we were having in the previous chapter.  You have to identify the base case, and then build on it.

You can see it working here. 

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

This chapter introduces functions – and the idea of the list of atoms and the member function.

When looking at list atoms, known as a 'lat' we are introduced to writing functions in Scheme. We write the lat? function in Clojure to test for a non-nested list of atoms.

(def lat?
  (fn [l]
    (cond
      (null? l) true
      (and (seq? l)
           (atom? (first l)))
             (lat? (rest l))
      true false)))

There are a couple of things we’ve transposed here. The key one to raise is the usage of def... fn[] rather than defn. This is a convention in the book, and glues in the readers minds that functions are by default anonymous, and we give them labels after the fact. This enables the reader to get into the feel of passing anonymous functions around later.

The other thing that is introduced here is the application of the Ten Commandments (of The Little Schemer). The big ideas of the 10 Commandments is to help you solve problems recursively. The first one states that you should always ask null?  as the first question in expressing any function. In idiomatic Clojure we would use the empty? function for this – but for the sake of being closer to the book, we will not apply it in this function, but use null?.

The question behind this is what is a non-nested list of atoms and why do we care?  One of the big themes in this book is solving problems using recursion rather than iteration. The point is that before you can solve a problem using recursion (where you’ve got a nested list) you need to learn to solve it for the base case where there is no nested list. To validate the base case – we use the lat? function.

The next function we look at is the member? function.

(def member?
  (fn [a lat]
    (cond
      (null? lat) false
      true (or
        (= (first lat) a)
        (member? a (rest lat)))) ))

Why do we have this function? It’s the first useful function in the book. We also keep building our recursion skills, and it is a key building block for later functions.

You can see it working here. 

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

The big theme in Chapter 1 is Simplicity of Data. In The Little Schemer world there are two levels in the syntax that describes data – atoms and lists. Note that an atom in TLS refers to a a string of characters (perhaps you could consider this a list element – ie a non-list), wheras in Clojure an atom refers to a unit of a transaction.

To test for atoms – we’ll use the atom? function:

(def atom?
  (fn [a]
    (not (seq? a))))

Note that we’re not using the defn syntax in Clojure but def ... fn. This is intentional because the book uses this standard, and then makes use of it later in the book when it passes anonymous functions around.

(def null?
  (fn [a]
    (or
      (nil? a)
      (= () a))))