x64 Compiler

Over my Spring 2023 semester at Northeastern, I was enrolled in CS 4410 - Compilers. In that class, I created a compiler for a functional, (initially) dynamically-typed programming language to x64 assembly with my partner Ryan Jung.

We used OCaml to store the ANF intermediate representation and perform transformations to assembly, and created a runtime with C to handle operations such as printing, collecting input, and executing garbage collection. We also implemented type checking and type inference with the logic DSL miniKanren in Racket.

We supported the following features:

• Basic datatypes, such as integers and booleans.
• Tuples with mutable members, arbitrary element access, nested tuples, and cyclic tuples (via mutation).
• Primitive prefix and infix operators for checking types at runtime and performing simple boolean and integer operations.
• First-class functions that allowed for higher-order functions, mutual-recursion, and anonymous functions (lambdas).
• Garbage collection in the C runtime by analyzing the stack using Cheney's algorithm.
• Register-allocation optimization to optimize register and stack allocations by analyzing liveness of variables and creating and coloring an interference graph.
• Type checking and type inference via declaring logic relations to define type constraints with miniKanren and Racket.

We had the following phases in the OCaml portion of our compiler:

• Lexing and parsing with ocamllex and ocamlyacc.
• Checking the well-formedness of the program.
• Tagging expressions with unique tags.
• Renaming identifiers to be unique using the tags.
• Desugaring expressions like tuple-bindings.
• Type checking the program.
• Transforming the expressions into the ANF representation.
• Locating bindings (depending on allocation strategy).
• Compiling the ANF into assembly.