Directly compiling Scheme to WebAssembly: lambdas, recursion, iteration!

It's been just over three months since we announced the Guile on WebAssembly project (codenamed Hoot). Since then we've brought on two fantastic hackers to develop the project and progress has been quick.

We now are at the point where we have things to show: we can now compile various Scheme procedures directly to WebAssembly. Let's clarify that: by compiling directly to WebAssembly, we mean they compile and run without any intermediate virtual machine. No C, no Rust, no Zig: Hoot outputs pure WebAssembly. It's early, but Hoot compiled programs are starting to work... and they're fast!

Hoot by familiar Scheme examples

The Hoot test suite includes some examples of fairly standard scheme procedures, compiled directly to WebAssembly and executed against V8. Let's take a look at some of those examples to contextualize what Hoot provides. (If you're not familiar with Scheme, you can focus on the text of this blogpost rather than the code. Or, you can read our Scheme Primer as a way to get started on following along!)

Here's an all time favorite intro-to-Scheme example (one of the first examples in SICP):

;; Your intro-to-CS factorial function
(test-call "120"                         ; expected value
           (lambda (n)                   ; factorial function which takes `n`
             (let fac ((n n))            ; start recursing at `n`
               (if (eq? n 0)             ; are we at zero?
                   1                     ; if so, return 1, otherwise...
                   (* n (fac (1- n)))))) ; `n` times factorial of `n` minus one
           5)                            ; run `factorial(5)`

test-call takes two or more arguments: the value we expect to see V8 spit out from running the compiled WebAssembly code, a procedure we want to test, and any more arguments are arguments to the function.

Hoot is compiling this program to WebAssembly directly. Astoundingly, at the time of writing, the size of the compiled WebAssembly program is only 970 bytes... less than a kilobyte! (Did you gasp?)

Other familiar intro-to-computer-science friends are also now available. Who doesn't love the Fibonacci function?

;; Fibonacci, everyone's favorite
(test-call "9227465"                     ; expected value
           (lambda (n)                   ; fibonacci function which takes `n`
             (let fib ((n n))            ; start recursing at `n`
               (if (<= n 1)              ; is `n` 1 or less?
                   1                     ; if so, return 1, otherwise...
                   (+ (fib (- n 1))      ; add `fib(n - 1)` to
                      (fib (- n 2))))))  ;     `fib(n - 2)`
           34)                           ; run `fibonacci(34)`

Now the astute reader may be looking at the above two functions and observing that these are recursive procedures! Yes, recursion is all fine and well in the land of Scheme, and it's all fine and well in the land of Hoot, too.

Of course, the astute reader will also recognize that neither of these is the most efficient way to implement either of these functions: both grow more memory than necessary. It's great that we can recurse, but should we recurse?

Well, it turns out that iteration can be defined in terms of recursion. If a procedure doesn't need to do any more work, there's no need to keep it on the stack anymore. And if a procedure doesn't need to do any more work and it's just calling itself, Scheme implementations are historically especially smart about this, because we can just reuse the same procedure where it was!

Which means, here's a very terse looking loop which looks kinda recursive but in terms of computational work is merely iterative:

;; Let's get loopin!
(test-call "500000000"                   ; expected value
           (lambda ()
             (let loop ((n 0))           ; start loop at 0
               (if (< n 500000000)       ; if we're less than 500 million...
                   (loop (1+ n))         ; keep looping and increment n
                   n))))                 ; otherwise we're done, return n

Once again, this program is less than 1 kilobyte when compiled, and carries with it everything a Hoot-compiled program needs to execute. That's cheap in terms of file size. But how fast is it?

Well consider that Guile is actually fairly speedy. It's not the fastest Scheme out there (their role in programming language research means that Schemes are a well trodden territory for optimizing languages), but it's quite fast. Shockingly then, the Hoot-compiled WebAssembly for the above executes, on local tests, is five times faster than native Guile!

Of course, looping over addition is a very limited benchmark. Still, we're happy for this early indicator that Scheme to WebAssembly is likely to be very performant.

Hoot is also a mini WebAssembly toolkit!

One of the interesting aspects of Hoot is that it takes advantage of Guile's compiler tower. Hoot is able to use all the optimizations that Guile already provides, because Hoot's compiler transforms Scheme code from Guile's CPS Soup intermediate language directly to WebAssembly.

(Guile's compiler tower has some limited support for other toplevel languages which are not Scheme; this also means that those too can compile directly to WebAssembly.)

One nice aspect of WebAssembly is that its textual representation is already very lispy, using parenthetical s-expression notation. This means that WebAssembly is already ripe territory for lispers to embrace, and Hoot has done just that.

Rather than use external tooling like binaryen or wabt, Hoot provides its own suite of tools for parsing, assembling, disassembling, and dumping WebAssembly directly. This means Hoot isn't just useful as a way of compiling Scheme to WebAssembly, it's a useful WebAssembly toolkit in and of itself!

What Hoot means for other languages

For a long time, programmers were given one real option to program in web browsers: Javascript. WebAssembly's initial introduction has provided a ripe ground for several other non-garbage-collected languages to enter the space, such as C, C++, Rust, and Zig.

But there is a large and beautiful array of programming languages available to programmers in the world. Many of those languages have been given less than ideal paths to participating on the web. Compiling an entire language environment or virtual machine to WebAssembly is perhaps better than transpiling to Javascript, but it is still an expensive operation.

This blogpost has primarily been centered around Scheme (Spritely's core tooling is written in Guile Scheme, and Hoot is a project to compile Scheme to WebAssembly, so this isn't too surprising). But the Spritely Institute is just that, a research institution. Hoot is breaking ground in some new spaces in WebAssembly land (and we are participating in the WebAssembly standards processes accordingly).

The web should be for everyone. We hope Hoot paves a path so that more languages may enter the web, including Python, Lua, Haskell, ML, and friends.

What Hoot means for Spritely

We showed some exciting demos in this blogpost, but it remains true that Hoot is still early. Some Scheme simple procedures can compile, but we have a ways to go. But we are on track, and the future looks bright. Hoot has been made possible due to a generous grant from Consensys/Metamask. This grant was given was a knowingly ambitious project; we are grateful for their support and are excited to be delivering towards those goals.

On the immediate roadmap is the compilation of the Scheme standard r7rs-small, with the goal to get Hoot compiled programs to appear on the r7rs benchmarks page. After that, it's onto getting Goblins itself to run in the browser and in the (increasingly) many places WebAssembly is supported. We are excited to have an optimistic path to get Spritely's tooling in the hands of as many users as possible.

We look forward to delivering more updates about Hoot as the project progresses. The future of WebAssembly (and Spritely) is bright!