Homework #9Assigned: April 7
Due: April 14, 4:30pm
 (10 points) The Fibonacci series
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
begins with the numbers 0 and 1 and has the
property that each subsequent Fibonacci number is
the sum of the previous two Fibonacci numbers.
The Fibonacci series occurs in nature and, in
particular, describes a form of a spiral. The
ratio of the successive Fibonacci numbers
converges on a constant value of 1.618.... This
number, too, repeatedly occurs in nature and has
been called the golden ratio or the
golden mean. Humans tend to find the
golden mean aesthetically pleasing. Architects
often design windows, rooms, and buildings with a
golden mean length/width ratio.
Define a function fibonacci in Haskell,
using only one tail call, which takes a
nonnegative integer n and returns the
nth Fibonacci number. Your definition of
fibonacci must execute in
O(n) time. You may define one
helper function, but it also must use only one
tail call. Do not use more than five lines of
code. Your function must be invocable as follows:
Main> fibonacci 0
0
Main> fibonacci 1
1
Main> fibonacci 2
1
Main> fibonacci 3
2
Main> fibonacci 4
3
Main> fibonacci 5
5
Main> fibonacci 6
8
Main> fibonacci 7
13
Main> fibonacci 8
21
Main> fibonacci 20
6765
 (10 points) Use call/cc to define a
while loop in Scheme without recursion:
(define mywhile
(lambda (condition body)
...))
You can demonstrate that your while loop is correct by using
it to print the numbers from 0 to 9 (one per line)
without recursion:
(define i 0)
(mywhile '(< i 10) '(begin
(write i)
(newline)
(set! i (+ i 1))))
We will award 5 points extra credit to any
student who can define mywhile without
using assignment (i.e., set!).
 (10 points) Rewrite the Scheme definition of
the product procedure developed in class
without call/cc, retaining the feature
that no multiplications are performed if any of the
list elements are zero. Do not use
continuationpassing style. Moreover, the call
stack must only grow to the length of the list plus
one (for the original function) once, not
more than once.
 (10 points) Define a function gcd* in
Scheme using continuationpassing style. The
function takes only a nonempty list of
positive, nonzero integers and a
continuation (in that order) and returns the
greatest common divisor of those integers. During
computation of the gcd, if a 1 is encountered in
the list, break out of the function immediately
with 1, without returning through any of the
recursive calls. Use only tail recursion.
 (10 points) Read Paul Graham's essay Beating the
Averages and write a 250 word commentary on it.
Be clear and concise in your prose.
 (5 points) Read M. Swaine's article It's
Time to Get Good at Functional Programming from
Dr. Dobb's Journal and write a 100 word
commentary on it. Be clear and concise in your
prose.
