Scheme from Scratch - Bootstrap - Conclusion
The main goal of this Scheme from Scratch series, as the title implies, was to record the creation of a bootstrap Scheme interpreter in a low-level language like C. This bootstrap interpreter could to be used to self-compile a Scheme compiler written in Scheme. It took about three weeks and the interpter’s code is less than a couple thousand lines lines of code. It is not efficient code but it is straightforward and easy to understand. It doesn’t have macros or continuations but it is enough to write a compiler. It does have closures so it has a better feature set then some languages do.
Going Meta-Circular
The read, eval, and write primitives in Scheme make it very easy to write a little Scheme REPL in Scheme. It almost feels like cheating.
$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (define env (environment))
ok
> (define (repl)
(write-char #\])
(write-char #\space)
(write (eval (read) env))
(write-char #\newline)
(repl))
ok
> (repl)
] (cons 1 2)
(1 . 2)
] (define (double x) (* 2 x))
ok
] (double 21)
42The bootstrap interpreter was modeled after the first meta-circular interpreter in SICP. The ability to implement a programming language in our new interpreter implementation is a great test. You can download the SICP meta-circular evaluator (cache) and run it yourself. I first wrote a little helper file called run-meta-circular.scm to load and start everything that is required.
; Add standard definitions to complete our
; Scheme implementation: cadr, length, etc.
(load "stdlib.scm")
; Add extra definitions needed by
; the meta-circular implementation.
(define true #t)
(define false #f)
; Cheat a bit but actually results
; in a better REPL
(define display write)
(define newline (lambda () (write-char #\newline)))
; Load the meta-circular implementation
; exactly as it appears in SICP.
(load "ch4-mceval.scm")
; Run the meta-circular interpreter.
; These lines appear but are commented out
; in the meta-circular implementation.
(define the-global-environment (setup-environment))
(driver-loop)With that file it is easy to fire up the meta-circular interpreter exactly as it is written in SICP.
$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (load "run-meta-circular.scm")
";;; M-Eval input:"
(define a (cons 1 2))
";;; M-Eval value:"
ok
";;; M-Eval input:"
(car a)
";;; M-Eval value:"
1
";;; M-Eval input:"
((lambda (x) x) 21)
";;; M-Eval value:"
21Unfortunately the SICP code doesn’t define many primitives in the meta-circular interpreter so the above example is not too rich. If you expand the interpreter you can just fill your boots with meta-circular goodness.
It was really great to see in the GitHub feeds that other people were running the meta-circular interpreter days ago and I hadn’t even mentioned it yet.
- - - -
The reason for documenting this whole adventure was I couldn’t find a book that I could just buy and read about implementing Scheme in C. Maybe one exists and I didn’t search hard enough. Maybe one should still be written. Maybe these articles has or will fill the need for at least a few readers. Regardless it has been fun documenting it and watching other enjoy implementing their own interpreters along the way. Enjoy your interpreter!
Previous article: Garbage Collection
Comments
Have something to write? Comment on this article.
kbob,
I do want to write a compiler but it won’t be right now. I’m looking forward to a little break. Planing the order of all these articles, writing the code, and preparing an article per day is quite a bit extra on top of life. Actually I thought this bootstrap interpreter series would be spread out over months but some people were interested and motivated me to move faster.
I’m not sure exactly what to build next. Do I learn how to build something that is actually useful for the real world? What kind of compiler? Should it be real Scheme or something similar but different?
Heh, I won’t mind a break too much -- gives me a little time to catch up!
I must agree with kbob though, I thought this was just the first half. Boostrap Scheme was (still is, and will be till I finish) a lot of fun, but the idea of writing the scheme compiler in scheme that compiles back to the bootstrap language is still tantalizing! I feel like I generally understand how interpreters work, even though I haven’t ever completed much more than what I have now for ada-scheme, but compilers are a whole nother thing. Especially when you compile while still inside the REPL like mosts CLs (not sure about schemes), I have no idea how that works, but it is fascinating!
I think when you do pick this up again (and you should!) we should continue with the straight scheme. With Scheme, we know exactly what we are implementing. If we decided to take artistic licenses (like #'a' instead of #\a) that opens up a can of worms. How far do we go? How many people are going to nitpick that this is better than that? On and on... Design by committee is weak, I like the tangible goals of straight scheme. Doesn’t need to be super practical. I think it should compile to the language that we bootstrapped in, you (and most others) to c, me to ada.
Seriously, you need to pick this up again in a couple months (or however long you need). Plan it out before starting coding again. Etc... Whatever helps you. I really want to get across that I have appreciated this series. There is a lot of noise on the internet, but this has been the strongest signal I’ve picked up in a long while. so participatory! I wish we could visualize our little github followers/watchers circle as a graph.
Starting to ramble, but let me summarize: great series, great code, great learning, great group.
Great series! Thanks a lot for documenting and presenting your project so nicely.
Now take a well-deserved break, but then come back and do the same thing for a compiler. We’ll be waiting. ;-)
I agree with the sentiments expressed thus far. This series has been absolutely fantastic. So much so, that I hate to see it end. Please take some well deserved time off and then come back and continue the series by writing a scheme compiler. By the way, have you considered the idea of turning this series, along with the continuation into a fully operable compiler, into a full fledged book? I was thinking something like this might be appealing to a company such as Apress since they also published the wonderful Practical Common Lisp by Peter Seibel. I know that I would purchase a copy of such a book if it existed, especially if the writing had the same clarity and simplicity that you’ve already shown you are more than capable of producing.
Either way, book or no book, compiler or no compiler, the series as it stands now is a really great resource for anyone wishing to dabble a bit in language development and I thank you for it.
Keep up the good work!
thank you very much for these amazing posts, i’ve read sicp but still it was a pleasure to revisit this topic in particular thanks to the way you've presented it, i’m sure many people have learned a lot and some probably got inspired and interested enough to read sicp
people like you creating useful, educational and free content are a boon for society and always in short supply, i hope you keep it up for a very very long time :)
As others have, I just wanted to say thanks and that this series was really great. I’ve been working on and modifying it most of the way through and have implemented primitive and compound macros (basically copying the code for the functions but passing the arguments uneval’d and evaluating the result). Anyway, because of this series, I've had a lot of fun, so once again, thanks :)
Hi Peter,
It’s been a long time I was in search for such a small practical series.
Even if my objective is to learn to write compilers, first starting using REBOL as my implementation language instead of C or Lisp (in fact REBOL is another modern parenthesis less dialect of Lisp having its own merits), your series is a perfect tool to learn from.
This even forces me to learn how to express C data structures to REBOL ones in the way and this is excellent.
Simply hopes you’ll continue step after step from your original list of possible implementations and choose any and all of them one after the other (Bootstrap, Compiling, Compile-to-C, byte code VM, JIT engine and Platform).
And yes, if you can afford time for this - see it in a more relax time frame and fun "passe-temps" - an e-book would be a fine contribution. May be you could also ask for small donations via paypal to help or implement something on a subscriber’s basis, asking for a small fee to login.
It’s sure that I would prefer to get it for free but I understand all the work required to plan and deliver such a quality content as you did. I am a teacher too but my knowledge is so limited on this subject that I even can’t think of being useful to you for the moment.
But definitely, there is some need for such a learning tool, outside of the formal schools...
Keep up the good work,
Thanks,
Gerard
I’m still a few episodes back, life bumped into the way of things... hopefully I will catch back up
Oops, I forgot to check back since my earlier comment.
My two cents:
First, this was a great series. I’d love to follow you through a follow-on system.
Keep it Scheme, for the reasons Nick stated. I am very interested in making a macro processor work, since that’s where my earlier effort bogged down. A compiler, or, better, a JIT, would also be fun.
Take your time -- after all, I’m still roughly at your v0.8. (Work interferes with fun again...) But you don’t need to produce such a tidy, finished product next time. Write a few articles about design alternatives before you have decided which way to go. Go down a few dead ends, too. (-:
BTW, if anyone reading this hasn’t checked out this course, you really ought to. The Elements of Computing Systems, aka NAND Gates to Tetris. It’s a one-semester undergraduate CS course that builds a complete system/ You start at the logic gate level, up through ever more complex hardware systems until you’ve built a simple computer. Then you write an assembler, virtual machine, compiler, OS, and application for your computer. There’s a textbook, lecture notes, videos, homework, and simulators. I did the whole thing; it was great fun.
Thanks to everyone for all the encouraging comments. I am definitely keen on continuing with a follow-up series when I feel like I’m ready and can say something at least moderately intelligent.
kbob,
I saw the NAND computer course a while ago when it was posted on Reddit, I believe. Thanks for the recommendation and reminder. I would really like to do that course one day.
I’m considering trying to take my “toy” interpreter and make a full or nearly full r6rs interpreter out of it. That will take a while :) Of course, if my record on apply is any indication, this will be an error prone process. I’m stilling finding bugs in how my implementation. Although, variadic procedures were realtively easy (I think . . . . hunts for bug spray). I just had to make a few minor adjustments to the argument binding logic. This project will very likely tie up my free coding time for a while to come. Finally, something with some meat on it.
Just finished and, or, begin, apply, and let over the last two days since I got lambda working. Everything seems really easy in comparison. Would be cool to do macros, but scheme macros seem very strange compared to CL macros, might take a while to just figure them out first. Think I’ll do let* pretty soon here; just looked it up in SICP and it is the next exercise that seemed to be skipped over in this series. I actually just bought SICP the other day, I had borrowed a copy from my school’s library, but only made it through Ch. 3 (didn’t realize Ch. 4 was the good stuff ;) ). I consider it a worthy investment despite the pretty penny they charge.
Anyways, the real reason I’m commenting is that I hadn’t come back to this thread since I last posted, and I think Christopher Roach has the best idea of us bunch so far:
Approach a publisher. Get a deal. Clean this stuff up. Expand on it. You deserve something from all this hard work. You can bet that I would go out and buy a copy.
Thanks again.
thank you very much for these amazing posts, i’ve read sicp but still it was a pleasure to revisit this topic in particular thanks to the way you’ve presented it, i’m sure many people have learned a lot and some probably got inspired and interested enough to read sicp
Have something to write? Comment on this article.
Are you done, or are you going to write a compiler now? I hope you’re going to write a compiler now...