sampsyo
commented
9 months ago Sounds great, Stephen! Seems like a good scope for the project.
You briefly mentioned the possible need for type inference. May I suggest that, for this project, you try to develop a version of the language that has explicit types everywhere? This way, (1) it will be possible to measure progress before having HM implemented, and (2) if you eventually do add HM inference, these explicitly-typed programs will provide a very useful test oracle for checking the correctness of the inference.
What will you do?
Caiman is an IR for CPU/GPU computing that makes explicit how, when, and where computations occur. It seeks to strike a balance between single-source solutions like CUDA and SYCL which make optimization more difficult by hiding details pertinent to performance and direct API usage. Caiman consists of value, spatial, and timeline specification languages and an implementation language.
I will be implementing a frontend to allow users to write Caiman programs in an easy-to-use, high-level syntax. Specifically, for this project, I will implement the lowering from the front-end AST to the Caiman assembly. Caiman assembly is in continuation passing style, so one of the challenges will be converting the front-end control flow into CPS. Furthermore, the Caiman assembly lacks many of the instructions one might find in a typical IR such as arithmetic operations. The front end, however, has such operators that must be lowered to invocations of external functions on the host device.
If I have time, I'll also need to implement type deduction with Hindley–Milner.
How will you do it?
First, I'll need to flatten the nested AST of the front-end which should be straightforward. I'll then generate external functions in Rust for basic operators that are built into the front end and convert other higher-level constructs into a series of Caiman assembly instructions. For example, slices could be lowered as a buffer (pointer) and a start and end index.
For converting to CPS, I can turn each basic block into separate functions and convert conditions to selections of the next continuation to run.
How will you empirically measure success?
I plan on starting by writing some simple-ish motivating examples and focusing on the work required to fully lower these frontend examples into caiman assembly and running them end-to-end through the caiman compiler. Success will be the successful lowering of these examples/test cases and getting the correct result when executing the compiled programs.