Lisp evaluation is kinda elegant. Although it can be difficult to fully understand at a deep level, particularly if you have already been "programmed" in programming.
The first interesting thing is that there is a difference between the textual representation of a Lisp program, and the data structure in memory that is generated when a text chunk is parsed. For example, given a string of Lisp code:
(+ 2 (+ 2 3))
If we were building a Lisp interpreter in Javascript would be parsed into this:
["+", "2", ["+", "2", "3"]]
But of course what you are reading now is a text document, so this thing just above is actually JSON, which is a textual representation of a Javascript array (of arrays). I cannot "show" what the internal representation of this parsed text is because I must show it as text.
Anyway, the parsing of a Lisp string is fairly easy. I always like to do it in two passes, because it makes each function of the two passes really simple. The first pass is a "tokenizer" which given this (+ 2 (+ 2 3)) would produce (again, in JSON):
["(", "+", "2", "(", "+", "2", "3", ")", ")"]
So a flat list of all the tokens including the parentheses. This makes it much easier to have quoted strings like:
(frobulate "a sentence with spaces")
["(", "frobulate", "a sentence with spaces", ")"]
A second pass converts the flat array into a tree-like structure. Given our example (+ 2 (+ 2 3)):
["+", "2", ["+", "2", "3"]]
So we use the presence of a "(" token to know that we are beginning a new sub-list.
And that's basically it regarding parsing. You end up with arrays of arrays or tokens. There are a few subtleties to this, but more or less good enough for now.
This arrays of arrays or tokens structure is also enough for our data needs. Most programmers use hash maps as key-value lookup tables, which can be inefficiently but simply expressed as an array of key and value pairs, eg:
[
["key1", "val1"],
["key2", "val2"],
]
Where finding a value for a key means iterating over all the pairs looking for a match. We need something like this for evaluating functions. Let's think a bit about what it means to evaluate a function. Let's say we have a graph of y = x^2 + 10. This is a classic parabola, shifted on the Y axis up by 10 units. In math we can express this as so:
f(x) := x^2 + 10
Meaning we are declaring a function called "f" which takes "x" as a parameter and evaluates to something. In a Python it might look like:
def f(x):
return (x ** 2) + 10
Or Javascript:
function f(x) {
return (x ** 2) + 10;
}
But how do these functions actually get executed? In these languages the answer is more complicated than what I am about to describe, but in general you can describe it as follows:
For our example function x^2 + 10 we know the "2" and the "10" because they are constants. The "^", the "+" are built-in operators. But we don't know the "x". What if we had a key-value store like:
[
["x", "3"]
]
And we had some function that was going to evaluate called eval, we might call eval like this:
eval(<x^2 + 10>, [["x", "3"]]);
As we are evaluating our function when we encounter a symbol ("x") that we don't know, we look this symbol up in the key-value store and replace the symbol with that value, "3" in this case. So our function would look like:
3^2 + 10
And our eval function now has everything it needs to execute. This is called "binding": we are taking all the unknown variables (or symbols) in our function definition and replacing their values with the bindings we passed.
Now imagine we re-write our x^2 + 10 function in a Lisp-ish way:
(+ 10 (^ x 2))
This gets parsed into a data structure:
["+", "10", ["^", "x", "2"]]
And our eval function now gets this:
eval(["+", "10", ["^", "x", "2"]], [["x", "3"]]);
I bet you would have a pretty good shot at implementing the eval function, right? You iterate over the functions structure that was passed. The first element of each array is the operator. You then iterate over the remaining elements in the list. If an element is not another list then you try a lookup in the key-value store. If the symbol is not in the lookup then you take it as-is. If it is in the lookup store you replace it with that value. If you encounter an array you recursively call eval again. Once all the arguments to your operator are all "resolved" you execute the operator and return the result. So for ["+", "10", ["^", "x", "2"]] it would go something like this:
eval recursively on each one.eval on the "10" it does not exist in the key-value lookup so we return "10".eval on ["^", "x", "2"] we are running a sub-expression.eval recursively on each one.eval on the "x" it is in the lookup table so we return "3".eval on the "2" we simply return "2".Let's try that in Javascript, renaming eval to myEval to avoid clashing with Javascripts eval:
function myEval(exp, lookup) {
if (<exp is not an array>) {
return findInLookup(exp, lookup);
}
let operator = exp[0];
let args = [];
for (let i = 1; i < exp.length; i++) { // note: we start at 1, not 0
args[i] = myEval(exp[i], lookup);
}
return runBuiltin(operator, args);
}
Provided we can:
exp is an array or not (which is surprisingly stupid in Javascript).findInLookup function.runBuiltin function that understands how to add two numbers, and run Math.pow() or something for our "^" operator.We should be basically good. Now, let that really sink in and perhaps even go away and try to actually write it and get it running. Once it sinks in really good proceed to the next mind-blowing thing: defining functions within our mini Lisp.
Remember we did: return findInLookup(exp, lookup)? And remember way up we defined f(x) := x^2 + 10? What if we could put something in our lookup table called "f"?
[
["f", ...]
]
Let's try putting our function body in there:
[
["f", ["+", "10", ["^", "x", "2"]]]
]
Now we can try evaluating:
myEval(["f", "3"], lookup);
When the myEval function runs this it is going to think that "f" is an operator and call runBuiltin function with it. So we clearly need to do our lookup on the operator as well as the arguments. So if we do that we transform our input expression ["f", "3"] into this:
[
["+", "10", ["^", "x", "2"]],
"3"
]
We almost know what to do here. We clearly need to make a new lookup table that has "x" set to "3", and then we can myEval the expression that "f" got turned into with that new lookup table. But there are two problems: 1) we don't know what name to assign to the "3", and 2) we don't know that we have to do this process at all. So we now modify our definition of "f" in the lookup table:
[
["f", [
"lambda",
["x"],
["+", "10", ["^", "x", "2"]],
]]
]
I have tried to make that clear with indentation, but perhaps it's not that clear. We are saying that the symbol "f" resolves to a "lambda expression", so the first element is the symbol "lambda". The second element is a list of the names of the arguments to our function, in this case just "x". And the third element is our function body.
Now, when myEval runs it can do the lookup and resolve "f" to this structure. It can then check if this is an array, and look for the magic "lambda" operator. If it sees that it can iterate over the ["x"] array, building up a new lookup table from the argument names and the evaluated arguments passed when we called ["f", "3"], in this case just "3". We can then shoot the function body back into myEval with the new lookup table.
Boom - we can now evaluate our own custom functions:
function myEval(exp, lookup) {
if (<exp is not an array>) {
return findInLookup(exp, lookup);
}
let evaled = exp.map(function(el) {
return myEval(el, lookup);
});
let operator = evaled.shift();
if (<operator is an array> && operator[0] == 'lambda') {
let nlookup = [];
for (let i = 0; i < operator[1].length; i++) {
let name = operator[1][i];
let value = evaled[i];
addToLookup(name, value);
}
return myEval(operator[2], nlookup);
}
return runBuiltin(operator, evaled);
}
Here we do something a bit different:
exp.That was a nice trick, but it's just smoke an mirrors. We are building a Lisp-ish evaluator inside a language that actually has many Lisp-ish attributes itself. This is totally cheating. Firstly we are evaluating everything recursively. This means we are using the Javascript call stack to store all our temporary values while we evaluate sub-expressions. We are also making good use of Javascript's garbage collection, so we don't need to clean up stuff or worry about if we are shallow-copying things or deep-copying things. But it's still a nice trick because it shows you kinda what a "function that runs functions" looks like.