Try the TINYLISP REPL live at: https://daneelsan.github.io/tinylisp/

TINYLISP is a minimal Lisp interpreter implemented in Zig, compiled to WebAssembly, and embedded in a web-based terminal emulator. It supports core Lisp features like atoms, lists, conditionals, arithmetic, and closures, along with an interactive REPL and debugging tools for inspecting the heap, stack, and environment.

I was inspired to build this project by the following paper: Lisp in 99 lines of C and how to write one yourself - Robert-van-Engelen.

Why Build Another Lisp Interpreter?

Lisp is one of the oldest programming languages, known for its simplicity and elegance. Building a Lisp interpreter is a great way to learn about language design, parsing, and evaluation. By implementing TINYLISP in Zig and compiling it to WebAssembly (WASM), I also got to explore how low-level systems programming can integrate with web technologies.

Features

TINYLISP supports the following core features:

  • Atoms: Symbols like #t (true) and ERR (error).
  • Lists: Constructed using cons, car, and cdr.
  • Arithmetic: Basic operations like +, -, *, and /.
  • Conditionals: if, and, or, and not.
  • Closures: Lambda functions and lexical scoping.
  • REPL: An interactive read-eval-print loop.
  • Debugging Tools: Inspect the heap, stack, and environment.

Here’s an example of TINYLISP in action:

λ (+ 1 2 3 4)
10

λ (define square (lambda (x) (* x x)))
square

λ (square 5)
25

Implementation in Zig

The core of TINYLISP is implemented in Zig, a modern systems programming language designed for performance, safety, and simplicity. Zig’s low-level control and lack of hidden costs make it an excellent choice for building interpreters. Below, I’ll break down the key components of the Zig implementation.

NaN Boxing for Efficient Memory Representation

One of the most interesting aspects of TINYLISP is its use of NaN boxing to represent Lisp expressions efficiently. NaN boxing is a technique that leverages the unused bits in IEEE 754 floating-point numbers to store additional information, such as type tags. In TINYLISP, every expression is represented as a 64-bit floating-point number (f64), with the following structure:

  • Tag Bits: The upper 16 bits are used to store a type tag (e.g., ATOM, CONS, PRIM, etc.).
  • Ordinal Bits: The lower 48 bits store the actual data (e.g., an index into the heap or stack).

This approach allows TINYLISP to represent different types of data (atoms, pairs, numbers, etc.) in a compact and efficient way.

The Lisp Interpreter

The interpreter is implemented as a Lisp struct, which manages the heap, stack, and environment. Here’s an overview of its key components:

  1. Heap and Stack:
    • The heap stores atom names (symbols) as strings.
    • The stack stores Lisp expressions (e.g., pairs, numbers, closures).
  2. Atoms:
    • Atoms are interned strings, meaning each unique symbol is stored only once in the heap.
    • The atom function checks if a symbol already exists in the heap; if not, it adds it.
  3. Pairs and Lists:
    • Pairs are constructed using the cons function, which allocates two cells on the stack.
    • The car and cdr functions retrieve the first and second elements of a pair, respectively.
  4. Evaluation:
    • The eval function evaluates Lisp expressions in a given environment.
    • It handles atoms, pairs (function application), and primitive operations.
  5. Primitive Functions:
    • TINYLISP includes a set of built-in functions like +, -, car, cdr, and lambda.
    • These are implemented as Zig functions and stored in the environment.
  6. Garbage Collection:
    • TINYLISP uses a simple garbage collection strategy: it resets the stack pointer to the environment’s location after each evaluation.

Compiling to WebAssembly

To make TINYLISP accessible in the browser, I compiled the Zig code to WebAssembly. WebAssembly is a binary instruction format that runs at near-native speed in web browsers.

This interface allows Javascript to initialize the Lisp interpreter and execute Lisp code.

The Terminal Emulator

The TINYLISP REPL runs in a web-based terminal emulator built with Javascript and HTML. This terminal emulator provides an interactive environment where users can type Lisp expressions, see the results, and debug their code. Below, I’ll break down how the terminal emulator works, from handling user input to communicating with the WebAssembly module.

Overview of the Terminal

The terminal emulator is a simple web application that consists of:

  1. HTML Structure: A <div> for the output and a <textarea> for input.
  2. Javascript Logic: Handles user input, communicates with the WASM module, and updates the terminal output.
  3. WebAssembly Module: The TINYLISP interpreter compiled to WASM.

The terminal is styled with CSS to resemble a classic command-line interface, with a fixed-width font and a dark background.

Handling User Input

The terminal listens for user input in the <textarea> and processes it when the user presses Enter. Here’s how it works:

  1. Keydown Event Listener:
    • The terminal listens for the keydown event on the <textarea>.
    • If the user presses Enter (without Shift), a newline is inserted into the input.
    • If the user presses Shift + Enter, the input is processed.
  2. Processing Commands:
    • When the user submits a command, it is sent to the WASM module for evaluation.
    • The result is displayed in the terminal output.

Communicating with WebAssembly

The terminal communicates with the TINYLISP interpreter through a WebAssembly module. Here’s how the integration works:

  1. Loading the WASM Module:
    • The WASM module is fetched and instantiated when the page loads.
    • The WASM object provides helper functions for interacting with the module.
  2. Executing Lisp Code:
    • When the user submits a Lisp expression, it is passed to the WASM module for evaluation.
    • The result is captured and displayed in the terminal.

Debugging and Introspection

The terminal includes debugging tools for inspecting the state of the Lisp interpreter. These tools are accessible through special commands:

  • print-heap: Prints all atoms stored in the heap.
  • print-stack: Prints the current state of the stack.
  • print-env: Prints the current environment.

Here’s an example of using these commands:

λ (print-heap)
------------------- HEAP -------------------
|  #  |  address |  symbol                 |
|-----|----------|-------------------------|
|   0 |  0x0000  |  ERR                    |
|   1 |  0x0004  |  #t                     |
|   2 |  0x0007  |  eval                   |
|   3 |  0x000C  |  quote                  |
|   4 |  0x0012  |  cons                   |
|   5 |  0x0017  |  car                    |
|   6 |  0x001B  |  cdr                    |
|   7 |  0x001F  |  int                    |
|   8 |  0x0023  |  +                      |
|   9 |  0x0025  |  -                      |
|  10 |  0x0027  |  *                      |
|  11 |  0x0029  |  /                      |
|  12 |  0x002B  |  <                      |
|  13 |  0x002D  |  >                      |
|  14 |  0x002F  |  =                      |
|  15 |  0x0031  |  not                    |
|  16 |  0x0035  |  or                     |
|  17 |  0x0038  |  and                    |
|  18 |  0x003C  |  if                     |
|  19 |  0x003F  |  lambda                 |
|  20 |  0x0046  |  define                 |
|  21 |  0x004D  |  print-heap             |
|  22 |  0x0058  |  print-stack            |
|  23 |  0x0064  |  print-env              |
|  24 |  0x006E  |  echo                   |
|  25 |  0x0073  |  echo-eval              |
--------------------------------------------
()

The terminal also supports features like command history and meta commands (e.g., ?help and ?clear).

Using print-env in a Deep Call Stack

One of the most powerful features of TINYLISP is its ability to inspect the environment at any point during execution using the print-env function. This is especially useful for debugging or understanding how closures and lexical scoping work. Let’s walk through an example of defining a function with nested closures and using print-env to inspect the environment during a deep call stack.

Step 1: Define the outer Function

We’ll start by defining a function called outer that takes one argument x and returns a new function. This new function captures x in its environment and itself returns another function, creating a chain of closures. Using progn, we can both inspect the environment and compute the result in the same function.

λ (define outer
    (lambda (x)
      (lambda (y)
        (lambda (z)
          (progn
            (print-env)  ;; Inspect the environment here
            (+ x y z))))))
outer

Here, outer is a function that:

  • Takes an argument x.
  • Returns a function that takes y and captures x.
  • That function, in turn, returns another function that takes z and captures both x and y.
  • The innermost function uses progn to:
    1. Print the environment using print-env.
    2. Return the sum of x, y, and z.

Step 2: Call outer to Create Nested Closures

Now, let’s call outer with an argument to create the first closure.

λ (define f (outer 10))
f

Here’s what happens:

  • outer is called with x = 10.
  • It returns a new function that captures x = 10 in its environment.
  • This new function is assigned to the variable f.

Next, call f with another argument to create the second closure.

λ (define g (f 20))
g

Here’s what happens:

  • f is called with y = 20.
  • It returns a new function that captures x = 10 and y = 20 in its environment.
  • This new function is assigned to the variable g.

Step 3: Call the Innermost Function and Inspect the Environment

Finally, call g with a third argument to execute the innermost function. This will print the environment and return the sum of x, y, and z.

λ (g 30)
    (
        (z . 30)
        (y . 20)
        (x . 10)
        (outer . «closure»)
        (f . «closure»)
        (g . «closure»)
        (print-env . «print-env»)
        (print-stack . «print-stack»)
        (print-heap . «print-heap»)
        (progn . «progn»)
        (define . «define»)
        (lambda . «lambda»)
        (if . «if»)
        (and . «and»)
        (or . «or»)
        (not . «not»)
        (= . «=»)
        (> . «>»)
        (< . «<»)
        (/ . «/»)
        (* . «*»)
        (- . «-»)
        (+ . «+»)
        (int . «int»)
        (cdr . «cdr»)
        (car . «car»)
        (cons . «cons»)
        (quote . «quote»)
        (eval . «eval»)
        (#t . #t)
    )
60

Here’s what happens:

  • g is called with z = 30.
  • The innermost function executes, capturing x = 10, y = 20, and z = 30.
  • The environment is printed using print-env.
  • The result of (+ x y z) is computed and returned.

Challenges

Building TINYLISP was a great learning experience. Some of the challenges I faced included:

  • Implementing NaN boxing for efficient memory representation.
  • Parsing and evaluating Lisp expressions correctly.
  • Debugging WASM memory issues.

One of the most rewarding parts was seeing the interpreter come to life in the browser, thanks to WASM + JS + HTML (no dependencies needed!).