A 1


CS 3 (Clancy)	Exam 2
November 4, 1991
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)
Your lab section day and time:		
Your lab t.a.:		
Name of the person sitting to your left:		
Name of the person sitting to your right:		
Problem 0			Total:  	/30
Problem 1		
Problem 2		
Problem 3				
Problem 4				
Problem 5				
This is an open-book test. You have approximately fifty minutes to 
complete it. 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 15% 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, either part of the ÒDifference Between 
DatesÓ case study, the ÒStatisticsÓ case study, the supplementary reading on 
applicative operators, or ÒInteger Division and its UsesÓ is ok, though. 
Your exam should contain 6 problems (numbered 0 through 5) on 6 
pages. Please write your answers in the spaces provided in the test; in 
particular, 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 (2 points)
Put your name on each page. Also make sure you have provided the 
information requested on the first page.
Problem 1 (6 points)
Fill in the blanks in the function definitions below so that each of the 
functions f1 and f2 returns the value 5 when given the list 
((january 2) (february 5) (march 4) (april 1) (may 3))
as input. Each blank should be filled with the name of an applicative 
operator. There are two answers for function f2; indicate both.
(defun 1-each (x sum) (+ 1 x) )
(defun f1 (L)
	(	 #'1-each (cons 0 L)) )
reduce
(defun f2 (L)
	(length (	 #'atom L)) )
mapcar
(defun f2 (L)
	(length (	 #'atom L)) )
remove-if

Problem 2 (3 points)
Indicate the result of evaluating each of the uses of applicative 
operators below. If an error results, explain the error. 
(defun 1-each (x sum) (+ 1 x))
(defun add1 (x) (+ 1 x))
(defun 1-element? (L) (= (length L) 1))
(defun sum-to-5? (x y) (= (+ x y) 5))
(reduce #'1-each '(2 4 6))
4
(reduce #'add1 '(1 4 6))
wrong number of inputs to add1
(remove-if-not #'sum-to-5? '((1 2) (2 3) (3 4)))
wrong number of inputs to sum-to-5?

Problem 3 (4 points)
Given below is the code for the min and list-min functions from 
Appendix A of the ÒStatisticsÓ case study.
; Return the smaller of two numeric values.
(defun min (x y)
	(if (< x y) x y) )
; Return the smallest value in the list L.
(defun list-min (L)
	(reduce #'min L) )
Suppose, when typing in the code for the min function, you 
mistakenly typed an x for a y in the if condition in min, so that min was 
defined as 
(defun min (x y)	; incorrect version
	(if (< x x) x y) )
Part a
Give an example of a list of at least three elements, for which list-
min using the incorrect version of min produces the same output as list-
min using the correct version of min.
Part b
Describe, as completely as possible, the collection of lists for which 
list-min using the incorrect version of min produces the same output as 
list-min using the correct version of min. Your answer is a description of 
test cases that would fail to reveal the bug in the mistyped min function.
those for which the min is the last thing in the 
list

Problem 4 (7 points)
The difference in days between two dates in 1991 can be computed 
recursively, with the aid of two functions date-before and date-after. 
Date-before takes a date as input, and returns the date immediately 
before; similarly, date-after returns the date immediately after its input. 
Some examples:
expression	value returned
(date-before '(january 5))	(january 4)
(date-before '(december 1))	(november 30)
(date-after '(january 31))	(february 1)
Part a
Complete the definition of the recursive version of days-between 
below, by filling in the base case(s).
; Return the difference in days between date1 and date2. 
; The two dates themselves are included in the difference.
; date1 and date2 both represent dates in 1990, 
; with date1 being the earlier of the two.
(defun days-between (date1 date2)
	(cond
((equal date1 date2) 1)
((equal date1 (date-before date2)) 2)
		(T (+ 2 (days-between (date-after date1)
			    (date-before date2) ))) ) )
Part b
Using only the date-before and equal functions (with if or cond), 
write another recursive version of days-between.
; Return the difference in days between date1 and date2. 
; The two dates themselves are included in the difference.
; date1 and date2 both represent dates in 1990, 
; with date1 being the earlier of the two.
(defun days-between (date1 date2)
(if (equal date1 date2) 1
	(+ 1 (days-between date1 (date-before date2))) )
)

Problem 5 (8 points)
Suppose that a table season-table, which associates the date on 
which each season begins with the name of that season, has been set up as 
follows.
(setf season-table
	'(((january 1) winter) ((march 31) spring)
	  ((june 21) summer) ((september 21) autumn)
	  ((december 21) winter) ) )
Suppose also that a function same-or-earlier? has been written that takes 
two 1991 dates as inputs, and returns true when the first date is the same 
as or comes before the second and false when the first date comes after the 
second. Some examples:
expression	value returned
(same-or-earlier? '(may 5) '(may 5))	true
(same-or-earlier? '(may 5) '(june 21))	true
(same-or-earlier? '(may 5) '(january 30))	false
Part a
Use same-or-earlier?, season-table, reverse, and find-if to 
write a function season that takes a date as input and returns the name of 
the season that contains the date. Some examples:
expression	value to return
(season '(january 5))	winter
(season '(june 20))	spring
(season '(june 21))	summer
(season '(december 25))	winter
Write your function in the space below. If you need an auxiliary 
function, you may use either defun or lambda to provide it.
(defun season (date)
	(second (find-if
		#'(lambda (x)
			(same-or-earlier? (first x) date))
		(reverse season-table) ))
)
Part b
Why could you not use assoc with reverse and season-table to 
write the season function?
assoc uses a test for equality, and only works with 
atomic keys