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 all the lectures in the course. It is a comprehansive exam. Listed here are topics not previously listed in midterm1.syllabus.html or midterm2.syllabus.html. They include writing lexers in ocamllex, writing parsers in ocamlyacc, Natural Semantics and Transition Semantics, Lambda Calculus, and Axiomatic Semantics. The following give examples of the kinds of questions you are likely to be asked for each topic on the exam:

• 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 recognize when there is a type error in code and why it is an error
  • be able to describe the environment that result from a sequence of declarations
  • be able to describe the closure that is the result of evaluating a function declaration
• Recursion
  • Be able to write recursive functions, possibly forward recursive or 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.
• 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.
  • Be able to write functions that use other functions as arguments
• Continuation Passing Style
  • Know what a continuation is
  • Know what makes a function be in CPS
  • Be able to write the CPS version of a given function
  • Be able to control the order of evaluation using continuations
• CPS Transformation
  • Be able to reproduce code for implementing the calculation of 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 Types
  • Be able to define recursive algebraic (variant) types in OCaml.
  • Know the difference between tupples and algebriac 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 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.
  • Know how unification is used for pattern matching, type checking, and type inference.
• Regular Expressions & Right Regular Grammars (RRGs)
  • Be able to tell when a string is in the language of a regular expression or a Right Regular Grammar.
  • Be able to construct simple RRGs/Regular Expression 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, or strings
• BNF Grammars
  • Creating 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.
  • Demonstrate that a grammar is ambiguous, if it is.
  • Be able to give a unambiguous grammar generating the same language as a given ambiguous grammar, for common sources of ambiguity.
• Parsers
  • Be able to write a simple parser in ocmalyacc by providing an unambiguous attribute grammar using a tokens type and a family of types for abstract syntax.
  • Know how Action and Goto tables are used to implement an LR parser (we did not cover, and you are not responsible for how to generate these tables from a grammar).
  • Know what shift/reduce and reduce/reduce conflicts are, why they happen, and how they can be resolved.
• Operational Semantics
  • Be able to derive the proof tree for the evaluation of an expression in Natural semantics.
  • Be able to derive the proof tree for one step of the the evaluation of an expression in Transition semantics.
  • Be able to compare Natural and Transition semantics.
  • Understand the evaluation rules in both semantics, and be able to write evaluation rules for new syntactic constructs.
  • Be able to implement Natural and Transition semantics rules as OCaml programs.
• Lambda Calculus (LC)
  • Be able to parse a lambda term correctly (e.g. which variable is bound by which abstraction, which variable is free, what the scope of an abstraction is, what the grouping of a series of applications is, which application is top-most, etc.)
  • Describe and know how to apply α-conversions, α-equivalence and β-reductions.
• Axiomatic Semantics
  • Be able to prove simple statements in Floyd-Hoare Logic, similar to the example of {y=a} if x < 0 then y:= y-x else y:= y+x {y=a+|x|} that was done in class.
  • Be able to prove a statement about a simple while loop, as in the definition of factorial.