The final exam is cumuluative. Hence, you should review the topic list for midterms 1 and 2, and make sure you undersatnd what you may have done wrong on the first two midterms. The additional topics are listed here:

Logic Programming / Prolog
===
What is logic programming?
Name a few ways that logic programming differs from functional and object oriented programming?
What is the difference between a fact and a rule in a Prolog program?
What is the difference between an uppercase and a lowercase identifier?
What is a query? How do you run one?
What is unification, and why is it at the heart of Prolog program execution?
We say that Prolog performs goal execution, aka goal-directed search. Explain this algorithm informally.
What does the term 'fail' do in Prolog?
Claim: Prolog is dynamically typed. How do you know?
Prolog supports a kind of pattern matching like OCaml. What are the Prolog patterns that correspond to the following OCaml patterns?
  h::t
  [1]
  [x]
  [x]::t
  h1::h2::t
  h1::h2::[]
An OCaml function can be transliterated into a sequence of Prolog rules. How would you convert the following OCaml functions to Prolog rules? After doing this exercise, give the strategy you used to convert them
let rec sumalt x =
  match x with
    [] -> 0
  | [x] -> x
  | h::_::t -> h + (sumalt t)
let rec drop x l =
  match l with
    [] -> []
  | h::t -> if x = h then drop x t else h::(drop x t)
let rec mkn x n =
  if n = 0 then []
  else x::(mkn x (n-1))

What is the 'is' operator used for? Why is it needed?
What does it mean to backtrack?
What is a most general unifier? How does it relate to Prolog execution?
What is cut used for? More precisely, what element of Prolog's execution algorithm does it affect, and in what way?
When we say negation is failure, what do we mean?
What is the difference between a red cut and a green cut?
Why does clause order matter when doing negation?

Lambda calculus
===
Who invented lambda calculus?
What is its relation to a Turing machine?
What is the beta reduction rule?
Be prepared to show how a term beta reduces
What is alpha conversion (aka alpha renaming)? Why is it needed? Give an example
Encodings for booleans, pairs, natural numbers (Church numerals), looping

Memory Management / GC
===
What are three attributes of memory in a program?
What are four standard classes of memory?
What are some memory errors that come up in C, which uses manual memory management?
Which errors are prevented by garbage collection (or reference counting)?
What is fragmentation? Show an example.
Give an intuition as to why determining whether an object is live (that is, if it will ever be used by the program in the future) is an undecidable problem.
In what way is reachability an approximation of liveness?
What are the roots of the program's memory?
How does reference counting work? What are its advantages and disadvantages?
What are two kinds of tracing garbage collectors? How do they work?
What are the advantages and disadvantages of each, compared to each other and to reference counting?
What is a conservative garbage collector? Why might you need one for C but not for other languages?
What is a generational garbage collector? Why might it be advantageous?
How might you have a memory leak in Java?

History of Programming Languages
===
Not on the final; just for fun!