Sample Final Exam Questions

Here are examples of the types of questions one might find on the
upcoming final exam.  While this gives you some idea about the 
kinds of knowledge you might need or the complexity of individual 
questions, you shouldn't make assumptions about the length
of the exam based on what you see below.  Also, don't assume that
because some topic doesn't appear below that it won't appear on
your exam this Thursday.  This exam is comprehensive, and everything
we've covered in class or in the notes will be fair game.

And no, we won't be posting sample answers to these sample questions.


1.  (20 points)  Write a function called shuffle which takes two 
lists as input (assume both lists have the same length) and returns 
one list which contains the first element of the first list followed 
by the first element of the second list followed by the second element 
of the first list and so on, like this:

? (shuffle '(A K Q) '(J 10 9))
(A J K 10 Q 9)

Write two different versions of this function -- one using iteration 
and one using recursion.


2.  (5 points)  Scheme evaluates function calls a little bit differently 
than LISP does.  Explain.


3.  (10 points)  A queue is a list data structure in which elements are 
added to one end and removed from the other end.  Thus, in contrast to 
a stack, which imposes a last-in-first-out (LIFO) ordering on its members, 
a queue imposes a first-in-first-out (FIFO) ordering on its members.  
Your task here is to construct an operator in Common LISP for this new 
abstract data type.  This operator is called enqueue, which puts an 
element on the "back end" of a list.  Here's how it works:

? (setq x '(a b c))
(A B C)
? x
(A B C)
? (enqueue 'd x)
(A B C D)
? x
(A B C D)
? 


4.  (10 points)  In Common LISP, construct your own iterative version of 
the predefined function member using dolist.  


5.  (10 points)  Use dotimes as the primary control structure in 
constructing your own version of the predefined Common LISP 
function nthcdr.


6.  (10 points)  Use mapcar as the primary control structure in 
constructing your own version of the predefined Common LISP function subst.


7.  (10 points):  Common LISP has several functions which generate 
a new symbol each time they're called.  For example, consider the 
following calls of the function gentemp:

? (gentemp)
T0

? (gentemp)
T1

? (gentemp)
T2

In order to make this work, functions like gentemp need to have access 
to an integer generator -- a function which returns the next integer 
in sequence each time it is called.  Using a lexical closure, construct 
a function called make-integer-generator which when called will return an 
executable function body that can be bound to a symbol.  Then construct a 
function get-next-integer which takes as a parameter a symbol that is 
bound to an integer generator and returns the next integer in the 
sequence for that specific integer generator.  If they work the way 
they're supposed to, the functions would behave like this:

? (setf foo (make-integer-generator))
#

? (setf bar (make-integer-generator))
#

? (get-next-integer foo)
0

? (get-next-integer foo)
1

? (get-next-integer bar)
0


8.  (20 points)  Below and on the next page is printed the mini-Scheme 
interpreter from the last homework assignment.  This time, some additional 
parts have been added to interp, but some other parts are now missing, 
namely the code for SET! and QUOTE.  In the space below, provide the 
Common LISP code that will make these two functions work.


The mini-Scheme interpreter:

(defun interp (x &optional env)
  (cond
   ((symbolp x) (get-var x env))
   ((atom x) x)
   ((case (first x)
      (QUOTE [** what goes here? **])
      (BEGIN (last1 (mapcar #'(lambda (y) (interp y env))
                            (rest x))))
      (SET!  [** what goes here? **])
      (IF    (if (interp (second x) env)
                 (interp (third x) env)
                 (interp (fourth x) env)))
      (LAMBDA (let ((parms (second x))
                    (code (maybe-add 'begin (rest (rest x)))))
                #'(lambda (&rest args)
                    (interp code (extend-env parms args env)))))
      (t      (apply (interp (first x) env)
                     (mapcar #'(lambda (v) (interp v env))
                             (rest x))))))))
(defun set-var! (var val env)
  (if (assoc var env)
      (setf (second (assoc var env)) val)
      (set-global-var! var val))
  val)

(defun get-var (var env)
  (if (assoc var env)
      (second (assoc var env))
      (get-global-var var)))

(defun set-global-var! (var val)
  (setf (get var 'global-val) val))

(defun get-global-var (var)
  (let* ((default "unbound")
         (val (get var 'global-val default)))
    (if (eq val default)
        (error "Unbound scheme variable: ~a" var)
        val)))

(defun extend-env (vars vals env)
  (nconc (mapcar #'list vars vals) env))

(defparameter *scheme-procs*
  '(+ - * / = < > <= >= cons car cdr not append list read member
      (null? null) (eq? eq) (equal? equal) (eqv? eql)
      (write prin1) (display princ) (newline terpri)))

(defun init-scheme-interp ()
  (mapc #'init-scheme-proc *scheme-procs*)
  (set-global-var! t t)
  (set-global-var! nil nil))

(defun init-scheme-proc (f)
  (if (listp f)
      (set-global-var! (first f) (symbol-function (second f)))
      (set-global-var! f (symbol-function f))))

(defun maybe-add (op exps &optional if-nil)
  (cond ((null exps) if-nil)
        ((length=1 exps) (first exps))
        (t (cons op exps))))

(defun length=1 (x)
  (and (consp x) (null (cdr x))))

(defun last1 (list)
  (first (last list)))

(defun scheme ()
  (init-scheme-interp)
  (loop (format t "~&==> ")
        (print (interp (read) nil))))




Copyright 1997 by Kurt Eiselt.  All rights reserved.