;; Lab 6 Solutions ;; tester statements commented out ;; CMPU 145, Spring 2019 ;; A few list-based natural numbers... (define nn0 '()) (define nn1 '(1)) (define nn2 '(1 1)) (define nn3 '(1 1 1)) (define nn4 '(1 1 1 1)) (define nn5 '(1 1 1 1 1)) ;;(tester 'nn0) ;;(tester 'nn1) ;;(tester 'nn2) ;;(tester 'nn3) ;;(problem "1. Make numbers with NN-SUCC and MAKE-NN") ;; NN-SUCC ;; ------- ;; INPUT: N, a natural number represented by a list of ones ;; OUTPUT: The successor to N, also represented by a list of ones (define nn-succ (lambda (n) (cons 1 n))) ;;(tester '(nn-succ nn0)) ;;(tester '(nn-succ nn1)) ;;(tester '(nn-succ nn3)) ;;(tester '(nn-succ '(1 1))) ;;(tester '(nn-succ '(1 1 1 1 1))) ;; MAKE-NN ;; ------- ;; INPUT: N, an ordinary natural number ;; OUTPUT: The corresponding list of ones ;; EXAMPLE: (make-nn 5) ==> (1 1 1 1 1) (define make-nn (lambda (n) (if (zero? n) ;; Base Case: Return "zero" (i.e., the empty-list) nn0 ;; Recursive Case: Return the "successor" of "n-1" ;; Notice the use of the previously defined NN-SUCC and MAKE-NN. (nn-succ (make-nn (- n 1)))))) ;;(tester '(make-nn 5)) ;;(tester '(make-nn 20)) ;;(problem "2. NN-ZERO? and NN-PRED aliases") ;; NN-ZERO? ;; -------- ;; INPUT: A natural number represented by a list of ones ;; OUTPUT: #t if that natural number is nn0 (i.e., '()). (define nn-zero? null?) ;;(tester '(nn-zero? nn0)) ;;(tester '(nn-zero? (make-nn 5))) ;;(tester '(nn-zero? '())) ;;(tester '(nn-zero? '(1 1 1 1))) ;; NN-PRED ;; ------- ;; INPUT: NN, a natural number represented by a list of ones ;; OUTPUT: The predecessor of NN, also rep'd by a list of ones (define nn-pred rest) ;;(tester '(nn-pred '(1 1 1 1 1))) ;;(tester '(nn-pred '(1))) ;;(problem "3. Addition of Natural Numbers") ;; NN-ADDN ;; ------- ;; INPUTS: X, Y, natural numbers represented by a list of ones ;; OUTPUT: The natural number, X+Y, also represented by a list of ones ;; ;; Notice that it is defined in terms of the functions NN-ZERO?, ;; NN-SUCC and NN-PRED, which are defined above. (define nn-addn (lambda (x y) (if (nn-zero? y) ;; Base case: Y = 0 ;; Thus X+Y = X x ;; Recursive case: Y = SUCC of some K ;; So, X + Y = X + SUCC(K) = SUCC (X + K) ;; Where K is represented by (NN-PRED Y) (nn-succ (nn-addn x (nn-pred y)))))) ;;(tester '(nn-addn '(1 1 1) '(1 1))) ;;(tester '(nn-addn nn5 nn4)) ;;(problem "4. Multiplication of Natural Numbers") ;; NN-MULT ;; ------- ;; INPUTS: NNX, NNY, two natural numbers represented as lists of ones ;; OUTPUT: The product of NNX and NNY represented as a list of ones ;; ;; Uses the following rules: ;; x * 0 = 0 ;; x * S(y) = (x * y) + x (define nn-mult (lambda (x y) (if (nn-zero? y) ;; Base case: Y = 0 nn0 ;; Recursive case: Y = SUCC of some K (nn-addn (nn-mult x (nn-pred y)) x)))) ;;(tester '(nn-mult nn2 nn3)) ;;(tester '(nn-mult nn0 nn4)) ;;(tester '(nn-mult nn4 nn0)) ;;(tester '(nn-mult nn3 nn4)) ;;(problem "5. Testing properties of NN-ADDN and NN-MULT") ;;(printf "Testing commutativity of NN-ADDN~%") ;;(tester '(equal? (nn-addn nn2 nn4) ;; (nn-addn nn4 nn2))) ;;(tester '(equal? (nn-addn nn3 nn0) ;; (nn-addn nn0 nn3))) ;;(printf "~%Testing associativity of NN-ADDN~%") ;;(tester '(equal? (nn-addn nn2 (nn-addn nn3 nn4)) ;; (nn-addn (nn-addn nn2 nn3) nn4))) ;;(tester '(equal? (nn-addn nn4 (nn-addn nn3 nn5)) ;; (nn-addn (nn-addn nn4 nn3) nn5))) ;;(printf "~%Testing commutativity of NN-MULT~%") ;;(tester '(equal? (nn-mult nn2 nn3) ;; (nn-mult nn3 nn2))) ;;(tester '(equal? (nn-mult nn3 nn4) ;; (nn-mult nn4 nn3))) ;;(printf "~%Testing that nn1 is a multiplicative identity~%") ;;(tester '(equal? (nn-mult nn3 nn1) ;; nn3)) ;;(tester '(equal? (nn-mult nn1 nn3) ;; nn3))