Programming language implementation is a very interesting topic, and it’s something that can seem a bit intimidating even to experienced programmers. I’m by no means an expert on programming language implementation, but I hope that by keeping things simple and going step-by-step I can write something that will be useful to other non-experts interested in the topic.
This is hardly an original idea - there are many books and blog posts about simple Lisp implementations (see “other resources” below for some examples). However, there are so many different approaches one can take that I think new entries are still potentially valuable. For instance, some use very high-level languages like Python or Lisp/Scheme, whereas I’ll use C. Some stop before getting to topics like garbage collection and error handling, whereas I hope to include both. Others are meant for practical use and therefore introduce considerable complexity to improve performance or provide particular features, whereas my goal is to emphasize simplicity and comprehensibility.
As I said, I’m not an expert on language implementation, either regarding Lisp or in general. I will certainly make mistakes, overlook things, have to double back, and so on. Look at this in the spirit of a fellow student sharing their studies rather than an expert imparting wisdom.
Why a Lisp? There’s a lot to like about Lisps, but the main reason is to more-or-less take syntax off the table. Not that programming language syntax isn’t a worthy topic - it’s just not what I want to focus on here. Don’t worry, I won’t wax poetic about the inherent virtues of Lisp.
- Sky 0.0.1: Basic data mode
- Sky 0.0.2: Immediate integers and characters
- Sky 0.0.3: Printing data
- Sky 0.0.4: Reading data
- Sky 0.0.5: A not-quite-REPL
- Sky 0.0.6: Making all symbols readable
- Sky 0.0.7: Basic equality
If you’re interested in this project, you may also enjoy these resources. They vary greatly in approach, complexity, and format.
- Structure and Interpretation of Computer Programs - includes a meta-circular Scheme interpreter
- Scheme from Scratch (see his archives for the subsequent posts, plus the repo on GitHub) - builds a “bootstrap Scheme” step-by-step
- (How to Write a (Lisp) Interpreter (in Python)) - a simple Lisp interpreter in only 117 lines of Python
- Paradigms of Artificial Intelligence Programming - includes an interpreter and compiler for Scheme written in Common Lisp
- Scheme 9 from Empty Space - a book detailing a Scheme implementation in C
- GNU Emacs - if you’re already familiar with Emacs, diving into the implementation of Emacs Lisp can be both approachable and rewarding
- Make a Lisp - a Clojure-inspired Lisp interpreter implemented in 72 languages
- Femtolisp - a small, robust, and fast Scheme-like Lisp
- Build Your Own Lisp - a book that teaches C programming by walking you through building a Lisp interpreter
- Recursive Functions of Symbolic Expressions and Their Computation by Machine - John McCarthy’s original paper about Lisp
Why “Sky”? It needed a name and that was the first thing that came to mind. Naming things is hard. ↩︎