“[login to view URL]” to Gradescope.
You may NOT use any of Scheme’s imperative features (assignment/loops) or anything else not covered in
class. You should use Racket ([login to view URL]) for your implementation. For all problems, you can
assume all inputs obey the types as specified in a problem.
Testing and Auto Grading We will use the Gradescope Autograder feature to grade the assignment. So it is
important to start from the code template “[login to view URL]” on Canvas, which only has dummy implementationsbut
is nevertheless useful since it obeys a few important requirements for auto grading, such as file name,
function names etc
one of the example problem is
we define Church number n as λf n: (fn z), where (fn z) represents the
n-fold composition of function f applied to z (i.e., f(f(: : : (f z))) where f is repeated for n times).
a) (5pt) Implement a function funPower, which takes a function f, an integer n and returns the function
fn. For example, ((funPower sqrt 2) 16) should return 2.
b) (5pt) Implement a function encode, which takes a natural number n and returns the church encoding of
n. For example, (encode 2) should return 2 (i.e., the function λf: λz: f (f z)).
c) (5pt) Implement a function decode, which takes n (the church encoding of some natural number n) and
returns n. For example, (decode (encode 2)) should return 2.
d) (5pt) Implement a function MULT, which takes two church numbers n1, n2 and returns the church number
of n1 × n2 (i.e., n1 × n2). For example, (decode (MULT (encode 2) (encode 3))) should be 6.