As programmers we take great pride in keeping up with new developments in libraries, languages and tools (and usually have a lot of fun doing it as well). If we stop learning, we know we'll soon end up like the Cobol-programmers of today. And this is of course a good thing — there's always something new and exciting to learn, something on which to sharpen our skills.
But sometimes I also find that it pays off to take a look at the old, rather than the new. It's good to go back to the roots, to see where it all comes from, and to have look at the fundemental ideas. Today we'll take a trip back to 1960, to the origins of Lisp as described by John McCarthy in his paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part 1.
There is really nothing novel in this blogpost. The ideas all belonged to McCarthy, but sometimes it's good to just study the masters. Lets explore the origins of one of our most powerful (family of) programming languages. We'll start by briefly covering the Lisp syntax and semantics, before moving on to an implementation of the language itself in Python.
Lets start out by explaining the basics of Lisp. If you're already familiar with this, I urge you to move on to the next section instead.
I have tried to keep this section brief. If you would like something a bit more elaborate, I really recommend The Roots of Lisp by Paul Graham, where he essentially describes McCarthy's Lisp by example and then show an implementation in Common Lisp.
Lisp programs consists of something called s-expressions, which stands for symbolic expressions. S-expressions are defined recursively, and consists of either a single atom or a list, which contains other s-expressions.
An atom is akin to what many modern languages would call an identifier. It consists of a series of letters or symbols — anything other than parentheses, single quote and whitespace, basically. Examples of atoms would be a, foo/bar! or +.
(Note that we simplify a bit here, compared to McCarthys original description. By limiting atoms to not contain spaces, we eliminating the need for commas separating atoms within lists. In the original Lisp, atoms were also limited to upper case letters, a restriction I don't see the need to enforce here.)
Lists use the parenthesis syntax that have become so iconic to Lisp. A list is expressed by a pair of parentheses enclosing a number of elements. Each element is another s-expression, which might be either an atom or a list. Here are a copule of examples:
(list of only atoms) (another list (with some ((nested)) (lists inside)))
In addition, although it's actually not in the original Lisp, we include a shorthand syntax 'x which is evaluated as (quote x), where x is any s-expression. This way, '(a b c) is interpreted as(quote (a b c)) and similarly, 'foo as (quote foo). We will later see why this turns out to be useful.
When evaluating an s-expression e, the following rules apply.
e is an atom its value is looked up in the environment.(<e0> <e1> … <en>), which is evaluated as a function application. How this is handled depends on the first element of the list, e0.e0 is the name of one of the builtin (axiomatic) forms, it is evaluated as described below.e0 is any other atom, its value is looked up. A new list, with the value of e0 replacing the first element is then evaluated. e0 is not an atom, but a list of the form (lambda (<a1> … <an>) <body>), then e1 through en is first evaluated. Then body is evaluated in an environment where each of a1 through an points to the value of the corresponding en. This constitutes a call to an anonymous function (i.e. a lambda function).e0 is of form (label <name> <lambda>) where lambda is a lambda expression like the one above, then a new list with e0 replaced by just the lambda is constructed. This list is then evaluated in an environment where name points to e. The label notation is how we solve the problem of defining recursive functions.The axiomatic forms are the basis on which the rest of the language rests. They behave as follows:
(quote e)e without evaluating it first.
(atom e)e and returns the atom t if the resulting value is an atom, otherwise f is returned. (Since we have no boolean type in our language, these two atoms are treated as true and false, respectively.)
(eq e1 e2)t if both e1 and e2 evaluates to the same atom, otherwise f.
(car e)e, which is expected to give a list, and returns the first element of this list.
(cdr e)car. It returns all but the first element of the list gotten by evaluating e. If the list only holds only one element, cdr instead returns the atom nil.
(cons e1 e2)e1 and e2, and returns a list constructed with the value of e1 as the first element and the value of e2 as the rest. If e2 evaluates to the atom nil, the list (e1) is returned.
(cond (p1 e1) … (pn en))p1 to pn in order, until one of them evaluates to t, at which time it will evaluate the corresponding en and return its value.
The evaluation rules above are, surprisingly, all we need to implement Lisp. In addition, however, I'd like to include another form that isn't explicitly described by McCarthy, but which is included in Graham's article. It could strictly speaking be replaced by doing a lot of nested labels but, but this would make things a lot less readable.
(defun name (a1 … an) <body>)define expression. It does this by adding a new binding to the environment it is itself evluated in: name→(lambda (a1 … an) <body>).
Now, with the syntax and core semantics of the language outlined, lets look at how to make this happen in Python.
The first step when implementing a language is usually the parser. We need some way to go from programs as strings to some datastructure we can interpret. Such a datastructure is usually called the Abstract Syntax Tree (AST) of the program.
Since Lisp is a language largely without syntax, with parentheses and atoms used for everything, writing the parser is relatively easy and uninteresting. This is not what I want to focus on in this blogpost, so we'll skip over the details here. Feel free to have a look at the code for the parser before we move on, if you like.
The parser works like this:
>>> from rootlisp.parser import parse
>>> program = "(lambda (x) (cons x (cons x '())))"
>>> ast = parse(program)
>>> ast
['lambda', ['x'], ['cons', 'x', ['cons', 'x', ['quote', []]]]]
The parse function takes one argument, the program string, and returns the corresponding AST. There is also an opposite function unparse which converts ASTs back into Lisp source strings.
>>> from rootlisp.parser import unparse
>>> unparse(ast)
"(lambda (x) (cons x (cons x '())))"
Before we move on to evaluating the ASTs, let's define another useful function, interpret, which we'll be using to test our language as we go:
def interpret(program, env=None):
ast = parse(program)
result = eval(ast, env if env is not None else [])
return unparse(result)
The function combines the power of parse and eval. interpret takes a Lisp program as a string, parses it, and finally evaluates the parsed expression. Since the evaluated expression might be a Lisp data structure (and even valid Lisp code) we "unparse" it back to it's corresponding source string. This is done to hide our internal ASTs from the user of the Lisp.
With parsing out of the way, and armed with the interpret function to test our code, it's time to have a look at the core of the langage, the eval function. It looks like this:
def is_atom(exp):
"""Atomes are represented by strings in our ASTs"""
return isinstance(exp, str)
def eval(exp, env):
"""Function for evaluating the basic axioms"""
if is_atom(exp): return lookup(exp, env)
elif is_atom(exp[0]):
if exp[0] == "quote": return quote(exp)
elif exp[0] == "atom": return atom(exp, env)
elif exp[0] == "eq": return eq(exp, env)
elif exp[0] == "car": return car(exp, env)
elif exp[0] == "cdr": return cdr(exp, env)
elif exp[0] == "cons": return cons(exp, env)
elif exp[0] == "cond": return cond(exp, env)
elif exp[0] == "defun": return defun(exp, env)
else: return call_named_fn(exp, env)
elif exp[0][0] == "lambda": return apply(exp, env)
elif exp[0][0] == "label": return label(exp, env)
As you can see, eval takes two arguments exp and env. exp is one of the ASTs returned by parse, env holds a list of associations which represent bindings from atoms to values in the environment.
We have now covered all the cases we need in order to implement the Lisp. Lets look at the implementation of each in turn. Keep the structure of eval in mind when we go through each case.
The first case we need to cover is when the evaluated expression is an atom.
The value of an atom is whatever it is bound to in the environment, so we do a lookup of the atom in env.
def lookup(atom, env):
for x, value in env:
if x == atom:
return value
Lets have a look at how this works in the REPL:
>>> from rootlisp.lisp import interpret
>>>
>>> env = [('foo', 'bar')]
>>> interpret('foo', env)
'bar'
quoteThe next form is quote, which is incredibly easy to implement: all we need to do is simply to return whatever the argument was, without evaluating it first.
def quote(exp):
# (quote e1)
return exp[1]
And it works as expected:
>>> interpret('(quote a)')
'a'
>>> interpret("'a")
'a'
>>> interpret("'(a (b (c) d))")
'(a (b (c) d))'
atomThe next case, atom determines whether the value of exp is atomic or not.
def atom(exp, env):
# (atom e1)
val = eval(exp[1], env)
return 't' if is_atom(val) else 'f'
Our Lisp does not have any boolean datatypes, so we simply return the atoms t or f depending on whether exp is an atom or not.
>>> interpret("(atom 'a)")
't'
>>> interpret("(atom '(a b c))")
'f'
>>> interpret("(atom (atom 'a))")
't'
eqThe eq function is defined as t if the value of its two arguments evaluates to the same atom.
def eq(exp, env):
# (eq e1 e2)
v1 = eval(exp[1], env)
v2 = eval(exp[2], env)
return 't' if v1 == v2 and is_atom(v1) else 'f'
>>> interpret("(eq 'a 'a)")
't'
>>> interpret("(eq 'a 'b)")
'f'
>>> interpret("(eq '(a) '(a))")
'f'
car and cdrThe car and cdr forms both evaluate the argument, expecting the resulting value to be a list. car returns the first item of the list; cdr returns the rest of the list, i.e. everything but the first element.
def car(exp, env):
# (car e1)
return eval(exp[1], env)[0]
def cdr(exp, env):
# (cdr e1)
lst = eval(exp[1], env)
return 'nil' if len(lst) == 1 else lst[1:]
Notice that if the list contains only one element, cdr return the atom nil which represents the empty list.
>>> interpret("(car '(a b c))")
'a'
>>> interpret("(cdr '(a b c))")
'(b c)'
>>> interpret("(cdr '(a))")
'nil'
conscons, short for construct, returns a list constructed with the value of the first argument as the first element, and the value of the second argument as the rest of the list.
def cons(exp, env):
# (cons e1 e2)
rest = eval(exp[2], env)
if rest == 'nil':
rest = []
return [eval(exp[1], env)] + rest
Once again, we treat nil as the empty list.
>>> interpret("(cons 'a '(b c))")
'(a b c)'
>>> interpret("(cons 'a 'nil)")
'(a)'
condThe expressions passed as arguments to cond are all lists of two elements. We evaluate the first element of each of the sublists in turn, until one evaluates to t. When the first t is found, the second element of that list is evaluated and returned.
def cond(exp, env):
# (cond (p1 e1) (p2 e2) …)
for p, e in exp[1:]:
if eval(p, env) == 't':
return eval(e, env)
Like in McCarthy's original Lisp, our cond is also undefined for cases where no p expressions evaluate to t.
>>> program = """
... (cond ((eq 'a 'b) 'first)
... ((atom 'a) 'second))
... """
>>> interpret(program)
'second'
defunAs noted above, the defun form isn't one of those specified by McCarthy, but we include it anyway to make the language easier to use. Evaluating a defun expression simply extends the environment where it is called with a label structure containing a lambda. The evaluation of lambdas and labels is described below.
def defun(exp, env):
# (defun my-fun (a1 …) body)
name, params, body = exp[1], exp[2], exp[3]
label = ["label", name, ["lambda", params, body]]
env.insert(0, (name, label))
return name
To see what's happening, lets look at the environment after evaluating a defun form.
>>> env = []
>>> interpret("""
... (defun pair (x y)
... (cons x (cons y 'nil)))
... """, env)
'pair'
>>> env
[('pair', ['label', 'pair', ['lambda', ['x', 'y'], ['cons', 'x', ['cons', 'y', ['quote', 'nil']]]]])]
To round of the case when the first element in exp in eval is an atom, we simply look this atom up in the environment, expecting to find a function. A new list with this function as the first element is then evaluated instead.
def call_named_fn(exp, env):
# (my-fun e1 …)
fn = lookup(exp[0], env)
return eval([fn] + exp[1:], env)
Lets try testing this by calling the pair function we defined with defun above.
>>> env
[('pair', ['label', 'pair', ['lambda', ['x', 'y'], ['cons', 'x', ['cons', 'y', ['quote', 'nil']]]]])]
>>> interpret("(pair 'a 'b)", env)
'(a b)'
lambda applicationIn the example above, pair is looked up in the environment and a new s-expression is evaluated. This new expression holds a function rather than an atom as the first element. (Actually, it holds a label with a function, but the label is stripped away in an intermediate step as explained bellow.) Thus, we end up evaluating an expression where the first element looks something like (lambda (list of parameters) body). The rest of the elements in exp are the arguments to the function. The apply function evaluates such expressions.
def apply(exp, env):
# ((lambda (a1 …) body) e1 …)
fn, args = exp[0], exp[1:]
_, params, body = fn
evaluated_args = map(lambda e: eval(e, env), args)
new_env = zip(params, evaluated_args) + env
return eval(body, new_env)
The first line separates the lambda-expression fn and the arguments. The function fn is then split further into its list of parameters and the body. The arguments are then each evaluated, before they are merged with the corresponding parameters and put into the environment. Finally, the body of the function is evaluated in this new environment.
>>> program = """
... ((lambda (x y) (cons x (cdr y)))
... 'z
... '(a b c))
... """
>>> interpret(program)
'(z b c)'
label applicationThe lambda syntax above is fine for defining normal non-recursive functions. It is also expressive enough to make recursive functions using the Y-combinator, but for this McCarthy introduces the label notation instead (which arguably is a lot easier to understand).
This evaluation case considers expressions on the form ((label name lambda-expression) arguments).
def label(e, a):
# ((label name (lambda (p1 …) body)) arg1 …)
_, f, fn = e[0]
args = e[1:]
return eval([fn] + args, [(f, e[0])] + a)
We handle this by extending the environment such that name points to the first element of e, i.e. the label expression. The lambda function is then applied to the rest of the elements of e (the arguments) in this environment, and the value returned.
Lets se an example:
>>> program = """
... ((label greet (lambda (x)
... (cond ((atom x)
... (cons 'hello (cons x 'nil)))
... ('t (greet (car x))))))
... '(world))
... """
>>> interpret(program)
'(hello world)'
And with that, we have enough of Lisp implemented to be able to start using it. Lets define a few functions.
We start with something simple, a function for checking whether lists are empty or not.
(defun null (x)
(eq x 'nil))
null returns t for any list that is without elements, and f otherwise.
> (null '(foo bar))
f
> (null (cdr '(a)))
t
We might also define the common logical operators.
(defun and (x y)
(cond (x (cond (y 't) ('t 'f)))
('t 'f)))
(defun or (x y)
(cond (x 't)
('t (cond (y 't) ('t 'f)))))
(defun not (x)
(cond (x 'f)
('t 't)))
Both and, or and not works as one would expect.
> (not 'f)
t
> (not (and 't (or 't 'f)))
f
Further we can define some functions working on lists. First append, which takes two lists as arguments, returning their concatination.
(defun append (x y)
(cond ((null x) y)
('t (cons (car x) (append (cdr x) y)))))
A couple of tests shows that it works:
> (append '(1 2 3) '(a b c))
(1 2 3 a b c)
> (append 'nil '(a b))
(a b)
Another useful function is zip, which takes two lists as arguments, returning a list of pairs where each pair consists of the corresponding elements from each of the argument lists.
(defun pair (x y)
(cons x (cons y 'nil)))
(defun zip (x y)
(cond ((and (null x) (null y)) 'nil)
((and (not (atom x)) (not (atom y)))
(cons (pair (car x) (car y))
(zip (cdr x) (cdr y))))))
The helper function pair is simply used as a convenience for creating lists of two elements.
> (zip '(a b c) '(1 2 3))
((a 1) (b 2) (c 3))
These functions are all nice and well, but one thing is still lacking.
One of the central concepts in Lisp is that code is data, and vice versa.
We already have quote which enables us to convert code into lists, but we still need some way to evaluate lists as if they were Lisp code again.
Our Lisp cannot do this yet. But, fortunately, we have enough pieces to be able to implement it within the Lisp itself!
Before we go on, lets just define a few shorthand notations for working with combinations of car and cdr. These will help keep the code a bit more concise and readable as we move on.
(defun caar (lst) (car (car lst)))
(defun cddr (lst) (cdr (cdr lst)))
(defun cadr (lst) (car (cdr lst)))
(defun cdar (lst) (cdr (car lst)))
(defun cadar (lst) (car (cdr (car lst))))
(defun caddr (lst) (car (cdr (cdr lst))))
(defun caddar (lst) (car (cdr (cdr (car lst)))))
Next, we need a function to help us look up values from an environment.
(defun assoc (var lst)
(cond ((eq (caar lst) var) (cadar lst))
('t (assoc var (cdr lst)))))
assoc takes two arguments: the variable we wish to look up, var, and a list of bindings, lst. The bindings in lst are lists of two elements, and assoc simply returns the second element of the first pair where the first element is the same as var.
> (assoc 'x '((x a) (y b)))
a
> (assoc 'y '((x a) (y b)))
b
With this, we are ready to implement the eval function:
(defun eval (exp env)
(cond
((atom exp) (assoc exp env))
((atom (car exp))
(cond
((eq (car exp) 'quote) (cadr exp))
((eq (car exp) 'atom) (atom (eval (cadr exp) env)))
((eq (car exp) 'eq) (eq (eval (cadr exp) env)
(eval (caddr exp) env)))
((eq (car exp) 'car) (car (eval (cadr exp) env)))
((eq (car exp) 'cdr) (cdr (eval (cadr exp) env)))
((eq (car exp) 'cons) (cons (eval (cadr exp) env)
(eval (caddr exp) env)))
((eq (car exp) 'cond) (evcon (cdr exp) env))
('t (eval (cons (assoc (car exp) env)
(cdr exp))
env))))
((eq (caar exp) 'label)
(eval (cons (caddar exp) (cdr exp))
(cons (pair (cadar exp) (car exp)) env)))
((eq (caar exp) 'lambda)
(eval (caddar exp)
(append (zip (cadar exp) (evlis (cdr exp) env))
env)))))
(defun evcon (c env)
(cond ((eval (caar c) env)
(eval (cadar c) env))
('t (evcon (cdr c) env))))
(defun evlis (m env)
(cond ((null m) 'nil)
('t (cons (eval (car m) env)
(evlis (cdr m) env)))))
As you see, the Lisp version of eval is very similar to the one we implemented in Python, both in structure and how it works. Lets see a couple of examples.
> (eval '(cons x '(b c)) '((x a) (y b)))
(a b c)
> (eval '(f '(bar baz)) '((f (lambda (x) (cons 'foo x)))))
(foo bar baz)
We have the Lisp implemented in terms of the Lisp itself.
We have now seen a full implementation of the original Lisp, and the final result is, of course, available on github.
The core of the language is pretty small. Given only a handful of axiomatic forms, implemented in Python, we were actually able to implement the rest of the language in itself. This implementation even included an eval function, able to interpret any new Lisp code (which makes this an example of a meta-circular interpreter).
Of course, while being a neat little language, our Lisp is missing a lot of features we expect in programming languages today. For example, it has no side effects (no IO), no types other than atoms (e.g. no numbers, strings, etc), no error handling, and it has dynamic rather than lexical scoping. The behaviour is also undefined for incorrect programs, and as an effect of this the error messages (which would bubble up from Python) can be rather strange and uninformative at times.
Most of this could easily be rectified, though. Either from within the Lisp itself, or by changing the Python implementation. To learn about some of the improvements that could be made, notably lexical scoping and mutable state, I reccomend to have a look at The Art of the Interpreter by Steele and Sussman.
I hope this blogpost have peaked your interest in how programming languages work, and that you find the implementation of Lisp as delightful as I do.