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