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…

  1. Identify expressions, forms, and callsites (in Racket).
  2. Implement traditional recursive algorithms in direct style using numbers, lists, and conditionals.
  3. Differentiate tail calls (and tail recursion) vs. direct-style calls; be able to implement tail-recursive list accumulation algorithms.
  4. Draw cons diagrams for arbitrary tree-shaped (Racket) data and (at a high level) explain its relation to layout in RAM / cache.
  5. Use (and define) maps over lists and tree-shaped data.
  6. Use (and define) folds (such as foldl/foldr) to accumulate results of traversals over lists.
  7. 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.
  8. 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.
  9. Identify the reduction context for a given dynamic extent. Implement recursive functions using the U and Y combinators.
  10. Use and continuations to implement various higher-order control idioms, including preemptive returns, exceptions, loops, and coroutines.
  11. Identify properties guaranteed by the type-soundness theorem for the simply-typed lambda calculus. Identify types for expressions in the simply typed lambda calculus.
  12. 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.