Lisp Quiz

Name: Solution Set

This Quiz is worth 50 points. Each point represents a minute of time. Use the point totals as a guide for budgeting your time. The exam is closed-book, closed-notes, open-mind.

(1.) [5 points total] For the following Lisp expressions, show how the result prints out. If the expression results in a run-time error, say why.

1.1) [1 pt] (list (+ 1 2) '(+ 1 2))

(3 (+ 1 2))

1.2) [1 pt] (cons (+ 1 2) '(3 4))

(3 3 4)

1.3) [1 pt] (reverse (append '(1 2) '(3 4)))

(4 3 2 1)

1.4) [1 pt] (remove-if #'(lambda (x) (>= x 10)) '(11 10 9 5 15 6 0))

(9 5 6 0)

1.5) [1 pt] (+ 10 (car '((1) (2) (3))))

Error! Cannot add lists!

(2.) [7 points total] For each of the following Lisp expressions, show how the result prints out AND also draw the cons-cell box and pointer diagram of the result. For example, for (list 1 2 3) I would answer:

(1 2 3)



2.1) [2 pt] '((1) (2))

((1) (2))



2.2) [2 pt] (list (cons 1 nil) '(2 3))

((1) (2 3))



2.3) [3 pt]

(let ((x '(1 2))

(y '(9 10)))

(list (+ (first x) (first y)) (+ (second x) (second y))))

(10 12)



(3.) [7 pt] Write the function nth, which takes a positive integer N, and a list L, and returns the element at the Nth position in the list. (Yes, I know that nth is built into CL, but pretend it isn't for this problem.) You may assume that 1 <= N <= length of the list. In other words, don't worry about an out-of-bounds index. Your function must be recursive.

(nth 2 '(joe bob bill)) => bob

(defun nth (n list)
       (cond ((= n 1) (car list))
             (t (- n 1) (cdr list))
        )
 )

(4.) [7 pt] Write a function called censor-word, which takes a symbol and list. It returns a list in which all occurrences of the symbol have been replaced by XXXXX. The function must be written recursively and cannnot make use of any of Lisp's higher-order functions such as mapcar. The function only has to traverse the "top-level" of the list. Here are some examples:

(censor-word 'FORTRAN '(I AM A FORTRAN PROGRAMMER)) =>

(I AM A XXXXX PROGRAMMER)

(censor-word 'NEWT '(BILL NEWT BOB PAUL)) => (BILL XXXXX BOB PAUL)

(defun censor-word (word list)
       (cond ((null list) nil)
             ((equal (car list) word) (cons 'XXXXX (censor-word word (cdr list))))
             (t (cons (car list) (censor-word word (cdr list))))
        )
 )

(5.) [5 pt] Write censor-word again, this time using mapcar. You must use a lambda expression (do not define extraneous helper functions).

(defun censor-word (word list)
       (mapcar #'(lambda (x) (if (equal x word) 
                                 'XXXXX 
                                 x
                              )
                  ) list)
 )

(6.) [9 pt] Write count-if, which takes a predicate function and a list as arguments. (Again, count-if is built-in, but pretend its not for this question.) This function should count the number of top-level elements in the list that satisfy the predicate. Do not use any higher-order functions. (Partial credit: if you can't figure out how to write count-if, try writing count, which takes an element and a list and counts the number of list elements that are equal to the given element.)

(count-if #'(lambda (x) (> x 4)) '(1 2 3 5 6 7)) => 3

(count-if #'(lambda (x) (> x 10)) '(1 2 3 4)) => 0

(defun count-if (pred list)
       (cond ((null list) 0)
             (t (if (funcall pred (car list))
                    (+ 1 (count-if pred (cdr list)))
                    (count-if pred (cdr list))
                 ))
        )
 )

(7.) [10 pt] Choose ONLY ONE of the below short-answer questions and answer it. We don't expect essay answers; clear, concise answers will be rewarded.

1. How did using CommonLisp (instead of C or Ada) to implement MiniScm make the job easier? How did it make it harder?

2. Give two disadvantages and two advantages of dynamic typing compared to static typing. Say why.

3. MiniScm has a simple, easy to specify language, with only a few basic concepts. In what ways does this make MiniScm a good language? In what ways does it make it a bad language?

Here are sample solutions. Obviously they are more complete than many answers which received full credit.
  1. Using CL made life easy because we didn't have to build an S-Expression data structure and its supporting operations (cons, car, cdr, read, print, etc.). We also didn't have to do much work to build data structures for environments (stacks) and frames (tables). We didn't have to worry about memory management, and lisp provided a nice programming environment. Using CL made life harder because it is hard to read, inefficient, the debugger isn't great, and it was conceptually hard to separate CL from MiniScm sometimes.
  2. Advantages of dynamic typing include the ability to support late binding, which allows us to write very abstract functions and supports a flexible programming style. Also, dynamic type checking means that there is less work at "compile" time. Disadvantages of dynamic binding include large object size (all data must be "tagged" with its type), inefficient run time (due to all of the type checking), and later error detection of certain classes of errors.
  3. MiniScm is good because it is easy to learn, easy to implement (which, by extension, should MiniScm programs more portable), and it is easy to keep the language design internally consistent (few special cases). On the bad side, the language is possibly quite inefficient, doesn't support programming-in-the-large (data hiding, modularity), and has very few built-in operators and almost no interesting built-in data types (although the list is arguably about all you need..).