Introduction

The best way to understand how something works is to try to build it for yourself. Reading somebody else's explanation might satisfy your curiosity, but without the experience of falling into all the little traps it is difficult to get a feel for why something is designed a certain way.

It's been said that every would-be programmer should write a compiler. While I think this is good advice (although I haven't followed it myself), there is so much effort involved just in parsing a language such as C that any potential insights risk getting lost in a mire of details. Perhaps creating an interpreter for some simple language would be a good first step.

I first started playing around with LISP a good few years ago, yet much later than I should have. This led me to the classic lecture series Structure and Interpretation of Computer Programs. If you have the next 24 hours free and haven't seen the videos already, go watch them now.

The course covers many topics, but the second half shows in detail how to evaluate LISP, first by implementing a simple version of eval in LISP itself. I figured that this would translate well into C, and so decided to try creating my own implementation of LISP.

It was really easy.

This article is an attempt to share the process by which I built my implementation, and the chapters occur roughly in the order in which I did things. Why not follow along and create your own version in your language of choice?^*

As a professional programmer (ha, ha), I spend the majority of my time writing C and C++. Most of the rest is Java. There are many languages out there, each with their own debatable merits, but I'd like to demonstrate just how simple a LISP machine can be — even built in as low-level a language as C. See John McCarthy's History of LISP for the story of the pioneers.

So here is my toy implementation of LISP. I've borrowed features from various dialects, but it's closer to Scheme than Common LISP. The differences are trivial enough that changing over would not require substantial changes to the interpreter. Don't worry if you're not familiar with LISP; I will define everything as I go along.

It is not meant to be the smallest possible implementation, nor the most efficient, nor the most complete; it could however be described as lazy. My goal was to write robust, easy-to-read code that does exactly what it needs to, and no more, and I hope that it conveys how little effort is required to construct an incredibly powerful environment like LISP.