Studying for this exam

[top]

• Understand the lecture slides and discussions thoroughly.
• Solve relevant problems in the Exam Database.
• Revisit the MPs and make sure you understand the solutions thoroughly. Repeat any you are not comfortable with.
• Take the sample exam as a dry-run for the actual exam.

Syllabus

[top]

The exam will cover the first 13 lectures, up to and including regular expressions and DFAs as means of describing languages. The following give examples of the kinds of questions you are likely to be asked for each topic (but the exam database provides a more comprehensive and useful source of example questions):

• Basic OCaml
  • Know the basic constructs (e.g., match, fun, let, let rec) like the back of your hand.
  • Be able to evaluate OCaml expressions
  • Be able to determine the type of OCaml expressions
• Recursion
  • Be able to write recursive functions, possibly tail-recursive.
  • Be able to recognize whether a function is tail-recursive, and when a recursive call is in tail call position
  • Understand the performance benefits of tail recursion.
• User-Defined Types
  • Be able to define record types and disjoint (variant) types in OCaml.
  • Know the difference between record and disjoint types, and when each should be used.
  • Be able to write OCaml functions over recursive disjoint types.
• Higher Order Functions (HOFs)
  • Be able to write the definitions of the common HOFs.
  • Be able to use map and fold to implement other functions, as in MP1.
  • Be able to write functions which use other functions as arguments
• Types and Type Derivations
  • Explain and apply the key terminology of types and type systems.
  • Make type proofs and type inferences using typing rules
• Unification
  • Solve simple unification problems such as the ones in the lecture slides.
  • Know how unification is used for pattern matching, type checking, and type inference.
• Lambda Calculus (LC)
  • Describe and know how to apply α-conversions and β-reductions.
  • Write simple non-recurisve functions as λ-expressions.
  • Understand Church numerals and how to manipulate/generate them in LC (e.g, be able to write addition and multiplication λ-expressions).
  • Understand how other high-level datatypes are implemented in LC.