BSc Programs as data


Lecture plan

Course weekISO weekDateSubjectMaterialsExercises After this week
135Mon 29 Aug F# as a meta language, abstract syntax, a simple expression language, direct interpretation of expressions in F# and C#, environments. PLCSD chapters 1 and 2 and Appendix A
and lecture01.pdf
1.1, 1.2, 1.3, 1.5 (implement toString instead of eval) no later than Tue 06 Sep You have installed Visual Studio 2010 or equivalent, eg. Mono 2.10, along with F# and the F# PowerPack. You can use F# Interactive to represent abstract syntax using F# datatypes, write evaluators and simplifiers for simple expressions.
236Mon 05 Sep Interpreters and compilers, static checking of programs, postfix (reverse Polish) notation, a simple abstract machine with stack, Postscript. Concrete syntax, overview of lexing and parsing: from linear text to abstract syntax tree.
PLCSD chapter 2
and lecture02.pdf
2.2, 2.3, 2.4, 2.8 no later than Tue 13 Sep You can write polymorphic functions and datatypes in F#. You can write and evaluate expressions in postfix notation, can distinguish an interpreter from a compiler, understand how to use a stack to store variables as well as intermediate results in very simple stack machine.
337Mon 12 Sep Lexing (scanning) and parsing using fslex and fsyacc. Scanner and parser specifications for the expression language and for micro-SQL. Lexer implementation: from regular expression to nondeterministic and deterministic finite automata. Parser implementation: From grammars to parsers; LR and LL grammars; bottom-up and top-down (recursive descent) parsers. PLCSD chapter 3
and Mogensen 2010 sections 2.1-2.7 except 2.6.1, 2.9
and Mogensen 2010 sections 3.1-3.6
and lecture03.pdf
3.2, 3.3, 3.4, 3.5, 3.6, 3.7 no later than Tue 20 Sep You can explain the concepts lexer, lexer generator, regular expression, nondeterministic and deterministic finite automata (NFA and DFA); can construct an NFA from a regular expression and construct a corresponding DFA; can modify a lexer specification and a parser specification to recognize new source syntax, and can use fslex and fsyacc to construct and use the corresponding lexers and parsers.
438Mon 19 Sep 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 rules; monomorphic type checking. Mogensen 2010 sections 3.12, 3.17
and PLCSD chapter 4
and lecture04.pdf
4.1, 4.2, 4.3, 4.4, 4.5 no later than Tue 27 Sep You understand how an LR parser automaton works in collaboration with the parser stack; you can hand-write a simple LL (recursive descent) parser; you can explain the effect of static scope and dynamic scope of variables; you can explain why closures are needed for static scope; you can extend a simple type checker for an explicitly typed functional language.
539Mon 26 Sep David: Higher-order functions in F# and C# and Java. A higher-order functional language. Parametric polymorphic types. Polymorphic type inference. Parametric polymorphism (generics) in Java and C#. PLCSD sections 5.1-5.4 and A.11 and chapter 6
and lecture05.pdf
6.1, 6.2, 6.3, 6.4 and 6.5 no later than Tue 4 Oct You can read type rules for an explicitly typed language and relate them to a type checker in F#; you can modify an interpreter for a simple higher-order functional language; you can define higher-order functions in F# and Java; you can define relevant generic types for classes and functions in F#, C# and Java.
640Mon 03 Oct Jonas: Modelling an imperative language: assignable variables, arithmetic and logical expressions, variable declarations, assignment, loops, output; expressions and statements; lvalues and rvalues; environment and store; parameter passing mechanisms; modelling pointers, pointer arithmetics and arrays. PLCSD chapter 7
and Fundamental Concepts (PDF)
and lecture07.pdf
7.1, 7.2, 7.3, 7.4 and 7.5 no later than Tue 11 Oct You can use concepts such as environment, store, lvalue, rvalue and pointer to describe the implementation and way of working of a simple imperative language. You can write C programs that allocate arrays and use pointer arithmetics correctly. You can modify the lexer and parser specifications for a realistic programming language.
741Mon 10 Oct 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. PLCSD chapter 8
and lecture08.pdf
8.1, 8.3, 8.4, 8.5 and 8.6 no later than Tue 25 Oct You can describe the run-time data structures and the functioning of a stack machine that is powerful enough to implement C, using concepts such as stack frame, base pointer, stack pointer, program counter, instruction interpretation loop. You can extend a compiler for a realistic programming language to generate code for additional kinds of expressions and statements.
42Fall break
843Mon 24 Oct Real-world abstract machines such as the Java Virtual Machine (JVM) and the Common Language Infrastructure (CLI, .NET); a comparison of JVM and CLI. A comparison of JVM implementations. Just-in-time compilation. Garbage collection techniques (reference counting, mark-sweep, stop-and-copy, generational), stack, and heap. List-C, a version of Micro-C with cons cells. PLCSD chapters 9 and 10
and Memory Management in HotSpot
and Realtime Garbage Collection
and lecture09.pdf
9.1 and 9.2 no later than Tue 1 Nov You can explain how a Java (or C#) source program relates to the JVM (or CLI/.NET) bytecode generated for that program, and how the virtual machine executes the bytecode. You can describe the major kinds of garbage collectors, and explain how the effect of a high memory allocation affects the time cost of garbage collection.
944Mon 31 Oct Continuations; a continuation-based interpreter for a functional language; exception-free modelling of exceptions; continuation-based interpreter for micro-Icon, a language with backtracking. PLCSD chapter 11
and lecture10.pdf
11.1, 11.2, 11.3, 11.4, 11.8 no later than Tue 8 Nov You can write simple functions in continuation-passing style, and describe how such functions are related to tail-recursive functions that use accumulating parameters. You can modify such functions to terminate computations early, and use continuations for error (exception) processing. You can modify a simple continuation-based interpreter for a language with backtracking, to handle new kinds of expressions.
1045Mon 07 Nov Backwards (continuation-based) code generation for micro-C, one-pass compilation of boolean expressions into control flow code, avoid jumps to jumps, compile tail calls to execute in constant space. PLCSD chapter 12
and lecture11.pdf
and ex13-code.txt
12.1, 12.2, 12.3, 12.4 no later than Tue 15 Nov  
1146Mon 14 Nov Scala, a functional and object-oriented language on the Java Virtual Machine platform. A Scala tutorial for Java programmers (2010) and An overview of the Scala programming language (2006) and lecture12.pdf Scala exercises, no later than Tue 22 Nov  
1247Mon 21 Nov More Scala: Implicits. Higher-kinded types. Monads, and their use in interpreters/semantics, for a small language with effects. Some comments on other recent programming languages: Clojure (2008), Google's Go language (2009), Ceylon (2011), Google's Dart language (2011). lecture13.pdf and ExpressionsMonads.scala and languagecomparison.xls
Language comparison exercise, no later than Tue 29 Nov  
1348Mon 28 Nov Maybe: Trial written exam (condensed to three hours).      

General information

Peter Sestoft, Last update 2012-03-26