BSc Programs as data


Lecture plan

Course weekISO weekDateSubjectMaterialsExercises After this week
135Mon 26 Aug F# as a meta language, abstract syntax, a simple expression language, direct interpretation of expressions in F# and C#, environments. Interpreters and compilers, static checking of programs, postfix (reverse Polish) notation, a simple abstract machine with stack, Postscript. PLC chapters 1 and 2 and Appendix A
and lecture0102.pdf
and rules for symbolic differentiation for 1.2(v)
1.1, 1.2, 1.4, 2.1, 2.2, 2.3 (optionally also 2.6) no later than Wed 04 Sep You have installed Visual Studio 2010/2012 or equivalent, eg. Mono 3.2, 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. 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 a very simple stack machine.
236Mon 02 Sep (Lecture by David, because Peter is in Stockholm) 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 2.1-2.5 (or BCD 2.1-2.7, 2.9, 3.1-3.6)
and lecture03.pdf
and David Christiansen's RE->NFA->DFA tutorial
3.2, 3.3, 3.4, 3.5, 3.6, 3.7 no later than Wed 11 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. Concrete syntax, overview of lexing and parsing: from linear text to abstract syntax tree.
337Mon 09 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 (or BCD 3.12, 3.17)
and PLC chapter 4
and lecture04.pdf
4.1, 4.2, 4.3, 4.4, 4.5 no later than Wed 18 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.
438Mon 16 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
and David Christiansen's polymorphic type derivation tutorial
6.1, 6.2, 6.3, 6.4 and 6.5 no later than Wed 25 Sep 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.
539Mon 23 Sep No lecture, both David and Peter are in the USA. The teaching assistants will be available in the exercise time slot to help students catch up on old exercises.      
640Mon 30 Sep 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 Kernighan and Ritchie chapter 5 about pointers
and lecture06.pdf
7.1, 7.2, 7.3, 7.4 and 7.5 no later than Wed 09 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 07 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 23 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 21 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 either 9.2 or 9.3 (see, no later than Wed 30 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 28 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. PLC chapter 11
and lecture09.pdf
11.1, 11.2, 11.3, 11.4, 11.8 no later than Wed 06 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 04 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-unoptimized.txt
12.1, 12.2, 12.3, 12.4 no later than Wed 13 Nov  
1146Mon 11 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 20 Nov  
1247Mon 18 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-2013.xls also in PDF
Optional exercise: complete the language comparison sheet  
1348Mon 25 Nov David: The pure functional language Haskell, laziness, type classes and kinds. (Peter is at F# in Finance in London) John Hughes: Why functional programming matters

General information

Peter Sestoft, Last update 2014-01-31