UNB/ CS/ David Bremner/ teaching/ cs4613/ outcomes
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.