Course pages 2015–16

Compiler Construction

Last change: Thu Feb 25 16:59:03 GMT 2016

Study/Supervision/Revision Guide

• Exam questions from 2015, 2014, and 2013 represent the kinds of questions you can expect.
• Three topics from the lecture notes will not be examinable: (1) CPS and defunctionalisation transformations, (2) implementation of exceptions, and (3) implementation of OOP objects.
• Some past exam questions mention lambda lifting, a topic that we did not cover this year.
• Some of the lecture material is covered in the excellent online book http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics.

• Lecture Slides
Lectures 1 -- 6
• cc_2016_lectures_1_to_6.pdf (one slide per page)
• cc_2016_lectures_1_to_6_2up.pdf (two slides per page)
Lectures 7 -- 12
• cc_2016_lectures_7_to_12.pdf (one slide per page)
• cc_2016_lectures_7_to_12_2up.pdf (two slides per page)
• Grammars from Lecture 7. Use ocamlyacc -v file.mly to generate file.output.
  • e0.mly, e1.mly, e2.mly, e3.mly, e4.mly, e5.mly, e6.mly, e7.mly.
  • e0.output, e1.output, e2.output, e3.output, e4.output, e5.output, e6.output, e7.output.
• sml_exponential_typing.txt
Lecture 13 -- 16.
• cc_2016_lectures_13_to_16.pdf (one slide per page)
• cc_2016_lectures_13_to_16_2up.pdf (two slides per page)
• Yes, the x86 translations of FST and SND in the slides are not correct --- they are missing one indirection! Thanks for Gábor Szarka (gs509) for this in-depth analysis: gas_asm_poc.tar.
• https://en.wikibooks.org/wiki/X86_Assembly
• Source Code. Can also be found GitHub: https://github.com/Timothy-G-Griffin/cc2016_cl_cam_ac_uk. Please contribute!
• slang_v1 : This first version contains only the definitional interpreter.
  • slang_v1.tar.gz
  • slang_v1.zip
• slang_v2 : This version contains four additional interpreters, from higher-level to lower-level (the Jargon VM).
  • slang_v2.tar.gz
  • slang_v2.zip
• basic transformations : for lectures 11 and 12:
  • basic_transformations.tar.gz
  • basic_transformations.zip
• Recommended Supervisions
  • Exercises Set 1.
    • http://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2012p3q4.pdf (a) and (b)
    • http://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2013p3q5.pdf (a) and (b)
    • http://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2015p3q3.pdf
  • Exercises_Set_2.ml
  • Exercises_Set_3.txt
  • Practival_Exercises.txt (OCaml hacking)
• Ocaml Resources
• The offcial site : https://ocaml.org
• Try OCaml! : http://try.ocamlpro.com
• Side-by-side comparison of SML and OCaml syntax : http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html
• ocamlbuild is very useful for small projects like our interpreters and compilers. No Makefile required! http://caml.inria.fr/pub/docs/manual-ocaml-4.00/manual032.html
• OCaml Labs : http://www.cl.cam.ac.uk/projects/ocamllabs
• New Book: https://realworldocaml.org/v1/en/html/index.html

Additional Resources

Here are some optional materials that you may want to explore.

• General Concepts
• Compiler : http://en.wikipedia.org/wiki/Compiler
• Interpreter : http://en.wikipedia.org/wiki/Interpreter_(computing)
• Virtual Machine: http://en.wikipedia.org/wiki/Virtual_machine
• Just In Time (JIT) compilation : http://en.wikipedia.org/wiki/Just-in-time_compilation
• Continuation Passing Style :
  • http://en.wikipedia.org/wiki/Continuation-passing_style
  • CPS and JavaScript
    • Continuation-Passing Style: and why JavaScript developers might be interested in it: http://marijnhaverbeke.nl/cps>/li>
    • CPS and tail-call emimination in JavaScript : http://www.eriwen.com/javascript/cps-tail-call-elimination
    • CPS by example: http://matt.might.net/articles/by-example-continuation-passing-style
    • Asynchronous Programming and Continuation-passing Style in JavaScript : http://css.dzone.com/articles/asynchronous-programming-and
• Abstract Machines. My derivations of stack machines using CPS and defunctionalisation are very much inspired by the following papers.
  • Mitchell Wand. Deriving Target Code as a Representation of Continuation Semantics. ACM Transactions on Programming Languages and Systems, 4(3):496-517, July 1982.
  • Definitional interpreters for higher-order programming languages (1972). John C. Reynolds
  • Olivier Danvy and Lasse R. Nielsen. Defunctionalization at Work. June 2001.
  • : Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard. From Interpreter to Compiler and Virtual Machine: A Functional Derivation.March 2003.
  • : Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard.A Functional Correspondence between Evaluators and Abstract Machines.March 2003.
• Virtual Machines
• JVM
• http://jasmin.sourceforge.net/ : Jasmin is a JVM bytecode assembler, taking an ASCII foo.j file to a binary foo.class file.
• http://www.angelfire.com/tx4/cus/jasper/ : Jasper is a JVM bytecode disassembler, taking a binary foo.class file to an ASCII foo.j file in the Jasmin syntax. Note that the javap dissassembler also prodoces ASCII. However, there does not seem to be an associated assembler (please correct me if I'm wrong).
• https://github.com/Storyyeller/Krakatau : Krakatau. A JVM bytecode assembler/dissassembler.
• http://commons.apache.org/proper/commons-bcel : BCEL. The Byte Code Engineering Library provides ways to analyze, create, and manipulate (binary) Java class files (those ending with .class).
• Compiling other languages to the JVM
• http://www.dcs.ed.ac.uk/home/mlj : MLj compiles SML to JVM bytecode.
• Ocaml VM
• http://ocsigen.org/js_of_ocaml : js_of_ocaml. A OCaml bytecode to javascript converter. See this paper for a detailed description.
https://github.com/nojb/ocaml-c0 : A A C0 to Ocaml bytecode compiler, witten in Ocaml.
• HLVM
http://www.ffconsultancy.com/ocaml/hlvm : HLVM.
• Selected Open-Source Compilers
• LLVM toolkit http://llvm.org/
• JAVA
• http://openjdk.java.net : OpenJDK.
• http://jikes.sourceforge.net : Jikes. IBM
• SML
• http://mosml.org : Moscow ML.
• http://www.polyml.org/ : Poly ML.
• http://www.smlnj.org/ : Standard ML of NJ.
• http://www.mlton.org/ : MLton.
• https://github.com/melsman/mlkit : MLKit
• OCaml
• https://ocaml.org
• Idris http://www.idris-lang.org : Idris is a new experimental language with a dependent type system.
• whitespace! http://compsoc.dur.ac.uk/whitespace
• Verified Compilers. An interesting area of much recent work. See motivation herehttp://gallium.inria.fr/~xleroy/courses/VTSA-2013/.
  • CompCert : http://compcert.inria.fr
  CakeML : https://cakeml.org/