“You think you know when you can learn, are more sure when you can write, even more when you can teach, but certain when you can program.” – Alan Perlis
Just after have read Lisp in Small Pieces I felt the urge to write a Scheme compiler. This sentiment is common in the Lisp community, I guess. There are dozens of Scheme systems, some good, some bad, some maintained, some abandoned. There are large optimising compilers and small interpreters for embedded systems. But I, well, needed to know. I needed to know how to write a program that takes another as input and generates simple instructions that do the same computation. I needed to know how to a write a program that interprets those instructions, a runtime to provide primitives, a garbage collector to manage memory etc. So I started doing some coding in my spare time, and called the monster Sly Scheme.
I failed miserably. I began with the reader, believing that basic I/O was fundamental for a REPL (the REPL was the goal I set myself to achieve). The reader was growing too complex and my interest simply disappeared. Then I focused on the types, creating a large hierarchy of them, only to lose interest again. After some time I came across Abdulaziz Ghuloum’s An Incremental Approach to Compiler Construction, which starts with the compiler itself. Let another Scheme do the I/O! I then took this path, running my compiler with Gambit-C. But instead of generating machine code, it generated instructions for a virtual machine. I then proceeded in lockstep: Wrote in Scheme a new compiler feature, and then in C just enough to interpret the new instructions. Finally most of R4RS Scheme is compilable. Then I wrote a simple stop-and-copy garbage collector with two semi spaces. After that, I needed a runtime with enough procedures to run the compiler without Gambit-C. Almost an year later, I have my REPL (I am not that bad as a programmer, but this is just a hobby that I do in my spare time).
The code now sits in a Github repository. For those who cares to check it out, I must warn that everything was done as simplistic as possible, so I could have a working interpreter ASAP. Some things were even done outright stupidly. The compiler generates too many closures, it fails with simple cases, the VM uses a giant switch, it is slow, the garbage collector too etc. I probably will hack this code for the years to come, even if only as a hobby of mine. But the most important contribution of this project is how much I have been learning from it.