Homework 11b

^^^ THIS HAS CHANGED. YOU NEED ASL! ^^^

MUST BE DONE SOLO

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

Purpose Practice with mutable state!

Exercises

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)

(begin

(set-box! mem (+ inc (unbox mem)))

(unbox mem))))))

(: make-incrementer-2 (-> (Number -> Number)))

(define make-incrementer-2

(lambda ()

(let ([mem (box 0)])

(lambda (inc)

(begin

(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)))

#t)

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)))

#t)

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)))

#t)