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.
Learning objectives with strikes have been changed
mid-semester to closer align exams with material covered in class as
the course naturally progressed.
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 by hand on small programs using numbers, cons cells, recursion, primitive arithmetic operations, let-binding, and application. Be able to evaluate such terms to normal forms.
Identify the reduction context for a given dynamic extent.Implement recursive functions using the U and Y combinators.- Use and continuations to implement various higher-order control idioms, including preemptive returns, exceptions, loops, and coroutines.
Identify properties guaranteed by the type-soundness theorem for the simply-typed lambda calculus.Identify types for expressions in the simply typed lambda calculus.- Write natural-deduction-style proof trees for correctly-typed terms in the lambda calculus, or explain (in english prose or using partial proof trees) when terms are ill-typed.