Please read the comments below before raising concerns about the grades you
received. 

Q1. This involved two user-defined Lisp functions, F and G, each with a single
parameter named p1 and q1 respectively, with a call to G in the body of F. The
question asked you to consider what will happen when the Lisp interpreter
evaluates the call (F ae) that appears at the top level, specifically what the
a-list will look like when the evaluation of F begins and when the evaluation of
G begins. 

When the evaluation of F begins, the alist will be ((p1 . av))
When the evaluation of G begins, the alist will be ((q1 . av) (p1 . av))

The key point is this: suppose in the body of F, the call to G looks like 
(G (plus p1 1))

Then the a-list when G is called would look like 
((q1 . av') (p1 . av))
where av' is av + 1.

Suppose now there is a bug in the definition of G and that some point, when
defining G, the user had typed p1 in place of q1. Then when evaluating the body
of G, the interpreter will use the value av rather than the value av + 1 that
the user intended. This is the result of the dynamic scoping in Lisp.

Q2. The question was about the inefficiency of *some* [*not* all] recursive
functions defined in a natural way in Lisp. A good example is maxList[] that we
saw in class. The first definition works but, for many lists, it will compute
the maximum of the same list multiple times. This results in exponential
inefficiencies for those lists. We addressed this by introducing the greater[]
function that has an extra parameter that we can use to avoid recomputing the
same value.

Q3. Many students said, possibly given the hint in the problem (:-), that ITE
cannot be defined. But the reasoning for why not and how to introduce it as a
primitive in Lisp was incorrect.

To see the problem, assume that ITE has been defined as a function (in design
notation) as follows: 
ITE[b, e1, e2] =
   [ b --> e1;
   | T --> e2]
   
Consider the following call to the above ITE:

(ITE NIL (CAR NIL) 42)

This call should, if ITE worked as intended, return 42. But, instead, it will
raise an exception because when the interpreter evaluates the call to the ITE
function, it will first evaluate all the arguments, then bind them to the
parameters of ITE. But when it evaluates e1, it will raise an exception. *This*
is why the user cannot define ITE using DEFUN.

So we have to add it as a primitive to Lisp. We have to do it in such a way that
when evaluating, e.g., the above:
(ITE NIL (CAR NIL) 42)
the interpreter doesn't try to evaluate b, e1, and e2 prematurely. Instead, it
should first evaluate b and if that turns out to be NIL, forget the evaluation
of e1, instead evaluate e2 and return that value. If b evaluates to T, forget
the evaluation of e2 and simply evaluate e1 and return that value. 

This change cannot be achieved by modifying apply[] because by the time apply[]
is called, the arguments have already been evaluated. So ITE has to be defined
as a new (special) form similar to COND or QUOTE and eval[] should be modified
to handle it as described in the last para.

4. This was about the two possible interpretations, in the notation for
axiomatic semantics, of 
p ==> q
The first is that the set P is a subset of the set Q.
The second is the assertion (~p \/ q)

Next you were asked which one you should use if (p ==> q) appears as a
pre- or post-condition in a result. You should use the second interpretation
because pre- or post-conditions must be assertions over states, not relations
between sets of states.

5. This made four claims and asked which were valid and which were not. Note
that term "valid" in this context was wrong for the first three reults (since
"valid" means "operationally valid"); I should have used something like
"correct" when talking about those three results. 

Anyway, (a) is correct, (b) and (c) are incorrect, and (d) is valid. 
(d) might be the puzzling one but it is valid because (d) is a partial
correctness result; and if, e.g., IN was empty when the statement begins
execution, the statement will abort so the result is not making any claims about
the final state. If we wrote the corresponding total correctness result [with
the same pre- and post-conditions], that result would indeed be (operationally)
invalid because, given same situation, the fact that the statement would
abort means that the total correctness result is *not* valid.