Course pages 2018–19

Compiler Construction

Last change: Mon Feb 18 09:44:12 GMT 2019 (Added "64 bit x86 experiments")

Lecture Slides.
- Compiler_Construction_2019_2up.pdf (two slides per page)
- Compiler_Construction_2019.pdf (one slide per page)
Source Code for our Slang compler can be found at GitHub: https://github.com/Timothy-G-Griffin/cc_cl_cam_ac_uk.
Recommended online book :
Mogensen, T. (2011). Introduction to compiler design. http://www.diku.dk/~torbenm/Basics.
64 bit x86 experiments
- x86 tutorial
- A slang implementation in Rust, by Nathan Corbyn https://github.com/doctorn/rusty_slang
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
- OCaml virtual machine.
Yacc sample grammars. Use ocamlyacc -v file.mly to generate file.output.
- e0.mly, e0.output : simple expressions, with shift-reduce conflicts
- e1.mly, e1.output: fix conflics with precedence directives
- e2.mly, e2.output: add unary "not" to grammar and get get new shift-reduce conflicts
- e3.mly, e3.output : fix conflics with precedence directives
- e4.mly, e4.output: add "e e" to grammar, get new conflicts
- e5.mly, e5.output: rewrite grammar to get rid of conflicts
- e6.mly, e6.output add unary "bang" to grammar and get a new shift-reduce conflicts
- e7.mly, e7.output : : fix conflics with precedence directives
Supervision Suggestions. Supervisors are strongly encouraged to assign practical work as well.
- (1) Lexing and parsing.
  - From Introduction to compiler design: Read Chapters 2 and 3 and do as many of the associated exercises as possible. Yes, solutions are available online, but don't peek before attempting on your own.
  - Some past tripos questions on similar topics:
    - y2015p3q3
    - y2012p3q4, (a), (b)
- (2) Program transformations.
  - Review basic transformations.
  - exercieses_cps.ml
  - y2017p23q4
- (3) A few past tripos questions:

Additional Resources

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

Introduction to X86-64 Assembly for Compiler Writers
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

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 C0 to Ocaml bytecode compiler, witten in Ocaml.