------------------------------------------------------------------
Assignment 2a: GETTING USED TO LISP ON YOUR COURSE ACCOUNT
------------------------------------------------------------------

You won't be doing any programming this week, but it's a good idea to
get used to the LISP environment, and you can do that even if you
don't know how to program in LISP yet.  This first part of this week's
assignment will walk you through a step by step tutorial introducing
you to some LISP basics. (Credit where due: I've adapted some of
Prof. Dorr's CMSC421 course materials!) This is far from an exhaustive
introduction, but it's a decent way you can get started entirely on
your own, to get a feeling for what LISP is like.

Part 2a includes problems at the very end of the tutorial
in Step 5.


1.  Type "lisp" (without the double quotes) at the shell prompt
    and hit return:

    ---
    % lisp
    CMU Common Lisp 17f, running on holmes.umd.edu
    Send bug reports and questions to your local CMU CL maintainer, or to
    cmucl-bugs@cs.cmu.edu.
    Loaded subsystems:
	Python 1.0, target Alpha
	CLOS based on PCL version:  September 16 92 PCL (f)
	CLX X Library MIT R5.02
	Hemlock 3.5
    * 
    ---


2. The star (*) is the prompt for working within LISP on this system.
   When you're in LISP, the interpreter waits for you to give
   it an expression of some kind, evaluates that expression,
   and then returns the value it got.  For example, try typing
   the number 7 and return:

    ---
    * 7

    7
    ---

   Try typing an expression like (+ 2 3) and see what gets returned:

    ---
    * (+ 2 3)

    5
    ---

    Note that any time you want to quit out of lisp, type (quit)
    at the star prompt.

    ---
    * (quit)
    %
    ---

    Notice that it has to be (quit) in parentheses! 


3. Try typing something that LISP actually doesn't know the value of;
   for example, if you type the symbol x, the LISP interpreter
   will try to figure out what the value of x is, but fail, because
   you haven't bound the symbol x to any value, and unlike numbers
   it doesn't have any intrinsic value.  LISP will tell you about
   the problem as follows:

    ---
    * x

    Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER:  the 
    variable X is unbound.

    Restarts:
      0: [ABORT] Return to Top-Level.

    Debug  (type H for help)

    (EVAL X)
    0]
    ---

   The message is telling you where LISP is reporting the error from,
   namely a part of the interpreter called 
   KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER.  You don't really
   care about that, but you do care about the error message:
   "the variable X is unbound".  Notice that it is reporting
   something about uppercase X, even though what you typed was
   lowercase -- LISP is not case sensitive, and traditionally
   everything is just treated as if it were uppercase.

   You can now muck around in the debugger (if you'd care to try,
   take a look at  for documentation), but
   what you'll want to do much of the time is just get out of the
   debugger and back to the star prompt.  To do this you can
   just type a 0 (to choose option 0, return to the top level),
   or you can type quit, which will pop you up to the top level.
   Be careful not to type (quit) in parentheses, though, or 
   you'll quit out of the LISP interpreter altogether!  In parentheses,
   it's a function call to the LISP interpreter; out of parentheses,
   it's a command to the debugger saying to go back to the top level.
   Yup, computers are a pain sometimes.

    ---
    * x

    Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER:  
    the variable X is unbound.

    Restarts:
      0: [ABORT] Return to Top-Level.

    Debug  (type H for help)

    (EVAL X)
    0] quit

    * 
    ---

4. Here are some basics of how expressions get evaluated:

    -   Number -> number itself (e.g., 7 -> 7)

    -   String -> string itself (e.g., "hi" -> "hi")

    -   Symbol  ->  value  of  symbol  (e.g.,  X -> 5,  
        if  X  has  the value 5).  Symbols are like variables in
        most languages, in that they have a value associated
	with them.  Some special symbols include  T and NIL.
        These represent true and false, and can't be set to 
        any values other than themselves.

    -   List -> normally function evaluation
        In usual mathematical notation, you write a function f
        with arguments a and b as f(a,b).  In LISP, the notation
        is to write it as a list, with the first element being
        the function and the rest of the list being the arguments,
        e.g. (f a b).  That's why to add 2 plus 3, the expression
        is (+ 2 3) -- you're applying the function + to arguments
        2 and 3.

    -   If you want to tell LISP to treat something as the
        thing itself, for example to treat a list as the list
        itself, you put a single quote in front it.  For example,

	  ---        
	  * (+ 2 3)

	  5
	  * '(+ 2 3)

	  (+ 2 3)
	  ---

        When you gave the first expression to the LISP interpreter,
        it evaluated it by calling function + on arguments 2 and 3,
        hence returning the result 5.  Since the second expression
        was quoted, it was evaluated and the result was the list
        containing the symbols +, 2, and 3.

   Here are some more examples to try.  If you get errors,
   see Step 3 above for how to get out of an
   error and back to the top level of the interpreter.

     (+  1  1)
     (*  23  13)
     (+  1  (*  23  13))
     (+  (*  2  2)  (-  10  9))
     (*  2  2  2  2)
     (sqrt  (*  2  2  2  2))
     (/  25  5)

   The following example shows that strings, like numbers,
   evaluate to themselves:

     "Hello,  world!"

   Here's another quotation example.  Quoting the symbol
   means that you want to get the symbol itself, not the
   value the symbol is bound to. (Compare this to what we 
   did in Step 3 above.)

     'x

   Here's how you assign (or "bind") values to variables.

     (setf  x  5)

   This binds the variable x to the value 5, and returns the value
   that x got bound to as a side effect.  Notice that now if you
   type just x without the quotes

      x

   it'll give you back the value x is bound to instead of an unbound
   symbol error. Similarly, consider:

     (setf  x  (* 2 3))

   By the way, don't worry about warnings that the interpreter 
   is "declaring X special".  

   Here are some more things to try:

     (setf  y  (reverse  '(+  a  b)))

   The "reverse" function takes a list and reverses it.  When this
   whole expression was evaluated, first the reverse function was
   called on the quoted list containing the symbols +, a, and b
   (you needed the quote, or it would have tried to call the plus
   function on variables a and b!), giving you a list containing
   b, a, and +.  Then y was bound to that value.  As mentioned above,
   the setf function then returned the value that the variable got 
   bound to.

   More to do: set the value l to be a list containing 5 symbols.
   (That's lowercase L, not the number 1!)

     (setf  l  '(a  b  c  d  e))          

   Here are some operations on lists: the length function returns the
   length  of  a  list:

     (length  l)                        

   The append function merges two lists together, returning the merged
   list as the value.  Notice here that l is not quoted but the list
   '(f) is quoted -- if you're not entirely sure why, go back and re-read 
   the description above where the "reverse" function was first used.

     (append  l  '(f))

   Now try:

     (length  l)

   Notice that the length of l hasn't changed!  That's because
   when you called the append function, it computed a NEW merged
   list, first copying l and then merging it with '(f) -- what
   got returned was the copy.  This kind of operation is called
   "non-destructive", since it creates a new value without messing
   with the values of its arguments.  This kind of copying can
   be wasteful, in terms of computational efficiency, but it's
   often useful and very characteristic of the LISP language.

   Now try:

     (list '(John Q Public) 'Sandy)

   The list function creates a new list whose elements are the 
   arguments to the function -- in this case a list whose first
   element is itself a list, and whose second element is the 
   symbol Sandy.  Symbols like 'Sandy are called "atoms" because
   they have no internal structure.  

   Note how list puts the arguments into  a  list; it 
   doesn't  merge  them  like append does.  Can you figure
   out what the result of the following is going to be before
   you try it?

     (length (append '(pat Kim) (list '(John Q Public) 'Sandy)))

   
   Notice the order of evaluation is critical here:  the
   innermost things get evaluated first.  That is, first
 
     (list '(John Q Public) 'Sandy)

   to give you the list

              ((JOHN Q PUBLIC) SANDY)

   (Remember that uppercase/lowercase doesn't matter!)
   Then, continuing, it's as if you've made the function call

     (length (append '(pat Kim) '((JOHN Q PUBLIC) SANDY))

   (Can you figure out why the second argument to append is quoted?
   Try it without the quote!)  Next, the append is evaluated,
   with its two list arguments, to get

              (PAT KIM (JOHN Q PUBLIC) SANDY))

   So in the next step it's just like you're evaluating

     (length '(PAT KIM (JOHN Q PUBLIC) SANDY))

   Can you see why the value is 4?  What is the first element
   of the list?  The third element?

   In case you haven't already figured it out, by the way,
   you must always be careful that your parentheses match.
   You get bizarre errors otherwise.

   Have you forgotten what the value of the symbol l is?
   Type it to find out:

      l

   Here are some more things you can do with lists:

      (first l)
      (rest l)

   That last one, rest, gives you a list that is "the rest"
   of l after the first element.  You can also do

      (second l)
      (third l)

   and so forth.  I'm not sure how high these go, but in general
   you can use the "nth" function to get the nth element of 
   a list, e.g. get the fourth element by calling

      (nth 3 l)

   (Notice numbering of list elements starts from zero.)

   And as usual, you can nest these calls.  So, for example,
   
      (first  (rest  l))

   gives you the first element of the rest of l, which is equivalent
   to the second element on the list.

   What will 

      (rest '(a))

   give you?  Yes, it should give you the empty list,
   since after that first element the list is empty.
   But in LISP the empty list is written NIL -- it is
   the same value that is used for "false".

   A few more things to do with lists, and we'll be done for now.

   An "association list", or a-list, is a special kind of list
   whose elements are pairs of elements; intuitively, this is a
   way to represent a mapping from one set to another (i.e.,
   a mathematical relation).  For example

     (setf departments '((smith physics) (jones math) (perez english)))

   This list has three elements, each of which is an ordered pair;
   for this example, it gives a fictitious name and the department
   that person is in.  The assoc function can be used to search
   such a list, e.g.

     (assoc 'jones departments)

   finds the pair where jones is the "key", and 

     (second (assoc 'jones departments))

   gives you the second element in the pair, which is the 
   way you can find out what value jones is associated with.
   If what you're looking for isn't found, the value NIL
   is returned
   
     (assoc 'jackson departments)

   and by definition any element of the empty list, NIL,
   is itself NIL:

     (second (assoc 'jackson departments))



5. Do the following to turn in next class as your answers to
   Assignment 2a:

   Set variable list1 to be a list containing symbols q1 q2 q3 q4.

   Set variable list2 to be a 3-element list whose elements are
   themselves the following lists:

      (a b)
      (c d e)
      (e f)

   To turn in:  what do you get when you do the following?  Do
   these in order and show the result at each step:

      (setf combined (append list1 list2))
      (length combined)
      (setf newlist (rest (rest (rest (rest combined)))))
      (third (assoc 'c newlist))
      combined
      (pop combined)
      (pop combined)
      (pop combined)
      (first combined)
      (push 'q5 combined)
      combined