This is the tenth 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, changing our functions to work with nested lists, building a numerical expression evaluator, performing analysis on sets and numeric functions and deriving the Y-Combinator.
Now we’ll come to the pinnacle of the book (and some would say the peak of LISP itself). We’re building a metacircular interpreter. “What on earth is that?” you might ask. In trying to think of the most concise way to convey this idea – I came across this image:
This is another one that gets the same idea across. It might seem unimaginably crude, but it conveys the big idea of what this post is all about. LISP is a programmable programming language.
It is also the language with the most minimal syntax. If it has the most minimal syntax – then it must also be the easiest to implement. So one of the benefits of Lisp is that it is the easiest to implement (even it itself). That’s what we’ll do today.
But I hear you asking, “Um, practical use case? How would I explain to my manager that I need to eval my eval?”
This is the building block for a couple of different directions. First – if a language is easy to implement – then it is easy to build it into a transpiler/code generator. Clojure is a DSL for JVM bytecode, just as Clojurescript is a DSL for javascript. (One might argue that C is a DSL for ASM). Work is being done on a Clojure to X10C assembler, as well as work on Clojure to x86 generator.
On the business end of things – there comes a time when we need to build a parser for a client app. This might be for a calculator that reads an equation to build a graph or do a financial calculation. Or it might be one of the other seven scenarios Steve Yegge lists here. The point is – you need to write a program that reads programs (and even evaluates them).
Now please have some patience with what follows. This is a port from Scheme to Clojure. (This is 1974ish Scheme in a point in time with dinosaurs down the road and no built in map data structures in the language). This is trying to build everything the book has covered from the the ground up – so <sigh> we’re going to build a map data structure.
We’ll start with a key-value pair to put in our map.
(def new-entry build)
Then we’ll build a function to get a value out of the map by key value. But first we’ll write a handler that gets passed in saying what the author wants to happen when the entry is not found.
(def lookup-in-entry-help
(fn [name names values entry-f]
(cond
(empty? names) (entry-f name)
(= (first names) name) (first values)
true (lookup-in-entry-help
name
(rest names)
(rest values)
entry-f))))
We’d use it with a helper function together like this:
(def couldntfind
(fn [a]
(println "couldn't find" a)))
(println (lookup-in-entry-help 'entree '(mains dessert) '(chicken icecream) couldntfind))
Now we’ll lookup the value in a key-value entry:
(def lookup-in-entry
(fn [name entry entry-f]
(lookup-in-entry-help
name
(first_ entry)
(second_ entry)
entry-f)))
Here is an illustration of how you’d use this:
(println (lookup-in-entry 'entree '((entree mains dessert) (garlicbread chicken icecream)) println))
Now we’ll add the ability to extend our table – which is a cons list:
(def extend-table cons)
Now we’ll lookup a value in the map
(def lookup-in-table
(fn [name table table-f]
(cond
(null? table) (table-f name)
true (lookup-in-entry
name
(first table)
(fn [name]
(lookup-in-table
name
(rest table)
table-f))))))
We can use it like this:
(println (lookup-in-table 'mains '( ((mains dessert) (steak gelato))) println)) ;//=> steak
Ok – we’ve done our data structure. Now we’re going to start handling s-expressions. We’re going to handle six types:
* self-evaluating
* quote
* identifier
* lambda
* cond, and
* application
We’ll build a table to capture our environment:
(def initial-table
(fn [name]
(cond
(= name 't) true
(= name 'nil) nil
true (build 'primitive name))))
The basic building blocks of lisp are functions and data. We’ll refer to our basic functions as identifiers, and our basic data atoms as self-evaluating. We’ll create some functions to capture this idea:
For functions we take the expression and go and lookup the handler in our table:
(def *identifier
(fn [e table]
(lookup-in-table
e table initial-table)))
For data atoms – we just leave them as they are – but keep the function convention:
(def *self-evaluating
(fn [e table]
e))
For our data atoms – we’ll split these into numbers and strings – and build a handler to do that:
(def atom-to-action
(fn [e]
(cond
(number? e) *self-evaluating
true *identifier)))
Now we’ll look at the quote function. First we’ll build a function to get the value being quoted
(def text-of-quotation second_)
The only quirk to this definition is that we only take the first atom quoted and ignore the rest. You may consider this a bug in the book! We’ll stick to the book’s definition for now.
Then we’ll build our quote function handler which basically gets the value being quoted:
(def *quote
(fn [e table]
(text-of-quotation e)))
Now we start to get into some interesting territory. We’re going to handle lambda. We’ll do this by creating a new entry in the table marked as a non-primitive and storing the body (and the argument) of the lambda function in the entry value:
(def *lambda
(fn [e table]
(build 'non-primitive
(cons table (rest e)))))
Giving this a try- we get:
(println (*lambda '(*lambda (b) (println b)) '())) ;//=>(non-primitive (() (b) (println b)))
We’re now going to look at cond (defined in the scheme way – not the Clojure way).
Now we’ll add some abstractions to get out the truth test and conditional expression to be evaluated from a line in a cond test:
(def question-of first_) (def answer-of second_)
I’m sure you didn’t really need that – but the authors of the book seemed to think it would aid readability.
Now we’ll write some code to evaluate a line in a cond expression:
(def evcon
(fn [lines table]
(cond
(meaning
(question-of (first lines)) table)
(meaning
(answer-of (first lines)) table)
true (evcon (rest lines) table))))
(We’ll define the function meaning in a moment. Yes there are a few circular references here. You can see on the code running page how they all hang together. )
Now we’ll get the body of a cond expression:
(def cond-lines rest)
Now we’ll write the code to evaluate a condition using all our build block functions:
(def *cond
(fn [e table]
(evcon (cond-lines e) table)))
Now we’ll build our s-expression function handler – based on the types we looked at before:
(def list-to-action
(fn [e]
(cond
(atom? (first e)) (cond
(= (first e) 'quote) *quote
(= (first e) 'lambda) *lambda
(= (first e) 'cond) *cond
true *application)
true *application)))
You’ll notice we excluded self-evaluating and identifier as these relate to atoms not functions. What we’ll build now is a function to do that step of filtering:
(def expression-to-action
(fn [e]
(cond
(atom? e) (atom-to-action e)
true (list-to-action e))))
This next function the book authors have assigned a profound meaning – but really it is just a combination of the function handler and the environment table. This is functions + data, not at an s-expression level, but at a program level. The beautiful thing about a LISP is that the s-expression level conceptually mirrors the program level. Let’s look at the function meaning:
(def meaning
(fn [e table]
((expression-to-action e) e table)))
Now we need a bootstrap function to be able to use our meaning function. In LISPs – this is the eval function. The authors here have chosen to call it value. All it is doing is calling the meaning function, with an empty environment table:
(def value
(fn [e]
(meaning e '())))
Now we’ll do a handler for primitive identifiers:
(def apply-primitive
(fn [name vals]
(cond
(= name 'car ) (first (first_ vals))
(= name 'cdr ) (rest (first_ vals))
(= name 'cons ) (cons (first_ vals) (second_ vals))
(= name 'eq ) (= (first_ vals) (second_ vals))
(= name 'atom? ) (atom? (first_ vals))
(= name 'not ) (not (first_ vals))
(= name 'null? ) (null? (first_ vals))
(= name 'number? ) (number? (first_ vals))
(= name 'zero? ) (zero? (first_ vals))
(= name 'add1 ) (add1 (first_ vals))
(= name 'sub1 ) (sub1 (first_ vals)))))
This maps the scheme primitive functions to corresponding clojure ones.
Now we’ll look at evaluating a list of items in the table:
(def evlis
(fn [args table]
(cond
(null? args) '()
true (cons (meaning (first args) table)
(evlis (rest args) table)))))
Now we’ll look at evaluating lambda functions as closures. We’ll start by getting a lambda expression identifier out of the table:
(def table-of first_)
Next we’ll get the lambda function arguments:
(def formals-of second_)
Next we’ll get the body of the lambda expression:
(def body-of third_)
For a given expression in a lambda body, we’ll extract the function from the s-expression:
(def function-of first_)
Next we’ll get the body of the s-expression inside the lambda expression:
(def arguments-of rest)
Now we’ll test to see if an expression in the table has been tagged as a primitive:
(def primitive?
(fn [l]
(= (first_ l) 'primitive)))
Now we’ll see the opposite – if an expression in the table has been tagged as a non-primitive:
(def non-primitive?
(fn [l]
(= (first_ l) 'non-primitive)))
Now we’ll evaluate our lambda expression against the arguments passed in. Note that we can nest lambda expressions to make a function return a function:
(def apply-closure
(fn [closure vals]
(meaning (body-of closure)
(extend-table
(new-entry
(formals-of closure) vals)
(table-of closure)))))
Now we’ll apply values to both primitive and non-primitive expressions:
(def apply_
(fn [fun vals]
(cond
(primitive? fun) (apply-primitive (second_ fun) vals)
(non-primitive? fun) (apply-closure (second_ fun) vals))))
Now we’ll step up a level and apply the results of one expression to return a function – to the results of another function to get the arguments to the first function:
(def *application
(fn [e table]
(apply_
(meaning (function-of e) table)
(evlis (arguments-of e) table))))
To approach self-hosting (we won’t get there – but it is the principle of the thing) – we’ll build our own cons function:
(def cons_
(fn [u v]
(fn [b]
(cond
b u
true v))))
Note that instead of returning a list – we’re returning a function:
(println (cons_ 'apple '())) ;//=> #<Chapter10WhatIsTheValueOfAllThis$cons_$fn__862 Chapter10WhatIsTheValueOfAllThis$cons_$fn__862@272b72f4> (def lunch (cons_ 'apple '())) (println (lunch 'apple )) ;//=> 'apple (println (lunch '1 )) ;//=> apple (println (lunch nil )) ;//=> ()
Now we’ll define car and cdr to operate on this concept of function-chaining to represent lists:
(def car_
(fn [l]
(l true)))
(def cdr_
(fn [l]
(l nil)))
As an aside – this reliance on function chaining is almost the opposite of what we want. Instead we want to be able to represent chained function calls as data structures – to make the overhead of calls in recursion much cheaper. This representation makes it more expensive. Consider it a toy to stretch your brain and how you think about functions.
We’ve got to the end now – and are about to do our closing demos – and yet the book leaves out a critical piece which is disappointing. We want to be able to take all the functions in the book, and run them in our new evaluator – to fully close the conceptual loop. The authors however leave out define. We’re left to define everything with anonymous functions. We could do it ourselves, but that’s beyond the scope of this blog post.
We’ll finish by taking our evaluator for a spin.
(value '(add1 1)) ;//=> 2 (value '(eq 2 1)) ;//=> false (value '(eq 1 1)) ;//=> true (value '(quote hello)) ;//=> hello (value '((lambda (x) 1) 2)) ;//=> 1 (value '((lambda (x) x) 2)) ;//=> 2 (value '((lambda (x) (add1 x)) 2)) ;//=> 3 (value '(((lambda (y) (lambda (x) 1) y) 4) 3)) ;//=> 1 (value '(((lambda (y) (lambda (x) x) y) 4) 3)) ;//=> 3 (value '(((lambda (x y) (lambda (u) (cond (u x) (t y)))) 1 '()) nil)) ;//=> () (value '((lambda (x) ((lambda (x) (add1 x)) (add1 4))) 6)) ;//=> 6
You can see an example of this running here.