Homework 11b

home work!

Programming Language #lang htdp/asl



Due Date Thurs at 9:00pm (Week 11)

Purpose Practice with mutable state!


In this assignment, we will be using the Advanced Student Language (ASL) to experiment with mutable state. In order to use checked signatures for boxed values, please include the following snippet at the start of your assignment:

(require deinprogramm/signature/signature)
(define (BoxOf T)
  (signature (predicate (lambda (v) (and (box? v) (not (false? (apply-signature T (unbox v)))))))))

Unlike previous autograded assignments, we will not be using wheats and chaffs to assess submitted test suites. Instead, this homework consists of a variety of puzzle-like exercises with relatively straightforward testing procedures described below.

Exercise 1 In this problem, we want you to identify the difference between two very similar functions that have the same signature (note that both make-incrementer-n functions are zero-argument functions, which are now allowed in ASL):

(: make-incrementer-1 (-> (Number -> Number)))
(define make-incrementer-1
  (let ([mem (box 0)])
    (lambda ()
      (lambda (inc)
          (set-box! mem (+ inc (unbox mem)))
          (unbox mem))))))
(: make-incrementer-2 (-> (Number -> Number)))
(define make-incrementer-2
  (lambda ()
    (let ([mem (box 0)])
      (lambda (inc)
          (set-box! mem (+ inc (unbox mem)))
          (unbox mem))))))

Your task is to implement a function incrementer-distinguish which should take a function with the above signature as input and use it in some way to produce a number:

(: incrementer-distinguish ((-> (Number -> Number)) -> Number))

Specifically, we want your distinguisher to use its input in such a way to produce different results when passed the two functions above. When thinking about the differences between the incrementer functions, it may be useful to try to write (distinct) purpose statements for them. Once you find a difference and write your distinguisher, you should expose it with a test like this:

(check-expect (not (equal? (incrementer-distinguish make-incrementer-1)
                           (incrementer-distinguish make-incrementer-2)))

Your distinguisher should not call either make-incrementer function directly; it should only be calling the function that is passed in (which will be an incrementer function, for the test case we care about above).

Exercise 2 In this exercise, we want you to fix a bug in the following code:

(: box-magic ([BoxOf Number] [BoxOf Number] -> [ListOf Number]))
; increments each input by 1, producing a list of their unboxed outputs
(define (box-magic b1 b2)
  (begin (set-box! b1 (add1 (unbox b1)))
         (set-box! b2 (add1 (unbox b2)))
         (list (unbox b1) (unbox b2))))

What is the bug? Well, there are certain inputs to this function that produce unexpected results. In particular, we would expect that for any B1 and B2, the following test would pass:

(check-expect (box-magic B1 B2)
              (list (add1 (unbox B1)) (add1 (unbox B2))))

But it doesn’t. Identify what’s wrong and write a test case that fails with the given implementation. Then, update the function to fix the issue; your previously-broken test case should now pass. Note: the updated implementation must still mutate the contents of the passed boxes, to abide by the purpose statement of box-magic, which now contains information about the side effects of the function.

Exercise 3 In this exercise, you will be again writing a function muter-distinguish that, when passed the following two very similar pieces of code, should produce different results.

(: muter-1 ([BoxOf Number] -> Number))
(define (muter-1 v)
  (local [(define the-v v)]
    (begin (set-box! the-v (add1 (unbox the-v)))
           (unbox the-v))))
(: muter-2 ([BoxOf Number] -> Number))
(define (muter-2 v)
  (local [(define the-v v)]
    (begin (set! the-v (box (add1 (unbox the-v))))
           (unbox the-v))))

i.e., you would like the following test to pass, similar to the distinguisher above:

(check-expect (not (equal? (muter-distinguish muter-1) (muter-distinguish muter-2))) #t)

Exercise 4 In this problem, you should write caller-distinguish that, like previous problems, can differentiate between the following two functions:

(: fn-caller-1 ((Number -> Number) (Number -> Number) -> Number))
(define (fn-caller-1 f1 f2)
  (+ (f1 1) (f2 1)))o
(: fn-caller-2 ((Number -> Number) (Number -> Number) -> Number))
(define (fn-caller-2 f1 f2)
  (+ (f2 1) (f1 1)))

i.e., you want the following test to pass:

(check-expect (not (equal? (caller-distinguish fn-caller-1)
                           (caller-distinguish fn-caller-2)))

Exercise 5 This function is similar to the previous one; please name your distinguisher caller-alt-distinguish, which should be able to detect differences between the following two functions:

(: fn-caller-alt-1 ((Number -> Number) -> Number))
(define (fn-caller-alt-1 f)
  (+ (f 1) (f 1)))
(: fn-caller-alt-2 ((Number -> Number) -> Number))
(define (fn-caller-alt-2 f)
  (let [(x (f 1))]
    (+ x x)))

i.e., make the following test pass:

(check-expect (not (equal? (caller-alt-distinguish fn-caller-alt-1)
                           (caller-alt-distinguish fn-caller-alt-2)))

Exercise 6 Consider the following code:

(: multi-update ([BoxOf Number] [BoxOf Number] (Number -> Number) [ListOf [BoxOf Number]] -> (predicate void?)))
; given two indices, transform the values of the corresponding cells in the list using the given function
; assumes indices are within bounds, and it will error if they are the same.
; i.e., if the two indices were i & j, and the list were ... vi ... vj ... (all values boxed) then the
; resulting list should be ... (f vi) ... (f vj) ... (note, of course, the i does not have to be less than j).
(define (multi-update-buggy i1 i2 f l)
  (if (= (unbox i1) (unbox i2))
      (error "Must pass different indices")
      (begin (set-box! (list-ref l (unbox i1)) (f (unbox (list-ref l (unbox i1)))))
                (set-box! (list-ref l (unbox i2)) (f (unbox (list-ref l (unbox i2))))))))

This function is intended to update two indices in a list. Since, in this HW, we are modelling languages where everything is mutable, we pass the indices as boxed values and also, the values inside the list are all boxed.

We claim that this function is buggy. Your first task is to figure out how; easiest done by writing code that shows it violating its purpose.

Now that you’ve identified the problem, fix the code for multi-update. Your fixed code should no longer pass whatever test you wrote that exposed buggy behavior (you should invert the test to show that the function now does the right thing).