UNB/ CS/ David Bremner/ teaching/ cs3613/ outcomes

Topic

Understand

Demonstrate

Operational Semantics

Semantics of simple languages using interpreters or abstract machines.

Define and use abstract evaluation rules. 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. Implement store passing.

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

Reference Counting, Garbage Collection.

Trace the lifecycle of a linked set of language objects. 2


  1. Time permitting.

  2. Time permitting.