A New Year’s resolution for 2019: Make a Lisp

This project is my New Year’s resolution for 2019. My goal is to reinvigorate my programming skills by creating an interpreter for a version of the Lisp programming language.

Lisp

Lisp first appeared in 1958, one of four early programming languages (the others being FORTRAN, COBOL and Algol) that massively influenced the subsequent development of computing technology. By way of example, here is a short Lisp expression that can generate Fibonacci numbers…

(def! fibonacci  (fn* (N)
   (if (= N 0)
      1
      (if (= N 1)
         1
         (+ (fibonacci (- N 1)) (fibonacci (- N 2)))))))

A Lisp interpreter is software that can read a Lisp expression, evaluate it to produce an answer, print the answer out, and then loop back to the beginning to read the next expression. This cycle is typically referred to as a Read-Eval-Print Loop, or REPL. If I loaded the fibonacci code into a Lisp interpreter, I’d be able to run it by typing something like (fibonacci 43), to which the interpreter would respond 433494437. From the perspective of 2019, it’s now hard to appreciate the power of the REPL concept - but in 1958 it was one of the first real steps toward the interactive computing environments that we now take for granted.

Making a Lisp

I’m following instructions from the Make a Lisp website for building an interpreter for a fully featured variant of Lisp called Mal. The instructions assume a working knowledge of programming and take the form of narrative statements, not code that you can copy and paste. The instructions define a step-by-step process, in which each step gradually adds more functionality to the emerging Mal interpreter. The initial steps create quite simple interpreters (e.g. that can do basic arithmetic) but the later steps add real computing power, culminating in an interpreter powerful to itself host a Lisp interpreter. Each step is supported by a comprehensive set of tests - short expressions that exercise the features added during the step, along with output that should be generated if the step is correctly implemented. In some cases, the tests make clear the intent of the instructions for the step.

The Make-a-Lisp instructions don’t assume that you will use any specific programming language to build the interpreter. I’ve therefore chosen C# and Visual Studio, largely because they are similar to the tools I used when I wrote software professionally. I know that implementing a Mal interpreter in C# is doable, because the Make-a-Lisp website includes the full source code for a Mal interpreter written in C#, along with versions of Mal written in more than 70 different programming languages. To avoid cheating, I’m going to try to avoid looking at the C# reference implementation unless something really defeats me.

Future posts in this series will describe my progress as I work toward completing this task. I’ll call my Mal interpreter JKL.