CAS CS 320 Final Exam Prep Material

This page contains some information/material may be useful in preparing for the final exam. The information here is not exhaustive, and I can pretty much guarantee that there will be at least one question on the final exam this is distinct from any problem that we've done before.

General Study Material

OCaml Exercises: A collection of basic exercises by the OCaml folks
OCaml Programming: Correct + Efficient + Beautiful: A reminder that the textbook to which we casually refer has exercises in it

Previous Exams

You should be able to…

~~design and implement a good and novel programming language~~ (yes, but not during the exam)

Basic OCaml

solve basic programming exercises
implement functions both directly and tail-recursively
determine if a function is tail-recursive
state the benefits of tail-recursion
write mutually recursive functions

Polymorphism

determine an expression that has a given polymorphic type
determine by inspection the (polymorphic) type given to an expression by OCaml
state the benefits of polymorphism
explain what restricts the type of an expression, e.g., why a type parameter does or does not appear in the type

Inference Systems

Translate an inference rule into an English description
Translate an English description into a inference rule
Write a derivation for a judgment in a potentially unfamiliar inference system
Design new (basic) rules for inference systems related to ones we've covered in this course

Algebraic Data Types (ADTs) and Records

design ADTs/records for a given programming task
determine ADTs/records based on use in OCaml code
write functions using pattern matching on ADTs/records
write functions using common ADTs, e.g., lists, trees, options, results, S-expressions, etc.

Higher-Order Programming

implement a function using map, filter, fold_left, and fold_right
implement new higher-order functions
state the benefit of higher-order functions
state and use the formal semantics of higher-order programming

Formal Grammar

determine the terminal and nonterminal symbols of a grammar
determine if a sentence is recognized by a grammar
give both a (leftmost) derivation and a parse tree for a sentence recognized by a grammar
determine if/demonstrate that a grammar is ambiguous
give an unambiguous grammar for basic formal languages, e.g., S-expressions, arithmetic expressions, etc.
determine the associativity of an operator based on a given grammar
determine the relative precedence of a pair of operators based on a given grammar

Operational Semantics

state the benefits/downsides of small-step and big-step semantics
give a small-step semantics that is equivalent to a given big-step semantics
give a big-step semantics that is equivalent to a given small-step semantics
give a derivation in a potentially unfamiliar semantic system

The Substitution Model

correctly parenthesize λ-expressions using the precedence/associativity rules of abstraction and application (seriously, figure this out)
determine the free variables of an expression
state the formal definition of α-equivalence
determine if two λ-expressions are α-equivalent
state the formal definition of capture-avoiding substitution
perform capture-avoiding substitution on a given expression
state the benefits/downsides of call-by-name (CBN) and call-by-value (CBV) semantics
give an expression that's easy for CBN and hard for CBV
give an expression that's hard for CBN and easy for CBV
give a semantic derivation of an untyped λ-expression for a given semantics
determine if evaluating an untyped λ-expression terminates for a given semantics
determine if evaluating an untyped λ-expression gets stuck for a given semantics
give a semantic derivation for the untyped λ-calculus
give a semantic derivation in a potentially unfamiliar alternative semantic system for the untyped λ-calculus

The Environment Model

state the difference between lexical and dynamical scoping
state of formal definition (and the point) of closures
determine if a given semantic inference system correctly implements lexical scoping
give a semantic derivation in a semantic system with closures
give a semantic derivation in a potentially unfamiliar alternative semantic system which uses closures
determine by inspection the closure that an expression evaluates to for a given semantics

Simple Types

give a typing derivation in the simply typed λ-calculus
give a typing derivation in a potentially unfamiliar alternative typing system
determine the smallest context necessary to give a type to an expression in a given typing system

Progress and Preservation

state the formal definition of progress
state the formal definition of preservation
determine if (simple) typing/semantic systems satisfy progress/preservation
give example of expressions that do not satisfy progress/preservation for given typing/semantic systems

Pattern Matching

state the typing/semantic rules for pattern matching
extend the inference rules for pattern matching given a new construct
determine if a pattern match is exhaustive
give type/semantic derivations of match-expressions

Hindley-Milner Type Inference

give a derivation in a constraint-based type inference system
determine a most general unifier for a type unification problem
determine the principal type of an expression using constraint-based inference and type unification
explain why our system HM light does not have let-polymorphism

You will not be asked to …

recall inference rules (they will be provided on the exam)
prove meta-theoretic properties about inference systems
answer questions about exhaustiveness checking
answer questions about specialization
implement an entire interpreter

Good luck and happy studying