Roughly one third will be modeled from Midterm #1. Questions are likely to follow the same format and cover the same materaial as those questions from the first midterm exam, which covers the first 1/3 of the course and quizzes administered during the same period. For details you are referred to those on-line resources. Prolog and Scheme programming comprise the most likely topics for final exam questions.

Roughly one third will be modeled from Midterm #2. Questions are likely to follow those from the second midterm exam and quizzes administered during the same period, which is the second third of the course. For details you are referred to those on-line resources. Prolog backtracking, weakest preconditions, loop invariants, and selected concepts from the second third of the course comprise the most likely topics for final exam questions.

The remaining third will be designed to test your familiarity with material covered since the second midterm and will emphasize testing your experiences with those materials. More details below.

List creation.

Quote; evaluating expressions with and without quotes.

CONS, CAR, CDR, CAAR, CADR, etc.

Scheme expressions involving closures.

Simple programs, such as those covered in lectures or modeled on programs developed in the assignment.

Lexical scoping examples.

Lambda expressions

Prolog Lists. Representation using .(head, tail) syntax and using [head | tail] syntax.

List manipulation predicates, such as append, member, del (also known as takeout).

Prolog Backtracking.

Small programming examples similar to the Prolog assignment.

Phases of Compilation.

Finite State Machines, Regular Expressions. Questions might take the following form(s): Given a machine or regex, choose what language (set of tokens) is accepted by that machine. Or indicate what state or states the machine is in after a specified input is scanned.

Equivalence of a finite state machine and a regular expression.

Context-free grammar. Questions to select the equivalent regular expression/state machine (assuming the CFG defines a regular set). Or, Given a parse tree, select which grammar rules. Or, Given grammar rules, select which parse tree(s).

Semantics. Overview of basic methods from axiomatic semantics.

Weakest Precondition. Predicate transformers. Questions will test your ability to compute WP (the Weakest Precondition) for assignment statements and if statements. You should understand how this relates to assert() and the effect on proving correctness.

Loop Invariants. Questions will relate to developing initialization code, guard expression, and the loop invariant for a simple loop.

Bindings

Scope: lexical, indefinite -- Extent: indefinite, dynamic

Closures

Garbage Collection Methods