Course pages 2014–15

Compiler Construction

Revision Guide. The following past papers indicate the topics you can expect for the exam this year. Topics that will not be covered this year: cps transformation, defunctionalisation. Note however that these topics do contribute to a deeper understanding our universe.
• 2014 paper 3 question 4
• 2014 paper 3 question 5
• 2013 paper 3 question 4
• 2013 paper 3 question 5
• 2011 paper 3 question 4
• 2011 paper 3 question 5

• Lecture Slides
Lectures 1 -- 4
• cc2015_L1_to_L4.pdf (one slide per page)
• cc2015_L1_to_L4_2up.pdf (two slides per page)
Lecture 5
• cc2015_L5.pdf (one slide per page)
• cc2015_L5_2up.pdf (two slides per page)
Lecture 6
• cc2015_L6.pdf (one slide per page)
• cc2015_L6_2up.pdf (two slides per page)
Lecture 7 -- 9
• cc2015_L7_to_L9.pdf (one slide per page)
• cc2015_L7_to_L9_2up.pdf (two slides per page)
• expr_machine_v2.ml New version of the expression machine derivation.
Lectures 10, 11
• cc2015_L10_to_L11.pdf (one slide per page)
• cc2015_L10_to_L11_2up.pdf (two slides per page)
Lectures 12 --- Inspecting slang2_derive
Lectures 13 -- 16 (Lexing and Parsing)
• cc2015_L13_to_L16.pdf (one slide per page)
• cc2015_L13_to_L16_2up.pdf (two slides per page)
Simple experiments with ocamlyacc.
• g0.mly: a simple grammar with shift/reduce conflicts
• g0.output: states and rules of the parsing machine produced by ocamlyacc -v g0.mly
• g1.mly: fix some of the shift/reduce conflicst
• g1.output
• g2.mly: fix all of the shift/reduce conflicst
• g2.output
• g3.mly: add rule (expr ::= expr expr) to the grammar to produce shift/reduce and reduce/reduce conflicts
• g3.output
• g4.mly: first attempt to fix the grammar ...
• g4.output
• g5.mly: second attempt to fix the grammar. Fixed!
• g5.output
• parser_slang2_fixed.mly: Slang.2 grammar fixed.
• Source Code
• Code for basic transformations basic_transformations.tar.gz (covered in Lectures 3 and 4).
• expr_machine_v2.ml New version of the expression machine derivation.
• Code for Slang.1 interpreter slang1_interpret.tar.gz (covered in Lecture 2). Use "ocamlbuild slang.byte" to build.
• Code for Slang.1 to Jargon compiler slang1_compile.tar.gz (covered in Lecture 7).
• Code for Slang.2 derivations, from interpreter 0 to interpreter 5 slang2_derive.tar.gz (covered in Lecture 7).
• Code for Slang.2 derivations, from interpreter 0 to interpreter 9 slang2_derive_v2.tar.gz (covered in Lecture 12).
• parser_slang2_fixed.mly: Slang.2 grammar fixed.
• Recommended Supervisions
• Exercises_Set_1.ml
• Exercises_Set_2.txt
• Practical_Exercises_Set_1.txt
• Practical_Exercises_Set_2.txt
• Practical_Exercises_Set_3.txt
• 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/

Part II Project Suggestions

• From CakeML project
• More coming soon ....