sampsyo
commented
4 years ago Sounds pretty cool! One big warning, however: your type list = nil of () | cons of (int, ptr<list>) example is not just algebraic but also recursive, which is a whole thing. I strongly recommend focusing on one step at a time: get the basic sum/product types working first, and only then come back and add recursive types if you have extra time. Don't try to do all this at once!
I think the first thing to do—which I would like to see sooner rather than later—is nailing down the type syntax and the Bril opcodes for constructors/destructors. For example, I think you'd probably be best off with a syntax like sum<T1, T2, ...> and product<T1, T2, ...>, where all types remain anonymous, as they currently are in Bril. Adding type names and also variant names seems like overkill and more trouble than it's worth. (Names are good for humans, but remember that Bril is an IL, not a user-facing language—so you can compile your friendly Rust subset, which uses names, to an anonymous version in Bril.)
What will you do?
I will add algebraic data types, specifically n-tuples and variants (tagged unions), to the Bril specification/brili. I will also implement a type-checker for these types, a simple garbage collector, and a translator from a subset of Rust syntax to Bril.
How will you do it?
The tuples will be structurally typed and the variants will be nominally typed, so there will need to be a section of the bril file for variant type declarations. For example, types could look like
(int, bool, ptr<int>)ortype list = nil of () | cons of (int, ptr<list>).I will add instructions for constructing tuples, accessing the nth element of a tuple, constructing a variant, and accessing the value of a variant.
I will implement a type checker pass. This is necessary because brili does not check types and I want to be able to verify that bril programs are correct with respect to types given the extra complexity I will be introducing.
Both tuples and variants will be stack-allocated. I expect, however, that variants will be most useful in combination with pointers from the memory extension in order to avoid copying lots of data. In addition, I suspect that it will be difficult to manually free memory while using things like linked lists idiomatically, so to this end I plan to also implement a simple garbage collector. (I may be able to use the garbage collector from lesson 10.)
Typescript supports tuples but not variants (only Java-style enums), so I don't think extending the ts2bril translator to support algebraic data types will be particularly helpful. Instead, I am considering creating a translator for a subset of Rust syntax (rs2bril?) because Rust supports tuples and enums (which work like variants). This translator will help a lot with testing.
How will you empirically measure success?
I will measure the success of the brili extensions, the type checker, and the Rust translator by running sample programs that utilize the full range of added expressivity, such as programs operating on linked lists and trees, and verifying the correctness of their behavior in brili.
I will measure the success of the garbage collector by checking that memory usage is bounded in the test programs described above
Team members:
Me! (Will, wds68)
Notes:
I am aware of some similar past/current projects for adding record types, adding structs and garbage collection, and type checking. While I may take inspiration from these projects, I think that the proposed work discussed here is different in a number of ways such that it is not redundant: the first project added only record types, not variants; the structs/garbage collection project plans to compile Bril to LLVM rather than staying in Bril; and the type checking project did not incorporate type checking for algebraic data types.