The empty list in BiwaScheme
Monday, 6 December 2010
I’ve been looking around for Scheme interpreters written in JavaScript for a while now. The original idea was to make some kind of interactive online teaching tool, like an interactive version of The Little Schemer.
Googling for “javascript scheme” turns up a few implementations:
- Douglas Crockford wrote a small Scheme interpreter as a companion to The Little Schemer, covering just the important stuff.
- Chris “doublec” Double modified someone else’s jsScheme that may or may not have JIT (it’s a little unclear whether the JIT checkbox does anything).
- Erik Silkensen’s JS-SCHEME
- and many more…
BiwaScheme popped up on my radar, and I was drawn in by their online REPL and the fact that they were on GitHub. Downloading the code and hacking it was relatively straightforward, and it comes with a suite of unit tests to check for a good portion of R6RS compatibility.
When I looked in the source code, I was at first confused by its car and cdr. Apparently BiwaScheme used an internal object typed Pair that contains a car and a cdr property, while car and cdr as used by the user were declared elsewhere. Even weirder, I found out, was that the empty list was a Pair of two other objects named by the comments as “inner nils” that acted as error guards.
It might not be obvious, but the empty list ‘() in Scheme is an atomic value. We call it the empty list, as if it’s a data structure, and (list? ‘()) returns #t, but ‘() is no more special than NaN is in JavaScript. If you think of a list as a chain of cons pairs (like they actually are!) then the use of ‘() as an end-of-list special marker makes sense.
I’ve since fixed this in BiwaScheme.