Scheme in the browser: A Hoot of a tale
Dave Thompson —
Hey there, it’s been a while! We’re back to share some more exciting news about Guile Hoot, a WebAssembly toolchain and Scheme→WASM compiler. In our last post we demonstrated that the Guile Hoot toolchain can be used to assemble programs written in WebAssembly Text (WAT) format, which allowed us to develop for the WASM-4 fantasy console. That was pretty cool, of course, but our goal is to compile Scheme programs (of the R7RS-small dialect, for now) to WASM. We are getting ready for our first release, and we’re happy to report that we’ve made excellent progress! We can now demonstrate the Hoot compiler working end-to-end.
Before we get to the demo, let’s go over what makes Hoot special. Hoot differs from most WASM compiler projects in some notable ways:
- Self-contained toolchain: No emscripten, binaryen, wabt, etc.
- GC reference type usage: The host provides the garbage collector.
- Small programs produce small binaries: Kilobytes, not megabytes.
- Full development environment: Compile and run WASM binaries without leaving Guile.
Self-contained toolchain
The Hoot toolchain has been written from the ground up to be self-contained with no external dependencies required (aside from Guile, of course.) This gives us a lot of flexibility and control over the entire compilation process. The toolchain includes:
- WAT parser: Converts WAT to WASM. Both folded and unfolded forms are supported.
- Assembler: Generates WASM binaries.
- Binary parser: Converts WASM binaries to an internal WASM data structure.
- Disassembler: Converts WASM to WAT.
- Linker: Composes WASM modules with a standard libary (for example), adding in only what is actually used.
- Interpreter: Validates and evaluates WASM without having to jump into the web browser.
All of these tools are available as a Scheme library that could be used to automate other WASM targeted build workflows.
GC reference types
In WASM 1.0, if a language implementation needed a garbage collector then it had to bring its own built on top of linear memory. There are many drawbacks to this approach:
- Large binaries: A whole GC needs to be shipped along with the program.
- Stop the world: Parallelism and concurrency are limited in WASM right now, so GC performance suffers.
- Collectable confusion: How do you know when references to your heap objects are collectable if they’ve been passed to JavaScript or other WASM modules? It’s a heap of trouble.
In other words, you had to ship a bad garbage collector when there is a battle tested, high performance, production garbage collector sitting right there in the browser. Check out Andy Wingo’s excellent BOB 2023 talk (in text or video form) for more detailed information about the problems with GC in WASM 1.0. (Andy is the lead engineer for the Hoot project.)
Thankfully, WASM GC has added the ability to allocate heap values that are managed by the host. Hoot is currently one of the few dynamic language implementations that makes use of GC reference types. We hope that by sharing our work and our experience we can help other dynamic languages find their way into web browsers, too.
Hoot is also taking advantage of another recent addition to WASM: tail calls. Loops are expressed as recursive function calls in Scheme, so having a tail call feature available simplifies our implementation effort. We don’t have to wait long to use these features, either. Production versions of WASM GC and tail calls are already shipping in bleeding edge versions of browsers and will become available to all users of the web soon.
Small programs produce small binaries
We made the choice when starting this project not to compile Guile’s C runtime to WASM using emscripten. While it would have been feasible, the resulting binaries would have been quite large, among other things. We did not want the end result of this project to be a multiple megabyte binary for “Hello, world.” Instead, we’ve taken the approach of writing a dedicated compiler backend for Guile with some handwritten WASM providing primitive functionality and calling out to imported host functions when necessary. Programs compiled with Hoot include only the parts of the standard library that they rely upon. As mentioned earlier, WASM GC obviates the need to link in an entire garbage collector. For these reasons, Hoot binaries tend to be much smaller than the output of most other compilers. Small programs produce binaries measured in kilobytes, not megabytes.
Full development environment
Hoot includes an embedded WASM interpreter that makes it possible to run WASM directly within the Guile process being used for development. Since the toolchain is also readily available as a set of Scheme modules, you can compile and test out programs (either Scheme programs or hand-crafted WAT) from the comfort of the Guile REPL. There is also a set of REPL tools to make inspecting and debugging WASM easier. Keep reading for a practical demonstration of the development workflow.
OK, onto Wireworld!
Wireworld part 1: Scheme
To show off the compiler, we decided to revisit our favorite cellular automaton: Wireworld. Check out our last post to learn more about what Wireworld is and how we used Hoot to build a pure WASM version of it. This time, instead of writing several hundred lines of WAT, we wrote about 70 lines of Scheme:
(let ((grid-size 40)
(empty 0)
(cu 1) ; copper
(ehead 2) ; electron head
(etail 3)) ; electron tail
(define (make-grid)
(make-bytevector (* grid-size grid-size) 0))
(define (grid-ref grid x y)
(bytevector-u8-ref grid (+ (* y grid-size) x)))
(define (grid-ref/wrap grid x y)
(bytevector-u8-ref grid (+ (* (modulo y grid-size) grid-size)
(modulo x grid-size))))
(define (grid-set! grid x y t)
(bytevector-u8-set! grid (+ (* y grid-size) x) t))
(define (neighbors grid x y)
(define (check x y)
(if (= (grid-ref/wrap grid x y) ehead) 1 0))
(+ (check (- x 1) (- y 1))
(check x (- y 1))
(check (+ x 1) (- y 1))
(check (+ x 1) y)
(check (+ x 1) (+ y 1))
(check x (+ y 1))
(check (- x 1) (+ y 1))
(check (- x 1) y)))
(define (update from to)
(do ((y 0 (+ y 1)))
((= y grid-size))
(do ((x 0 (+ x 1)))
((= x grid-size))
(let* ((t (grid-ref from x y))
(t* (cond
((= t empty) empty)
((= t cu)
(if (<= 1 (neighbors from x y) 2) ehead cu))
((= t ehead) etail)
((= t etail) cu))))
(grid-set! to x y t*)))))
(define (copy from to)
(let ((k (bytevector-length from)))
(do ((i 0 (+ i 1)))
((= i k))
(bytevector-u8-set! to i (bytevector-u8-ref from i)))))
(define grid-a (make-grid))
(define grid-b (make-grid))
(define (update-and-swap)
(update grid-a grid-b)
(copy grid-b grid-a))
(define (ref x y)
(grid-ref grid-a x y))
(define (set x y t)
(grid-set! grid-a x y t))
(define (cycle x y)
(set x y (modulo (+ (ref x y) 1) 4)))
(values grid-size ref set cycle update-and-swap)))
After compiling and gzipping the resulting binary, we’re looking at a
28KiB download. Not too shabby! (And we’re anticipating adding a
size optimization pass resembling binaryen’s wasm-opt -Oz in the
future to reduce binary size even further.)
Before we get to the browser, let’s take a quick detour and talk about
development workflow. It took several iterations to arrive at the
code above. In true Scheme fashion, the program was developed
incrementally in an interactive REPL session. By using Hoot’s WASM
interpreter, we repeatedly compiled and tested the program without
having to load it into a web browser or shell out to V8’s d8 tool.
We think it’s pretty neat! Below is an annotated excerpt of a REPL
session that shows the values of 3 cells before and after an update.
;; Import necessary Guile modules.
scheme@(guile-user)> ,use (hoot reflect) (wasm parse)
;; Load reflection WASM module.
scheme@(guile-user)> (define reflect-wasm
(call-with-input-file "js-runtime/reflect.wasm"
parse-wasm))
;; Compile and evaluate Wireworld source.
scheme@(guile-user)> (define-values (grid-size grid-ref grid-set
grid-cycle grid-update)
(compile-value reflect-wasm wireworld-src))
scheme@(guile-user)> (grid-ref 0 0) ; electron tail at (0, 0)
$10 = 3
scheme@(guile-user)> (grid-ref 1 0) ; electron head at (1, 0)
$11 = 2
scheme@(guile-user)> (grid-ref 2 0) ; copper at (2, 0)
$12 = 1
scheme@(guile-user)> (grid-update) ; step the simulation
scheme@(guile-user)> (grid-ref 0 0) ; copper at (0, 0)
$13 = 1
scheme@(guile-user)> (grid-ref 1 0) ; electron tail at (1, 0)
$14 = 3
scheme@(guile-user)> (grid-ref 2 0) ; electron head at (2, 0)
$15 = 2
The electron has moved to the right one cell, exactly as it should. With some amount of confidence that the program is working, we proceed to the web browser.
Wireworld part 2: JavaScript
To get this version of Wireworld running in the browser, an additional
~100 lines of JavaScript were used to glue the Scheme program to
various browser APIs. Since we aren’t targeting WASM-4 this time, we
needed a new rendering method. We chose HTML5 canvas to keep things
simple. The code below updates the simulation at some regular
interval, renders to the canvas, and handles keyboard/mouse input.
Hoot’s reflect.js library allows us to call Scheme procedures from
JS.
async function init() {
const canvas = document.getElementById("canvas");
const ctx = canvas.getContext("2d");
const [_gridSize, gridRef, gridSet, gridCycle, gridUpdate] =
await Scheme.load_main("scheme-wireworld.wasm", {});
const gridSize = Number(_gridSize), tileSize = 16;
const canvasSize = gridSize * tileSize;
const empty = 0, cu = 1, ehead = 2, etail = 3;
let paused = true, mouseX = 0, mouseY = 0;
function render() {
requestAnimationFrame(() => {
for (var y = 0; y < gridSize; y++) {
for (var x = 0; x < gridSize; x++) {
const t = Number(gridRef.call(BigInt(x), BigInt(y)));
switch(t) {
case empty:
ctx.fillStyle = "#fff6d3";
break;
case cu:
ctx.fillStyle = "#f9a875";
break;
case ehead:
ctx.fillStyle = "#7c3f58";
break;
case etail:
ctx.fillStyle = "#eb6b6f";
break;
}
ctx.fillRect(x * tileSize, y * tileSize, tileSize, tileSize);
if(x == mouseX && y == mouseY) {
ctx.fillStyle = "#00000020";
ctx.fillRect(x * tileSize, y * tileSize, tileSize, tileSize);
}
}
}
});
}
function update() {
if(!paused) {
gridUpdate.call();
render();
}
setTimeout(update, 100);
}
function pixelToTile(p) {
return Math.min(Math.max(Math.floor(p / tileSize), 0), gridSize - 1);
}
function cycleTile(x, y) {
gridCycle.call(BigInt(x), BigInt(y));
render();
}
function setTile(x, y, t) {
gridSet.call(BigInt(x), BigInt(y), BigInt(t));
render();
}
function clearTile(x, y) {
setTile(x, y, empty);
}
function togglePause() {
paused = !paused;
}
canvas.width = canvasSize;
canvas.height = canvasSize;
canvas.addEventListener("mousemove", (event) => {
mouseX = pixelToTile(event.offsetX);
mouseY = pixelToTile(event.offsetY);
if(event.buttons == 1) { // left
setTile(mouseX, mouseY, cu);
} else if(event.buttons == 2) { //right
clearTile(mouseX, mouseY);
}
render();
});
canvas.addEventListener("mousedown", (event) => {
const x = pixelToTile(event.offsetX);
const y = pixelToTile(event.offsetY);
if(event.button == 0) { // left
cycleTile(x, y);
} else if(event.button == 2) { // right
clearTile(x, y);
}
});
canvas.addEventListener("contextmenu", (event) => event.preventDefault());
document.addEventListener("keydown", (event) => {
if(event.code == "Space") togglePause();
});
update();
render();
}
window.addEventListener("load", init);
Note the use of BigInt in several places. This is a consequence of
how JavaScript’s Number type works. JS numbers are floating point
values, but Scheme has a much richer set of numeric types including
exact integers. So, values of type Number are treated as Scheme
floats, and the BigInt type is used to box all integer values that
traverse the JS⇄Scheme bridge.
As Hoot matures and we implement a foreign function interface (FFI) for calling into JS (or other hosts) from Scheme, we expect to see the amount of glue code shrink considerably.
Live demo
OK, now it’s time to see Scheme Wireworld in action! But first, a disclaimer: As of publishing, major web browsers are just beginning to ship WASM GC support. Starting with Firefox 120 and Chrome 119, GC is enabled by default. Neither version is stable yet, so use either Firefox Nightly or Chrome Dev if you’d like to run the demo. If you’re reading this further into the future then congratulations! The browser you are using should have everything you need.
How to use:
- Press the left mouse button and move the cursor to draw copper.
- Press the right mouse button and move the cursor to erase.
- Left click on a cell to cycle its type (copper becomes electron head, etc.)
- Right click on a cell to clear it.
- Press the space bar to pause or resume the simulation.
Now you try!
If you’d like to compile and run this yourself, check out our GitLab repo for this demo. Like most of our projects, it uses Guix to setup the development environment. The environment requires an unreleased version of Guile compiled from source, so be prepared to wait awhile for it to build.
git clone https://gitlab.com/spritely/scheme-wireworld.git
cd scheme-wireworld
guix shell
# The following commands are evaluated *within* the Guix shell
guile wireworld.scm
guile web-server.scm
Once the web server is up and running, visit http://localhost:8080 in your web browser. Feel free to modify the code and have some fun!
We look forward to sharing more when we release Hoot 0.1.0!