In spirit of SICP exercises 5.49-52.
- The compiler is based on the Scheme to register machine compiler from SICP section 5.5
- Wasm stands for WebAssembly
- WAT is the WebAssembly Text Format
- Implement the compiler in Scheme R6RS, using Racket as the development platform
- Learn about Scheme and compilation of functional languages in general
- Get familiar with WebAssembly as an execution environment and compiler target
- Stay in the spirit of simple Scheme and target initially to support a subset of R7RS-small Scheme
- Compile Scheme forms directly to as idiomatic Wasm as feasible
- Use only basic, standardised Wasm core features initially
- Implement as much of the required run-time support in Scheme as possible
- Write the required native run-time support in WAT
- Compile a Scheme interpreter to Wasm using the compiler (see also SICP exercise 5.52)
- If the interpreter works, host it on a web page with minimal JavaScript-driven REPL
- Maybe try to bootstrap the compiler at some point as an interesting exercise
- Build a full-blown implementation with robust error reporting, tooling, full Scheme libarary support etc.
- Good interoperability with JavaScript is not critical, except where it helps in testing the compiler or hosting an interpreter or the compiler on the Web
- Do not aim to replace JavaScript on the Web
Required tools:
- GNU Make
- Racket with R6RS support (Other R6RS supporting Schemes may work too, but the Makefile at least will need modification)
- WABT for running the compiler tests as defined in the Makefile. Compiler's output can be tested with any Wasm tooling that provides a WAT to Wasm assembler and a Wasm runtime.
On macOS the built-in make is sufficient. Racket and WABT can be installed with Homebrew.
- Run
maketo compile the compiler. Requires Racket to be installed and in PATH. make test-unitto run unit tests defined in test-unit of the compiler support librariesmake test-compilerto run tests defined in test-compiler for the full compiler. This requires WABT to be installed and in PATH.make testto run both unit and compiler testscat test.scm | make compileto compile the Scheme filetest.scmto a WAT module to standard output.
Test runs can be a bit slow, but can be executed faster in parallel using GNU make's concurrent exeuction. For example, make -j4 -O test compiles the compiler and runs all tests with 4-way concurrency. Requires recent-enough GNU make. The option -O keeps the output ordered despite the parallel execution.
- Compilation of 32-bit integer values and open-coded application of + - * / = operators
- Compilation of comparison operators = < > <= >= for 32-bit integeres
- Scheme if statement to Wasm if statement
- Compilation of lambda expressions to Wasm functions and values that can be applied to arguments
- Port the compiler from Racket
#lang sicpto standard R6RS Scheme (still using Racket as the development platform) - A simple compiler "driver" that can be given a Scheme program from standard input and that emits a Wasm module to standard output in WAT format
- Makefile for building the compiler and regression test execution
- Regression tests for the implemented features
- Tests are specified in WAST and executed with WABT's spectest-interp tool
- The tests invoke the compiler with a Scheme expression, compile it and check the executed WebAssembly's result with WAST assertions
- See test-compiler for the tests. They also give an overall idea of what works and has been implemented in the compiler.
- Compilation of Scheme R7RS library to a Wasm module with the top-level code in an exported
func"main" - Top-level
defineof values and procedures set!top-level and in-scope binding values- Support for exported top-level procedure definitions with R7RS libary syntax
- Basic syntax and semantic error detection and tests for error handling
- Implement
letandlet*with Wasm locals instead oflambda, if possible. (Using the bindings in closures will need further work) andandorexpressions with short circuit using Wasm block structure and conditional branch instructionsnotexpression- Compile
condto Wasm block structure and conditional branch instructions - Special form symbols and inlined procedures can be overridden with local bindings
- The Scheme values are not type checked in the compiled programs: a number can be used as a procedure reference and vice-versa. Using of uninitialized values is not detected.
- The Makefile always runs the tests twice after clean before recognizing that there is nothing more to be done
- Add a way to raise errors from compiled code. Needed for halting the program when a type error is detected.
- Add bit tagged typing to values and type predicates:
number?,procedure?and uninitialized value and add type checking to generated code. (see Known issues) - Add support for read-only symbols and strings
- Add run-time support for rudimentary heap-based values: vectors, pairs
- Implement simple garbage collection using SICP section 5.3 as a guideline in WAT
- Implement lexical closures with function activation records as vector lists on the heap
- Implement
letrecform. It does not make sense to implement it before closure support to enable common use case of recursion and procedures calling each other. - Scan out (see SICP chapter 4.16) internal definitions and implement the bindings with
letrec* - Come up with a name for this project
- Add high-level design documentation with guide to the source code of the compiler
- More R7RS-small features, prioritisation TBD.
- Structure and Interpretation of Computer Programs (SICP) Web Site
- WebAssembly home page
- WebAssembly specification
- WebAssembly text format (WAT)