a11ce.com/talk-to-computers.html
This page is adapted from my Feb 2026 5MoF talk.
The original slides are here.
Let's say we want to tell a computer to add 1 and 1:
add 1 1This is unambiguous. Yay! How about adding 1 to the result of multiplying 2 and 3?
add 1 multiply 2 3Or adding 1 to the result of multiplying 2, 3, and 4?
add 1 multiply 2 3 4 ; This is backwards forthBut wait, what if we actually want to add 1, the result of multiplying 2 and 3, and 4? Let's use parentheses for grouping.
add 1 (multiply 2 3) 4Okay cool, now we can represent whatever math we want.
add 1 1.5 (multiply 2 3 4)What about calculating two things in the same program? We can put them on different lines:
add 1 1.5
multiply 2 3 4But now we have a whitespace-sensitive language and that sucks, so let's add parentheses to top-level expressions too.
(add 1 1.5)
(multiply 2 3 4)And now we can do stuff like this:
(add 1 1.5) (multiply 2 3 4)And our old math problem
add 1 multiply 2 3becomes
(add 1 (multiply 2 3))We're actually looking at a tree structure here, where the first element of a list is the node label and the rest of the elements are subnodes.
To evaluate it, we resolve operations from the bottom up. (If we went
top-down, then our add operation would have to handle lists
like (mul 2 3) instead of just numbers like 1
and 6.)
This is cool because trees are everywhere in computing! Filesystems, HTML, object class hierarchies, Source engine maps, etc. If you have a tree, you can represent this type of nested computational structure.
If you don't, it's really easy to get one. Start with a string,
"(add 1 (multiply 2 3))"split on parens and whitespace to get a list of tokens,
; a trick here is to replace "("/")" with " ( "/" ) "
; then just split on whitespace
["(", "add", "1", "(", "multiply", "2", "3", ")", ")"]then, starting with an empty list for the top-level expressions,
for each token:- if it's an open paren, start a new sublist- if it's a close paren, end the current sublist and add it to the list above it- otherwise, add the token to the current sublistto get
["add", "1", ["multiply", "2", "3"]]As a shorthand, let's use 'add to mean the unevaluated token "add". So our parsed expression can be written as
['add '1 ['multiply '2 '3]]and we can evaluate '2 to the number 2. This gives us our first evaluation rule:
1. Numbers evaluate to themselves.What about 'add? It evaluates to a function that adds numbers, but we need some way of mapping the name 'add to the thing that it refers to. This mapping is called the environment:
{'add: <function that adds numbers>}and gives us our second evaluation rule:
2. Other non-lists are names, and evaluate to whatever the environment says the name means.Now we can start doing math:
3. To evaluate a list,...['multiply '2 '3]...first evaluate each element of the list...[multiply 2 3]...then call the first element (which must be a function) with the other elements as arguments.6Let's use these three rules to evaluate
['add '1 ['multiply '2 '3]]Since this is a list, the first step is to evaluate each element of the list. For the first two elements, look up 'add in the environment to get the addition function, and '1 is a number so it evaluates to 1.
The third element is itself a list. Following the evaluation rules, we evaluate the elements of the sublist (one environment lookup and two numbers) to get
[multiply 2 3]then call multiply with the arguments 2 and 3 to get 6. After evaluating all the elements of our top-level expression, we end up with
[add 1 6]and finally call add with the arguments 1 and 6 to get 7.
Notice that these rules lead to the same sort of bottom-up evaluation as the tree from earlier, even though they start with the top-level expression!
Let's add some more stuff to our language:
(if (whatever)
(print "yes")
(print "no"))Three additions: First, we need booleans and strings.
Implicit in our number evaluation rule is that the language has some way of knowing when a token represents a number. We can simply extend that to booleans (written as '#t or '#f) and strings (written as '"meow"). These are called values, and our first rule is now:
1. Values evaluate to themselves.Second, we need to add print to our environment. We can do that explicitly, or, if we're implementing our language using a language with a built-in print, then we can choose to implicitly fall back to the definition of a name from the perspective of the interpreter itself.
This is not a normal thing that most languages do! It tightly couples the language you're defining to the interpreter language, and can punch a hole in whatever interesting semantics you want your language to have. On the other hand, it's a neat trick to get a bunch of functionality for free, and is pretty useful for writing a language that interacts with or embeds into an existing system. Also, if you plan for this behavior when defining your interpreter, then you can write the interpreter mostly in the language you're interpreting.
So, with the interpreter fallback, our second rule is now:
2. Other non-lists are names, and evaluate to whatever the environment says the name means. If the environment doesn't define the name, check our own definition of it.Third, evaluating an if statement according to our existing rules is no good:
; first, evaluate the if to get the if function.
(if
; then, evaluate the condition.
(whatever)
; then, evaluate the true branch. This prints yes.
(print "yes")
; then, evaluate the false branch. This prints no.
(print "no"))
; finally, call the if function with the other
; elements as args, which prints either yes or no again.Some things that look like function calls actually need special handling. These are called special forms, and are marked as such in the environment:
{'if: special: checks the condition then evaluates only one branch}We need to update rule three:
3. To evaluate a list,1. If the first element evaluates to a special form, call the special form with the other elements unevaluated.2. Otherwise, evaluate each element of the list then call the first element (which must be a function) with the other elements as arguments.Another special form is define:
(define x (add 1 2)){'define: special: evaluates the second arg, adds its value to the environment with the first arg as its name}Last but not least, we need a way to define our own functions. Enter lambda. The first argument is a list of parameter names, and the second argument is what the function does. For example,
(lambda (x) (add x x))evaluates to a lambda object (a new type of value!) that doubles its argument. It can be used in place of a function name or special form:
((lambda (x) (add x x)) 1) -> 2{'lambda: special: evaluates to a value that contains the parameter names, function body, and current state of the environment. when this value is called as a function, it extends the stored environment with the parameter names defined as the values that it was called with, then evaluates the body with that environment}Why do we need to store the current environment? Because lexical scope is awesome.
Since lambda objects are values, we can use define to give them names:
(define double (lambda (x) (add x x)))
(double 2)
-> 4Finally, let's update rule three:
- If the first element evaluates to a lambda object, do the lambda thing.and our complete rules become:
1. Values evaluate to themselves.2. Other non-lists are names, and evaluate to whatever the environment says the name means. If the environment doesn't define the name, check our own definition of it.3. To evaluate a list,1. If the first element evaluates to a special form, call the special form with the other elements unevaluated.2. If the first element evaluates to a lambda object, do the lambda thing.3. Otherwise, evaluate each element of the list then call the first element (which must be a function) with the other elements as arguments.THIS IS LISP!!!!!!
These rules (plus whatever you want defined in the initial environment) are really all you need for a perfectly functional programming language, and you can implement them in all kinds of non-obvious contexts. Try it out!