I’ve always been interested in language implementations, and have built a number of small interpreters of various types and styles, following along with books such as the fantastic Robert Nystrom’s Crafting Interpreters and Andrew Appels’s Modern Compiler Implementation in ML.
SpiderMite-lang is the next link in this long chain of learning and discovery, with a focus around more advanced techniques and compiler functionality that isn’t covered well (or at all) in books. It’s also one of my first few “unguided” language implementations, everything has been designed and built without following along with books or existing tutorials and as such it’s proven quite valuable from the lessons learned as the language has evolved.
The goal with this language is to implement a small ML/Ruby/Swift like language that has type-checking and pattern matching. Since I want to focus on more advanced passes within the compiler, the implementation uses a classic but simple hand written recursive-descent parser and has a basic “reference” tree-walking interpreter. These choices, while not ground breaking or interesting, lend themselves to a lot of quick flexibility when it comes to trying out new ideas around the type system and pattern matching.
Here’s a “kitchen sink” example of some SpiderMite code, as it appears in winter of 2023:
external def print(_ _: Any) -> Nil
external def toString(_ _: Any) -> String
let b = 1
let c = 41
def matchThings(a: Number) -> String do
let d = 0
loop do
match d with
| 10 do
print(10 * 3 + 7)
break toString(b + c) # "never" type for this branch, `loop` infers to type `String`
| i do
print(i)
d = i + a # value of the match expression isn't captured, it's okay that the branch doesn't align in types with the loop or the other branch
end
end
end
print(matchThings(a: 1))
SpiderMite has been a really interesting dive into interpreting and compiling pattern matching, and both the inclusion of type annotations within the parser output as well as the implementation of type checking and type inference through a quasi bi-directional type system. It also led me to experiment with different approaches to representing the AST that the parser outputs, in a way that attempts to work with Swift’s own type system and pattern matching without requiring too much boilerplate code for each processing pass that interacts with the AST.
All of this experience (plus a working fizz-buzz using the pattern matching feature) is exactly what my end goal for this project was. Consequently, it feels like this is a good point to consider the project done and to start on my next round of learnings to take this into a bytecode, stack based virtual machine interpreter!
external def print(_ _: Any, terminator: String) -> Nil
let counter = 0
loop do
# print(counter, terminator: " ")
match counter, counter % 3 == 0, counter % 5 == 0 with
| 50, _, _ do break nil
| count, false, false do print(count, terminator: "")
| _, true, false do print("fizz", terminator: "")
| _, false, true do print("buzz", terminator: "")
| _, true, true do print("fizzbuzz", terminator: "")
end
counter = counter + 1
print(" ", terminator: "")
end