StudyGuide for Cmput325 [Midterm]

CMPUT325 2004 Midterm Study Guide

Here is an overview of the material that could appear on the midterm exam. N.B., this list is just meant to be SUGGESTIVE! You should know about EVERYTHING covered, up to and including the 26/Oct/04 lecture. (Of course, focussing on the material here would be a good starting point :-) )

Functions (domain, range, composition)
LISP Constructs:

car, cdr, (first, rest,..), cons
cond, and, or, quote, function, ...
null, list,
t, nil, (numbers), ...
eq, equal, =, atom, consp, listp, ...
eval, apply, funcall, ...
lambda, let, labels, defun, ...
setf, setq, ...

Programming Techniques in Functional Languages
- Be able to WRITE a RECURSIVE function (set of functions)
- Be able to TRACE a RECURSIVE function (set of functions)
- Be able to INTERPRET a (given) RECURSIVE function (set of functions)
- Know types of list recursions and how to write them
- Understand and be able to apply accumulator variables in a recursion
- Know how to identify tail-recursion and its significance
- Efficiency O( f(n) )
  - be sure to specify how "n" is measured (e.g., length of input list, or number of cons-cells, ...)
  - know what operations to count for f(n)
    [Recall it may involve more than one quantity.]
- Issues in scoping and variable values
  - Variables -- free vs bound
  - Dynamic vs Static Scoping ... Funarg problem (and solution)
  - Side-effects
- Lazy evaluation: delay and force
- Contexts and Closures
Lambda Calculus

Goal: reduce to Normal Form
Syntax: applications, definitions, constants, bracket dropping conventions
Alpha, Beta and Eta substitution rules (rewriting)
Reduction, Normal Form, Normal order vs Applicative Order
... call by value vs call by name
Church-Rosser Theorems (Uniqueness, Existence) -- Why is normal order important?
Translating Abstract programming idioms to lambda calculus
- Numbers (+, *, ...)
- Lists (car, cdr, cons, ...)
- Conditionals (and, or, if/then/else)
- nested LET statements ("let")
- parallel LET ("let*")
- LETREC statement ("labels")
- Recursive definition and the Haskell Curry Combinator (Y-operator)
- Multiple arguments, currying and partial application
Contexts, Closures
Self Interpretation