Your name: 	

	1



	1


CS 3 (Clancy)	Final exam
May 21, 1992

THIS COPY HAS ANSWERS DISPLAYED.
Read and fill in this page now.
Do NOT turn the page until you are told to do so.
Your name:		
	(please printÑlast name, first name)
Name of the person sitting to your left:		
Name of the person sitting to your right:		
	Total:  	/60
Problem 0					Problem 5				
Problem 1									
Problem 2					Problem 6				
Problem 3									
Problem 4					Problem 7						
This is an open-book test. You have approximately three hours to 
complete it; time estimates accompanying each problem suggest a pace to 
finish in three hours. You may consult any books, notes, or other 
inanimate objects available to you. To avoid confusion, read the problems 
carefully. If you find it hard to understand a problem, ask us to explain it. 
If you have a question during the test, please come to the front or the side of 
the room to ask it.
This exam comprises 30% of the points on which your final grade 
will be based. Partial credit will be given for wrong answers. 
You are not to use setf within functions. Any other Lisp construct 
described in Touretzky chapters 1-8, any of the case studies, or any of the 
CSÊ3 handouts is ok, though. In particular, either recursion or applicative 
operators is allowed in a solution unless otherwise specified.
Anywhere you are directed to write a function, your solution may 
include auxiliary functions. You need not rewrite a function that appears 
in Touretzky, in any of the case studies, or in any of the CS 3 handouts; 
merely cite the page in Touretzky, the case study and page number or 
appendix, or the handout in which the function appears.
Your exam should contain 8 problems (numbered 0 through 7) on 18 
pages. Please write your answers in the spaces provided in the test; in par-
ticular, we will not grade anything on the back of an exam page unless we 
are clearly told on the front of the page to look there. 
RelaxÑthis exam is not worth having heart failure about.

Problem 0 (3 points)
You earn the points for this problem if you have done the following:
¥	you have put your name on each page of this exam, and provided the 
information requested on the first page;
¥	you have completed and handed in the ÒCS 3 Final SurveyÓ (handed 
out in lecture; copies of the latter are available from Mike Clancy or 
the t.a.s) and the ÒSurvey AddendumÓ (which should accompany this 
exam);
¥	you have completed an interview.
Check with Mike Clancy or the t.a.s to make sure your survey submission 
and your interview have been recorded.

Problem 1 (3 points, 5 minutes)
Part a
Supply the body of the mystery function below, so that the value it 
returns is as follows:
If n = 0, then return k;
otherwise, return a one-element list containing (mystery k (Ð n 1)).
(defun mystery (k n)	; n is a nonnegative number.
(if (= n 0) k (list (mystery k (- n 1)))))
1 pt (all or none)
)
Part b
Describe briefly but completely what mystery returns, given an atom 
k and a nonnegative integer n as inputs.
k, enclosed in n sets of parentheses
2 pts: -1 for vagueness
Problem 2 (2 points, 10 minutes)
Define a function f, so that the expression 
(funcallÊ(funcallÊ#'f)Ê1) returns the value 3 when evaluated.

(defun f ()
	#'(lambda (n) 3) )

(defun f ()
	#'(lambda (n) (+ n 2)) )

f must return a function for any partial credit

Problem 3 (6 points, 2 parts, 10 minutes)
Part a
The Evaluation Modeler substitutes equivalent expressions for calls 
to applicative operators. For each entry in the table below, you are either to 
supply the name of an applicative operator in the expression
(evaluate (	 #'evenp '(1 2 3)))
that would cause the Evaluation Modeler to display the given expression, or 
to explain why no applicative operator would produce the given expression 
during evaluation. 

grading is 1 point each, no partial credit, except 
only -1 if they say find-if-not and remove-if

Expression allegedly displayed by the
Evaluation Modeler	Name of applicative
operator that, when typed
in the blank space in the
call to evaluate given
above, would cause the
Evaluation Modeler to
display the expression	(or) Reason that no
applicative operator
could produce the
expression during
evaluation
(LIST 
(EVENP 1)
(EVENP 2)
(EVENP 3))	mapcar	
(COND
((EVENP 1) 1)
((EVENP 2) 2)
((EVENP 3) 3))	find-if	
(APPEND
(IF (EVENP 1) (LIST 1) NIL)
(IF (EVENP 2) (LIST 2) NIL)
(IF (EVENP 3) (LIST 3) NIL))	remove-if-not	
(LIST
(IF (EVENP 1) NIL (LIST 1))
(IF (EVENP 2) NIL (LIST 2))
(IF (EVENP 3) NIL (LIST 3)))	not possible; mapcar is the only
applicative operator that always
gives back a list as long as it's
given, and mapcar doesn't work
like this
	

Part b
The expression 
(evaluate (reduce #'evenp '(1 2 3)))
eventually produces an error, because the function input to reduce must 
take two inputs and evenp only takes one. Before detecting the error, 
however, the Evaluation Modeler substitutes an equivalent expression for 
(reduceÊ#'evenpÊ'(1Ê2Ê3)). What is it?

(EVENP (EVENP 1 2) 3)
2 pts: -1 if wrong order of eval but otherwise correct

Problem 4 (5 points, 20 minutes)
Recall the pattern matching code from lab assignment 12. (It appears 
on the last page of this exam.) 
How many calls to match-with-*-list are made as a result of 
evaluating the expression (matchÊ'(*ÊCÊ1)Ê'(AÊCÊA))? For full credit, 
make it clear how you got your answer.

1 Calling (MATCH-WITH-*-LIST (* C 1) (A C A) NIL) 
2  Calling (MATCH-WITH-*-LIST (C 1) (A C A) (NIL)) 
2  MATCH-WITH-*-LIST returned NIL
1  Calling (EXTEND-MATCH (* C 1) (C A) ((A))) 
3   Calling (MATCH-WITH-*-LIST (C 1) (C A) ((A))) 
4    Calling (MATCH-WITH-*-LIST (1) (A) ((A))) 
5     Calling (MATCH-WITH-*-LIST (A) (A) ((A))) 
6      Calling (MATCH-WITH-*-LIST NIL NIL ((A))) 
6      MATCH-WITH-*-LIST returned T
5     MATCH-WITH-*-LIST returned T
4    MATCH-WITH-*-LIST returned T
3   MATCH-WITH-*-LIST returned T
1  EXTEND-MATCH returned T
2 MATCH-WITH-*-LIST returned T

5 pts
One way to grade this is to allot 1 point per call, 
with the two calls to handle symbols being handled 
together. Another is to allot 2 pts for dealing with 
the attempt to match the * with nil, 2 pts for dealing 
with the call to extend-match, and 1 pt for the rest.


The next two problems involve the use of words, defined as nonempty 
lists of atoms with one-letter names. The list (AÊBÊC) is a word; the list 
(AÊBÊCÊ(AÊB)) is not.
Problem 5 (16 points, 4 parts, 45 minutes)
Part a
Supply the body of the function precedes? below. Given two atoms a 
and b and a list L of distinct atoms, precedes? should return a true value 
when a and b are both in L and a precedes b in L; otherwise, precedes? 
should return nil. Thus
expression	value returned
(precedes? 'hello 'goodbye '(x y z))	nil
(precedes? 'x 'a '(x y z))	nil
(precedes? 'a 'x '(x y z))	nil
(precedes? 'x 'z '(x y z))	some true value
(precedes? 'y 'y '(x y z))	nil
(precedes? 'z 'x '(x y z))	nil
If your function calls auxiliary functions, supply their definitions also.
(defun precedes? (a b L)

(member b (rest (member a L))

2 pts, -1 per bug
)

Part b
Write a function alphabetical-order? that, given two words, 
returns true when the words are in alphabetical order. The two words need 
not have the same length; both, however, will be nonempty. Two identical 
words are in alphabetical order. If the second word results from adding 
letters to the end of the first, the two words are in alphabetical order. Some 
examples:
expression	value returned
(alphabetical-order? '(b e d) '(b e t))	some true value
(alphabetical-order? '(b e) '(b e t))	some true value
(alphabetical-order? '(b a t s) '(b e t))	some true value
(alphabetical-order? '(b e t) '(b e))	nil
(alphabetical-order? '(b e t) '(b e e))	nil
(alphabetical-order? '(b i t) '(b e t))	nil
(alphabetical-order? '(b i t s) '(b e t))	nil
In writing alphabetical-order?, you may use the function 
precedes? described in part a. Assume that precedes? works as intended 
regardless of what you wrote for part a. If your function calls auxiliary 
functions, supply their definitions also.
(defun alphabetical-order? (word1 word2)

(cond
	((null word1) T)
	((null word2) nil)
	((eq (first word1) (first word2))
		(alphabetical-order? (rest word1) (rest word2)))
	((precedes? (first word1) (first word2)
		'(a b c d e f g h i j k l m
		  n o p q r s t u v w x y z))) T)
	(T nil) ) )

5 pts, -1 per trivial bug, -2 for nontrivial bug (e.g. 
forgetting a cond clause)
)

Part c
Given below is the code from the Statistics case study to sort a list of 
numbers. Making as few modifications as possible, and using the 
alphabetical-order? function, fix the code so that it sorts a list of words 
into alphabetical order. Clearly indicate what code changes and what code 
is unchanged.

4 pts total
(defun sort (L)
	(reduce #'insert (cons (list (first L)) (rest L))))

no change
-1 if they try to change it
(defun smaller+equal-vals (L x)
	(remove-if-not #'(lambda (y) (<= y x)) L))

replace the function by 
#'(lambda (w) (alphabetical-order? w x))
2 pts
(defun larger-vals (L x)
	(remove-if-not #'(lambda (y) (> y x)) L))

replace the function by 
#'(lambda (w) (not (alphabetical-order? w x)))
2 pts
(defun insert (L x)
	(append (smaller+equal-vals L x) (list x) (larger-vals L x)))

no change
-1 if they try to change it

Part d
A word structure is a list, each of whose elements is either a word or 
a word structure. Thus
(c a t)	is not a word structure, since its elements are
neither words nor word structures;
((c a t)
 ((f i s h))
 (d o g))	is a word structure, whose first and third elements
are words and whose second element is a word
structure;
((c a t (d o g)))	is not a word structure, since its single element is
neither a word nor a word structure.
Consider a function word-in? that searches for a word in a word 
structure. Word-in? should return true if its first input, a word, is one of 
the words in its second input, a word structure, and will return false 
otherwise. Examples:
expression	returned value
(word-in?
  '(f i s h)
  '((c a t) ((f i s h)) (d o g)) )	some true value
(word-in?
  '(i s)
  '((c a t) ((f i s h)) (d o g)) )	nil 
(word-in?
  '(c a t e r)
  '((c a t) ((f i s h)) (d o g)) )	nil 
Complete the definition of the function word-in? below. If your code uses 
auxiliary functions, supply their definitions also.
(defun word-in? (word word-str)
	((null word-str) nil)
	((word? (first word-str))
		(or (equal word (first word-str))
			(word-in? word (rest word-str)) ) )
	(T (or (word-in? word (first word-str))
			(word-in? word (rest word-str)))) ) )

5 pts, essentially 1 per line

(defun word? (L) (atom (car L)))

Problem 6 (13 points, 4 parts, 60 minutes)
The fall 1991 CS 3 final exam asked for a function 1extra? that, given 
two words as inputs, should return true exactly when the first word is the 
result of inserting a single letter into the second word. Examples:
expression	value returned
(1extra? '(H E A T) '(H A T))	some true value
(1extra? '(T H A T) '(H A T)) 	some true value
(1extra? '(H A T E) '(H A T))	some true value
(1extra? '(A B B C) '(A B C))	some true value
(1extra? '(A T) '(H A T))	nil 
(1extra? '(H A T) '(H A T))	nil 
(1extra? '(H A T E D) '(H A T))	nil 
(1extra? '(C H E A T) '(H A T))	nil 
One solution to this problem appears below. It does not work as 
specified.
(defun 1extra? (word1 word2)
	(cond
		((null word1) T)
		((not (= (length word1) (+ 1 (length word2)))) nil)
		((eq (first word1) (first word2))
			(1extra? (rest word1) (rest word2)))
		(T (1extra? (rest word1) word2)) ) )
Part a
Provide a call to 1extra? for which the given function does not 
perform as specified, that is, it returns true when nil is the correct answer, 
or it returns nil when true is the correct answer. 

1 pt

Part b
Describe briefly in English the complete set of words for which the 
result of evaluating the expression (1extra?ÊwordÊ'(HÊAÊT)) is true, but 
word is not the result of inserting a single character into the word 
(HÊAÊT). Note: it is possible that there are no words for which 1extra? 
returns true incorrectly.

There are no words for which (1extra? word '(H A T)) 
incorrectly returns true, since word must be nonempty. 
Consider the call at which (length word) is 1; (H A T) 
must therefore have been reduced to nil, so word 
originally must have started with (H A T), and 1extra? 
should return true.

They only need the answer, not the reasoning. They 
might get partial credit for explaining their 
reasoning with a wrong answer, though.
2 pts
Part c
Describe briefly in English the complete set of words for which the 
result of evaluating the expression (1extra?ÊwordÊ'(HÊAÊT)) is nil, but 
word is the result of inserting a single character into the word (HÊAÊT). 
Note: it is possible that there are no words for which 1extra? returns nil 
incorrectly.

Any word in which the insertion of the letter into 
(HÊAÊT) occurs before the end will cause 1extra? to 
return nil incorrectly.

2 pts; partial credit for partly-correct reasoning 
with a wrong answer.

Part d
Another way to write 1extra? would be to use the pattern matcher 
from lab assignment 12 as follows. First, check that word1, the first input 
to 1extra?, is one character longer than word2, the second input. Then, 
match word1 against the results of inserting a single * into all possible 
positions in word2, returning true if any of the matches succeed and false 
otherwise.
For example, to evaluate (1extra?Ê'(HÊAÊTÊE)Ê'(HÊAÊT)), this 
procedure would result in the following calls to match:
(match '(* H A T) '(H A T E))
(match '(H * A T) '(H A T E))
(match '(H A * T) '(H A T E))
(match '(H A T *) '(H A T E))
Given below is the 1extra? function. Provide the match-result 
function that it calls, along with any necessary auxiliary functions, that 
implements the process just described. You may use the next page for more 
space.
(defun 1extra? (word1 word2)
	(and
		(= (length word1) (+ 1 (length word2)))
		(match-result word1 word2) ) )
(defun match-result (word1 word2)
; Return true when the result of inserting a single * somewhere
; in word2 produces a pattern that word1 matches.

Recursive version:

(helper1 word1 word2 0) )

(defun helper1 (word1 word2 k)
	(cond
		((> k (length word2)) nil)
		((match (insert-* word2 k) word1))
		((helper1 word1 word2 (+ k 1))) ) )

(defun insert-* (word k)
; insert a * at position k of word, where positions
; are as follows: (0 w1 1 w2 2 ... wn n)
	(if (= k 0)
		(cons '* word)
		(cons (first word)
			(insert-* (rest word) (- k 1)) ) ) )

Applicative operator version:

(find-if
	#'(lambda (pattern) (match pattern word1))
	(mapcar
		#'(lambda (k) (insert-* word2 k))
		(0to (length word2)) ) )

(defun 0to (n)
; return the list (0 1 ... n)
	(helper2 0 n) )

(defun helper2 (k n)
	(if (> k n) nil (cons k (helper2 (+ k 1) n))) )

More space for your answer to part d of problem 6

Problem 7 (12 points, 3 parts, 30 minutes)
Consider a rule-based programming environment in which each 
rule contains a numeric application priority. The idea here is that rules 
with high priority are to be applied in preference to rules with low priority.
Part a
Write a function highest-priority that, given a list of rules, returns 
the highest priority of any of the rules. Assume that there is a function 
priority that, given a rule, returns the priority of that rule. There may be 
more than one rule with the same priority. 
(defun highest-priority (rule-list)
; rule-list is a nonempty list of rules.

(reduce #'max (mapcar #'priority rule-list)) )

2 pts, 1 for each applicative operator application
)

Part b
Write the choose function. Choose, given a list of rules, should 
return the rule with highest priority. If there are more than one rule in the 
list with that priority, choose should choose randomly among them.
In writing choose, you may use the function highest-priority 
described in part a. Assume that highest-priority works as intended 
regardless of what you wrote for part a.
For this part, you may use applicative operators, but not recursion. 
That is, neither your choose function nor any of the auxiliary functions you 
write may contain a recursive call.
(defun choose (rule-list)
; rule-list is a nonempty list of rules.
(let ((high-prio-rules 
			(remove-if-not 
				#'(lambda (r) 
					(= (priority r) 
						(highest-priority rule-list)) 
				rule-list) ))
	(nth
		(random (length high-prio-rules)) 
		high-prio-rules) ) )

5 pts: -1 for trivial bugs, -2 for nontrivial bugs
)

Part c
Rewrite the choose function from part b, using recursion but not 
applicative operators. 
As in part b, choose, given a list of rules, should return the rule with 
highest priority. If there are more than one rule in the list with that 
priority, choose should choose randomly among them. You may use the 
function highest-priority described in part a. Assume that highest-
priority works as intended regardless of what you wrote for part a.
(defun choose (rule-list)
; rule-list is a nonempty list of rules.

5 pts: -1 for trivial bugs, -2 for nontrivial bugs
)

Pattern matching code from lab assignment 12

(defun match (pattern object)
  (match-with-*-list pattern object nil) )

(defun match-with-*-list (pattern object *-list)
  (cond
   ((null pattern) (null object))
   ((prev-ref? (first pattern))
    (match-with-*-list
     (append (matched-value (first pattern) *-list) (rest pattern))
     object *-list ) )
   ((null object)
    (and (arb-sequence? (first pattern))
         (match-with-*-list (rest pattern) object 
                            (add-*-entry *-list nil) ) ) )
   ((arb-sequence? (first pattern))
    (or
     (match-with-*-list (rest pattern) object (add-*-entry *-list nil))
     (extend-match pattern (rest object)
       (add-*-entry *-list (first object)) ) ) )
   ((symbol? (first pattern))
    (and (equal (first pattern) (first object))
         (match-with-*-list (rest pattern) (rest object) *-list) ) )
   ( T 'INVALID-PATTERN ) ) )

(defun extend-match (pattern object *-list)
  (cond
   ((match-with-*-list (rest pattern) object *-list))
   ((null object) nil)
   ( T (extend-match pattern (rest object)
                     (extend-*-entry *-list (first object)) )) ) )

(defun arb-sequence? (pattern-elem)
  (equal pattern-elem '*) )

(defun symbol? (pattern-elem)
  (and (atom pattern-elem)
       (not (arb-sequence? pattern-elem))
       (not (prev-ref? pattern-elem)) ) )

(defun prev-ref? (pattern-elem)
  (numberp pattern-elem) )