UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ Lab 4

# Questions from last time

Time
10 Minutes
Activity
Group discussion
• The programming languages we will study this term are all dynamically typed. This means that not only the value but also the type of variables can change at runtime. Why does this make testing even more important?

• What kind of software problems is testing not well suited to find?

• Why might mutable state (e.g. instance variables in Java) make writing unit tests harder?

# Setup

• make a directory labs/L04 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

# Simulating Natural Numbers I

Time
30 minutes
Activity
Individual work
Summary

Write the times function from Exercise 11 in FICS. You can (and should) use the following code from the linked discussion

#lang htdp/bsl
(define-struct Z ())
(define-struct S (pred))
(define (pred nat)
(cond
[(Z? nat) (error "can't apply pred to Z")]
[(S? nat) (S-pred nat)]))

(define (plus nat1 nat2)
(cond
[(Z? nat1) nat2]
[(S? nat1) (make-S (plus (S-pred nat1) nat2))]))

Here is the template for structural recursion on (simulated) natural numbers. See the linked text (or the plus function just above) for how to add a second "carried-along" parameter.

(define (my-nat-fn nat)
(cond
[(Z? nat) ...]
[(S? nat) ... (my-nat-fn (S-pred nat)) ...]))

Here are some tests to get you started. As always, try to have complete test coverage.

;; 0 * 0 = 0
(check-expect (times (make-Z) (make-Z)) (make-Z))
;; 0 * 1 = 0
(check-expect (times (make-Z) (make-S (make-Z))) (make-Z))
;; 2 * 1 = 2
(check-expect (times (make-S (make-S (make-Z)))
(make-S (make-Z)))
(make-S (make-S (make-Z))))

You may find it helpful to refer back to your solution from L03.

# Simulating Natural Numbers II

Time
30 minutes
Activity
Individual work
Summary

Write the compare function from Exercise 11 in FICS. Your function compare should use the struct definitions Z and S, and pass the following tests

;; 0 = 0
(check-expect (compare (make-Z) (make-Z)) 'equal)
;; 0 < 1
(check-expect (compare (make-Z) (make-S (make-Z))) 'less)
;; 1 > 0
(check-expect (compare (make-S (make-Z)) (make-Z)) 'greater)
;; 2 > 1
(check-expect (compare (make-S (make-S (make-Z)))
(make-S (make-Z))) 'greater)

# Structural recursion, on numbers

Time
20 minutes
Activity
Individual work
Summary

Use structural (note that structural here is only indirectly related to Racket structs) recursion on natural numbers (not the simulated ones from above, but regular Racket numbers like 1, 42, and 1337) to define a function (sum-factors n max-factor) that sums all factors of n (including 1) no larger than max-factor

Recall the template for structural recursion on natural numbers:

(define (my-nat-fn n)
(cond
[(zero? n) ...]
[(positive? n) ... (my-nat-fn (sub1 n)) ...]))

Try to use only one recursive call to sum-factors like in the template. Keep in mind that the n in the template might be a different parameter of your function. You can use the builtin function remainder to test for divisibility.

The following tests should pass

;; 1+2+3 = 6
(check-expect (sum-factors 6 5) 6)
;; 1+2+4+7+14 = 28
(check-expect (sum-factors 28 27) 28)