Alok Menghrajani

Security engineer at Square. Previously co-author of Hack and put the 's' in https at Facebook. Maker of CTFs.

Home | Contact me | Github | Twitter | Facebook

The goal of the compilers course is to give students an overview of how compilers work and let them experience the challenges of an actual implementation.

The course, thought by Prof. Peter Lee, used Andrew Appel's very reputated book: "Modern Compiler Implementation in ML". I however programmed in OCaml, which is similar to ML (both are functional programming languages).

You might wonder why functional programming is well suited for writing compilers. There are two reasons: processing tree structures is easier with functional programming. Support for complete case matching provides errors at compilation vs run time.

The compiler was implemented in 3 phases:

  • the first phase was a compiler for a very simple (assignments-only) language, that we called 'A'. The goal was to learn how to use our tools (parser and grammar) and write a code generator.
  • the second phase was a compiler for a language which had conditionals (basic blocks) called 'B'. source
  • the third phase was a compiler for a safe subset of C. I implemented type checking, fat pointers and garbage collection.

The main challenge was writing the type checker and doing register allocation for x86. In order to allocate the variables to registers, I first did liveness analysis and then register allocation using graph coloring.

I used the Boehm-Demers-Weiser garbage collectory.

Finally I also wrote a PS libary, which allowed me to write small programs that would generate nice graphics in PS format.

For more information about C like safe languages, have a look these projects:

Compilers are an interesting piece of software. More and more applications, such as Office or Photoshop, have built-in runtime engines or compilers, which let the user write macros.