BSc Programs as data


Lecture plan

Course weekISO weekDateSubjectMaterialsExercises After this week
135Mon 27 Aug F# as a meta language, abstract syntax, a simple expression language, direct interpretation of expressions in F# and C#, environments. PLC chapters 1 and 2 and Appendix A
and lecture01.pdf
1.1, 1.2, 1.3, 1.4 no later than Wed 05 Sep. PDF of chapter 1 exercises. 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 03 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.
PLC chapter 2
and lecture02.pdf
2.1, 2.2, 2.3, 2.6 no later than Wed 12 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 10 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. PLC chapter 3
and Mogensen ICD sections 1.1-1.8
and Mogensen ICD sections 2.1-2.5
and lecture03.pdf
3.2, 3.3, 3.4, 3.5, 3.6, 3.7 no later than Wed 19 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 17 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 ICD sections 2.11, 2.12, 2.16
and PLC chapter 4
and lecture04.pdf
4.1, 4.2, 4.3, 4.4, 4.5 no later than Wed 26 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 24 Sep 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#. PLC sections 5.1-5.4 and A.11-A.12 and chapter 6
and lecture05.pdf
6.1, 6.2, 6.3, 6.4 and 6.5 no later than Wed 03 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 01 Oct 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. PLC chapter 7
and Fundamental Concepts (PDF)
and chapter about pointers
and lecture06.pdf
7.1, 7.2, 7.3, 7.4 and 7.5 no later than Wed 10 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 08 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. PLC chapter 8
and lecture07.pdf
8.1, 8.3, 8.4, 8.5 and 8.6 no later than Wed 24 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 22 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. PLC chapters 9 and 10
and Memory Management in the HotSpot JVM
and Realtime Garbage Collection
and lecture08.pdf
9.1 and 9.2 no later than Wed 31 Oct 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 29 Oct (David:) Continuations; a continuation-based interpreter for a functional language; exception-free modelling of exceptions; continuation-based interpreter for micro-Icon, a language with backtracking. PLC chapter 11
and lecture09.pdf
11.1, 11.2, 11.3, 11.4, 11.8 no later than Wed 07 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 05 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. PLC chapter 12
and lecture10.pdf
and ex13-code.txt
12.1, 12.2, 12.3, 12.4 no later than Wed 14 Nov  
1146Mon 12 Nov Scala, a functional and object-oriented language on the Java Virtual Machine platform. A Scala tutorial for Java programmers (2011) and An overview of the Scala programming language (2006) and lecture11.pdf Scala exercises, no later than Wed 21 Nov  
1247Mon 19 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). lecture12.pdf and ExpressionsMonads.scala and languagecomparison-2012.xls also in PDF
Optional exercise: complete the language comparison sheet  
1348Mon 26 Nov Automatic program specialization and the Scheme programming language. lecture13.pdf    

General information

Peter Sestoft, Last update 2013-02-21