Alternative implementation of the ArithLang, VarLang, DefineLang, FuncLang, RefLang, and TypeLang languages used in COM S 3420 at Iowa State University. The languages are described in the textbook An Experiential Introduction to Principles of Programming Languages by Hridesh Rajan.
xlang is written using the master version of the Zig programming language. Zig allows xlang to run on many different platforms such as the web via WebAssembly.
The tokenizer is piped directly into code generation and xlang compiles the source code into a bytecode format on the fly. This technique is also used by the QuickJS JavaScript engine and avoids the cost of building a parse tree.
Values are efficiently stored in 64-bit floating point numbers using NaN boxing. The NaN boxing implementation used in xlang is adapted from the one I contributed to the Kiesel JavaScript engine.
Locals are immutable memory but they must be allocated on the stack for every function call. Defines are mutable memory so they are allocated as a list of registers at the top of the stack. Captured variables, i.e. using an outer function's local, are more complex and require attaching values to lambda values.
The tail call optimization reuses the stack of the current call when returning another function call. Note that this is not limited to self-recursive functions but also works when returning any function call to efficiently support mutual recursion.
Memory is managed via a simple garbage collector that maintains a free list amongst a list of pages. I did not spend any time optimizing the garbage collector, but more efficient methods such as generational garbage collection would most likely improve its performance.
The web playground uses the Monaco Editor, xterm.js, and a Wasm build of xlang to interpret programs on the web. Build the playground using
zig build playground
# --watch for build on save
# -Doptimize=ReleaseFast for optimized Wasm
Test files are located in the examples folder. Run the tests against xlang:
zig build test -Djava_compat
# --fuzz to enable fuzz testing
Run the tests against RefLang and TypeLang:
zig build test -Dreflang_source=../path/to/reflang -Dtypelang_source=../path/to/typelang