CS 421: Programming Languages and Compilers

Syllabus and Study Guide for Midterm 2

Studying for this exam

[top]

  • Understand the lecture slides and discussions thoroughly.
  • Revisit the MPs and WAs 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 lecture 7 (Sep 12), which is on Continuations and Continuation Passing Style (CPS), followed by CSP Transformation, User-defined Data Types in OCaml, Type Systems, Type Derviations lecture 14 (Oct 5) The following give examples of the kinds of questions you are likely to be asked for each topic:

  • 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, with the resulting code being in full continutation passing style.
    • Be able to put a complex, possibly recursive, possibly higher-order procedure into full continutation passing style, while preserving the order of evaluation.
  • CPS Transformation
    • Be able to perform by hand steps of the transformation from OCaml to the formal language of CPS described in both WA5 and MP6.
    • Be able to reproduce code for implementing the calculating the free varaibles in an expression
    • Be able to reproduce code for implementing the CPS transformation of the abstract sytnax of an OCaml expression in abstract syntax for CPS, given the mathematical formulation of the cases for each of these in ordinary syntax.
  • User-Defined Type
    • 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, and write functions overit to meet a specification.
  • Polymorphic Types and Type Derivations
    • Explain and apply the key terminology of types and type systems.
    • Make proofs of polymorphic type derivations using typing rules.
    • Be able to recognize incorrect versus correct usages of the typing rules