|
- Understand the lecture slides and discussions thoroughly.
- Solve relevant problems in the Exam Database.
- Revisit the MPs 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 the material through the lecture on CPS
(to be given this coming Monday). The exam is comprehensive,
so you can expect a repeat of some material on type derivations,
lambda calculus, etc. A rough estimate is that 1/3 of the material
is from the lectures included in the midterm, while 2/3 is new.
The following give examples of the kinds of
questions you are likely to be asked for each topic (but the exam database
provides a more comprehensive and useful source of example questions):
- 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
- Recursion
- Be able to write recursive functions, possibly 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.
- User-Defined Types
- Be able to define record types and disjoint (variant)
types in OCaml.
- Know the difference between record and disjoint
types, and when each should be used.
- Be able to write OCaml functions over recursive disjoint types.
- 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 MP1.
- Be able to write functions which use other functions
as arguments
- Be able to write map and fold functions appropriate
to user-defined data types (like in lecture and in MP2)
- Types and Type Derivations
- Explain and apply the key terminology of types and
type systems.
- Make type proofs and type inferences using typing rules
- 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.
- Lambda Calculus (LC)
- Describe and know how to apply α-conversions
and β-reductions.
- Write simple non-recurisve functions as λ-expressions.
- Understand Church numerals and how to
manipulate/generate them in LC (e.g, be able to write
addition and multiplication λ-expressions).
- Understand how other high-level datatypes are implemented in LC.
- Be able to write functions that manipulate user-defined
datatypes in LC
- Regular Expressions & DFAs
- Be able to tell when a string is in the language of a
regular expresion or DFA
- Be able to construct simple DFAs/Regular Expression
given a description of the strings they should accept.
- Be able to convert from NFAs to DFAs
- Be able to convert from Regular Expressions to NFAs
- Lexing
- Be able to construct a simple lexer given
a description of the language
- Given a lexer definition and an input string,
be able to specify the list of tokens that
will be generated by the lexer
- Context-Free Grammars and Parsing
- Given a description of the language, be able
to construct a context-free grammar for the
language
- Given a context-free grammar and an input
string, illustrate left-most and right-most
(canonical) derivations
- Given a context-free grammar and an input
string, show a parse tree, possibly
constrainted by a certain derivation order
- Be able to say whether a given grammar is
ambiguous, including showing multiple
parse trees to illustrate the ambiguity
- Natural and Transition Semantics
- Given a description of the semantics for
a language, show a derivation (the
evaluation in the semantics) for a term in
the language
- Given existing semantic rules and an
English-language description of a new language
feature, give rules for the new feature
- Names and Variables
- Be able to calculate the referencing
environment at a program point in both
static and (with a specified path) dynamic
scope
- Be able to determine the values variables
will take on in simple programs under both
static and dynamic scope
- Data Abstraction and ADTs
- Understand the basic data abstraction
capabilities of most languges -- arrays,
records, variants, and tuples
- Understand the limitations of these
abstractions and the need for ADTs
- Be familiar with ADT mechanisms as
illustrated in languages such as Ada
and C++
- Be familiar with the concept of a generic,
or parameterized, ADT
- Be aware of the limitations of ADTs
- Object-Oriented Languages
- Be familiar with the core concepts in OO
languages: encapsulation, inheritance,
and polymorphism
- Be familiar with design decisions in each
of these concepts, including different protection
levels in encapsulation, different models of
inheritance and code reuse, interaction between
inheritance and encapsulation, and the basic
workings of polymorphism and dynamic dispatch
- Control Flow
- Understand the use of continuations to model
control flow as functions
- Be familiar with the use of exceptions, especially
in Java, and alternate models (such as return codes
from functions) that have historically been used
in languages
- Be familiar with the use of and terminology
around coroutines, including having a basic
understanding of the model of execution
- Continuation-Passing Style
- Be familiar with the terminology associated with
continuation-passing style, including such terms
as tail position, tail call, direct style,
and available
|
Last updated Th June 22 21:26:00 CDT 2006