Written Learning Objectives for CIS352
The following learning objectives will be formally assessed via written (or typed) exam throughout the term of CIS352. Each learning objective will be turned into a written exam question which students will have the opportunity to complete during quizzes / final.
The student must be able to…
- Identify expressions, forms, and callsites (in Racket).
- Implement traditional recursive algorithms in direct style using numbers, lists, and conditionals.
- Differentiate tail calls (and tail recursion) vs. direct-style calls; be able to implement tail-recursive list accumulation algorithms.
- Draw cons diagrams for arbitrary tree-shaped (Racket) data and (at a high level) explain its relation to layout in RAM / cache.
- Use (and define) maps over lists and tree-shaped data.
- Use (and define) folds (such as foldl/foldr) to accumulate results of traversals over lists.
- Perform common (beta, alpha, eta) reductions / conversions for the lambda calculus; evaluate lambda calculus terms to normal form using various reduction strategies, including call-by-name/value.
- Perform Church encoding to translate higher-level program constructs (variable-arity lambdas, `let`-binding, recursion) to the lambda calculus. Specifically, be able to use the U and Y combinators to implement recursion.
- Be able to understand code written with `call/cc` (i.e., full, undelimited continuations). Use `call/cc` to implement control constructs such as preemptive returns, exceptions, and loops.
- Write proof trees for correctly-typed terms in the simply-typed lambda calculus (and its immediate extensions), or explain (in English prose or using partial proof trees) when terms are ill-typed.