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); // 18

Lisp

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: 18

Methods

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"); // 3

Lisp

Same situation as operators and methods. Function on the left, arguments on the right.

(parse-integer "3") ; Value: 3

Notice 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: 10

Since 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: 10

See 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     otherwise

Turns 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 function uppercase? 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 4

The 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:

1. Implement define for creating new abstractions on the environment, variables, and functions! Can prototypical inheritance be used to mimic a stack for function variable scoping?
2. Implement additional special forms!
3. Someone please explore streaming evaluation and tell me how it goes!