[We don't post the answer key, so don't bother to ask us for one]

CS 2360
Midterm 1    Spring 1998

[Note: don't make any assumptions about the length of your exam based on
the length of this sample exam.]

Please write your name on the upper right hand corner of this page.
There are 80 points possible on this exam.  You have 80 minutes to
complete it and turn it in.  Put only what you want to be graded on the
front sides of the pages, and use the back sides of the pages as scratch
paper.  If you run out of room on the front side of the page, you can
put part of your answer on the back of that same page, but make sure you
note on the front of the page that there's stuff to be graded on the
back.  And please strive for legibility, because I don't give credit for
stuff I can't read.  Write nicely and carefully, and use appropriate
indentation.  For this exam, use only recursive programming techniques
for your control structures as indicated in the individual problems.
Don't use applicative programming, and don't use traditional iterative
methods (no loop, do, dolist, dotimes, etc....you'll see them in a few
weeks).  Before you start, check out the cheat sheets on the last page
of this exam.  Every LISP function you'll need (and then some) is there,
but if you think you need something that's not there, feel free to
create it from what is on the cheat sheet.  Make sure that these
additional functions adhere to any constraints given in the problem.
You may remove the cheat sheets from the rest of the exam.  Do not
comment your code on this exam.

Important note:  As the end of the time period approaches, I will count
down the number of minutes that remain in the time period.  All exams
must be in my possession by the end of the 80-minute period.  I will not
accept an exam for grading after I have called time, so pay close
attention to the time warnings.  In other words, if I don't have your
exam when the 80-minute period has ended, you'll get a score of 0 on
this exam.

Do not turn this page until you have been told to do so.

 1.  (10 points)  In general, when you cons the first of a list
structure with the rest of that same list structure, you get something
that looks just like the original list structure.  For example:

Welcome to Macintosh Common Lisp Version 4.1!
? (setq test '(a b c d))
(A B C D)
? test
(A B C D)
? (first test)
A
? (rest test)
(B C D)
? (cons (first test) (rest test))
(A B C D)
? (equal test (cons (first test) (rest test)))
T
? 

What happens when you cons the first of nil with the rest of nil?  That
is, when you type the following at the LISP evaluator:

? (cons (first nil) (rest nil))

what does LISP return?

 2.  (10 points)  The LISP function pairlis sort of works as follows:
it takes two lists of equal length and makes an "association list" that
associates elements of the first list to corresponding elements of the
second list.  Here are some examples:

? (pairlis '(a b c) '(1 2 3))
((A . 1) (B . 2) (C . 3))
? (pairlis '(a (b) c) '(1 2 3))
((A . 1) ((B) . 2) (C . 3))
? (pairlis '(a b c) '(1 2 (3)))
((A . 1) (B . 2) (C 3))

In the space below, use augmenting recursion to construct your own
version of pairlis in Common LISP.  Call your function my-pairlis,
don't worry about lists of unequal length, and no, you can't use LISP's
predefined pairlis function.

 3.  (10 points)  Now show us the tail-recursive version of my-pairlis.
In Common LISP, of course.  Call it my-pairlis-tr.  (You may assume that
any function given on the cheat sheets is available in a tail-recursive
version when that function might use recursion.)

 4.  (10 points)  What value (T or nil or some sort of error) will LISP
return when it evaluates each of these expressions?

a)  (eq '(a b c) '(a b c))



b)  (eql (third (make-list 10)) ())



c)  (eq 999888777666555444333222111000
        999888777666555444333222111000)



d)  (equal '((a . 0) (b   . 1) (c   .   2))
           '((         a .   0) (b .       1  ) (c . 2)))



e)  (= 1/2 0.5)



f)  (eql 999888777666555444333222111000
         999888777666555444333222111000)



g)  (eql () nil)



h)  (eql '() nil)



i)  (eql 3 3.0)



j)  (eql 3 12/4)



 5.  (10 points)  Show the following lists in box (or box-and-pointer or
boxcar) notation:

((a (b (c))) d)



(a (((b) c) d))



6.  (0 points)  So that we can post your scores on the newsgroup, we'd
like you to provide us with a super secret identification code (of no
more than eight characters) that will allow you to find your scores
without anyone else knowing which scores are yours.  If you want us to
post your scores on the newsgroup, please print your code in the space
below.  If you don't want us to post your scores, just leave the space
blank.


___________________________

 7.  (10 points)  Here are some questions that don't require you to
write LISP code (short but understandable answers would be greatly
appreciated):

a) What principles of the functional programming paradigm distinguish
that paradigm from other programming paradigms?


b) What advantages does the functional programming paradigm offer over
other programming paradigms?  (Note: "principles" and "advantages" do
not mean the same thing; the answer to 7a is not the same as the answer
to 7b.)



 8.  (10 points):  Let's say that the Common LISP predicates equal and
equalp don't exist.  Using multiple recursion and eql as your only
equality predicate, construct a new predicate called list-equal which
takes two (possibly nested, tree-like) lists as arguments and returns T
when both lists have the same structure and the atomic elements are eql
(i.e., the trees look alike), and nil otherwise.  Here are some
examples:

? (list-equal '(a b c) '(a b c))
T
? (list-equal '(a b) '(a))
NIL
? (list-equal '(a b) '(a b c))
NIL
? (list-equal '(a (b) c) '(a (b) c))
T
? (list-equal '(a (b) c) '(a (b) d))
NIL
? (list-equal '(((a) b) c) '(((a) b) c))
T
? (list-equal '(((a) b c)) '(((a) b) c))
NIL
? (list-equal '(a (b (c d)) (e (f g))) '(a (b (c d)) (e (f g))))
T
? (list-equal '(a (b (c)) (e (f g))) '(a (b (c d)) (e (f g))))
NIL

Write your solution in the space below.

 9.  (10 points)  The code below is pathetic.  The author has made no
attempt (other than some nice indentation) to make it readable by
another programmer.  There are no meaningful argument or function names,
the abstraction is unclear, there's no documentation, and related
functions aren't even grouped together.  In fact, it looks just like
what some of you turn in as homework!  As part of our ongoing efforts to
help you understand why it's so important to write code that other
people can easily read, take a good look at the following functions and
try to appreciate what your graders have to deal with on a weekly basis:

(defun list-1 (list1 list2 list3 list4)
  (list-2 (list-3 list1 list2) (list-4 list3 list4)))

(defun list-2 (list1 list2)
  (cond ((null list2) nil)
        (t (append (list (first list1))
                   (append (list (first list2))
                           (list-2 (rest list1) (rest list2)))))))

(defun list-3 (list1 list2)
  (cond ((null list1) list2)
        (t (append (list (first list1))
                   (list-5 (rest list1) list2)))))

(defun list-4 (list1 list2)
  (list-6 list1 list2 nil))

(defun list-5 (list1 list2)
  (cond ((null list2) nil)
        (t (append (list (first list2))
                   (list-3 list1 (rest list2))))))

(defun list-6 (list1 list2 list3)
  (cond ((and (null list1) (null list2)) list3)
        (t (list-6 (rest list1) (rest list2) 
                      (append list3 (append (list (first list1))
	                                            (list (first list2))))))))

Now tell us what will be returned when the following call to list-1 is
evaluated:

? (list-1 '(w l o b) '(_ _ e a) '(e l v r) '(a l _ k))



 The cheat sheet

(first  '(a b c d e)) => a
(second '(a b c d e)) => b
(third  '(a b c d e)) => c
(rest   '(a b c d e)) => (b c d e)

(cons 'a   '(b c d e)) => (a   b c d e)
(cons '(a) '(b c d e)) => ((a) b c d e)
(append '(a b) '(c d)) => (a b c d)
(append '(a b) nil) => (a b)
(append nil '(a b)) => (a b)
(list 'a 'b 'c) => (a b c)
(list 'a) => (a)
(list '(a b) '(c d)) => ((a b) (c d))

(remove 'a '(a nil b nil a)) => (nil b nil)
(remove nil '(a nil b nil a)) => (a b a)

(length '(a b c d e)) => 5
(length nil) => 0

(* 4 2) => 8
(+ 4 2) => 6
(/ 4 2) => 2
(- 4 2) => 2
(sqrt 25) => 5

(null '()) => T
(null '(a b c)) => nil
(atom 'a) => T
(atom '(a b c)) => nil
(listp 'a) => nil
(listp '(a b c)) => T
(numberp 3) => T
(numberp 'a) => nil

(and T nil) => nil
(or T nil) => T
(not T) => nil

(eql 'a 'a) => T
(eql '(a b) '(a b)) => nil
(equal 'a 'a) => T
(equal '(a b) '(a b)) => T

(= 3 3.0) => T
(= 3 5) => nil
(< 3 5) => T
(> 3 5) => nil

(cond (   )
        :
      (   ))

(if 
    
     )

(defun   )

(assoc 'b '((a x) (b y) (c z))) => (b y)