Lisp is a programming language that is often used didactically in higher education for its simplicity and minimal syntax. Sounds fancy, right? I wouldn't know to be honest, and I didn't make it all the way through the third grade to have you judge me.
Anyways, in a few paragraphs, you'll be able to read & write Lisp! By the end of this article we'll have implemented Lisp style evaluation with our programs provided as JSON, or JSON Lisp™, to be precise.
Lisp Crash Course
If you're familiar with Lisp feel free to skip this crash course introduction and jump straight to JSON Lisp where stuff gets weird.
Symbolic Expressions (S-expressions)
Lisp uses something called S-expressions for its syntax. An expression is an entity that may be evaluated to determine its value. In Lisp, everything is an expression. Let's take a look at some Lisp Expressions that are also valid JavaScript expressions.
; semicolon is how you introduce a comment in lisp
; (the // in JavaScript)
4 ; Value: 4
"hello" ; Value: "hello"
true ; Value: #t (that means true)These are called primitive values. Primitive values and expressions aren't the only concepts shared with JavaScript though, Lisp also has function calls! However, the syntax for them is different. They are wrapped in parentheses which makes the order of evaluation unmistakable. Arguments are separated by a space instead of a comma.
; --- This is the name of the function.
; |
; |
; ˅
(+ 1 2) ; Value: 3
; ˄ ˄
; | |
; | |
; | |
; ------ These are the arguments to the "+" function,
; arguments are separated by a space.It's a little weird to see + before 1 & 2, instead of in-between it.
That's called prefix notation.
It's also a bit odd to see an operator like + referred to as a function. Here
are a bunch of JavaScript next to Lisp examples to make this more concrete.
Operators
JavaScript
Operators are built-in with infix notation and you only need to provide parenthesis to opt-out of the built-in order of operations.
3 * 3 + 3; // 12
3 * (3 + 3); // 18Lisp
Operators are just function calls. Parenthesis are always provided which means special syntax is not required to override built-in operator precedence, the developer always has to provide it.
(+ (* 3 3) 3) ; Value: 12
(* 3 (+ 3 3)) ; Value: 18Methods
JavaScript
In JavaScript, some operations are provided as functions on the object's
prototype. The value on the left becomes this in the implementation of
toUpperCase. Don't be deceived by the special method syntax, they're also
functions you can reference directly.
"hello".toUpperCase(); // 'HELLO'
String.prototype.toUpperCase.call(["h", "i"]); // 'H,I'
// An Array? Yes. How? Coercion. Why? Life is pain.Lisp
Same situation in Lisp as we had for operators, function on the left, arguments on the right.
(string-upcase "hello") ; Value: "HELLO"Function Calls
JavaScript
Function calls have the name of the function on the left, some parentheses to indicate calling that function, and arguments are provided in the parenthesis.
parseInt("3"); // 3Lisp
Same situation as operators and methods. Function on the left, arguments on the right.
(parse-integer "3") ; Value: 3Notice how in JavaScript, special syntax is used for operators, method calls & function calls? In Lisp, they all use the same syntax! Suddenly it checks out why the brainiacs use it.
Lisp Evaluation
Lisp evaluates a program with a strategy called Applicative order. Applicative order means that innermost arguments are evaluated before they are provided to their function in Lisp.
(+ 1 (+ 2 3))
; ˄ ˄
; | |
; | |
; | - Value: 5
; |
; Value: 1
;
; (+ 1 5)
; ; Value 6, All done!All the Lisp examples we've seen thus far have been evaluated this way!
You'll notice Applicative order seems a great deal like what you're used to in JavaScript! JavaScript uses a similar strategy called Call by sharing which is very similar to Applicative order but differs in some important ways.
Special Forms
Unfortunately, there are some exceptions to this simple evaluation strategy.
Since arguments are evaluated before they are provided to their function in
Lisp, certain types of constructs can't be evaluated this way. Let's explore a
hypothetical broken if-else function in Lisp to clarify this.
Lisp
; Given Applicative Order, arguments are evaluated before applying `if`.
(if-else (> 2 1) (+ 5 5) (+ 2 2)) ; Evaluate the arguments first.
; | | |
; ˅ ˅ ˅
;(if-else true 10 4)
; ˄
; |
; |
; - Cripes! We executed the else branch
; even though we shouldn't have!
; Value: 10Since the arguments were evaluated before they were provided to the if-else
function we end up evaluating the else branch even if we shouldn't. Here is a
JavaScript interface to this problem:
JavaScript
// By the time ifElse gets the arguments, it's too
// late. As they say, "Young Herc was mortal now."
ifElse(2 > 1, 5 + 5, 2 + 2);To solve this problem Lisp keeps the same syntax but treats the evaluation for those entities differently. This handful of specially interpreted expressions are called special forms. Special forms look like normal function calls, however, the interpreter treats them, specially.
Lisp
(if (> 2 1) (+ 5 5) (+ 2 2))
; ˄
; |
; Lisp understands `if` is different,
; it evaluates the conditional first
; to determine what to do next.
;
;(if true (+ 5 5) (+ 2 2))
; ˄
; |
; Now this will be evaluated but
; (+ 2 2) will never be evaluated.
; Value: 10See how Lisp knows that if is different? Special even? Worthy of a noble
treatment indeed!
Alright, that's everything we need to know to start our JSON Lisp journey.
Lisp in JSON
Let's migrate our Lisp examples into a JSON syntax.
Our basic primitive values, like 4, "Hello" and true hold-up just fine as
values in JSON. So we don't need to do anything there. Things start to get
interesting when we look at expressing function calls in JSON. Which, if you
remember from our Lisp crash course above, buys us operators and methods too.
Function Calls
To represent function calls in JSON let's take a look at our addition example.
Lisp
(+ 1 2)Unfortunately for us the elegant parenthesis, (), are invalid symbols in JSON.
Fortunately, their rectilinear cousins [] are totally valid. So let's swap
those. While we're at it whitespace is insignificant and will be thrown out by
most JSON deserializers/parsers, so we'll use the , as our separator. These
two modifications alone, give us a mechanism for expressing the above program in
JSON.
JSON Lisp
["+", 1, 2]Let's look at our other examples in light of these rules.
Example JSON Lisp Programs
JSON Lisp Operators
["*", 3, ["+", 3, 3]]JSON Lisp Methods
["uppercase", "hello"]JSON Lisp Function Calls
["alert", ["uppercase", "Life is dope."]]JSON Lisp Special Forms
["if", [">", 2, 1], ["+", 5, 5], ["+", 2, 2]]
// ˄ ˄ ˄
// | | |
// | | |
// condition if true otherwiseTurns out that Lisp's simple S-expression syntax make it pretty easy to model
in JSON.
JSON Lisp Implementation
Our JSON Lisp implementation will be done in TypeScript.
TypeScript, so hot right now. - Mugatu
Lexical Analysis & Parsing
First things first, programming language implementations typically need a mechanism for taking the source program, a string of text, and turning it into a structure that the interpreter or compiler can work with, this is called a parse tree The parse tree is often subsequently converted into an abstract syntax tree for further analysis, however, our implementation will interpret the parse tree directly. So what do we need for the lexer and parser? Get ready.
export const parse = JSON.parse;Yup, JSON.parse. Takes care of our lexing and parsing. It converts values
nicely and even gives useful syntax errors. Out of the gate, our JSON Lisp will
have a great headstart for other host language implementations!
The growth of modern streaming architectures & streaming JSON parsers raises an interesting possibility I'd love to explore further (or hear about if you explore it) around streaming evaluation, or the ability to evaluate the program as it is downloaded and parsed. This would make JSON Lisp or something like it a really interesting general-purpose format for primarily server rendered architectures with persistent views that emit instructions to the client using Web Sockets like Phoenix Live View.
Ok, since we have a type system at our disposal we may as well add some nice type annotations for JSON.
type Json =
| null
| boolean
| number
| string
| Json[]
| { [prop: string]: Json };
export const parse = (source: string): Json => JSON.parse(source);Evaluation
To evaluate a JSON Lisp expression we'll provide a function called evaluate.
Which will take in a JSON Lisp expression, the return value of parse above,
and an environment. The environment is the context the program will be run
in. The environment will contain the implementations of our built-in operators
and provide us a place for storing user-land function definitions and values.
You can think of the environment as the global namespace in a browser window.
There are some built-in functions you can call that are implemented in the host
language like alert. It also contains functions that you put there.
So our Environment type will be a map of identifiers (global names) to either
JSON (user-land implementations) or to JavaScript Functions (host language
provided functions).
// The environment is a map of identifiers to values.
type Environment = {
[name: string]: JSON | Function
// ˄ ˄
// | |
// | |
// user host
};
export const evaluate = (
expression: Json,
environment: Environment
) => {
// TODO Write the evaluator
};Applicative Order Evaluation
In Applicative Order evaluation, each expression is evaluated before providing it to its function. For our base case, we'll evaluate each of the arguments along with the function recursively as we walk down the expression tree, and we'll apply our evaluated procedures on the way up (in Lisp the function is often called the procedure).
When we encounter a string, we'll look up its function implementation in the environment often called a procedure in Lisp, or by the OG programmers of 20+ years ago.
export const evaluate = (expression: Json, environment: Environment) => {
// When we encounter an expression, `[ ]`
if (Array.isArray(expression)) {
// Evaluate each of the sub-expressions
const result = expression.map((expression) =>
evaluate(expression, environment)
);
// If there is nothing to apply, we have a value.
if (result.length === 1) {
return result[0];
} else {
// Retrieve the procedure from the environment
const procedure = result[0];
// Apply it with the evaluated arguments
return procedure(...result.slice(1));
}
} else {
// Look up strings in the environment as references.
if (
typeof expression === "string" &&
environment.hasOwnProperty(expression)
) {
return environment[expression];
}
// Return values.
return expression;
}
};This is enough to implement our operator examples! In fact, with this small
implementation we can implement the 1.1 exercises from MIT's famous
Structure & Interpretation of Computer Programs.
const add = (...args) => args.reduce((x, y) => x + y);
const subtract = (...args) =>
(args.length === 1 ? [0, args[0]] : args).reduce((x, y) => x - y);
const division = (...args) =>
(args.length === 1 ? [1, args[0]] : args).reduce((x, y) => x / y);
const multiplication = (...args) => args.reduce((x, y) => x * y, 1);
// We provide the environment that references read from here.
const defaultEnvironment = {
"+": add,
"-": subtract,
"/": division,
"*": multiplication,
};
expect(
evaluate(10, defaultEnvironment)
).toEqual(10);
expect(
evaluate(["+", 5, 3, 4], defaultEnvironment)
).toEqual(12);
expect(
evaluate(["-", 9, 1], defaultEnvironment)
).toEqual(8);
expect(
evaluate(["/", 6, 2], defaultEnvironment)
).toEqual(3);
expect(
evaluate(["+", ["*", 2, 4], ["-", 4, 6]], defaultEnvironment)
).toEqual(
6
);
expect(
evaluate(["+", ["*", 2, 4], ["-", 4, 6]], defaultEnvironment)
).toEqual(
6
);Other Functions
With that, the pattern for adding functions to call is to provide their
implementations on the environment and then reference them by name in the left
most position in our JSON Lisp S-Expression.
For example, we could add uppercase to our environment:
evaluate(["uppercase", "Hello world!"], {
uppercase: (str) => str.toUpperCase(),
});Using strings to double as identifiers creates a weird class of bugs, what if I mean the string
"uppercase"instead of the functionuppercase? To solve this a special form could be introduced for reading identifiers or expressing strings. E.G.["Text", "Hello world!"]
Special Forms
As we explored above, certain constructs can't be implemented as functions using
strict applicative order evaluation, for example, if. Let's explore adding a
special form for handing if.
["if", true, ["+", 2, 2], 0];
// ˄ ˄ ˄
// | | |
// | | Else branch
// | Run this only if the predicate is true
// Evaluate the predicate first
// returns 4The way we'll go about this is checking to see if the expression reflects one of our special forms before we evaluate. If it does we'll evaluate it specially, if it doesn't we'll evaluate and apply as usual!
In the case of if, we'll first evaluate its predicate. Depending on the value
returned we'll then subsequently evaluate the correct branch.
export const evaluate = (expression: Json, environment: Environment) => {
if (Array.isArray(expression)) {
const procedure = expression[0];
// Look for special forms based on the first array entry.
switch (procedure) {
// Check if we have a special form!
case "if": {
// Retrieve the predicate
const predicate = expression[1];
// Evaluate the predicate in the environemnt
if (evaluate(predicate, environment)) {
// If it is true evaluate the first branch
return evaluate(expression[2], environment);
} else {
// If it is false evaluate the false branch,
// if one is provided.
if (expression[3]) {
return evaluate(expression[3], environment);
} else {
return null;
}
}
}
// Time for some applicative order evaluation Ma!
default: {
const result = expression.map((expression) =>
evaluate(expression, environment)
);
if (result.length === 1) {
return result[0];
} else {
const procedure = result[0];
return procedure(...result.slice(1));
}
}
}
} else {
// Nothing changed here.
if (
typeof expression === "string" &&
environment.hasOwnProperty(expression)
) {
return environment[expression];
}
return expression;
}
};Sweet! Now we've got support for conditional branching in our JSON Lisp!
expect(evaluate(["if", true, ["+", 1, 1]])).toEqual(2);
expect(evaluate(["if", false, 1, ["+", 1, 2]])).toEqual(3);
// If an else branch isn't provided return a null value.
expect(evaluate(["if", false, 1])).toEqual(null);With, that the pattern for adding special forms is to add additional branches to
the switch statement.
Summary
At this point, our JSON Lisp implementation is in a place where we can add more special forms and provide new function implementations. I hope that this toy implementation illuminated some dark corners about how programming languages work. At the least, I hope you had fun!
You can play with JSON Lisp here by
cloning the repository and running yarn test.
Some suggestions for taking this a step further:
- Implement
definefor creating new abstractions on the environment, variables, and functions! Can prototypical inheritance be used to mimic a stack for function variable scoping? - Implement additional special forms!
- Someone please explore streaming evaluation and tell me how it goes!