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

Some uScheme Exercises

  1. 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.

  1. 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.

  2. 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.

  1. Write a function, o that takes as arguments two functions, f and g, and returns the composed function f o g (recall that 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
    
  2. 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.

  3. 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
    
  4. 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.

  5. 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.

  6. 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))
    
  7. 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
    

John H. E. Lasseter