A minimum viable Scheme
By John Hardy
I’m building Skate, a Scheme compiler for the Z80 running CP/M, as part of my Triptych computer project. In Starting Skate I explained the appeal of bringing a more dynamic style of programming to this small machine. The question now is how much Scheme we can fit into this environment while keeping it useful for substantial programs.
I’m searching for a minimum viable Scheme. Skate should be able to run most of the example programs in the classic programming book Structure and Interpretation of Computer Programs. Where an example needs rewriting, we can examine the limitations of the implementation and whether the result still expresses the algorithm clearly.
Scheme is a member of the Lisp family with a small core from which we can build quite sophisticated programs. Procedures are values alongside numbers and other data: we can pass one as an argument, return it from another procedure or store it in a list. This is what it means for procedures to be “first-class”. Alongside these procedures, Skate’s basic values will cover arithmetic, logical decisions and text. Lists let us assemble values into larger structures for programs such as searches and symbolic calculations.
The Z80 has a 64 KiB address space, part of which the CP/M operating system occupies. Skate will translate Scheme source into native Z80 machine code before the program runs. The generated code will link with a runtime that supports dynamically allocated objects and automatically reclaims memory the program can no longer reach. Compiling to machine code should give us efficient execution, but the program and its runtime must also leave enough room for useful amounts of data.
During compilation the compiler and its working data must fit in the available memory. For Skate I’m adapting the source-streaming techniques developed for my assembler ATOM, which processes source in a small working area. The compiler finishes before the resulting program runs, so we can consider their memory requirements separately.
Through this series we’ll work from small Scheme programs down to their implementation and document the compromises along the way. Readers will be able to try the examples in Triptych’s browser-based CP/M environment. The test is whether we can still express substantial algorithms clearly and leave enough space to run them. That’s the useful minimum I’m working towards.
---