| Syllabus and Study Guide for Midterm 2 |
|
- 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.
The exam will cover all the lectures in the course. It is a
ccomprehansive exam. Listed here are topics not previously listed
in midterm1.syllabus.html or
midterm2.syllabus.html.
They include writing parsers, Lambda Calculus, Evaluation
strategies (eager and lazy evaluation), Natural Semantics and
Transition Semantics,
Continuation Passing Style, Infinite data and call-by-need
evaluation. The following give
examples of the kinds of
questions you are likely to be asked for each topic:
- Parsers
- Be able to write a recursive descent parser for a given simple
grammar.
- Know the limitations and consequences of recursive descent
parsing, be able to calculate FIRST sets and know what their use is.
- 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.
- Lambda Calculus (LC)
- Be able to parse a lambda term correctly (e.g. which
variable is bound by which abstraction, which variable is
free, which application is top-most, etc.)
- Describe and know how to apply α-conversions
and β-reductions.
- Write simple non-recursive functions as
λ-expressions.
- Know the differences between and be able to
demonstrate lazy/eager evaluation and unrestricted
alpha-beta reduction.
- Understand Church numerals and Church booleans and how to
manipulate/generate them in LC (e.g, be able to write
addition and multiplication λ-expressions).
- Understand how other high-level datatypes and
primitive recursive functions are encoded in LC.
- 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 the evaluation of an expression in Transitional semantics.
- Be able to compare Natural and Transitional semantics.
- Understand the evaluation rules in both semantics, and be able to write evaluation rules for new syntactic constructs.
- 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
- Know how exceptions or exception-like behaviour can be handled using CPS.
- Know how tail and non-tail recursion work, and their differences.
- Infinite Data
- Know the difference between and demonstrate on an example call-by-value, call-by-name, and call-by-need semantics.
- Know how infinite data can be represented and processed.
- Understanding the idea of thunks and forcing as a way to
implement call-by-need evaluation.
- Objects
- Know how an object-oriented programming feature (e.g. inheritance, message dispatch, method overriding) can be implemented in a functional language.
- Know the basic difference between dynamic and static message dispatching.
|
|