| Topic |
Understand |
Demonstrate |
| Operational Semantics |
Semantics of simple languages using interpreters or abstract
machines. |
Define evaluation functions for simple languages. Trace the
execution of code including scoping, recursion, conditionals. |
| Syntax |
EBNF or equivalent notation for grammars. Concrete and abstract
syntax |
Parse using a grammar. Define and use a data type for abstract
syntax. Use pattern matching. |
| Higher Order Programming |
Functions as first class values. Function composition and
combinators, generic functions. |
Write folds and other generic functions. Implement simple list
operations using folds. |
| Scope |
Lexical and dynamic scope. Environments. |
Trace code using different scoping rules. Implement dynamic and
lexical scope. |
| Laziness |
Eager and lazy evalution. Applications of infinite lists.
Substitution and dataflow based laziness. |
Trace code under lazy and eager evaluation. Implement lazy and eager
evaluation. |
| State and Mutatation |
Appropriate uses for state. Modelling state. The store. Variables.
References and aliasing. |
Write non-trivial programs without mutation. Trace code under pass
by value and pass by reference. |
| Types |
Types, basic type inference/checking |
Deduce types of expressions, including function types. Structure
code using variant types. Implement a simple type checker |
| Recursion |
Iteration and Tail Recursion. Accumulators and Invariants. Recursive
data structures (lists and trees). Let-over-lambda. Practical
implementations for recursion. |
Design and implement efficient recursive algorithms for lists and
trees. Implement evaluators supporting recursive functions. |
| Metacircularity and Embedding |
Implicit and explicit influence of host language on target. |
Explain dangers and benefits of re-using host language
features. |
| Memory Management |
Manual and automatic memory management. Collector and Mutator.
Roots. Liveness. Object Graphs. |
Trace the life cycle of a linked set of language objects. |
| Garbage Collection |
Mark and Sweep. Compaction. Copying collectors. Generational
Collectors. Reference counting. |
Implement a simple garbage collector. |