CMPU-145, Spring
Lab 5
March 4, 2013

In this lab, you will represent the natural numbers using lists of the
form: (), (1), (1 1), (1 1 1), (1 1 1 1), etc.
    

a.  Define several global variables: nn0, nn1, nn2, ..., nn5, where nn0
    evaluates to (), nn1 evaluates to (1), nn2 evaluates to (1 1), nn3
    evaluates to (1 1 1), etc.  These will be used for testing
    purposes later on.  

      > nn0
      ()
      > nn1
      (1)
      > nn2
      (1 1)
      > nn3
      (1 1 1)


b.  Define the successor function, NN-SUCC, for this representation
    of natural numbers.  Its behavior is illustrated below:

      > (nn-succ nn0)
      (1) 
      > (nn-succ nn1)
      (1 1)
      > (nn-succ nn3)
      (1 1 1 1)
      > (nn-succ '(1 1))
      (1 1 1)
      > (nn-succ ())
      (1)


c.  Define a function, called MAKE-NN, that takes an "ordinary" number
    as its input, and returns as its output the corresponding list-based
    natural number, as illustrated below:

      > (make-nn 3)
      (1 1 1)
      > (make-nn 6)
      (1 1 1 1 1 1)

    NOTE:  In the base case, use NN0, not ().  Even though they are
             equal, it's better from a design standpoint to use the
             "constructors" for natural numbers when creating new
             natural numbers.  That way, if we were later to change
             the underlying representation, we would simply change the
             value of NN0, and wouldn't have to change every place
             it's used.
	 
           Simiarly, in the recursive case, use NN-SUCC to create the
             successor of the thing returned by the recursive function
             call.

     
d. Define a function, called NN-ZERO?, that takes a list-based natural
    number as its input.  It should return #t if that input is the
    list-based version of zero; otherwise, #f.

      > (nn-zero? nn0)
      #t
      > (nn-zero? ()) 
      #t
      > (nn-zero? nn3)
      #f
      > (nn-zero? '(1 1 1))
      #f

    HINT:  Just define an abbreviation for one of the built-in functions!              

e.  Define a function, called NN-PRED, that implements the "predecessor"
    function.  It should take a list-based natural number as its input
    and return that number's predecessor, as illustrated below:

      > (nn-pred nn4)
      (1 1 1)
      > (nn-pred '(1 1 1 1))
      (1 1 1)

    HINT:  Just define an abbreviation for one of the built-in functions!


f.  Define a function, called NN-ADDN, that takes two list-based natural
    numbers as its input, and generates their sum as its output, as 
    illustrated below:

      > (nn-addn nn1 nn4)
      (1 1 1 1 1)
      > (nn-addn nn3 nn3)
      (1 1 1 1 1 1)
      
    NOTE:  Do *NOT* use the built-in APPEND function or any other such
           function. Instead, your implementation should mimic the
           following definition from the natural numbers handout.

              x + 0  = x          Base Case

              x + Sy = S(x + y)   Recursive Case

           In other words, the recursion is being driven by the second
           input.  If the second input is zero, do one thing...  Oh,
           and use the NN-ZERO? function to determine whether you're
           in the base case.

           For the recursive case, it may help to rewrite the above
           rule as follows, where Sy is replaced by q:

              x + q = S(x + PRED(q))

           That is:  x + q = the successor of (x plus the predecessor of q).

           You should use the previously defined functions, NN-SUCC and
           NN-PRED, as well as the recursive function call of NN-ADDN,
           to achieve the desired result.

Remember to test all of your functions using TESTER!

=================

  When you are finished, ask me or one of the coaches to come over
  to check your work.  Also, be sure to save your work and submit
  it using the submit145 command.