CMPUT325 2004 Midterm Study Guide

# 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
• Car recursion
• Cdr recursion
• Car/Cdr recursion
• 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