ACL Chapter 2

Chapter 2 of ANSI Common Lisp (ACL) is available online. Chapter 1 is free too.

Let's work through the exercises in chapter 2:

1. Describe what happens when the following expressions are evaluated:

a. (+ (- 5 1) (+ 3 7))
b. (list 1 (+ 2 3))
c. (if (listp 1) (+ 1 2) (+ 3 4))
d. (list (and (listp 3) t) (+ 1 2))

a. 14
b. (1 5)
c. 7
d. (NIL 3)

2. Give three distinct cons expressions that return (a b c).

1. (cons 'a '(b c))
2. (cons 'a (cons 'b (cons 'c nil)))
3. (car (cons '(a b c) nil)) ; *

* I cheat by using car, but I can't think of a third way using only cons. [update]: A very kind commenter, agillesp, shows the third way:

(cons 'a (cons 'b '(c)))

3. Using car and cdr, define a function to return the fourth element of a list.

(defun my-fourth (x)
  (car (cdr (cdr (cdr x)))))

4. Define a function that takes two arguments and returns the greater of the two.

(defun my-greater (x y)
  (if (> x y)
      x
    y))

5. What do these functions do?

a. (defun enigma (x)
     (and (not (null x))
          (or (null (car x))
              (enigma (cdr x)))))

If x is empty, then enigma returns nil; if first(x) is nil, then it returns T; otherwise it recursively calls itself on the rest(x). Enigma returns T only if the list x contains a nil element.

b. (defun mystery (x y)
     (if (null y)
         nil
       (if (eql (car y) x)
           0
         (let ((z (mystery x (cdr y))))
           (and z (+ z 1))))))

If y is empty, then mystery returns nil; if first(y) equals x, then mystery returns 0; otherwise it recursively calls itself with x and rest(y). If y becomes empty first, then nil propagates back up. If x is found in list y then (+ z 1) adds up how many elements were in the list before it. Thus, mystery returns nil if x is not in y; otherwise it returns the location of the first x in y with the first position being 0.

6. What could occur in place of the x in each of the following exchanges?

a. > (car (x (cdr '(a (b c) d))))
   B
b. > (x 13 (/ 1 0))
   13
c. > (x #'list 1 nil)
   (1)

a. car
b. or
c. apply

7. Using only operators introduced in this chapter, define a function that takes a list as an argument and returns true if one of its elements is a list.

(defun element-listp (x)
  (and (not (null x))
       (or (listp (car x))
           (element-listp (cdr x)))))

8. Give iterative and recursive definitions of a function that
a. takes a positive integer and prints that many dots.

(defun print-dots-iterative (x)
  (do ((i 1 (+ i 1)))
      ((> i x) 'done)
    (format t ".")))

(defun print-dots-recursive (x)
  (if (eql x 0)
      'done
    (progn
      (format t ".")
      (print-dots-recursive (- x 1)))))

b. takes a list and returns the number of times the symbol a occurs in it.

(defun number-of-a-iterative (lst)
  (let ((n 0))
    (dolist (obj lst)
      (if (eql obj 'a)
          (setf n (+ n 1))))
    n))

(defun number-of-a-recursive (lst)
  (if (null lst)
      0
    (if (eql (car lst) 'a)
        (+ (number-of-a-recursive (cdr lst)) 1)
      (number-of-a-recursive (cdr lst)))))

9. A friend is trying to write a function that returns the sum of all the non-nil elements in a list. He has written two versions of this function, and neither of them work. Explain what's wrong with each, and give a correct version:

a. (defun summit (lst)
     (remove nil lst)
     (apply #'+ lst))

remove only returns a new list containing everything but nil; it does not remove nil from lst. A solution is to pass the new list into apply:

(defun summit (lst)
    (apply #'+ (remove nil lst)))

b. (defun summit (lst)
     (let ((x (car lst)))
       (if (null x)
           (summit (cdr lst))
         (+ x (summit (cdr lst))))))

This version does not first check to see if lst is empty; (cdr lst) will cause an error. A solution is to check for an empty lst first:

(defun summit (lst)
  (if (null lst)
      0
    (let ((x (car lst)))
      (if (null x)
          (summit (cdr lst))
        (+ x (summit (cdr lst)))))))

Chapter 2 is done.