This is the quiz that I used last spring. I will probably have to dream up a few new questions, and disguise the other ones, but this should give you the idea of what to expect.

Note that the parenthesis based language used in Spring 1997 was Common Lisp, not Scheme.

I expect that there will be a question about prolog control (e.g., the
*cut*) on this quarters quiz.

- Open Book, Open Notes
- Time limit: 50 minutes
- Answer the problems on the exam paper.
- If you need extra space use the back of a page
- Problems are not of equal difficulty, if you get stuck on a problem, move on.

**Problem 1 (12 points)**
Provide the response that Common Lisp will give to each of the input
expressions. (In the case of an error - you only need to indicate
what the error is - not the exact error message!).

USER(1): (quote (a b c)) USER(2): (reverse '(a b c)) USER(3): (cond ((= 1 2) 3) (4 5) (t 6)) USER(4): (equal '(worm slug) '(worm slug)) USER(5): (eq '(worm slug) '(worm slug)) USER(6): (mapcar #'(lambda (x) x) '(worm slug snail)) USER(7): (car (cdr (cdr '(1 2 3 4 5 6 7 8)))) USER(8): (cdr (car (car '(1 2 3 4 5 6 7 8)))) USER(9): (+ (length '(1 2)) 7 'cow)) USER(10): (defun snork (L) (cond ((null L) L) ((null (cdr L)) L) (t (cons (car (cdr L)) (cons (car L) (snork (cdr (cdr L)))))))) USER(11): (snork '(1 2 3 4 5 6 7 8 9 10)) USER(12): (snork '(1 2 3 4 5 6 7 8 9 )) USER(13): (lambda (x) (+ x 1)) 1) USER(14): (and (= 1 2) (+ 'bob tom)) USER(15): (defun bob (bill jill) (list jill bill)) USER(16): (setq bob 'rob) USER(17): (bob 'bob bob)Lisp hints: The functions

`car`

and `cdr`

are
the same as the
functions `first`

and `rest`

. The functions
`length`

,
`list`

and `reverse`

| are built-in lisp functions.
** Problem 2 (12 points) **

a) Write a lisp function which given a list, returns the list which is the result of removing every other element of the list, starting from the first element.

b) Write a lisp function which tests if a list of integers is in increasing order.

**Problem 3 (12 points)**

Give short answers to the following questions:

What is the most important difference between LISP and ML.

\item What is the distinction between the lisp functions equal, eq, and =.

How are the \verb|bob|'s different in the following lisp expression:
`(bob 'bob bob)`

.

What does it mean to say the Prolog uses the "Most General Unifier" when matching expressions and variables.

What is the declarative meaning of the following Prolog program.

b(red,_). b(X,Y):-b(Y,X).What is the

b(red,_). b(X,Y):-b(Y,X).

**Problem 4 (12 points)**

Consider the following university data base, which has a department relation (dept(x,y) says that x works in department y, note that joint appointments are possible), a chair relation (chair(x, y) says that y is the chair of department x), and a rank relation (rank(x, y, z) says that x has rank y, and earns salary z).

dept(newton, physics). dept(newton, math). dept(erdos, math). dept(vonNeumann, compSci). dept(turing, math). dept(turing, compSci). dept(babbage, compSci). dept(euler, math). dept(church, compSci). dept(einstein, physics). dept(feynman, physics). chair(physics, newton). chair(math, euler). chair(compSci, vonNeumann). rank(newton, full, 35). rank(erdos, assoc, 25). rank(vonNeumann, full, 45). rank(turing, assist, 20). rank(babbage, assist, 23). rank(euler, assoc, 40). rank(church, assoc, 40). rank(einstein, full, 45). rank(feynman, assoc, 35).

a) What are all the possible answers to the query:

?- rank(A, assoc, _), dept(A, math).

b) What query would you ask to get the names and ranks of department chairs.

c) The colleague relation, colleague(x,y) says that x and y are in the same department. Write a rule to define the colleague relation. (x is considered to be a colleague of x).

d) The boss relation, boss(x,y) says that x is the chair of the department that y is in. Write a rule to define the boss relation.

e) A professor is highly paid if he earns *more* than his chair.
Write a rule to define the highlyPaid predicate.

f) Is it possible for a chair to be highly paid, by the above definition. If it is, add the appropriate facts so that there is a highly paid chair.

** Problem 5 (12 points) **

a) Give a Prolog rule for the shift relation, using the append relation.
`shift(L1,L2)`

is true if list `L2`

is a
circular shift of the list
`L1`

, e.g., `shift([1,2,3,4],[3,4,1,2])`

is true.

b) Give a Prolog program which computes the "EveryOther" relation, so that
`L2`

consists of every other element of `L1`

,
starting with the second element
of the list. Thus, `everyOther([1,2,3,4,5],[2,4])`

is true.