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.
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 procedural meaning of the following Prolog program.
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.