14 Homework 9B

Due:

Thursday, 3/14 at 9PM

This assignment is SOLO, and entirely AUTOGRADED.

What to Download:

hw9b.rkt

Please start with this file, filling in where appropriate, and submit your homework to the HW9B assignment on Gradescope. This page has additional information, and allows us to format things nicely.

14.1 Problem 1

In this problem, we have two implementations of a "counter": make-counter-1 and make-counter-2. Each is a single argument function that, when called, produces a single argument function. The function that is produced, the counter, takes a number as input and adds that to a running current sum. Each time the counter is called, it returns the current value of the sum. These could be used to keep track of a count within a larger software system.

For example:

(define counter (make-counter-2)) (counter 1) ; outputs 1 (counter 5) ; outputs 6 (counter 2) ; outputs 8

They are not, however, identical. Your task is to write a function, counter-distinguish, which should produce different results when called with make-counter-1 as an argument vs. when called with make-counter-2 as an argument. Note, you pass the function to create the counter (i.e., make-counter-1, make-counter-2), not a counter itself (i.e., counter in the example above). You do not need to worry about your function working when invoked with any other arguments.

If your function works, the following test should pass:

(check-expect (not (equal? (counter-distinguish make-counter-1)

(counter-distinguish make-counter-2)))

#t)

Note: your code should not call either make-counter-n function within its body. It will be passed one of them as an argument, but will have no way of knowing which one.

14.2 Problem 2

Sometimes batching operations can speed things up. In this case, we simulate this by creating a function, fast-incr, that increments two counter structs (defined for Problem 1) at once, and then returns the sum of their new count.

We would expect the following property to hold; i.e., that after incrementing them both, the new sum would be two higher than previously.

This turns out not always to be the case. Define a function, fast-incr-exercise, that calls fast-incr with inputs that cause it to violate this property. Your function should create the appropriate inputs to fast-incr; it can return the output of fast-incr, or any other Natural.

Note: your function should not call, or use in any way, fast-incr-prop: that code is just provided as a reference for what should hold of how you are invoking fast-incr. The call to fast-incr should be internal to fast-incr-exercise. You can, however, use fast-incr-prop to help figure out what to do: call it with different arguments until you find something that causes it to fail. Those are the arguments you should pass to fast-incr within your fast-incr-exercise.

14.3 Problem 3

In this problem, we give the same code as fast-incr, but call it fast-incr-fixed. Why? Because we want you to give it a signature (using Function) that ensures that inputs that cause it to violate fast-incr-prop will not be allowed by the signature. i.e., if you run the code from your fast-incr-exercise (changing fast-incr to fast-incr-fixed), you would get a contract violation.

14.4 Problem 4

Consider the following redefining of lists:

This has the exact same shape as a normal list, so we can define a length function as follows:

However, there is a problem. There are some inputs for which mlength, despite following structural recursion, will run forever. Think about how that could be, and then define a contract using Record that ensures that it does not run forever, instead producing a contract violation when handed inputs for which there is not a finite answer.

Note: do not change the code, only the contract.

Hint: in addition to mlength running forever, the contract MList will also run forever on the same inputs, as it checks the entire list. When you fix the contract, it’s okay to just remove that check (i.e., replace MList with Any, or just remove it if you have (AllOf Any ...)).