Lab 6 Instructions
CMPU 145, Spring, 2019

Introduction
------------

In class, we've discussed a recursive definition of the natural numbers,
where every natural number was either 0 or the successor of a natural
number. In this lab, you will represent the natural numbers using a
related idea: Numbers will be expressed as lists of the form (), (1), (1 1),
(1 1 1), (1 1 1 1), etc.


Problem 0
---------

Define global variables nn0, nn1, nn2, nn3, nn4, and 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. Super easy; in fact this has already been added to the template file.

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


Problem 1
---------

a. Define the successor function, NN-SUCC, for this representation of natural
numbers. This is the naming convention that Professor Hunsburger used in the
handout fromm last week. 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)

b. Use NN-SUCC to 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)


Problem 2
---------

Hint: These should be one-line definitions providing aliases for built-in
functions!

a. 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 and #f otherwise.

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

b. 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)


Problem 3
---------

Use the previously defined functions NN-PRED, NN-SUCC, and NN-ZERO? to
define NN-ADDN, a function 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)

Your implementation should follow the recursive definition from Section 3
of the handout "The Natural Numbers, Induction, and Numeric Recursion":

    x + 0  = x               Base case
    x + S(y) = S(x + y)      Recursive case

It may help to rewrite the recursive case as
    x + q = S(x + PRED(q))
That is: x + q = the successor of (x plus the predecessor of q).

All you really need are the functions you've already defined.


Problem 4
---------

Define a multiplication function that implements the recursive definition
we've seen in class:

    x * 0 = 0                Base case
    x * S(k) = (x * k) + x   Recursive case

Here are some examples:

    > (nn-mult nn2 nn3)
    (1 1 1 1 1 1)
    > (nn-mult nn3 nn4)
    (1 1 1 1 1 1 1 1 1 1 1 1)

To compute the product of X and Y in Racket, we can rewrite these
rules as:

- If Y is zero, then the answer is zero
- Otherwise, Y is SUCC(K) for some K (i.e., K is the predecessor of
  Y) and the answer is (X * K) + X

The contract for this function is given in the template file.

As above, do not use any built-in functions; only NN-ZERO?, NN-SUCC,
NN-PRED, NN-ADDN and the constant NN0.

(This means that we could change the underlying representation of numbers
and our NN-ADDN and NN-MULT functions would still work!)


Problem 5
---------

For this problem, we will just check that the NN-ADDN and NN-MULT
functions have the properties we expect. In the template file you've been
given tester statements that you should uncomment.

Verify for your functions that
- NN-ADDN is commutative,
  i.e., for all natural numbers x and y:
      x + y = y + x

- NN-ADDN is associative,
  i.e., for all natural numbers x, y, and z:
      x + (y + z) = (x + y) + z

- NN-MULT is commutative,
  i.e., for all natural numbers x and y:
      x * y = y * x

- NN1 is a multiplicative identity for NN-MULT,
  i.e., for all natural numbers x:
      x * 1 = x
  and by commutativity of NN-MULT:
      1 * x = x

Be sure you understand these properties!


----

Remember to test all of your functions.

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

    submit145 lab6 <your directory>