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 lecture 8 (Sept 15), which is on The CPS Transformation, followed by Data Types in OCaml, up to and including lecture 19 (Oct 25), the lecture Intro to BNF Grammars and Ambiguous Grammars. The following give examples of the kinds of questions you are likely to be asked for each topic:

• CPS Transformation
  • 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 an OCaml expression, given the mathematical formulation of the cases for each of these.
• 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.
• Polymorphic Types and Type Derivations
  • Explain and apply the key terminology of types and type systems.
  • Make proofs of polymorphic type derivations and polymorphic type inferences using typing rules
  • Be able to recognize incorrect versus correct usages of the typing rules
• Polymorphic Type Inferences
• Implement polymorphic type inferences using polymorphic typing rules, include the gathering constraints
• Unification
  • Solve simple unification problems such as the ones in the lecture slides.
  • Recognize correct versus incorrect applications of steps in the unification algorithm.
  • Know how unification is used for pattern matching, type checking, and type inference.
• Regular Expressions & Regular languages
  • Be able to tell when a string is in the language of a given regular expression
  • Be able to construct simple Regular Expression or Regular Grammar given a description of the strings they should accept.
• Lexing
  • Be able to describe lexical items using regular expressions
  • Be able to write a simple lexer in ocamllex by providing semantic actions associated with corresponding regular expressions
  • Be able to write mutually recursive lexers in ocamllex, and use arguments to lexers to be able to implement different kinds of comments
• BNF Grammars
  • Be able to create a grammar that generates a given language (set of strings) described in English
  • Be able to build a parse tree for a string in the language of a grammar, or say none exists if the string is not in the language.
  • Be able to create a family of data types (abstract syntax trees) representing the parse trees of a given grammar.
  • Be able to demonstrate that a grammar is ambiguous, if it is.