In the first term of my Master’s, I took the course CS 842: Advanced Topics in Language Design and Implementation. The course was broken down into 3 components: 20% participation, 40% a presentation, and 40% a project. The project specification was to implement a significant programming project of our own devising, with approximately 1 day of work per week for up to 2 months. Example projects included:
- Implement a mini interpreter to illustrate a language feature.
- Extend an open source language processor with a feature.
- Do a comparative analysis and benchmarking of a specific feature in different languages.
- Analyze a code base to determine which language features are really used.
- Write a program transformation tool for a specific purpose.
My project, that I negotiated with the professor Stephen Watt, was to build a compiler for a subset of Lua to WebAssembly. I was interested in doing something with WebAssembly, since I have professional experience in web development but never had the opportunity to experiment with WASM before. I chose Lua because it is a relatively small language, and one that I have a decent amount of experience with thanks to lots of game development I did as a teen in the Löve framework.
A short demo video I created for the project follows:
I had a few goals with the project:
-
Write a compiler for a dynamically typed language. My previous experiences in writing compilers consisted of implementing statically typed languages.
-
Write a garbage collector. My experience in compilers so far came from course work, which always allowed us to assume an infinite amount of memory.
-
Learn the intricacies of the WebAssembly platform and its virtual machine.
Overall, I would say I achieved each of these goals. I was able to implement the following features in my compiler and associated runtime:
- Integer,boolean,string,nil,function,andtablevalues
- If statements, While loops, Repeat-Until loops, Numerical For loops, Generic For loops over iterators
- Tables as maps from any type of non-nil key to any type of value
- String concatenation
- Assignment between variables of different types
- Well-defined equality checks between any types
- Functions as first class values with lexical scoping
- Functions returning multiple values
- Forwarding of multiple return values in return statements and function arguments
- Boolean operators
andandorwith short-circuit evaluation, as well as not - Boolean operators over integers: addition, subtraction, multiplication, division, modulo, less than, greater than, less than or equal to, greater than or equal to
- Garbage collection
- Primitive functions
printandipairs
A full description of the inner workings are available in this documentation PDF
And all of the source code is available in the following Github Repo