Assignment 2 Part A

1)  The general rule for symbol names in Lisp is, if Lisp can't interpret a string of non-blank characters as something else, it can be a symbol name.  So, for instance, legal numbers aren't allowed as symbol names because Lisp can interpret them as numbers.  Likewise, strings that have the form of lists aren't legal symbol names...with one exception:  Lisp makes a special exception for the string () which it interprets as being the same as NIL, which is a symbol.  These following punctuation characters are ok to use in symbols  + - * / @ $ % ^ & _ = < > ~ .  but note that + or - in front of a number is interpreted as part of that number.  Other punctuation has meaning in Lisp statements, so even if one could get away with using it in a symbol in some cases, it's better not to.  So for the strings in the problem...
 
The string... ...is interpreted as a...
SYMBOL symbol
(0) list
(A B) list
17 number
( ) symbol (special case!)
T symbol
1+ symbol
NIL symbol
4A symbol

2)  What would Lisp evaluate these expressions to?  A simple way to check whether your intrpretation is right is to type them at the Lisp prompt and look at the result.
 
Expression Value Description
(1+ (* 4 5)) 21 the number 21
(first (quote (a list))) A the symbol A
(first '(a list)) A the symbol A
(rest '(a list)) (LIST) a list containing the symbol LIST
(car '(another list)) ANOTHER the symbol ANOTHER
(cdr '(another list)) (LIST) a list containing the symbol LIST
(second '(another list)) LIST the symbol LIST
(cons 'to '(be or not to be)) (TO BE OR NOT TO BE) a list containing the symbols, in order: TO BE OR NOT TO BE
(cons (cdr '(cats dogs))(car '(bears lions))) ((DOGS) . BEARS) a cons with car containing the list containing the symbol DOGS, and cdr containing the symbol BEARS
(cond (nil 1) (t 2)(nil 3)(t 4)) 2 the number 2

3)  How many calls does Lisp make to function COUNT-SUBLISTS in the expression (count-sublists '(a (b) (c (d))))?  A good thing to do is to compare what a function claims to do with what it really does -- it might be buggy.  So let's ignore the documentation string and execute it by hand.  (You could check this by executing it in the clisp debugger.  Or you could add an expression that adds one to a global symbol inside the call.)  Recall the definition of COUNT-SUBLISTS: 

(defun count-sublists (lst)
    (cond ((null lst) 0)
          ((atom lst) 0)
          ((atom (first lst)) (count-sublists (rest lst)))
          (t (+ 1
                (count-sublists (first lst))
                (count-sublists (rest lst))))))
Here are all the calls it makes to itself:
 
Why it makes this call What the call is
initial call (count-sublists '(a (b) (c (d))))
Inside the initial call, (atom (first '(a (b) (c (d)))) is true. (count-sublists '((b) (c (d))))
Inside (count-sublists '((b) (c (d)))), evaluates 2nd arg of the (+ ...). (count-sublists '(b))
Inside (count-sublists '((b) (c (d)))), evaluates 3rd arg of the (+ ...). (count-sublists '((c (d))))
Inside (count-sublists '(b)), (atom (first '(b))) is true. (count-sublists NIL)
Inside (count-sublists '((c (d)))), evaluates 2nd arg of the (+ ...). (count-sublists '(c (d)))
Inside (count-sublists '((c (d)))), evaluates 3rd arg of the (+ ...). (count-sublists NIL)
Inside (count-sublists '(c (d))), (atom (first '(c (d)))) is true. (count-sublists '((d)))
Inside (count-sublists '((d))), evaluates 2nd arg of the (+ ...). (count-sublists '(d))
Inside (count-sublists '((d))), evaluates 3rd arg of the (+ ...). (count-sublists NIL)
Inside (count-sublists '(d)), (atom (first '(d))) is true. (count-sublists NIL)

So it makes 11 calls to itself.

Here's a way to check your result -- or to make Lisp do the work for you!-- by adding a counter: 

(setf *NCALLS* 0)

(defun count-sublists (lst)

    (setf *NCALLS* (1+ *NCALLS*))

    (cond ((null lst) 0)
          ((atom lst) 0)
          ((atom (first lst)) (count-sublists (rest lst)))
          (t (+ 1
                (count-sublists (first lst))
                (count-sublists (rest lst))))))
(Gotta remember to set *NCALLS* to zero in between tests...)  The more complicated the expression, the more useful it is to do some automated checking.  (I counted the number of calls incorrectly the first time I tried it by hand, so it was a good thing I checked!  I forgot the list that (rest '(X (Y))) wraps around '(Y)...)

4)  This problem was changed so that we only want to replace non-NIL atoms in one level of list in the argument.  (This isn't quite consistent:  If we're not delving into sublists, why should we go into any argument that's a list at all?  So to be more precise, let's say, if the argument is an atom itself, we want to replace it, and if it's a list, we want to replace atoms in that list, but not go any further.  It's fine if you did this either way.)

I'm going to define a little helper function to choose between NIL or 'X or leaving an item alone, which I'll apply to each element in the list (recall NIL is an atom): 

(defun NILorX (thing)
    (cond ((null thing) NIL)
          ((atom thing) 'X)
          (t thing)))
(defun exify (lst)
    (if (atom lst) (NILorX lst)
                   (cons (NILorX (first lst)) (exify (rest lst)))))
Here's another way, that doesn't use recursion, but instead uses one of the "map" functions that traverses lists.  The function "mapcar" is a bit more general than "dolist", which you've seen.  The first argument to mapcar is a function that takes some number of variables.  The remaining arguments to mapcar are lists, where the number of lists must match the number of arguments in the supplied function.  Mapcar goes through all the lists in parallel, taking one element from each and passing them to the function, in the same order as the lists they came from.  It returns a list of the results. 
(defun exify (lst)
    (if (atom lst) (NILorX lst)
                   (mapcar #'NILorX lst)))
This is faster than recursion, because Lisp is simply following the pointers in the list -- it doesn't have to make new call frames and then back out of the calls.

-- Pat