Metacircular Evaluation Essay

Meta-circular evaluators are awe-inspiring.

This will be a walkthrough of the meta-circular evaluator demonstrated in Chapter 4 and Lecture 7A of The Structure and Interpretation of Computer Programs (SICP). The chapter and video are on the subject of "meta-linguistic abstraction" – the establishing of new languages.

To evaluate a computer language you need an evaluator (also called interpreter) for that language. Evaluating an expression in a programming language means that the evaluator performs or executes the instructions described in the expression. An evaluator is called meta-circular if it evaluates the same language as it is written in using the same language constructs as the language itself (circular definitions).

Why would you want such a thing? One of the reasons is that having a meta-circular evaluator makes it very practical to implement new languages on top of the implementation language. Using a meta-circular evaluator you can, for example, create a language that is particularly suited for a problem at hand (a Domain Specific Language). Another reason is that it is insightful for educational and experimental purposes. The basic eval-apply structure below can be used to write interpreters for all kinds of languages. It is the kernel for every computer language.

What does a meta-circular evaluator look like? In SICP it is stated that:

It is no exaggeration to regard this as the most fundamental idea in programming:

The evaluator, which determines the meaning of expressions in a programming language, is just another program.

So it is just another program. In this post I have translated the code from meta-circular evaluator program from SICP (you can find the original code here) to Clojure.

Clojure is interesting because:

  • It runs on the Java Virtual Machine (therefore having access to all Java libraries and being able to interoperate with existing Java code bases).
  • It has a functional core (therefore being particularly suited for concurrent programming, necessary to utilize multiple CPUs).
  • And it is a dialect of Lisp (therefore having all the interesting properties described below).

Now, before I continue, let me be clear. I am not an expert on the subject matter. It is impossible for me to improve on the explanation in SICP. What I have attempted to do here is translate the Scheme code of SICP to Clojure and thereby deeper understand what is going on in the meta-circular evaluator and also learn something about Clojure. I have tried to put into my own words what is described in SICP. If you have a background in computer science this post is probably not much new. After all, SICP is an introductory level computer science book. I don't have such a background so for me this was all pretty mind blowing. I learned quite a lot from this post myself. Before I started to write I thought I understood, but when converting the SICP code to Clojure I realized I did not understand it as thoroughly as I thought. I needed quite a lot of help from the web and the end result is basically different sources copy-pasted together till I had a reasonably working evaluator.

It is very likely that the text in this post contains mistakes and I would be happy if they will be pointed out to me as well.

Now, let's get started.

Background

The idea of a meta-circular evaluator was first described by John McCarthy in his paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.

(There has by the way never been a Part 2, although some people have some ideas what it would look like).

This is the paper where McCarthy invented Lisp (acronym for LIst Processing). It contained the definition for – the universal function. is a universal machine: if you feed it a Lisp program, starts behaving as that program. It required inventing a notation where you could represent programs as data.

For McCarthy, writing this function was just a theoretical exercise. It was never his idea that the language or the function was actually implemented. What then happened was that Steve Russell, one of McCarthy's graduate students (who also invented one of the first computer games) transformed his theory into an actual programming language. As McCarthy stated in an interview:

Steve Russell said, look, why don't I program this eval..., and I said to him, ho, ho, you're confusing theory with practice, this eval is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the in my paper into IBM 704 machine code, fixing a bug, and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today..." (Source)

Alan Kay (famous computer scientist and creator of the language Smalltalk) describes his excitement when he first saw this and understood that it was Lisp written in itself.

These were "Maxwells Equations of Software!" This is the whole world of programming in a few lines that I can put my hand over.

Note: the Maxwell equations are four extremely elegant equations from which everything there is to know about the electromagnetic field can be derived.

Lisp is special because it does not enforce syntactic and semantic rules: it can be programmed at a higher level of abstraction than other languages. Lisp can be transformed in other languages. Some of that we will see below.

So what does Lisp look like?

Lisp, Lisp, Lisp

The nice thing about Lisp is that is has almost no syntax. The rules are simple (like Go), but the possibilities within these rules are virtually endless (like Go). Lisp is infamous for its parentheses.

(Source: https://xkcd.com/297/)

Combined with prefix notation these parentheses makes it so that Lisp data structures have the same makeup as Lisp code. The fundamental data structure in Lisp is a list (in Clojure we have some more data structures, we will not worry about that now). The first part of a list is interpreted as the operator, and the rest as the operands.

So for example in:

The operator is and the operands are 1, 2, and . Lisp applies the operator to the operands and this leads to the result of 12 in the case of and 15 in the case of .

The abstract syntax tree (AST) looks like this:

(Source: https://github.com/jiacai2050/JCScheme)

As can be seen the AST of Lisp is the same as Lisp itself. A Lisp is a language that is written in an AST, when the language is interpreted or compiled these code trees can be manipulated.

Now, let's look at the seven or so special forms of the language. The rest of Lisp can be implemented in these special forms. (Note: in reality Lisp is not implemented this way, there are some more special forms used in most Lisps for for example performance and usability reasons).

My description of these special forms (from which can be created) is roughly based on the article Roots of Lisp of Paul Graham where he explains what McCarthy has discovered. The original definitions of McCarthy can be found here.

In Lisp there are about seven fundamental forms:

Everything in Lisp is either a list or an atom. (In Clojure we also have some other types like vectors, but we do not worry about that.) Atoms are for example numbers (1), strings ("hello") or symbols (add1). Lists consist of parentheses surrounding atoms separated by whitespace or other lists or both.

Quoting an expression means that the expression does not need to be evaluated. This is similar to our use of quotes in natural language, where we use quotes to refer to the symbol itself instead to the meaning. To "say your name" I reply with "Erwin", to "say 'your name'" I reply with "your name". The quote operator can be used to blur the distinction between code and data. By quoting code you can pass it as data to another method which can then inspect and evaluate the expression. To quote you can use the operator or put a in front of the expression.

Example: . Which is equal to . When this expression is evaluated the result is (instead of 6, the result of evaluating the unquoted ).

returns true if the values of a and b are the same atom or both the empty list (defined as ), and false otherwise.

stands for construct and is used to add one element a to a list l. Lisp lists are chains of cons cells, where the second element points to the first element of the next cons cell (a linked list). The last element of a list is the empty list (or nil).

Note that Clojure does not use the cell as described above to create a list. Clojure has . Again, we will not worry about that now since the operations supported are similar, only the underlying implementation is different.

returns the first item in a list. In Clojure this form is called .

returns everything but the first item in a list. In Clojure this form is called .

comes from "Contents of the Address part of Register number" and from "Contents of the Decrement part of Register number". They refer to the way cons cells were stored in early computers. This is no longer the way it is, but Lispers have decided to stay with it because you can easily combine them. E.g., the car of the (the second element of a list) is the . Clojure breaks this connection with these roots, but has introduced other forms to make it easier to chain methods together (e.g., ->) and has special utility methods like to obtain the nth element from a list.

A conditional (conditionals were among other things first introduced in the paper of McCarthy). If pn is true en is evaluated. Also an :else clause can be introduced if no predicates are true.

So in the result is n1 if p1 is true, n2 if p1 is false, and p2 is true, and if both p1 and p2 are false.

Besides these fundamental forms you can create functions with . In a function you have a list of arguments and a list of expressions. The value of the arguments are assigned to the values that are passed during the function call (this becomes relevant later). A lambda expression (anonymous function) is created like this:

And you call the lambda expression as follows:

This can be read as "call the lambda expression with argument and body with the argument 1 substituted for , resulting in which evaluates to 2".

Expressions can be bound to a symbol in Clojure with as follows:

Here with argument is bound to .

As said Clojure has more collection types than the list. Clojure also contains maps, vectors and sets.

It is interesting to note that these other data structures are implemented in Clojure in such a way that they are immutable (unchangeable). And because they share underlying structures when being copied they have very good performance characteristics. To learn some more about this you can view a video where the creator of Clojure explains this how these data structures are implemented.

One more thing you will see in the implementation below: some data structures are demarcated by different types of symbols. The vector uses the and . In Clojure the argument list to a function or definition is a vector (not a list) and looks like this:

Since it supports the same basic operations as a list (like , rest`) it is fine to think about it as a list.

Example of use: implementing

To define functions and to evaluate them often recursion is used. Below we will define a procedure that is called . applies a given function f to every argument in a list (coll) and returns a list with the results. So when we do (using defined above) the result will be .

This is done by ing ("ing" in the case of Clojure) down a list and ing up the result. It applies f to the first element of the list, and combines () the result with f mapped to the rest of the list. The recursion breaks if the collection is empty. The evaluator has a lot of these type of recursive definitions as well so it is crucial to understand.

The seven forms above ( is not a primitive) are all the primitives you need to create a meta-circular evaluator.

Now, in an actual Lisp implementation there are a lot more primitives. The code belows also uses more forms. Most of them can be implemented in the code below, but others can't. The reason for that is that sometimes the evaluation order matters.

Another form we will see is , which is of the form

can be used to bind variables (var) to value (val) (to declare variables basically). These are in scope in the body. This let can roughly be written as:

Where you create a lambda where the variables are substituted for the values.

This is impossible to implement in a normal function, since the variables are always evaluated. When evaluation order needs to be controlled, a so-called macro can be created.

A macro hooks provides a convenient way to hook directly into the abstract syntax tree and change it at compile time (before the code runs). We will not be using or supporting macro's in this meta-circular evaluator, but it is definitely possible. If you want to learn more about macros you can read Paul Graham's On Lisp or Doug Hoyte's Let Over Lambda.

Now we have defined all the basic operators. Let's look at the meta-circular evaluator.

The implementation of the meta-circular evaluator

The meta-circular evaluator consists of two methods: and .

These methods call each other recursively as follows. This can be displayed as follows:

(Source: https://github.com/jiacai2050/JCScheme)

If no descriptive names are used for definitions inside and , the whole evaluator fits on one page. As shown in the Lisp manual (p. 13) it fits on one page, and as demonstrated in SICP lecture 7A: on a blackboard. In the current implementation a bit more descriptive names are used since it helps for clarity. And also a somewhat sophisticated environment structure is used to store procedures. Therefore this code does not fit on one page, but it is definitely still a short program.

Unfortunately the implementation described below is possibly not truly a meta-circular evaluator. A defining characteristic of a meta-circular evaluator is that it is written in the language it evaluates. This evaluator is written in Clojure, but it cannot evaluate everything of Clojure. What it can evaluate looks a lot like Scheme translated to Clojure, because in fact it is. But... Since Clojure is a Lisp and Scheme is a Lisp, I think the name meta-circular evaluator is still warranted.

Now we will implement and .

Eval

is a procedure that takes two arguments: an expression and an environment. And like every interesting procedure, it is a case analysis:

When we call with a quoted expression to evaluate (e.g., in an environment, it will look at what type of expression we are dealing with, and then dispatch to another procedure to handle it.

I'll first go over it just describing in words, and next dive deeper into the routines. When an expression is self-evaluating (like a string ["hello"], a number [1] or a boolean []) just gets the expression back. If is a variable (), we look up the value of the variable in the environment (we will discuss how this works later). If is a definition we want to define the value in the environment. (If we define () we want "a" stored in the environment to be "hello", and when we look up the variable a later we want to have "hello" returned.) If is an assignment (), we will look up in the environment, and set it to a new value. If is a lambda expression (anonymous function) we create a procedure of this lambda expression (we create a list tagged with the flag 'procedure), where we store the parameters and the body of the procedure alongside with the current environment captured in it (see below). Next, we have an if-statement and conditional: a conditional is transformed to a list of if-statements via a routine named . In an if-statement: if the predicate is true the first clause is evaluated, and if false the second clause is evaluated. For example, leads to if is true and to otherwise.

The above is all reasonably straightforward. It is a way to implement all the reserved words. As an aside, Gerald Jay Sussman states:

The number of reserved words that should exist in a language should be no more than a person can remember on its fingers and toes. I get very upset with languages which have hundreds or reserved words. (Source)

If the expression does not start with a reserved word, the expression is an application. This means we apply the result of evaluating the operator of the expression in the environment, to the list of values that follow, each evaluated in the environment.

First we look at , which is implemented as follows:

This is a recursive definition (like above) where we construct a new list with as first argument the first operand evaluated in the environment, and as the rest, the rest of the operands evaluated in the environment. When we come to the empty list (the second element of the last cons cell in a linked list) the recursion breaks and we return the empty list .

We will discuss the implementation of after we have looked at the inner definitions of a little bit closer. These consist of routines to detect expression, routines to get information out of expressions, and routines to transform expressions.

Routines to detect expressions.

First a little heads up: all definitions used above to get information out of expressions (like and ) are all implemented with s and s ( and in Clojure). E.g.,

Detecting what type of an expression we are dealing with, is done by comparing the first element of the list via :

This checks if the expression is a list, and (using the code inspecting facilities of Lisp) if the first expression is equal to the tag.

For example, to see if a variable is a definition or quoted we check if the first element is respectively the symbol or :

And in a similar manner:

Note that if a definition contains a boolean result (true or false), by convention we end the definition with a question mark .

This is how routines to detect expressions are implemented.

Routines that get information out of expressions

Beside routines to detect expressions we have some procedures to get information out of expressions. We know the syntax of our language and we know at which position certain elements should be located. First we define some helper methods to get certain elements out of a list besides the rest and the first, so for example the second is:

These routines are implemented in Clojure as follows:

Here we see that for example is the . Which is indeed the case. If we look at:

We see that everything after the second element is the body.

All the other implementations of routines that get information out of expressions are defined in the same manner.

Routines to manipulate expressions

As seen in the definition of above, when an expression is a lambda expression (as identified by ), we make a procedure. This is implemented as follows:

So we create a new list via the procedure (which is a routine to create a linked list via a chain of 'es). Note that the procedure creates a new list where the environment is stored in. This is a way to create something called a closure: the environment at the moment the procedure was called is captured. Next when we look at we will see how this environment is retrieved. Furthermore, we will discuss the difference between two types of scope (dynamic and lexical) and their implementation later.

In a similar manner as we can create a new type of expression from an if-expresion in .

Note: using is a convention to signify the routine is a conversion.

Via a expressions (conditional) can be converted using an internal procedure named . recursively expands every clause of a expression to nested if-statements.

So evaluated an expression by detecting the type of expression, getting the information out of the expression and possibly converting it to something else, If it does not start with one of the reserved words it is treated as an application. This will be handled with in the next segment.

Apply

We have arrived at . is called in if the expression is not one of the reserved words (like , , , and ). An expression is an application if it is not one of the special forms, but still a (e.g., in the case of , is not in the list of the reserved words). Then the expression will be handled by this part of (see above):

We already looked at that evaluated all the operands in an environment. What remains is applying the operator to the arguments. then feeds back the expression and the environment to , et cetera.

is a procedure that takes as input a procedure and its arguments, and produces an expression and an environment:

Again it is a case analysis. Let's go through it. We first check if a procedure is a primitive procedure with . A procedure is a primitive procedure if it is looked up in the environment and it was in the list of primitive procedures defined in the environment. The primitive procedures are defined as follows, and are later added to the environment (how the environment is constructed will be discussed later).

If the procedure is a primitive procedure we apply the primitive procedure with the underlying apply of Clojure. At the beginning of the evaluator we store the underlying to not confuse it with the newly defined :

How this apply that is built into Clojure works, is outside of the scope of this post (to be honest I don't know). Interesting to note is that these types of primitives are not essential for computation. You can do everything with lambda and something called a Y Combinator. But using that is not as convenient.

The application of a primitive procedure is defined as follows:

Where is a method to retrieve the procedure:

As can be seen above where the are defined the primitive-implementation is a symbol like or . Again, these are evaluated by the underlying Clojure implementation.

If we are dealing with a compound procedure (a list tagged with ), we evaluate the sequence of elements with the routine :

Note that is used to evaluate multiple expressions (in it is detected by , a similar construct in Scheme).

is a recursive definition where we, if we have only one expression, only evaluate this one expression in the environment, and if we have more than one expression, we evaluate the first expression and the rest of the expressions in the environment.

Here , and are defined as follows:

Naturally the first expression is the first element of the sequence (of expressions). The rest of the expressions is the rest of the sequence. And we are dealing with the last expression if the rest of the sequence after it is empty.

Important to note is that when we use in the definition of we extend the environment of the evaluation with the procedure parameters, arguments, and the procedure environment itself. This way the environment of the procedure (which was stored when it was created) are available during evaluation.

So what exactly is this extending of an environment? And in what way are symbols added to it?

The environment

We now go step by step through the environment.

An environment consists of frames stacked together in a list. A frame is empty or consists of two lists: one lists with variables, and one list with values. When a definition is looked up we look at the first frame to see if the variable is defined there. If we find it we return the value. If it is not, we look one frame further to see if it is defined there. Until we finally get to the global environment. If it is not found there we have an error ("Unbound variable"). So the goal of an environment is to store variables and the values associated with them.

A simple environment structure looks like this:

Source: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-21.html#%sec3.2.

Here we see multiple frames (I, II and III) that are connected. A will find that the value of the variable x is 7, but C will find 3.

The environment is crucial to the evaluation process, because it determines the context in which an expression will be evaluated. Each time a procedure is applied, a new frame is created.

It turns out that my assumed immutability (I thought nothing could be changed, which was not completely true from a user's perspective) of Clojure made the implementation quite difficult (for me). Clojure has, unlike Scheme (the language where this evaluator was translated from), no mutable (changeable) cons cells (no actual cons cell at all as described earlier). Where in Scheme you can change the first element or last element of a list respectively with the routines and , this is not possible in Clojure.

We can however accomplish mutation by defining a so-called (different from the basic building element defined above). An Atom in Clojure is a mutable value, that can be mutated in an atomic way, free of concurrency problems (see this chapter on Metaphysics in Clojure for the Brave and True for an explanation).

The algorithm used in the Scheme version checks the first frame, loops over it (with a method called scan) and if it finds the variable, it returns the value associated with it. If it does not find anything it will loop over the enclosing environment and scans there.

When redefining a variable in the environment, a similar process is used. When the variable is found however, is used to overwrite the variable value in that frame.

After using some environment structures with bugs in them (for example being unable to define recursive definitions) I found a better environment definition in the SICP answers of Jake McCrary. The implementation has the same behavior as that of the original of the SICP.

We now go step by step through this environment structure by Jake McCrary.

The empty environment is an empty list.

(Note that is similar to without arguments.)

To get the enclosing environment (frame) of the current environment (frame), we look at the rest from the frame we are in now.

To make a frame, we use a routine to add two lists of variables together which "returns a map with the keys mapped to the corresponding vals" (ClojureDocs). A map is a list of key-value pairs.

Let's illustrate the behavior of this creating of frames with .

We have a list of variables to be added to the environment:

A list of corresponding values (the primitive and rest operator, and a lambda expression and a created procedure to be added to the environment:

When we zipmap them:

This leads to the following result:

{+ #object[clojure.core$PLUS (...)],
rest #object[clojure.core$rest_ (...))],
add1 (procedure (x) (fn (x) (+ x 1)) {:+ +, :x 2, (...)})}

So a frame is a map (key value pairs, differentiated with and in Clojure) with variables (keys of the map) bound to values (values of the map) (in this case the primitive objects from the underlying Clojure).

Next we get methods to add bindings to frames:

Note that by convention routines that mutate state are ended with an exclamation mark .

uses in combination with to associate a variable and new value to a frame. This is one of the ways to have (safe) mutable state.

Next we need a way to extend our environment (this is the method used in and to add variables and values to a frame, for example when storing the variables of a procedure in the environment where it will be evaluated in, or when new definitions are added):

takes variables and values and a base environment. It then makes a frame of the variables and values and es that up to the base environment. The rest is error handling for when the amount of variables and values applied are not the same (e.g., when evaluating it will returns "Too many arguments supplied").

Next, we have a method to lookup a variable in an environment. This one looks a bit more complicated because of the inner methods.

Know that is just like , only now we define functions and bind them to a name only available in the scope. Furthermore, checks if a variable is available in a map and returns true if it does, false it it does not.

What happens at the bottom of is that we start an with the . defines a method to look for a variable in a frame.

If the frame contains the variable we (get is a way to retrieve the value belonging to a key) the value belonging to the variable from the frame. Otherwise, we start a new over the enclosing environment (the next frame or frames).

When the is started we first check if we are dealing with the empty environment. If that is the case we break the recursion: we have scanned all frames in scope and we are therefore dealing with an unbound variable. If we are not dealing with the empty environment, we are getting the first frame from the (remaining) environment (remember that the environment is a list of frames), get the value from the atom by using , and scan that.

So now we can understand how to lookup a variable, we also need a way to define a variable value in the environment. To accomplish this we have a similar procedure, which uses a similar scanning method as above.

The difference with is that in we are trying to find the variable, and in the first frame we find which contains the variable we change this variable's value for the current value. If the frame doesn't contain it we start the over the enclosing environment. The recursion breaks when we end up with the empty environment (unbound variable) or when we find a variable and have set it.

Furthermore,to define a variable we get the first frame of the environment and add the variable as a key with the value as a value. (So we add it to the top-level frame, the global environment.)

Finally, at the beginning we setup the environment:

We load the primitive procedures in the environment and we set as our base environment.

Now you've seen everything but a way to interact with this evaluator.

Interacting with the evaluator

Last but not least we have a way to interact with the evaluator. When we run the code a asks for input, and when it has received input it will evaluate the input in our environment:

That's it. Works like a charm.

Example interaction

The goal of this thing was to be able to feed the evaluator program a Lisp expression, and have it return the result. So when we feed it it should know what this means and add the symbol to the environment.

Here we see some interactions with the evaluator:

So "Hello" evaluates to itself since it is self-evaluating. is found in the environment and termined to be a primitive operation from the underlying Clojure. And we can also define functions like and and apply these to arguments.

If you would like to see a full evaluation of an expression by hand, I can recommend watching the second part of Lecture 7A of SICP. You can also run the code of the evaluator and put some break points or s at strategic points.

Dynamically scoped environment

In my journey to create a working version I also stumbled upon this implementation of Mathieu Gauthron.

A dynamically scoped environment is a bit simpler to implement, what is defined latest is found first (instead of passing an environment along in a certain procedure scope, we just update the environment). It is a bit harder to reason about though, because in a dynamically scoped environment it is only at runtime defined what is in scope.

After we define what lexical and dynamic scope is, below will follow an experiment with the dynamic evaluator.

Lexical scoping versus dynamic scoping

Lexical scope means that the structure of the program determines which variables are in scope (for example in C-like languages the scope is defined by curly braces and . In dynamic scope the scope is defined at runtime, that what was defined latest when the program is evaluated at runtime is found first. Currently there are almost no languages with dynamic scope. Lexical scope is more logical to reason about. Nevertheless there are valid use cases for dynamic scope. A nice example is exception handling (throwing an exception and catching it):

Exception handling in most languages utilizes dynamic scoping; when an exception occurs control will be transferred back to the closest handler on the (dynamic) activation stack.

One way to test if a language is dynamic or static is by the following idea:

First you define a method that uses a variable in its body:

When you call this method:

this returns

Is not a valid symbol – LOOKUP-VARIABLE-VALUE scope

This is because scope is not available in the environment. It is not defined.

Next when you introduce a new binding with the same name () wherein you call test:

A lexically scoped language will return "Is not a valid symbol – LOOKUP-VARIABLE-VALUE scope" as above, because the environment when the definition of was created does not contain this binding. A dynamically scoped language will return . It does not care about what the value of scope was when test was defined and just looks up the nearest definition. In other words: the lexical environment was not captured.

(The idea for the test was obtained from this Stack Overflow answer, but slightly modified since our language does not know how to evaluate .

As expected from the above description, the evaluator with the dynamic environment has the following behavior:

Closing remarks

What we have seen above is some nice copy, paste and explaining. For this I was inspired by SICP, and the evaluators of Greg Sexton, Jake McCrary and Mathieu Gauthron.

What we have seen above is an elegant model of computation. Using about seven primitives we can define in which we can implement our language.

The idea that an evaluator is just another program (and such a short one) is remarkable. Once you understand how the meta-circular evaluator works, it becomes possible to change the implementation and create interpreters for other languages.

Indeed, new languages are often invented by first writing an evaluator that embeds the new language within an existing high-level language.

(Source)

The fact that Lisp code trees can be changed at runtime or compile time makes it so that it is possible to deeply influence the language. Where in languages like Java you have to wait for a committee to put a new feature into a language, in Lisp you don't have to wait and can implement these features yourself.

One quote (incorrectly stated according to the supposed author but nevertheless instructive) describes the difference between languages without the ability to modify its structure (like Java or APL) and Lisp as follows:

APL is like a beautiful diamond - flawless, beautifully symmetrical. But you can't add anything to it. If you try to glue on another diamond, you don't get a bigger diamond. Lisp is like a ball of mud. Add more and it's still a ball of mud - it still looks like Lisp.

One nice example of the ball of mud idea is the -routine that is added to Clojure for asynchronous programming (communicating sequential processes). Go also has them, but for Go is it a fundamental language feature. Because the language can be fundamentally and syntactically changed, it could be introduced as a library in Clojure. (See here for more information.)

In SICP among other things the evaluator is extended and modified to become an evaluator for:

And the same idea is used to create an evaluator for machine language and to create a compiler that converts Scheme to a machine language. In SICP it is also explained how the mechanisms works by which procedures call other procedures and return values to their callers (which the meta-circular evaluator borrows from the underlying Lisp).

One of the other things that is missing in the above implementation is a way to define macros, which are used for defining syntax language extensions. I am not so well-versed in them yet. I might play with them in a later post.

I did learn a great deal from the above implementation. I hope it is useful for others as well.

The source code of the evaluators can be found at:

Further reading:


Tags: John McCarthyLispClojureLifeSICP


« Vim and Emacs

The Metacircular Evaluator

Steve Russell said, look, why don't I program this eval..., and I said to him, ho, ho, you're confusing theory with practice, this eval is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the eval in my paper into IBM 704 machine code, fixing a bug, and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today..."John McCarthy

The most important lesson of SICP is perhaps that the interpreter for a programming language is just another program

Eval and Apply

The core of our interpreter is the interaction between the two mutually recursive functions and

We have spent a while building up a mental model of how Clojure evaluates the s-expressions that constitute our programs.

In words it looks something like this:

Eval

Primitive expressions

  • Some things (like numbers) evaluate to themselves
  • Vars need to have their values looked up in the current environment

Special Forms

  • : Return the thing quoted (without it being evaluated)
  • : Assign the name to the (evaluated) expression
  • : Create a function, closing over the current environment

Evaluating Combinations

  • Evaluate the subexpressions of the combination
  • Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands)

Apply

Primitives

  • Apply them to their arguments

functions made with fn (ie 'compound procedures')

  • Evaluate the body in an environment where the formal parameters are assigned to the arguments

As Code

Destructuring

We make heavy use of destructuring, if you don't know how it works, see this blog post from Jay Fields

Quick note on state

In order to have a purely functional interpreter we rely on eval-sexp returning a that contains both the value of the passed in s-expression and a (potentially updated) environment. I chose Clojure maps for the environment as it simplified implementation massively.

SICP actually relies on mutation and an associative data structure they create from cells, I think this version brings out the idea in a cleaner way and you see sooner all the code needed to run it yourself (< 100 lines).

Eval

Apply

Even though we have not yet seen the definitions of a few of the functions called by and , I hope you agree that's pretty amazing!

First a few helpers, takes an s-expression and an environment and returns a that has both a and a new environment

While returns a , eval returns the resulting value and can be called without an environment (by automatically passing the empty environment)

Booleans

We can use the symbols and as Boolean's

What in our language is self-evaluating?

Numbers in our language are just Clojure's numbers, which in turn are Java numbers, we leave them as-is.

Also the bools above will be self-evaluating

Primitives

Primitive procedures, are stored in a Clojure map, keyed by the symbol that represents them. This is subtle and you should think about it for a while.

The symbol '+ is mapping to the value of + looked up by the Clojure interpreter, ie the function itself.

We add some predicates to check if something is either the Clojure function we want to use as a primitive or the name we gave it.

Note that nothing is special about the names, or the fact that we are using things that happen to be primitive in Clojure too, we could have done

Environments

You can see that environments in our interpreter are Clojure maps, the keys are symbols and we lookup symbols in the current environment.

Evaluating lists

We are looking at something like

def

calling adds the value of evaluating sexp in the current env to the environment

if

to evaluate we need a special evaluation rule, note how we only evaluate one of predicate and alternative

Crucially here is not Clojure's

So in our language, anything that is not is truthy

Also we return our languages if the predicate is false and we don't have an alternative.

fn

If an expression is a expression we return a object and don't change the environment.

Programs

In our simplifed interpreter, a program is just a list of s-expressions and the result is the return value of the last one.

We can:

  • name things with
  • lookup things in an environment (here we just use Clojure maps)
  • create functions with
  • apply primitive procedures
  • apply compound procedures

So can run some simple programs, such as:

and

The idea is to thread the evaluation through all the s-expressions using

We start with a that has as the return value and the empty environment and update it by evaluating the s-expressions one by one.

You can see that the function passed to reduce only looks at the in the state. This is correct, without side-effects there is no point doing anything other than in all bar the last s-expression as only that is returned.

will return 4, the second line achieves nothing

Derived Expressions

We have not yet implemented or , we could go and make a special evaluation rule as we did for but a useful trick is to rewrite the expression in terms of previously defined special form.

We can rewrite

as

To do this in our interpreter we can just add another clause to our in where we recursively call with a transformed s-expression

The cond->if function looks like this:

Using this helper to build expressions

As is a way to create a new scope with some symbols (re-)bound to expressions, we can actually rewrite it as a function application (remember that we apply compound functions is to evaluate the body in an environment where the formal parameters are assigned to the arguments)

Can be rewritten as

Again, we can add another clause to

Here is the function that does the transformation

We destructure out the bindings, in our case , and the body , we create a function with and as the formal parameters, immediately called with 1 and 2 as arguments

Recursive Function Definitions

While the interpreter feels fairly complete, one thing it cannot do is handle recursive function calls

We cannot define a recursive factorial function

To achieve this we need to allow functions to refer to themselves in their bodies, we can change our records to hold a name

We can add as a special form by adding to our in

and we have to change the special form too to return a new , with stored for the name

We need to change the part of our function

Exercises

First download the project from Github, I recommend lein autoexpect to give you a nice workflow changing the interpreter.

1. Add more types

  • What other types might we add to our language that are self-evaluating besides numbers and bools?
  • Are they inherited from Clojure or just in our language?
  • Add some primitives that operate on them, try and make some Clojure primitives and some plain Clojure functions

2. Add

It should be that =>

3. /

Add and to the interpreter, with tests.

Do one as a special form and one as a derived expression

4.

in our language does not behave like Clojures, which allows bindings to refer to previous ones.

Add a function , such that

returns 39

Try and do it as a special form, and a derived expression (and add tests)

Can we use (ie derive from a derived expression)?

5. Iteration

We can express iterations as recursive function calls, but sometimes it is convenient to have iteration constructs

Can you add , , constructs? (not necessarily matching any existing Clojure definitions)

6. Recursive anonymous functions

Clojure allows you to 'name' anonymous functions so that you can recursively call them

Can you implement this in our interpreter?

Instead of making a special form, can you derive it from now?

0 thoughts on “Metacircular Evaluation Essay”

    -->

Leave a Comment

Your email address will not be published. Required fields are marked *