This is a series of posts meant for those that are interested in writing their own interpreter. It is written in the style of “An Incremental Approach to Compiler Construction”, where you have a fully working interpreter at each step. This series will begin by implementing a small subset of Scheme in Chicken Scheme.
The purpose of this interpreter is 100% educational and it will serve as a platform for me to research language features and their implementation. After implementing a bit of Scheme, I will begin implementing Lispy. Lispy is a language that is strongly rooted in Scheme with some Python and Clojure influences.
A basic version of Lispy already exists as an implementation in C, this is a rewrite of that interpreter. Since the purpose of Lispy is to teach myself about the implementation of programming languages, I believe it is the perfect candidate for a series such as this. I tried to explain everything as simply as possible so even a relative newcomer to Scheme should be able to follow along.
You can find the most recent version of Lispy in Scheme at github
* Development of Lispy is being put on hold for the moment. I will definitely pick it back up at some point in the near future.
Other Resources for Writing a Programming Language
Structure and Interpretation of Computer Programs
Chapter 4 onward covers designing and implementing a number of interpreters and was the inspiration for this interpreter.
An Incremental Approach to Compiler Construction (PDF)
Great paper on building a Scheme compiler from the ground up. Each step is simple and results in a fully working compiler.
Scheme from Scratch
The blog series that inspired and guided the development of the original Lispy. Even if you don’t know C (I didn’t at the time) you will still be able to follow along and construct your own Scheme. Peter’s coding style is easy and pleasant to read and he mentions tips for going in different directions for your own implementations.
A Self-Hosting Evaluator using HOAS (PDF)
An interesting implementation of Scheme using a Higher-Order Abstract Syntax representation. This paper, An Incremental Approach to Compiler Construction and SICP were the primary motivating forces behind my interest in PL design and implementation. The author, Eli Barzilay, has many other interesting papers at his site.
Chai – Math ∩ Programming
A series detailing the development of Chai (what appears to be a Scheme-like language). It is well written and currently in development. I’ll post more information when it’s available.
Scheme in Scheme
Another series that is just beginning about writing a bytecode interpreter. It appears to be put on hold as of April 2011.
Lisp in Small Pieces
Great book. Contains code for 11 interpreters and 2 compilers. Source code from the book available here.
* Interestingly, developing Lispy in this manner has led to a sort-of hybrid between literate programming and version control systems. Each part reads like a commit to version control, except that the commit messages are a bit wordier and combine together to form an article. I don’t know if it has any merit as a development technique, but it sure has been fun for me to watch this come together in this manner.
** I am in no way an expert and I welcome comments and criticisms on both the design and implementation of this interpreter. This is a series for people who are new to PL implementation, by a relative newbie to PL implementation.