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.
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) 42
The 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:" 21
Unfortunately 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
Have something to write? Comment on this article.