How small does it have to be? Chibi Scheme does syntax-rules in 174 lines of Scheme, layered over explicit renaming. Indeed, Chibi does essentially all of R5RS in 4822 lines of C + 708 lines of Scheme.
— John Cowan
Scheme 9 from Empty Space is also very small from what Nils said.
(via this thread in r6rs-discuss, I have the email but can not find the archive of it)
8 thoughts on “How Small Can a Scheme Implementation Be?”
S9fES is not /that/ small any longer: about 5550 lines of C and 1400 lines of Scheme, but it includes bignums, decimal-based exact flonums, and both define-macro and define-syntax.
The amount of source code is only one aspect. What is also interesting is the size of the resulting binary. When we tried to find a Lisp/Scheme implementation that we could run on an SPE for the Cell processor, we didn’t find anything that could actually fit. All Scheme implementations we found, including the supposedly small ones, needed more than 500 kByte in total (when statically linked, which is necessary for the SPEs).
That’s a pity given the fact that Scheme was originally supposed to be a small language…
(We were now able to squeeze our own implementation down to 150 kByte, which is still quite large…)
Pascal, would you be able to say any more about this Lisp implementation for the Cell SPE? Sounds like a very interesting project.
Nils: Got it.
Pascal: Please elaborate on your implementation ;).
Pascal-you should look at Tinyscheme, which I have compiled down to about 19K, and shipped at 52K. It’s far and away the smallest scheme I’m aware of.
We did try Tinyscheme. It gets too big when you statically link the libraries it needs, and that’s necessary in this case. The numbers you report are only possible, as far as I can tell, when you link the libraries dynamically. (Please correct if I’m wrong.)
There have been a number of Lisps on 8-bit systems, and most of them ran on a single-bank machine, so all code, data and runtime environment must have fit into 64k (but they probably had really limited number support — a modern CPU would at least get floating point numbers for free!) I’ve found references to the following:
* VLisp, Jérôme Chailloux, 1979
* Le Lisp 80, Jérôme Chailloux, 1983 (Z80 assembler source available, targets many 8 bit systems including CP/M)
* Toolworks LISP/80, Walt Bilofsky, for Z80 under CP/M
* InterLisp/65 for the Atari 6502 machines
* Acornsoft Lisp for the BBC 6502 machines, 1984
* SpecLisp, Serious Software, for the ZX Spectrum, 1983
* P-Lisp, Gnosis Software, for Apple 6502 machines, 198x
* Z80 Scheme, by Ken Dybvig and George Cohn, mentioned in The Development of Chez Scheme
The Dream interpreter is written in x86 assembler and the executable is 38k (but depends on libc.so and libdl.so):