| 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 1 |
| 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. |
Time permitting.↩︎