BSc Programs as data


Lecture plan, preliminary

Course weekISO weekDateSubjectMaterialsExercises After this week Your feedback
135Mon 30 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) You have installed VS2010. You can use F# Interactive to write small functions, represent abstract syntax using F# datatypes, write evaluators and simpliers for simple expressions. Your feedback
236Mon 6 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 14 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. Your feedback
337Mon 13 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 21 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. Your feedback
438Mon 20 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 28 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. Your feedback
539Mon 27 Sep Higher-order functions in F# and C# and Java. Google MapReduce. PLCSD sections 5.1-5.5 and A.11
and Google MapReduce paper
and lecture05.pdf
5.1, 5.3, 5.4, 5.5 no later than Tue 5 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 explain how higher-order functions may be used to describe MapReduce and parallel-for operations. Your feedback
640Mon 4 Oct Hannes: A higher-order functional language. Parametric polymorphic types. Polymorphic type inference. Parametric polymorphism (generics) in Java and C#. PLCSD chapter 6
and lecture06.pdf
6.1, 6.2, 6.3, 6.4 and 6.5 no later than Tue 12 Oct   Your feedback
741Mon 11 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. 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 26 Oct   Your feedback
42Fall break
843Mon 25 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 2 Nov   Your feedback
944Mon 1 Nov 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 9 Nov   Your feedback
1045Mon 8 Nov Hannes: 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 16 Nov   Your feedback
1146Mon 15 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 23 Nov   Your feedback
1247Mon 22 Nov Scala, a function/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
    Your feedback
1348Mon 29 Nov Trial written exam (condensed to three hours).        

General information

Peter Sestoft, Last update 2011-02-21