| Subject | Materials | When | |
|---|---|---|---|
| 1 | Standard ML as a meta language, the Moscow ML system, abstract syntax, a simple expression language, direct interpretation of expressions, environments. | Lecture 1 slides
Exercise sheet 1 sem1.sml Moscow ML Programming language map | Wed 6 Feb at 9h (lecture only, no exercises) |
| 2 | Interpreters and compilers, static checking of programs, postfix (reverse Polish) notation, a stack (abstract) machine, Postscript, correctness of compilation relative to interpretation | Lecture 2 slides
Exercise sheet 2 Notes 2 sem2.sml sierpinski.eps expr/Stack.java | Wed 13 Feb at 13h |
| 3 | Concrete syntax, regular expressions, context free grammars, scanning and parsing: from linear text to abstract syntax tree, using mosmllex and mosmlyac, a scanner and parser for the expression language, a scanner and a parser for micro-SQL, a sublanguage of SQL; SML: simple Moscow ML modules and compilation units. | Lecture 3 slides
Exercise sheet 3 Notes 3 expr/Absyn.sml, expr/Exprlex.lex, expr/Exprpar.grm, expr/parse.sml expr/ex1.ex, expr/bad1.ex, expr/bad2.ex, usql/grammar.txt, usql/Absyn.sml, usql/Sqllex.lex, usql/Sqlpar.grm, usql/parse.sml Preparation: Read Sections 2.1-2.5, 3.1-3.5, and 3.15 of Torben Mogensen's Basics of Compiler Design. | Wed 20 Feb |
| 4 | Interpretation of a first-order functional language: arithmetic and logical expressions, non-assignable variables, if-then-else expressions, function calls (without explicit evaluation stack), and recursive closures. Explicit monomorphic types, type checking. | Lecture 4 slides
Exercise sheet 4 Notes 4 fun/grammar.txt, fun/Absyn.sml, fun/Funlex.lex, fun/Funpar.grm, fun/parse.sml, fun/fun.sml, fun/tychk.sml Env.sig, Env.sml | Wed 27 Feb |
| 5 | A higher-order functional language. An implicitly typed language. Parametric polymorphic types. Type inference. | Lecture 5 slides
Exercise sheet 5 Notes 5 sem5.sml, fun/hofun.sml, fun/tyinf.sml | Wed 6 Mar |
| 6 | Modelling an imperative language: assignable variables, arithmetic and logical expressions, variable declarations, assignment, loops, output; lvalues and rvalues; environment and store; parameter passing mechanisms; C pointers and arrays. | Lecture 6 slides
Exercise sheet 6 Notes 6 Naivestore.sig, Naivestore.sml, imp/imp.sml, imp/Parameters.cs, Sto.sig, Sto.sml, imp/grammar.txt, imp/Absyn.sml, imp/Clex.lex, imp/Cpar.grm, imp/parse.sml, imp/c.sml, imp/ex1.c, imp/ex2.c, imp/ex3.c, imp/ex4.c, imp/ex5.c, imp/ex6.c, imp/ex7.c, imp/ex8.c, imp/ex9.c Read Sections 5.1-5.5 of Kernighan and Ritchie. | Wed 13 Mar |
| 7 | An abstract machine with program counter, explicit evaluation stack, and instructions for arithmetics, jumps, conditional jumps, function call, return etc. Compilation of the imperative language micro-C to a sequence of abstract machine instructions, whose store is a collection of numbered storage cells. | Lecture 7 slides
Notes 7 Exercise sheet 7 imp/Machine.java, imp/prog0, imp/prog1, imp/Machine.sml, imp/comp.sml, imp/ex10.c, imp/ex11.c, imp/ex12.c, imp/ex13.c, imp/ex14.c, imp/ex15.c, imp/ex16.c, imp/ex17.c | Wed 20 Mar |
| 8 | A continuation-based interpreter for a functional language, exception-free modelling of exceptions; continuation-based interpreter for an imperative language, modelling of abrupt termination in loops (break, continue), ... |
Lecture 8 slides
Notes 8 Exercise sheet 8 cont/fun.sml, cont/imp.sml cont/Factorial.java | Wed 3 Apr |
| 9 | Backwards (continuation-based) code generation, one-pass compilation of boolean expressions into control flow code, avoid jumps to jumps, compile tail calls to execute in constant space. |
Lecture 9 slides
Notes 9 Exercise sheet 9 imp/contcomp.sml, imp/ex18.c, imp/ex19.c, imp/ex20.c | Wed 10 Apr |
| 10 | Java Virtual Machine (JVM) as a realistic abstract machine, code generation for the JVM. A comparison of JVM and CIL (Microsoft Common Intermediate Language) as used in Microsoft .NET. |
Lecture 10 slides
Notes 10 Exercise sheet 10 imp/jvmcomp.sml, imp/InOut.java, imp/ex13.java, imp/ex13.cs, Peter Bertelsen's SML-JVM Toolkit compiled for Windows, a brief description of it, Sun's JVM specification, Microsoft .NET Framework download (even source available since March 26). The ECMA Standard for the Common Language Infrastructure | Wed 17 Apr |
| 11 | Modelling of an object-oriented language: classes, objects with fields, objects with methods. Lexer and parser specifications for micro-Java, a sublanguage of Java. Comparison of Java and C#. |
Lecture 11 slides
Notes 11 Exercise sheet 11 oo/grammar.txt, oo/Absyn.sml, oo/Oolex.lex, oo/Oopar.grm, oo/parse.sml, oo/oo.sml, oo/ex1.java, oo/ex2.java, oo/ex3.java, oo/ex4.java, oo/Util.java oo/Invokevirtual.java, oo/Invokevirtual.cs, oo/Override.cs, oo/LinkedList.cs C# Language Specification (from Microsoft) | Wed 24 Apr |
| 12 | Recent trends and techniques in programming languages: Partial evaluation or automatic program specialization. Runtime code generation in Common Language Runtime. |
Lecture 12 slides
Notes 12 Mogensen and Sestoft: Partial Evaluation rtcg/Reflect0.cs, rtcg/Reflect1.cs, rtcg/Reflect2.cs, rtcg/Reflect0.java, rtcg/Reflect1.java, rtcg/Reflect2.java, rtcg/Reflect3.java, rtcg/Reflect4.java rtcg/RTCG1.cs, rtcg/RTCG2.cs, rtcg/RTCG3.cs, rtcg/RTCG4.cs, rtcg/RTCG5.cs, rtcg/RTCG6.cs, rtcg/RTCG2.java, rtcg/RTCG3.java, rtcg/RTCG4.java | Wed 1 May |