Core Topics
The following topics are planned for this term.
| Topic | Understand | Demonstrate |
| Operational Semantics | Semantics of simple languages using interpreters or abstract machines. | 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. |
| 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. |
| Laziness | Eager and lazy evalution. Applications of infinite lists. Substitution and dataflow based laziness. | Trace code under lazy and eager evaluation. |
| State and Mutatation | Appropriate uses for state. Modelling state. The store. Variables. References and aliasing. | Trace code under pass by value and pass by reference. Implement store passing. |
| Types | Types, basic type inference/checking | Implement a simple type checker |
Optional Topics
Time permitting, we may look at some of the following.
| Monads | Combinators, injecting and unwrapping. Haskel do notation'' | Write simple programs using monads to model mutable state and short-circuit control flow. Translate between core combinator syntax and Haskell do notation. |
| Efficient Recursion | Iteration and Tail Recursion. Accumulators and Invariants. Recursive data structures (lists and trees). | Design and implement efficient recursive algorithms for lists and trees. |
| Memory Management | Reference Counting, Garbage Collection. | Trace the lifecycle of a linked set of language objects. |