Lab 7 Instructions
CMPU 145, Spring 2019.

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

There's alot to read, but a bit (!) less for you to code. 
When we want to test a property, it can be helpful to run randomized
simulations and examine the results. Racket has a built-in RANDOM function
which takes a natural number K as its argument and generates a random
integer in the range 0 to K-1:

    > (random 1)
    0  ;; This will always be 0. Why?
    > (random 2)
    1
    > (random 2)
    1
    > (random 2)
    1  ;; Is this thing stuck?
    > (random 2)
    0  ;; Good.
    > (random 1000)
    14 ;; That's so random.

We can use RANDOM to define different types of generator functions, e.g.,
to toss a 6-sided die:

    (define toss-die
      (lambda ()
        (+ 1 (random 6))))

    > (toss-die)
    3

And we can define a test that a particular instance (e.g., a toss of the
die) might satisfy or not:

    ;; A function that tests whether a given value is a 5 or 6.
    (define test-die
      (lambda (die)
        (or (= die 5) (= die 6))))

To generate multiple random outcomes and test what percent satisfy a given
test, we can define the function GEN-AND-TEST (i.e., generate-and-test):

    (define gen-and-test
      (lambda (n gen test [print #f])
        ;; COUNT is a counter variable
        (let ((count 0))
          ;; FOR executes its body N times
          (for ((i n))
            ;; Use (GEN) to generate a random instance;
            ;; Use TEST to determine whether that instance has the
            ;; desired property
            (let* ((rnd (gen))
                   (result (test rnd)))
                (when print
                   (printf "[~A: ~A] " rnd result))
                (when result
                   ;; If it does, then destructively increment the counter!
                   (set! count (+ count 1)))))
          ;; After the FOR loop finishes, return the fraction of the
          ;; trials that satisfied the TEST.
          (/ count n 1.0))))

It takes three inputs:
- N, the number of random trials to perform
- GEN, a function (of zero inputs) that generates random instances of some
  event (e.g., toss of a die; dealing of a hand of cards)
- TEST, a function that tests whether a given instance satisfies some
  property (e.g., whether die is greater than 4; or a hand of cards
  contains three-of-a-kind)
- PRINT, an optional argument that says to print each random value and
  the rest outcome. Don't make this true for large numbers of trials!

It uses the special FOR construct to run N random trials. In each trial,
GEN is used to generate a random instance of some event, and TEST is used
to determine whether that random instance satisfied some property. A
counter is used to keep track of how many random instances satisfied the
property. The percent of random instances that did satisfy the property
is returned at the end.

Here's how we can use GEN-AND-TEST to simulate the repeated tossing of
a single die, returning the fraction of times the tossed die was a five or
six:

    > (gen-and-test 10 toss-die test-die #t)
    [3: #f] [6: #t] [5: #t] [5: #t] [5: #t] [4: #f] [5: #t] [4: #f] [6: #t]
    [3: #f] 0.6

If we want to simulating 1000 tosses of a single die, let's not print them
all!

    > (gen-and-test 1000 toss-die test-die)
    0.151
    > (gen-and-test 1000 toss-die test-die)
    0.172

Note: In your definitions file, you can embed a call to GEN-AND-TEST
inside a TESTER expression.


Problem 1
---------

Define a function, called TOSS-PAIR-DICE, that takes zero inputs. When
called, it should return as its output a list of two values, each
representing the toss of a single die:

    > (toss-pair-dice)
    (1 3)
    > (toss-pair-dice)
    (5 2)

Next, define a function, called TEST-PAIR-DICE, that takes a list of
two dice values as its only input. It should return #t if the sum of
the two dice is 8 or more.

    > (test-pair-dice '(3 4))
    #f
    > (test-pair-dice '(4 5))
    #t

Finally, use GEN-AND-TEST to simulate 10,000 tossings of a pair of dice.
It should return the fraction of tossings that resulted in a sum of 8 or
more.


Problem 2
---------

In the previous lab, we represented natural numbers as lists of 1s,
used this representation to implement recursive definitions of addition
and multiplication, and tested that these definitions obeyed matched
expected properties of commutativity and associativity.

Now we can run simulations to check that properties hold for a variety of
inputs. Here's an example:

    Claim 1: 0 + x = x for all natural numbers x.

To test this claim, we can define generator and test functions and run
GEN-AND-TEST:

    ;; Generate a natural number between 0 and 99, represented as a
    ;; list of 1s
    (define random-nn
      (lambda ()
        (make-nn (random 100))))

    (define test-claim1
      (lambda (nn)
        (equal? (nn-addn nn0 nn)
                nn)))

    > (gen-and-test 10 random-nn test-claim1)
    1.0

Thankfully, it holds for 100% of the simulations!
Does this, by itself prove that the claim is true?


Recall this property:

    Claim 2: x + S(y) = S(x) + y for all natural numbers x and y

Define a generator function, RANDOM-NN-PAIR, that generates two (possibly
different) random numbers from 0-99 as lists of 1s, and a test function,
TEST-CLAIM2. Run GEN-AND-TEST to verify this claim holds for random
examples, trying inputs of at least 20.

----

When you are done, ask me or one of the coaches to check over your work.
Also, submit electronically as usual:

    submit145 lab7 <your-directory>