Assignment 1

Principles of Programming Languages (201-1289101)

Iterative vs Recursive Processes -- Procedures as Arguments

Due 17 Mar 1997

Notes

The easiest way to work in Scheme on the UNIX machines is to work as follows:

Work in Emacs
Split your screen in 2 (C-x 2)
Run scheme in one window (M-x run-scheme)
Edit your file in the other window (C-x o switch among windows)
To load a complete file in scheme type (load "a.scm") in scheme.

In case you are not in the right directory, type (chdir "mydir") in scheme

To send a definition of a function from the buffer to the scheme process, put the cursor in the body of the function at do M-C-x

Questions

Iterative Fast Exponentiation (1.16 from book)
Logarithmic Fibonacci (1.19 from book)
Product higher order function (1.31 from book)
Accumulate higher order function (1.32 from book)

Question 1: Iterative Fast Exponentiation

(Exercise 1.16 from book)

Design a procedure that generates an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-exp.

Hint: Using the observation that (b^n/2)²=(b²)^n/2, keep along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product abⁿ is unchanged from state to state. At the beginning of the process, a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.

For reference, the recursive version of fast-exp is:

(define (fast-exp b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-exp b (/ n 2))))
        (else (* b (fast-exp b (- n 1))))))

Question 2: Logarithmic Fibonacci

(Exercise 1.19 from book)

There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fid-iter process of the class:

a <- a + b
b <- a

Call this transformation T. Observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n+1) and Fib(n). In other words, the Fibonacci numbers are produced by applying Tⁿ, the nth power of the transformation T, starting with the pair (1,0).

Now consider T to be the special case of p=0 and q=1 in a family of transformations T_pq, where T_pq transforms the pair (a,b) according to:

a <- bq + aq + ap
b <- bp + aq

Show that if we apply such a transformation T_pq twice, the effect is the same as using a single transformation T_p'q' of the same form, and compute p' and q' in terms of p and q.

This gives us an explicit way to square these transformations, and thus we can compute Tⁿ using successive squaring, as in the fast-exp procedure. Put this all together to complete the following procedure, which runs in logarithmic number of steps:

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>     ;; compute p'
                   <??>     ;; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

Question 3: Product higher order function

(1.31 from book)

We studied in class the sum procedure:

(define (sum term a next b)
  (if (< b a)
      0
      (+ (term a) (sum term (next a) next b))))

The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. Write a similar procedure called product that returns the product of the values of a function at points over a given range. Show how the factorial function can be defined in terms of product. If your product procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Question 4: Accumulate higher order function

(1.32 from book)

Show that both sum and product (from question 3) are both special cases of a still more general notion called accumulate that combines a collection of terms using some general accumulation function: (accumulate combiner null-value term a next b) accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure of two arguments that specifies how the current term is to be comined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out.l Write accumulate and show how sum and product can both be defined as simple calls to accumulate. Write both an iterative and a recursive version of accumulate.

The end.