Scheme from Scratch - Bootstrap v0.1 - Integers
Scheme from Scratch has begun. Our first objective is a Bootstrap Scheme interpreter implemented in C that can be used to compile a Scheme-to-Assembly compiler. Bootstrap Scheme is a quick and very dirty REPL interpreter.
Bootstrap Scheme is a C port of the the metacircular evaluator presented in SICP section 4.1. The SICP metacircular evaluator is able to cut many large corners because the implementation and implemented languages are both Scheme. There is no need to build a parser or garbage collector, for example. With a C port, all of these sorts of features need to be implemented from scratch eventually.
I’ll introduce the interpreter incrementally in the style of Ghuloum’s An Incremental Approach to Compiler Construction. This first step is only a language of integers with some of the general structure of the C implementation. The objective is to have an interactive REPL session like the following.
$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> 123
123
> -123
-123
> 007
7
> ^C
$We need to implement a model layer of integer (a.k.a fixnum) objects allocated in the heap. There also needs to be a read layer to read an integer. The evalulate layer is particularly simple because integers are self evaluating. The results are finally displayed in the print layer. A little driver loop in main directs the show.
The code is only about 100 lines long. For anyone familiar with very basic C and SICP should be quite straightforward. It is written to be readable above all else. I remember a time when I thought only super-humans could implement an interpreter but a naive interpreter like this one is really just a matter of putting one foot in front of the next.
There is no garbage collection for now and there won’t be for quite a few more steps. There is no pressing need for garbage collection because the programs being run are very small and so is the leaked memory. Also a precise garbage collector really gums up the implementation making it less readable. It is better to leave that until we are more comfortable with the interpreter implementation.
I’ve put the code on github. I’m new to git and github which adds a bit more flavor to the project. You can browse the code at the following address
http://github.com/petermichaux/bootstrap-scheme
and I created a branch specifically for this integers-only version
http://github.com/petermichaux/bootstrap-scheme/tree/v0.1
You can get the code with the following command
$ git clone git://github.com/petermichaux/bootstrap-scheme.gitYou should be able to just run make and then the above REPL session example should work.
If anyone happens to be following along I’d be glad to know.
Previous article: Introduction
Next article: Booleans
See also comments on: Hacker News and Reddit.
Comments
Have something to write? Comment on this article.
I’m following along. I also have the project to write a little lisp dialect close to scheme (but I don’t want to annoy me if it’s not strictly a scheme). I currently don’t have time to because of my studies, but I’ll do it.
I didn’t plan to go further than what you call "bootstrap" but now that I read the introduction to your series of articles, I also want to :-).
I’ll certainly won’t look at your code and I may not read some part of your posts if I think they could "spoil" me to much, but I’ll follow you in your adventure which I feel gonna be great!
Good luck!
A long time schemer, I’ve been reading your site for awhile, especially your oop implementations for javascript which I found very useful. I’m going to follow you on this great exercise! I just have to clean the dust of my C...
I’m following this thread. Its close to my interests. I’ve been writing a Lisp from scratch for about ten years now. I’ll write an interpreter or compiler and often a VM, discover something I don’t like about it, and table it while I think about what I should do differently. I think it’ll be interesting to follow your adventure in similar lands.
You should probably use the readonly git URL (git://github.com/petermichaux/bootstrap-scheme.git). Nice work, BTW!
I don’t code in C but find the structure of your code clean and quite readable. Nice work.
I too will be following your progress.
Good Luck.
fwiw, Abdulaziz Ghuloum’s scheme compiler tutorial is really easy to work through in other languages too. I’m doing it in python here: http://github.com/zellyn/zheme
You’re off to a fine start. I’m watching avidly.
I’ll be following this line of articles very closely! I love the incremental approach your going to be taking.
Great start! I’ll be following along. I’ll point my students toward this series the next time I teach compilers.
Wow! I am pleasantly surprised in how much interest there is in writing Scheme from Scratch. Thanks for all the positive comments and I hope folks continue enjoying.
Instead of writing as Scheme→Assembler compiler, why not write a Scheme→C compiler, in essence using C as a high-level assembler? The advantages would be:
- C is easier to code as a back-end than most assembly languages
- it would be portable; there are very few CPUs for which there is not a C complier.
Hi Phil,
Yes there are advantages to writing a Scheme→C compiler. Gambit-C has similar reasons to be as the ones you are suggesting. I’d like to try writing a Scheme→C compiler.
There are advantages to writing a Scheme→Assembly too. It is a good warm up exercise for writing a Scheme engine with a JIT, for example.
I am following you as well - very interesting! Thanks!
Hiya,
I’m enjoying this as well. I’m glad I caught this at the beginning stages so I can follow along.
Good luck and have fun!
Having come somewhat late to the party, as it were, I nonetheless have to thank you for the inspiration you've given me. I've toyed with the idea of writing my own Scheme interpreter for several years, but it was your article that has finally given me the impetus to begin working on one in earnest.
Of course, masochist that I am, I had to give a twist to this; so I have been writing my interpreter in (of all things) MIPS assembly language, using the SPIM emulator to run the code. It is a laborious job, to be sure, but not nearly as bad as writing it in x86 assembly would be - and I know more than one professor who would appreciate having a largish SPIM project available to show their students. I have managed to get as far as accepting integers as input and creating integer objects, more or less equivalent to your v0.01 version; however, I will probably be deviating from the order of development in the near future, as string handling presents some major hurdles given my design. I have not yet posted this publicly, but I may follow your lead and create a page and repository for the project for those who are morbidly curious about such a beast.
Have something to write? Comment on this article.
I got a link to your announcement from hacker news and have started following your blog specifically for this project. Thank you, I’ve had similar itches.