Homework 7a
Due Date Tues at 9:00pm (Week 7)
MUST BE DONE WITH YOUR PARTNER
MUST USE CHECKED-SIGNATURES!
Purpose Explore Lambda
Exercises
Alternators and Repeaters
(define Alternator (signature (%X %X -> %X)))
Exercise 1Why do you think we call them that?
Define the two shortest functions that have this signature. The functions are restricted to only use λ expressions and variables. These will be our Alternators.
Exercise 2 Design an alternator->boolean function, which will allow us to test the functions we define below by converting from an Alternator to an ISL #true / #false. Note: there are two (correct) ways of doing this! (In this problem, you are obviously also allowed to use #true / #false).
For the following three functions, besides define and λ, your function definitions should not use any ISL-provided functions or keywords (and certainly not alternator->boolean, #true or #false).
Exercise 3 Design and/alt, which functions analogusly to and, but takes in two Alternators and outputs an Alternator. By "analogously to and", we mean, in particular, that if you take two Alternators, convert them using alternator->boolean, and then call and on them, you should get the same result as calling and/alt first and then using alternator->boolean on the single resulting Alternator.
Exercise 4 Design or/alt, which functions analogusly to or, but takes in two Alternators and outputs an Alternator.
Exercise 5 Design not/alt, which functions analogusly to not, but takes in one Alternator and outputs an Alternator.
Repeat After Me
Exercise 6 Design the function two that takes a function (: f [%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:
(define Repeater (signature ((%X -> %X) -> (%X -> %X)))) ; That, given a one-argument function f, outputs a ; function that will repeatedly apply f some specific number of times
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 may 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) Hint: 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 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!