| 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. |
| 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. Analyse code samples
using boxes or vectors. Implement a simple object system. |
| Types |
Types, basic type inference/checking |
Deduce types of expressions, including function types. Structure
code using variant types. Implement a simple type checker |
| 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. Dynamic typing. |
Trace the life cycle of a linked set of language objects. Implement
and use a tagged store. |
| Garbage Collection |
Mark and Sweep. Compaction. Copying collectors. Generational
Collectors. Reference counting. |
Implement a simple garbage collector. |