Median = 23
Average = 21.9

Histogram:
 

Range	Count
26-30	13
21-25	20
16-20	11
11-15	7
6-10	0
0-5	0

Quiz 1 solutions and comments

Besides solutions, there are comments concerning common confusions, denoted by short labels in () at the start of each comment.  It's those labels that appear on your answer sheets -- look up the meaning here.  (Not all of the comments mean you lost points, and you never lost multiple points for one sort of error within one problem.)

You didn't lose points if you didn't remember the name or argument order of a built-in function as long as you told me what you expected it to do.

Give yourself a pat on the back if you included documentation, comments, or meaningful argument names in your code.
 

1.  (5 points)

Write a definition using DEFUN for a function FOO that is called with a form such as (FOO A B C) and returns a non-NIL value if and only if A evaluates to a symbol, B evaluates to a string, and C evaluates to a number.

We need to test one condition on each argument, and we need all of them to be true.  So each argument gets tested in a predicate, which returns false (nil) or true (anything else).  To require all three to be true, we can "and" them:

(defun  foo  (sym  str  num)
      (and  (symbolp  sym)  (stringp  str)  (numberp  num)))

There are plenty of other ways to do this (e.g. cascaded if, cond).

Comments:

(A)  The names that appear in the argument list are variables -- you want Lisp to evaluate them.  If you quote them, Lisp will give you the unevaluated symbols (and foo will always return false, because the stringp and numberp tests will fail).
(B)  Not a problem, but some answers included a bit of extra code, e.g.:  "And" returns t or nil by itself -- no need to wrap it in an "if".  The predicates do the right thing on a nil input, so don't need to test for that case.  "Cond" can take any number of pairs of test and return value.  "And" can take any number of args.  Etc. etc.
(C)  Predicates like symbolp, etc., just return t or nil.  If you told me what you thought these were doing, or if it was clear, fine.  You'll find out quickly enough how they work when you try to use 'em ;-).
(D)  There's stuff here that's not related to the problem at all...
(E)  The function = is one of several functions used to compare the value of two items -- it can't test what type the item is.
(F)  Don't put () around things unless they're supposed to be there -- () perform an action in Lisp, they're not for grouping or clarity.
(G)  A, B, and C were all separate arguments, not packed in a list.
(H)  In Lisp, "return" is used to get out of a "block" of code.  Most commonly, it's used to quit early from an iteration -- it's like break in C.  It's not needed to return a value from a function -- the return value of the function is whatever the last form (if there's more than one) in its body evaluates to.  For instance, a "cond" form encloses a bunch of pairs -- it evaluates to (returns) the second form in whichever pair was the first whose first form was true.  Putting in a "return" may not break your program if there are no loops or blocks, but it's dangerous...
(I)  For those using cond:  If you want it to fall out on the first failure, you need to test for the opposite of the thing you want to be true.
(J)  Remember Lisp doesn't have infix expressions, just forms -- gotta say (and  x  y  z ) not "x and y and z".  Likewise, the function name comes first in the ().  Function names and their arguments are all enclosed in () -- not like C, where the function name is outside.
(K)  If you need something non-nil to represent true, make sure it's something that really will be non-nil, and that won't cause a Lisp error.  (The convention is to use t, if you don't have something meaningful to return.  Lisp makes an exception for t -- like nil, it doesn't need to be quoted.)
(L)  "If" just tests the value of its first argument for true or false -- it doesn't trap syntax errors or runtime type exceptions.  "Cond" can't trap exceptions either.
(M)  Forgot a function?  For instance, you need a boolean function to combine the results of a bunch of predicates.
(N)  Foo is supposed to do something different on each of its arguments.  Even if the arguments were supplied in a list, foo couldn't be recursive.
(O)  To make an "and" out of a cascaded if, you'd need to put each successive nested "if" in the second slot, so it'll be evaluated if the outer "if" is true.
(P)  "Cond" looks like this:  (cond  (test1  value1)  (test2  value2) ... ).  Cond checks the (testN  valueN) pairs one at a time, in order:  On the first testN that's true, it stops, evaluates valueN, and returns that.  So all the previous tests were false -- can't use it as a substitute for "and".
(Q)  Caution!  Don't reuse your argument names as scratch variables unless you're really really sure that's what you want...  For instance, if you declare a local variable in a "let", and it has the same name as an argument, then inside the "let", you'll see only that local variable.
(R)  "Atom" is more inclusive than "symbol" -- strings and numbers are atoms, too.

Draw a box-and-pointer diagram for the S-expression:

(APE  (BROWN  BEAR)  (CAT . 1))

 
The "top level" of this structure is a list that has three elements in it, APE, (BROWN BEAR), and (CAT . 1).  That gives us three boxes, with the cdr pointers pointing to the next box, except the last is nil, and the car pointers point to the elements.  The first element is a bare symbol, the second is a list (so it has the same structure as the top level list), and the third is a cons -- its car points to CAT and its cdr points to 1.  (It's fine to write the atom names in the boxes.  The things in the car and cdr are pointers, even if they point to atoms rather than other conses, but that's an implementation detail.)

Comments:

(2A)  Didn't get the nested list (brown  bear) right.
(2B)  Didn't get the dotted pair (the non-list cons) (cat . 1) right.
(2C)  Didn't get the top-level (outermost) list right.  It is an actual list (no dots), so the cdr of each cons points to the next, except the last, which ends with a nil.
(2D)  Atoms aren't packaged up in conses.
(2E)  In a linked list (in Lisp or any other language), each element has a pointer to the next.  They're not packed next to each other in memory like an array.
(2F)  Conses just have two places to put pointers.
(2G)  The (cat . 1) is the contents of the third element in the top-level list.

Write a definition for a function DEEP-DOUBLE that takes a list as input and returns a new list in which each original element has been repeated, and this happens recursively in any sublists.  Example:

(DEEP-DOUBLE  '(A  B  (C  (D))))

returns the list:

(A  A  B  B  (C  C  (D  D)  (D  D))  (C  C  (D  D)  (D  D)))

 
We want to do recursion on sublists that appear in either the car or cdr.  For recursion, the first thing we need to do is decide when to stop...or we probably won't...and what to return at the end.  The easy case is nil -- it's a list with no elements, so we have nothing to double -- we just return nil.  The question doesn't tell us what to do if the argument is not a cons, so we can do whatever makes our job easiest in that case.  We can start by putting in a tests for an atom, and and leaving the result value open.  (Technically, the question doesn't tell us what to do if the argument is a cons that's not a list, like that (CAT . 1) above -- again, we can do whatever's easiest.)  So far, we have something like:

(defun  deep-double  (lst)
      (cond
            ; End cases
            ((null  lst)  nil)    ; Done if the list is empty.
            ((atom  lst)  ??? )   ;Don't decide what to return yet.
            ; Here, we have a cons -- this is the recursion case.
            ; We don't care what happens if this isn't a list.
            (t  ??? )))

In the recursion case, we know our argument is at least a cons, and maybe a list.  We know we want to apply the recursion to sublists in the car, so we'll call deep-double on that.  Then we'll want to put that car result twice on the front of whatever we do with the cdr.  Since we're going to use that car result twice, why don't we compute it once and save it in a local variable:

(let  ((first-result  (deep-double  (first  lst))))
      (cons  first-result  (cons first-result ??? )))

This tells us what we want deep-double to return if its argument is an atom.  If we look at the sample argument and the expected output, we see that the symbol A in the car of the list ends up with two As consed onto the front of the list.  To do that, we should just return the argument itself if it's an atom:

((atom  lst)  lst)

(Recall we weren't told what (deep-double 'a) should do, so we can choose whatever makes our work simpler.)

Note the choice to use (cons ...  (cons  ...  ??? ))  also implies that we want ??? to be a list.

The thing we want to cons onto is the tail of the recursion -- the recursion on the rest (cdr) of the list.

(deep-double  (rest  lst))

Putting the pieces together:

(defun  deep-double  (lst)
      (cond
            ; End cases
            ((null  lst)  nil)    ; Done if the list is empty.
            ((atom  lst)  lst)   ; Just return atoms.
            ; Here, we have a cons -- this is the recursion case.
            ; We don't care what happens if this isn't a list.
            (t  (let  ((first-result  (deep-double  (first  lst))))   ; Capture the result of recursion on the first element.
                  ; Put that twice onto the result for the rest of the list.
                  (cons  first-result  (cons  first-result  (deep-double  (rest  lst))))))))

There are alternatives -- you-all found a number of them.  Here was a common one:  Instead on consing the car result on twice, make a list of two car results and append it to the cdr result.

(append  (list  first-result  first-result)  (deep-double  (rest  lst)))

Here's a solution found by a couple of you, using the above.  Note it doesn't need a case for the argument being an atom:

(defun deep-double  (lst)
      (cond
            ((null  lst)  nil)    ; Done if the list is empty.
            ((atom  (car  lst))   ; If the car is an atom, just double it and tack it onto the cdr result.
                   (append  (list  (car  lst)  (car  lst))  (deep-double  (cdr lst))))
            ; Here, the car is a cons.
            (t  (append  (list  (deep-double  (car  lst))  (deep-double  (car  lst)))  (deep-double  (cdr lst))))))

Note it doesn't quite work to just make a list of all two car results and a cdr result because the cdr result is a list by itself -- putting it in a list will make it a nested list rather than appending it onto the tail.

Comments:

(3A)  Forgot to double -- should be two of these.
(3B)  For the case where the car of the argument is an atom -- forgot to cons just the car of the argument onto the recursive call.
(3C)  If the car of the argument is a list, this won't double the recursive call on the car.
(3D)  This will put the recursive result in a nested list.
(3E)  Forgot to stop at the end of the list.
(3F)  Didn't combine the results correctly.  (E.g. forgot the combining function, or inserted the cdr result as a sublist...)
(3G)  Forgot to do recursion on the car.
(3H)  Assorted syntax problems.  (E.g. cons only takes two args -- need to nest repeated conses.  Can't combine things with dots.  Need a function to combine things.  Put function names first.  Etc.)
(3J)  Forgot the atom case.
(3K)  In order for a recursion to terminate, the argument to the recursive calls has to be "smaller" than the original argument.  In particular, don't give the original argument to the recursive call, or it'll never stop...
(3I)  Forgot to include the recursion on the cdr in some case.

Here are two things that are often done in Lisp programs -- you might find yourself using these in later assignments...

Say you have a function called xxx that takes one argument (that is, you can do calls like (xxx  'A) with it).  Write a function doXXX that takes a list as an argument, calls xxx on each element in the list, and returns a list of the results, in the same order as their sources in the original list.

We could write a recursive function that does this, but our old friend mapcar does just what this asks -- applies a function to each element in a list.We quote the function name to warn Lisp that we want the function

(defun  doXXX  (lst)  (mapcar  #'xxx  lst))

Why did we use that #'?  That's the same as saying (function xxx).  A "function name" is a symbol whose function field, not the value field, points to the function.  Defun is what we use to get the function into the symbol's function field.  Normally, if we hand Lisp a symbol, with no quotes, it thinks we want to treat it as a variable name, and it looks for a value stored in the symbol's value field.  We don't want the value here, so we have to tell Lisp which field in the symbol to use.

(defun dofn (lst fn) ...

What's different here is that we have a function stored in a variable -- this time around, we do want Lisp to treat the symbol as a variable, and pull out the value.  Since that is what Lisp will do if we don't tell it otherwise, we can just leave the variable name unquoted:

(defun  dofn  (lst  fn)  (mapcar  fn  lst))

(The following is in here only as an example of using a lambda expression -- don't do this if you don't have to...)  If we happen not to know how Lisp stores values and functions in a symbol, but we remember that we can ask Lisp to call a function stored in a variable by using "funcall", then we could instead give mapcar a little anonymous function (a lambda expression) that uses funcall to execute the supplied function:

(defun  dofn  (lst  fn)
      (mapcar  (lambda  (x)  (funcall  fn  x))
            lst))

Your TA (Pat, that is) did this for years before realizing that the previous form worked...  However, this is what you would need to do if, say, fn took serveral variables and you wanted to fill some of them in with constants.  That's called "currying".

One way to do this is to write a recursive function that looks at the first element in the list it's given, and if it's not nil, conses it onto the result of calling itself on the rest of the list.  If it is nil, it just don't cons it on.  Here's one way to do this:

(defun  noNILs  (lst)
      (cond
            ; The end case...  If the list is empty, we're done.
            ((null  lst)  nil)
            ; The recursion cases -- decide whether to cons on the first element.
            ((null  (first  lst))  (noNILs  (rest  lst)))   ; First element is nil -- leave it off.
            (t  (cons  (first lst)  (noNILs  (rest  lst))))))   ; Not nil -- keep it.

There are lots of variants.  For instance, you might want to use a "let" form to make local variables for (first lst) and (rest lst) to avoid clutter.  But one big reason for using "let" is to avoid re-evaluating something.  That won't happen here, because the cond will only execute one of its branches.  So we could use a let, but it won't make the function run faster.

Or, we might happen to know that there are built-in functions that do exactly this sort of thing -- "remove" strips a given item out of a sequence, and "remove-if" and "remove-if-not" strip out elements that satisfy a predicate or don't satisfy it, respectively.  To remove nils, we could tell remove to remove nils, or give remove-if #'null as its predicate:

(defun  noNILs  (lst)  (remove  nil  lst))
(defun  noNILs  (lst)  (remove-if  #'null  lst))

Thanks to Hao L. and Kai W. for pointing out the "remove" solution!  (I only knew about remove-if and remove-if-not. ;-)

I wasn't clear about whether the function was supposed to be hard-coded in, or passed in as an argument -- either of these was ok.  (I was thinking about having the function passed in as an argument, but then I should have named it something ugly like doFnNoNILs, to go along with dofn above.)

We can use our dofn or doXXX to get a list of results, then run noNILs on it to get rid of the nils.  (Caution:  We don't want to strip nils out of the input list -- we want to take them out of the list of results.)  Here are some options -- explicit function name xxx or a passed-in function:

; Apply the function xxx to elements of a list, but don't keep any nil results.
(defun doXXXnoNILs  (lst)  (noNILs  (doXXX  lst)))
; Or...
(defun doXXXnoNILs  (lst)  (noNILs  (mapcar  #'xxx  lst)))
; Or...
(defun doXXXnoNILs  (lst)  (remove  nil  (mapcar  #'xxx  lst)))

; Apply the function supplied as an argument...
(defun doXXXnoNILs  (lst  fn)  (noNILs  (dofn  lst  fn)))
; Or...
(defun doXXXnoNILs  (lst  fn)  (noNILs  (mapcar  fn  lst)))
; Or...
(defun doXXXnoNILs  (lst  fn)  (remove  nil  (mapcar  fn  lst)))

These are all short enough functions (if we use built-in functions) that making helper functions isn't much of a savings.  But for larger applications, helper functions are very common.  We can debug the helpers thoroughly, then trust them.  It's easier to understand the code and we're less likely to make mistakes.  It's like we're extending the programming language, or making a toolkit.

Comments:

(4A)  Remember to put in an end case when doing recursion.
(4B)  Use the function quote on actual function names when they're used as arguments, e.g. #'xxx or (function xxx).  (Of course, don't quote them when they're being used as functions, at the front of a form!)
(4C)  Don't quote variable names when they're used as arguments, or Lisp will think you don't want the value, just the name.  E.g. if I say (setf fn #'+), so fn is a variable containing a pointer to the function +, then (funcall #'fn 1), Lisp will complain that there's no function named "FN".  Recall a function named, say, abc is a symbol with its function field pointing to a lambda expression (i.e. the definition of the function), while a "variable" is a symbol with its value field pointing to something.  That something can be a function, but to Lisp, it's still a variable with a value.  (For you Schemers out there:  Scheme doesn't have this wrinkle -- its symbols have only one field to point to a value or function -- it can distinguish them by checking their type.)  I've never seen anyone do anything useful with Lisp's ability to store both a function and a value in one symbol, and it causes lots of confusion.
(4D)  The question asked for the non-nil results of applying the function, not the results of applying the function to only the non-nil arguments...
(4E)  The question said apply the function to each element in the list, so this shouldn't step into nested lists.  Consider:  If you did step into nested lists, you couldn't pass any lists as arguments to the supplied function.
(4F)  Need a cons to combine the current item with the result of the recursive call.
(4G)  Assorted syntax errors.
(4H)  Use "funcall" if you want to apply a variable containing a function to a single set of its arguments, e.g. (funcall fn arg).
(4I)  Do functional programming -- avoid assignment and destructive modification -- if only for the snob value...
(4J)  We want to apply the supplied function to each element of the supplied list separately -- we don't want to apply the function to the whole list, or to the tail of the list, or call the function with an argument list made out of the contents of the supplied list.  (Note apply isn't mapcar -- see 4K also.)
(4K)  Apply calls its function (its first argument) with its list (its last argument, with any middle arguments consed on the front) turned into arguments to a single function call.  That is, (apply #'+ '(1 2 3)) is the same as (+ 1 2 3).  Apply is one of only a few forms that can take the contents out of a list.  It's sort of the opposite of mapcar -- it executes the function once, will all the list elements as arguments, where mapcar executes the function once for each list element, with that one element as its sole argument.  (I'm lying -- mapcar is fancier than that.  If you have a function that takes N arguments, you can give mapcar N lists, and it will step through all the lists in parallel, and call the function with one element from each of the lists asits arguments, in the same order as the lists appear in the mapcar form.  E.g. (mapcar #'+ '(1 2 3)  '(4 5 6)) yields (5 7 9).)
(4L)  Need to handle the case where there's a nil at the head of the list.
(4M)  Don't quote lists unless you want their contents to all be treated as literal symbols, e.g. '(cdr lst) means a list containing the symbols 'cdr and 'lst.
(4N)  Need to handle the case where there's not a nil at the head of the list.
(4O)  "Non-destructive" operations like (cdr lst) do not change their arguments -- lst is still the same afterward.

List two problems with the Turing Test as a way to measure the intelligence of a system.  Then describe how these two problems could be overcome.

There are all sorts of possible right answers -- here are a few.  Some are from your own answers.

Problem:  What if the system doesn't naturally communicate by dialogue?  What if its normal input is numbers or images or a database or what-all?

Fix:  The dialogue-based test is slanted toward the human, because dialogue (it turns out) is a very hard problem -- and even worse if it's speech, not text.  We could just say, lets supply the system's natural input to both the system and the human, but then we might be pushing the bias the other direction -- humans are great at dialogue but lousy at processing terabyte databases, for instance.  So we might let the human use appropriate tools -- Matlab, or Photoshop, or Oracle, etc.

Problem:  The Turing Test is subjective.  What if our system produces values that we could, instead, compare against real data?  Or maybe we don't have "hard" data, but we have answers provided by experts.

Fix:  If we do "know the right answers" on some set of input data, then, by all means, we should forget about the human questioner's judgement and compare the machine's answers to the correct ones.  That is, we should measure the performance of our system by seeing how accurate it is.  One caution:  If we're using data with answers to "train" our system, then it's not fair to test it on exactly the same data!  It could just be recording and spitting back what we gave it.  A piece of paper could do that...  We want to see how well it does on new examples -- we want to know how well it "generalizes" or "predicts".

We might also want to test it on cases where we don't already know the answer.  Then, after getting an answer from our system, we'd have to go figure out if it could be right.  (Sometimes there are surprises -- the system may produce an answer that disagrees with an expert, and after careful checking, it could turn out the system has a better answer.  This has happened, for instance, in recommendations for medical treatment.)

The following answer wins the popularity award.  Thanks to David K., Kai W., Varo L., Benjamin B., Phong H., Flor M., Ross Y., Andy S., Marshella T., ...:
Problem:  Some people are easier to fool than others.  People will be swayed by their own preferences.  Similarly, the test relies on the ability of the hidden human.
Fix:  Use multiple judges and multiple human subjects.  (This will "average out" the effects of individual differences.)

Thanks to Seth W., Justin S., Hao L., Natascha M., ...:
Problem:  Just asking questions doesn't give a way to test for a capacity to learn.  Also, it can't learn from its mistakes unless it gets feedback.
Fix:  Let the interrogator also act as an educator.

Plus lots of other good suggestions...

Comments:

(5A)  The question was about the Turing Test...
(5B)  < 2 problems + fixes.