CS 421: Programming Languages and Compilers

Syllabus and Study Guide for Midterm 1

Studying for this exam

[top]

  • Understand the lecture slides and discussions thoroughly.
  • Revisit the MPs and HWs 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 10 lectures, up to and including the lectures of user-defined recursive datatypes . The following give examples of the kinds of questions you are likely to be asked for each topic:

  • 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
    • Be able to describe the environment that results from a sequence of declarations
    • Be able to describe the closure that is the result of evalutating a function declaration
    • Understand what effect sequencing, function application and lambda lifting has on the order of evaluation of expressions
  • Recursion
    • Be able to write recursive functions, including (but not limited to) possibly tail-recursive or possibly forward 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.
  • 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 MP4.
    • Be able to write functions that use other functions as arguments
  • Continuations and Continuation Passing Style
    • Understand what the basic idea of what a continuation is.
    • Be able rewrite an operation / procedure in direct style to take a continuation to which to pass its results, while preserving the order of evaluation.
    • Be able to put a complex, possibly recursive procedure into full continutation passing style, while preserving the order of evaluation.
    • Be able to reproduce code for implementing the CPS transformation, given the mathematical formulation of its cases.
  • User-Defined Types
    • Be able to define recursive algebraic (variant) types in OCaml.
    • Know the difference between tuples and variant types, and when each should be used.
    • Be able to write OCaml functions over recursive algebraic types.
    • Be able to create a recursive algebraic type to model a problem.