### Homework 7a

Due Date Tues at 9:00pm (Week 7)

MUST BE DONE WITH YOUR PARTNER

Purpose Explore Lambda

Exercises

Choosers and Repeaters

Challenge! Can you think of any possible other functions that have exactly this signature? Why or why not?

Exercise 1 Define the two shortest functions that have this signature (as in, literally the fewest non-whitespace characters you can manage). The functions are restricted to only use λ expressions and variables. These will be our Choosers.

In a comment, explain what these two functions do, and why we called this data definition a “chooser.”

Exercise 2 There are exactly two functions with this precise signature, and we would like to test them, but we can’t directly check-expect functions. One obvious way to do this is to simply call both functions and see what their outputs are, but there’s another approach to take here which will be more interesting: Design an chooser->boolean function, which will convert from an Chooser to an ISL boolean (#true or #false), such that the two functions you defined above produce different boolean results. Note: there are two (correct) ways of doing this! (In this problem, you are obviously also allowed to use #true and #false).

If we have a one-to-one correspondence between Choosers and Booleans, perhaps we could define functions operating on Choosers akin to how existing ISL functions operate on Booleans...?

For the following three functions, besides define and λ, your function definitions should not use any ISL-provided functions or keywords (and certainly not chooser->boolean, #true or #false).

Exercise 3 Design and/alt, which functions analogusly to and, but takes in two Choosers and outputs an Chooser. By “analogously to and”, we mean, in particular, that if you take two Choosers, convert them using chooser->boolean, and then call and on them, you should get the same result as calling and/alt first and then using chooser->boolean on the single resulting Chooser. You do not need to consider short-circuiting here.

Exercise 4 Design or/alt, which functions analogusly to or, but takes in two Choosers and outputs an Chooser.

Exercise 5 Design not/alt, which functions analogusly to not, but takes in one Chooser and outputs an Chooser.

Repeat After Me

Exercise 6 Design the function two that takes a function with signature {X} [X -> X] as input and returns another function that applies f twice in a row. That is, two returns a function which first applies f to its input, then applies f again to the output of the first application (all within one function call).

Exercise 7 Design the function three, similarly, that applies a function f three times in a row.

Exercise 8 Design the functions one and zero. Writing one is easy, but what about zero? What does it mean to apply a function to its argument zero times?

The functions zero, one, two, and three look curiously similar to numbers: all they do is repeat their input some number of times. Let’s call functions like these Repeaters:

Exercise 9 Design a function rep->nat which consumes a Repeater as input and produces the number of times it repeats its argument. This function is allowed to use the add1 function, 0, in addition to lambdas, variables and application.

Here are some tests:

(check-expect (rep->nat zero) 0) (check-expect (rep->nat one) 1) (check-expect (rep->nat two) 2) (check-expect (rep->nat three) 3) (check-expect (rep->nat (λ (f) (λ (x) ((three f) ((two f) x))))) 5) (You should spend a few minutes trying to read that last example expression out loud, to convince yourself that it makes sense. Figure out how that starting (λ (f) (λ (x) ...)) matches with the data definition. Figure out what the subexpressions (three f) or (two f) mean, and then try to put all the pieces together.)

Recall from class when we introduced local, that we defined maximum, largest and biggest: they all computed the same answer as each other on any possible input, but took dramatically different time to do so! Would you consider those functions to be “equal”?

Hint: You cannot directly check-expect that one function is “equal” to another function. All you can check is whether two functions behave the same way and produce the same outputs when given the same inputs. So if you have a Repeater, all you can do is give it some inputs and see what it gives you back. So your task here is simply to devise some inputs that will force it to tell you which number it represents.Note: You should use this function only for debugging or for test cases; do not use it to implement any of the functions below.

Exercise 10 Design the function rep-add1 that increments a Repeater by 1. Remember, do not use rep->nat; you don’t need it!

Exercise 11 Design the function nat->rep that converts a Nat n to the Repeater that repeats its input n times. This function may use recursion and basic functions from ISL (e.g., zero?, sub1).

Exercise 12 Design the function rep+, that takes two Repeaters and produces a new Repeater that represents their sum. Remember, do not use rep->nat; you don’t need it!

Exercise 13 Design the function rep*, that takes two Repeaters and produces a new Repeater that represents their product. Remember, do not use rep->nat or rep+; you don’t need them!

Exercise 14 Design the function rep^, that takes two Repeaters and produces a new Repeater that represents the first raised to the power of the second. Remember, do not use rep->nat, rep+, or rep*; you don’t need them!