Com Sci 221 --- Programming Languages Assignment #7 --- Winter 1995 Due Monday, 27 February

Last modified: Mon Feb 20 14:53:11 1995

Other versions:

  1. Briefly discuss the relations between the set-theoretic types
    A + B + C + (A x B x C)
    and
    (A + {nil}) x (B + {nil}) x (C + {nil})
    Are they equivalent? Nearly equivalent? Does one represent the other?
  2. Discover a type equivalence or representability relation that we did not discuss in class. Tell how this relation might be used in a programming problem or a programming language design/implementation problem.
  3. Use the programming language ML to implement the Fibonacci function in the following 4 different ways.
    1. Encode the usual recursive definition as directly as possible: 
        fib(0) = 1

  fib(1) = 1
	   
fib(n+2) = fib(n) + fib(n + 1)
      See p. 41 of the text.
    2. Take advantage of the fact that arrays and functions in programming languages both correspond to the abstract idea of function. Create an array called fib, and store the first n values of the Fibonacci function into it. Then, compute values of the Fibonacci function on demand by simple table look-up.
    3. Notice that each array entry in the last solution was computed from only the previous two entries in the array, ignoring all earlier ones. Take advantage of this fact to develop an iterative (while-loop) implementation of the Fibonacci function, using two integer variables to store two adjacent values of the function.
    4. Rewrite the last solution tail-recursively. You should get essentially the program of problem 2.6, p. 59 of the text.
  4. Write a short essay (one or two pages should suffice) on the relationship between the solutions above. In particular, focus on their relative advantages and disadvantages in clarity, efficiency, and any other characteristics that seem important. Explain why you are confident that all 4 methods compute the same function. Focus on the fact that the same integer data values are being computed from one another in the same way, but the control of that computation is varying. Your explanation should show exactly where and/or when each value of the Fibonacci function appears in each program.
Comments