Course pages 2016–17

Compiler Construction

Last change: Wed Feb 1 09:51:04 GMT 2017

• Lecture Slides. CompilerConstruction2017_2up.pdf (two slides per page)
• Source Code for our Slang compler can be found at GitHub: https://github.com/Timothy-G-Griffin/cc2016_cl_cam_ac_uk.
• Yacc sample grammars. 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.
• Practival_Exercises.txt (OCaml hacking). Please contribute to the GitHub code!
• 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
• Recommended Supervisions. Supervisors may wish to assign Practival_Exercises.txt as well.
  • 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 : coming soon ...

Additional Resources

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

• Recommended online book :
  Mogensen, T. (2011). Introduction to compiler design. Springer. http://www.diku.dk/ torbenm/Basics.
• 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/