#### Due by the start of class on Friday, March 13th

# Some uScheme Exercises

Write a Scheme function,

`polish-compute`, that takes as an argument an arithmetic expression, written in reverse polish notation, and returns the value of this expression:(polish-compute '(8 2 - 4 3 + *)) ==> 42

## Functional Representation of Iteration

In his influential Turing Award address, John Backus [CACM 1978] defined
several higher-order functions that capture essential imperative features in a
purely functional style. Among these is the WHILE function, which is analogous
to a `while`-loop in an imperative language:

(val WHILE (letrec ((f (lambda (test body store) (if (not (test store)) store (f test body (body store)))) )) f))

What is captured by this is the fact that a loop requires three functions in order to work: the loop entry test, the body, and the contents of memory. For the memory contents (the "store"), think of it as a function from variable names to contents). In fact, we can simply use a list of the values we need to track, being careful to consistently associate a variable with a given position in the list.

- For example, the factorial function uses a state consisting of two
variables, as is evident from this version in Python:
def fact(n): res = 1 while n > 1: res = res * n n = n - 1 return res

Here's the same thing in uScheme, where we'll represent the state as a list of values:

(define fact (lambda (n) (let ((state (WHILE (lambda (x) (> (car x) 1)) ; the predicate (lambda (x) (list2 (- (car x) 1) ; the body (* (cadr x) (car x)))) (list2 ???? ????)) ; initial state before the loop )) (???? state) ; car or cadr? which one? )))

You fill in the ???? parts.

Use

`WHILE`function to define an ``iterative'' version of the Fibonacci function, using no assignment, sequence, or explicitly recursive calls. The following is an iterative version in Python, which you should use to guide you:def fib(n): fcur = 1 fmin1 = 0 while n > 1: tmp = fcur fcur = fcur + fmin1 fmin1 = tmp n = n - 1 return fcur

## Tacit Programming

Backus further proposed an algebraic style of functional programming that removes the need for program variables by providing a sufficiently rich set of higher order functions. One of the example applications he gave is the computation of an inner product. The following problems establish the construction.

Write a function,

`o`that takes as arguments two functions,*f*and*g*, and returns the composed function*f*(recall that`o`g`o`is an associative operation, although not commutative):> (define inc (lambda (x) (+ x 1))) > (define neg (lambda (y) (* y -1))) > (define dec (lambda (z) (- z 1))) > ((o neg inc) 3) -4 > ((o inc neg) 3) -2 > ((o inc (o neg dec)) 3) -1 > ((o (o inc neg) dec) 3) -1

Write a pair of functions,

`curry`and`uncurry`. The first takes a function whose argument is a pair and returns a curried version of the function:> (curry *) #

> ((curry *) 5) # > (((curry *) 5) 6) 30 Its inverse,

`uncurry`, returns a two-argument version of its curried function argument:> ((uncurry (curry *)) 5 6) 30

*NOTE:*these are actually built in to μScheme. It is, however, a great exercise to write them on your own.Write a pair of functions,

`tuple`and`untuple`. The first takes a function of two arguments and returns a function that takes a two-argument list:> ((tuple +) '(1 2)) 3

Naturally,

`untuple`is the inverse:> ((untuple (lambda (xs) (if (> (car xs) (cadr xs)) (car xs) (cadr xs)))) 3 4) 4 > ((untuple (tuple +)) 1 2) 3

Write a function

`reduce`of two arguments: a function*f*and a list of values,*ls*. The function should return the value that results from collapsing*ls using*f,*reducing from the beginning of the list to the end, not vice-versa*. For example:> (reduce + '(1 2 3 6 4 5)) 21 > (reduce (lambda (x y) (if (> x y) x y)) '(1 2 3 6 4 5)) 6 > (reduce - '(5 4 3 2 1)) -5

*NOTE:*Like`curry`and`uncurry`,`reduce`is built in to μScheme.Write a function

`map`of two arguments: a function*f*and a list of values,*ls*. The function should return the list that results from applying*f*to every element of*ls*. For example:> (map (lambda (x) (+ 1 x)) '(1 3 5 7 9)) (2 4 6 8 10) > (map (lambda (pr) (reduce * pr)) '((2 2) (3 3) (4 4) (5 5) (6 6))) (4 9 16 25 36)

*NOTE:*Again, built in to μScheme, and again, good practice.Write a pair of functions,

`zip`and`unzip`. The first,`zip`, takes a list consisting of two lists of equal length and returns the list of corresponding pairs.> (zip '((1 2 3 4 5) (6 7 8 9 10)) ) ((1 6) (2 7) (3 8) (4 9) (5 10))

Its inverse is

`unzip`:> (unzip '((1 6) (2 7) (3 8) (4 9) (5 10))) ((1 2 3 4 5) (6 7 8 9 10)) > (unzip (zip '((1 2 3 4 5) (6 7 8 9 10)))) ((1 2 3 4 5) (6 7 8 9 10)) > (zip (unzip '((1 6) (2 7) (3 8) (4 9) (5 10)))) ((1 6) (2 7) (3 8) (4 9) (5 10))

Using some or all of the functions defined above, construct the function

`IP`, which takes two vectors of equal length and returns their*inner product*. Do*not*write any further function definitions here: if your solution involves any occurrence of`lambda`or any bound variables, it's wrong.> (IP '((2 2 2) (3 3 3))) 18