----------------------------------------------------------------
Assignment 3a.  More LISP Basics: writing simple programs
----------------------------------------------------------------

This assignment covers some basics of LISP programming.  It includes a
tutorial that is very selective in its content, not a thorough intro
to LISP!  But it should provide enough to do the problems in this
part.  You should already be able to run LISP on your course account,
so I'm going to assume you're typing things in and seeing what the
results are like as you work your way through this little tutorial.

Parts 1 and 2 below are not required; they are for your benefit if you
have not programmed in LISP before.  Please do NOT turn in anything
from Parts 1 and 2 -- only turn in what you're asked to in Part 3! 



PART 1

As you saw in Assignment 2a, LISP is organized around the idea of
evaluating FORMS -- you type a form, and it gets evaluated and the
value returned to you.  For example, if you go into LISP and type

  (+ 2 3)

the value 5 comes back.  Recall that the list (+ 2 3) is interpreted
as a function call:  the first element of the list says what the
function is, and the remaining elements are the arguments passed to
that function.  The arguments can be forms themselves, in which case
they are evaluated first before getting passed to the function; for
example, evaluating the form

  (+ (- 6 4) (/ 9 3))

leads to the same result, because the first argument becomes the
result of evaluating (- 6 4) and the second argument becomes the
result of evaluating (/ 9 3).

Here are one or two new expressions we didn't try last time.
In LISP, set the variable mylist to contain the first 5 letters of the
alphabet:

  (setf mylist '(A B C D E))

Now, if you want to know if a particular symbol is on the list, you
can use the MEMBER function:

  (member 'Z mylist)

The value returned here, NIL, is equivalent to "false".  Notice,
interestingly, that when the symbol is in fact on the list,
what gets returned is not the symbol itself, but the entire rest of
the list following that symbol:

  (member 'C mylist)

Another useful form is the 'if' statement.  Like most programming
languages, LISP has a way of saying

  if 
  then  
  else  

Here's an example:

  (if (> 4 2)
      'YES
      'NO)

Remember that everything in LISP returns a value, so instead of DOING
something, you can look at the if statement as telling you to RETURN
something.  In this case, 4 is indeed greater than 2, so the symbol
YES is returned; you can turn > into < to get the opposite effect.
Notice that you can also negate the condition being tested in an "if"
statement (or, generally, any expression):

  (if (not (> 4 2))
      'YES
      'NO)

You can also omit the "else" part, if all you want is the "if":

  (if (not (> 4 2))
      'YES)

This is equivalent to saying that if the condition is true, 
you should return the symbol YES; otherwise the false value (NIL) will
be returned.

Putting all this together, suppose you want to print the value
'NOT-FOUND if the symbol 'D is absent from mylist, and otherwise not
do anything.  What would this statement look like?  Here it is:

  (if (not (member 'D mylist))
      (print 'NOT-FOUND))

Notice that "print" returns, as its value, the thing it printed, so
you'll see NOT-FOUND twice: once when it was printed, and once when
returned as the value of the if statement.


On to function definitions.  When you define a function in LISP, you
typically provide the function name, and a set of names for the
arguments -- these will be treated as local variables inside the
function definition.  For example, here is a simple function
definition:

  (defun add-them (x y)
    (+ x y))

This form has the effect of defining a function that takes two
arguments, which internally it will call x and y.  What's inside the
function definition gets evaluated with x and y BOUND to the arguments
that are passed in, and the result is passed back out as the value of
the function.  So, having defined the function as above (by typing it
into the LISP interpreter, same as anything else), you can call

  (add-them (+ 1 1) (- 7 4))

The variable x gets bound to the result of (+ 1 1) and the variable y
gets bound to the result of (- 7 4), so when (+ x y) gets called, 
x and y evaluate to 2 and 3, respectively, and the returned result is 5.

Get the idea?  Ok, here's another one:

  (defun add-first-and-second (list)
    (+ (first list) (second list)))

Call it:

  (add-first-and-second '(4 9 10 12 14))

Now let's do something more interesting.  We're going to use a
construct for ITERATION, that is, for repeating something over and
over.  Instead of typing what follows, you probably will want to copy
it into a file called, say, "maxval-1.lisp", and then do

  (load "maxval-1")

in order to load the function and work with it.

 ;;; ---- start copying at this line --------------------------------------

 (defun maxval-1 (number-list)

   (do 

    ;; THINGS TO DO BEFORE THE LOOP STARTS, INCLUDING DECLARING LOCAL VARIABLES
    ((current-maximum (first number-list))
     (num))

    ;; UNDER WHAT CONDITIONS TO STOP THE LOOP, AND WHAT TO RETURN WHEN DONE
    ((null number-list)
     current-maximum)

    ;; WHAT TO DO REPEATEDLY WHILE EXECUTING THE LOOP
    (setf num (pop number-list))
    (if (> num current-maximum)
	(setf current-maximum num))))      

 ;;; ---- stop copying at this line --------------------------------------

  
Ok.  At this point, either by copying and loading the function, or by
typing it in (you can ignore the lines that start with semicolons, by
the way, since they're ignored by LISP!), you should have function
maxval-1 defined.  Try it:

  (maxval-1 '(12 6 4 56 87 43))

Now let's look at what the function does.  The variable number-list
gets bound to the list argument you gave the function.  Then the 'do'
form is executed.  Notice there are 3 sections to a 'do' form.  First,
there's a list of local variable declarations.  The first declaration
on the list is 

   (current-maximum (first number-list))

which says to create a variable called current-maximum, and to give it
the value (first number-list).  Now, what is the value of 
(first number-list)?  You guessed it, that value is the first element
on the number-list.  So at this point, current-maximum was set
to the value 12.  The next variable declaration is

   (num)

This declares num to be a local variable, something that can be used
later in the program, but does not assign it an initial value;
therefore its initial value is NIL.

After the variable declarations, you have the second section of the
'do'; in here, you specify when you should stop the loop, and what
value should be returned from the loop when it stops.  In this case
the condition for stopping is (null number-list), which is true
when number-list is empty.  And the second thing in that list, what to
return when you're done, is current-maximum -- that is, when the loop
stops, you should return the value of that variable.

Finally, in the third section you have the things to do during the
loop, every time you go through it.  The first statement says to take
the next element off the front of number-list (also known as "popping"
it from the list; the list is behaving like a stack!), and assign it
as the value of variable num. Then there is an if statement: if the
first expression in the if statement is true, then the second thing
gets executed.  In this case, if num is greater than the value of
current-maximum, then current-maximum gets reset to the value of num.

That's the whole thing!  Take a look at the code again, and this time
work through by hand what happens when you call 

  (maxval-1 '(12 6 4 56 87 43))

First current-maximum gets set to (first number-list), which is 12.
Then you start looping.  Is (null number-list) true?  Nope,
number-list isn't empty.  So we pop 12 off number-list and give num
that value.  If 12 is greater than 12... no, it's not.  So we're done
with this run through the loop, and we go back to the top of the third
section.  Now the first element of number-list is 6, so we pop that
off and give num that value...  Try going through the program the rest
of the way like this, so you can see how the final value gets
returned!

Here's another kind of loop, illustrated using the same function.
Create a file called "maxval-2.lisp" containing the following:

 ;;; ---- start copying at this line --------------------------------------

 (defun maxval-2 (number-list)

   ;; Use 'let' to initialize current-max
   (let ((current-max (first number-list)))

     ;; Loop through each num in the number list
     (dolist (num number-list)
	     (if (> num current-max)
		 (setf current-max num)))

     ;; Return current-max when we're done
     current-max))

 ;;; ---- start copying at this line --------------------------------------

Load the file into LISP, and call

  (maxval-2 '(12 6 4 56 87 43))

Notice, of course, that you get the same value.  Here's what the
function does.  First, the 'let' form lets you set up an environment
containing a local variable, just like the first section of a 'do'
form.  So this function, like maxval-1, is setting up a local
environment with a variable called current-max, and setting the
initial value of current-max to be the first number on the list.

Now, instead of the general 'do', we use a special form called
'dolist', which is used to go through a list.  The 'dolist' form has
two sections.  The first section is just a list containing two
elements:  (1) the name of a variable, and (2) the list you want to go
through.  What's going to happen is that the variable is going to take
on each value in the list, in turn, and each time it takes a new one
of those values, all the statements in the second section of the
'dolist' will get executed -- in this case, just the 'if' statement.

For example, try the following in your LISP:

  (dolist (letter '(A B C D)) 
    (print letter))

First letter gets set to the symbol A, and the print statement gets
executed; then it gets set to B, and the print statement gets
executed; and so forth.  So using the 'dolist' construct inside the
function maxval-2 is a different way of having num loop through all
the numbers on the list.


PART 2:

Copy the following into a file called dfs.lisp (short for
"depth-first search").

 ;;; ---- start copying at this line --------------------------------------

 (defun get-outward-edges (node)
   "Returns a list of all edges coming out of the given node"
   (let ((edges (second (assoc 'Edges *graph*))))
     (remove-if #'(lambda (pair) (not (eq (first pair) node))) edges)))

 (defun search (start-node target)
   (do
    ;; THINGS TO DO BEFORE THE LOOP STARTS, INCLUDING DECLARING LOCAL VARIABLES
    ((possibilities (list start-node))
     (current-node))

    ;; UNDER WHAT CONDITIONS TO STOP THE LOOP, AND WHAT TO RETURN WHEN DONE
    ;; If the possibilities list is empty, we didn't find the target.
    ((null possibilities)
     'FAILURE)

    ;; WHAT TO DO REPEATEDLY WHILE EXECUTING THE LOOP
    (format t "~%~%Current possibilities: ~S, " possibilities)
    (setf current-node (pop possibilities))

    ;; If we've found the target, break out of the loop and accept.
    (format t " now exploring node ~A" current-node)
    (if (eq current-node target)
	(return 'SUCCESS))

    (dolist (pair (get-outward-edges current-node))
	    (push (second pair) possibilities))))

 ;;; ---- stop copying at this line --------------------------------------


Now copy the following into a file called graph-1.lisp.

 ;;; ---- start copying at this line --------------------------------------

 (setf *graph*
   '((Nodes (a b c d e f g))
     (Edges ((a c) (a b) (b e) (c d) (c e) (d f) (e f) (e g)))))

 ;;; ---- stop copying at this line --------------------------------------

Go into LISP, and do

  (load "dfs")
  (load "graph-1")

This program defines a depth-first search over a graph.  To run it,
you call (search start-node target), for example:

  (search 'A 'G)

Go ahead and try it.  For our purposes here, you can ignore the
function get-outward-edges; let's focus on the search function.  As
you can see, it mainly uses a do loop, just like the one we talked
about.  

  (i) In the first section of the do construct, it initializes the
  possibilities list to contain just the start node.  

  (ii) In the second section, it says that the loop should stop when the
  possibilities list is empty, and in that case, the value returned
  should be the symbol FAILURE.

  (iii) In the third section, it sets the current-node variable to the first
  thing on the possibilities list -- this is where the search is
  exploring right now.  If the value of current-node is equal to the
  name of the target node, then we can break out of the loop by
  returning the value SUCCESS.  Otherwise we get the list of 
  outward-directed edges from this node (that list is returned by
  the get-outward-edges function).  What we want to do is go through
  each of the edges on that list, and add the destination of that
  edge to the possibilities list.  This is easily done using the
  'dolist' construct:  we set the variable "pair" to each edge
  in turn.  (Why call it "pair"?  Well, an edge is represented
  as a pair of nodes symbols.)  Then we add the destination node
  (which is the second symbol in the pair) to the possibilities list.
  These will become other places to search, as we go back to the top 
  of the third section to begin iterating through the loop again.

Try some more searches -- for example,

   (search 'C 'B)

and work through step by step, making sure you understand why the
search is progressing the way it is.


PART 3

Ok, here's the "assignment" part of this assignment, finally.  It's
just to get you doing a little bit of LISP programming based on what
you've seen so far.

First, copy file dfs.lisp into a new file, dfs-2.lisp.  

Second, create a new file, graph-2.lisp, that contains the following:

 ;;; ---- start copying at this line --------------------------------------

 (setf *graph*
   '((Nodes (a b c d e f g))
     (Edges ((a c) (a b) (b e) (c d) (c e) (d f) (d a) (e f) (e g)))))

 ;;; ---- stop copying at this line --------------------------------------


TO TURN IN:

  Problem 3a.1 [10 points]

    Draw the graph in graph-2.lisp.  What might happen if you
    load it and call (search 'a 'f)?  Before you try, note
    that to interrupt a program while it's executing, you type
    control-c  -- that is, you hold the control key down like
    a shift key and then press c.  In fact, let me recommend that 
    you DON'T try at all using the computer:  work it out in 
    terms of what you know about the behavior of the program.

  Problem 3a.2 [20 points]

    Here's one way to stop what happens from happening.  

     1.  In the first section of the do loop, create a new
	 variable called visited, with no initial value.

     2.  In the third section of the loop, after you've popped
	 the current-node value from the possibilities list,
	 add that current-node to the "visited" list.  (If you're
	 not sure how to add a symbol to a list, see the end of
	 iii, above.)

     3.  In the dolist statement, instead of just blindly pushing
	 the destination node onto the possibilities list, first
	 make sure that it hasn't already been visited; that is,
	 that it's not already on the visited list.  (You can
	 do this by using an 'if' statement in the second part of the
	 dolist.)

    Turn in a listing of the revised dfs-2.lisp and a dribble
    of it running 

	(search 'a 'f)
	(search 'c 'a)