Homework #9

1. (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 non-negative 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 5 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
   

2. (10 points) Use call/cc to define a while loop in Scheme without recursion, e.g.,

   (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!.

3. (10 points) Re-write 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 make more than one pass through the list of numbers, and do not use continuation-passing style.
   
   
4. (10 points) Define a function gcd* in Scheme using continuation-passing style. The function takes only a non-empty list of positive, non-zero integers and a continuation (in that order) and returns the greatest common divisor of those integers.
   
   
5. (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.
   
   
6. (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.