Index · Compiler design
WHILE to WASM
A WHILE (protolanguage) to WASM self-hosting compiler.
Online demo Compiler toolchain GitHub organization
Abstract
This project addresses the question of how a theoretically minimalist programming language can be practically adapted to modern runtime environments. The focus is on the elementary Turing-complete language WHILE. Using a specific application example, it is demonstrated that WHILE can not only represent models of computability but is also sufficient to implement a complete and efficient compiler targeting WebAssembly (WASM).
The task is to develop a compiler that translates WHILE programs into WASM and is entirely written in WHILE itself. This involves overcoming central challenges: the lack of support for module structures and complex control flows, handling arbitrarily large integers, ensuring efficient code generation, and constructing a multi-stage process for incremental self-compilation of the compiler.
As an approach, a minimalist compiler for WHILE is initially implemented that translates fundamental language constructs and generates initial WASM modules. This is followed by the development of a runtime library for arithmetic operations on arbitrarily large natural numbers and a translation tool that converts programs in an extended WHILE variant back into the base language. Through a multi-step process, a self-compiler ultimately emerges that uses its own WHILE definition to compile itself.
The result is a functional translation pipeline that converts WHILE programs into efficient WebAssembly code while applying rudimentary code optimisations for selected constructs. Tests confirm that the self-compiler can correctly process its own source code and produce an executable version identical in content to itself. It reproduces itself consistently over multiple iterations.
About
Together with Alex Kolenaty, we developed a complete compiler pipeline. Initially, we built a minimal compiler as a foundation. Alex then focused on creating a WASM BigInt runtime library, while I worked on the transpiler and the E-WHILE language, a superset designed to translate down to WHILE. Finally, we implemented a self-hosting compiler: Alex developed the lexer, and I handled the parser / generator modules, which produce the WASM binary format.
Our work demonstrates that a self-hosting compiler written in WHILE is efficient enough to reliably generate stable WebAssembly code during the bootstrapping process. Developing such a compiler posed significant challenges due to the limited expressiveness of WHILE, which required careful compromises in design and implementation. The simplicity of the language also provided clear advantages, enabling a straightforward implementation of the minimal bootstrap compiler.
The results deepen the understanding of minimalist compiler architectures and provide a foundation for further exploration in bootstrapping and compiler construction for restricted languages.