Notes on: An Introductory Compilers Class

Neel Krishnaswami posted an outline of a (yet fictional) Introductory Compilers Class and I found the syllabus intriguing.

My own compiler construction class was 7 years ago, and we didn’t implement some of the fancier features such as polymorphism or SSA. So I’m pondering doing another toy compiler but this time using the references of above post.

I also want to pickup Rust, in which I’ve so far only dabbled into, and I think it’s a kind of problem where Rust is quite suitable.

Lexing and Parsing

I’m going to skip this at first, because I’m quite familiar with the theory and techniques.

Typechecking

Here, Krishnaswami proposes an interesting approach of Cousot.Patrick Cousot, “Types as Abstract Interpretations,” in Conference Record of Popl’97: The 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Papers Presented at the Symposium, Paris, France, 15-17 January 1997, ed. Peter Lee, Fritz Henglein, and Neil D. Jones (ACM Press, 1997), 316–31, https://doi.org/10.1145/263699.263744.

I’ll skip this for now as the proposed type system is not very interesting.

Conversion to SSA/CPS

Here comes the first part I’m curious about, translating the code via CPS into SSA, as explained in Richard Kelsey’s paper.Richard A. Kelsey, “A Correspondence Between Continuation Passing Style and Static Single Assignment Form,” SIGPLAN Not. 30, no. 3 (March 1, 1995): 13–22, https://doi.org/10.1145/202530.202532.

MLton uses a similar approach.