The assignment is due: Feb 11, 2000.
The aim of this project is again two fold. To introduce you
  1. Good programming notation
  2. Functional programming
Let me first state the problem and then explain how the above aims are achieved.

Problem

Suppose you are given a sequence like: 1, 1, 2, 3, 5, 8, 13, 21 What is the ``structure'' of the sequence? If you stare at it for a sufficiently long time and/or if you already know something about Fibonacci sequences, you'll say something like this: Each number is the sum of the previous two numbers.

More formally, what this means is that the above sequence is a second order recurrence relation with the structure 

         F(n) = F(n-1) + F(n-2)  // structure
         F(0) = 1, F(1) = 1      // initial condition
We will consider recurrence relations having a restricted structure. The structure of our recurrence relations is 
         F(n) = F(n-1) + g(n)
where g(n) is a function of n. The permissible form of g(n) is defined recursively as follows.
  1. g(n) = 1 is a permissible form
  2. g(n) = n is a permissible form
  3. If g(n) is a permissible form, then g(n)+1, g(n)+n, g(n)-1, g(n)-n, g(n)*n, and g(n)^n are permissible forms.
The following are some examples of g(n). 
     1
     (n-1)*n
     2n (= n+n or (1+1)*n)
     n^2 (= n*n)
     2^n (= (1+1)^n)
The problem is, given an example sequence, can you output the next two numbers? For example, consider the sequence, 1, 2, 4, 7, 11, 16. In this case, the function g(n) = n. And the sequence is 
   F(0) = 1;
   F(1) = F(0) + g(1) = 1 + 1 = 2
   F(2) = F(1) + g(2) = 2 + 2 = 4
   F(3) = F(2) + g(3) = 4 + 3 = 7
   F(4) = F(3) + g(4) = 7 + 4 = 11
   F(5) = F(4) + g(5) = 11 + 5 = 16
   F(6) = F(5) + g(6) = 16 + 6 = 22
   F(7) = F(6) + g(7) = 22 + 7 = 29
Note that F(n) = F(n-1) + n with F(0) = 1. The next two numbers are: 37, 46.. (The same sequence is also given by F(n) = n(n-1)/2 + 1. You can't write F(n) as g(n) for any permissible g(n). This is where recurrence relations help.)

Solving the problem

There are two ways of solving the problem. Consider the solution in C. We need to
  1. create the permissible forms of g(n)
  2. evaluate the expressions
  3. test whether the values correspond to the input values.
The expressions are usually represented using a combination of structs, unions, and pointers.

Another way of solving this is to create functions, evaluate them, and to test them on the the sequences. The evaluation part is easy in this case since we can use ML itself to evaluate the functions. It is not possible to create functions in C, but functions can be created in ML.

One way to compare imperative and functional programming is to write code in C and ML and then compare the codes. But the fact is it is difficult to write such imperative code in C. ML provides better support for creating and evaluating expressions!

The assignment

Your need to use only ML for this assignment. You should write two ML functions (and supporting functions, as well).
  1. The first function should do it a la C. As mentioned before, you need to create expressions, evaluate them, and compare the resulting sequence with the given sequence.

    The function which does this should be called evalExprComplete. It should take an integer list as argument and return an integer list containing the next two integers in the sequence.

  2. The second function should create functions, evaluate them, and then test the resulting sequences. It should also take an integer list as argument and return an integer list containing the next two integers in the sequence.

    This function should be called evalFunComplete.

You should keep both these functions and the associated functions in a file called completeSeq.ml and use bundleP2 to submit the assignment.

Your program should use O(dB) space where d is the depth at which the solution is found and B is the branching factor.

Some test sequences: 

1, 0, 0, 9, 41, 116, 260, ... [g(n) = (n-2)n^2]
1, 0, 0, 1, 17, 260, ... [g(n) = (n-2)^n]
10, 8, 12, 4, 20, ~12, ... [g(n) = (-2)^n]

The report

In your report write about the following aspects.
  1. Imperative programming as in C: Even though there is no coding in C, you can imagine writing the code in C for expression creation and evaluation and write about that experience.
    1. If you had written the code in C, what would have been the difficulties?
    2. What are the features needed to make coding easier in C?
    3. How can these features be incorporated in C? Can they be incorporated by writing a preprocessor?
    4. Why does C lack the necessary features? (Hint: It is not the lack of knowledge. Lisp had many features needed to solve this problem and Lisp predates C.)
  2. Imperative programming as in ML:
    1. Which aspects of ML notation make solving this easy?
    2. Do you know any other language which supports this notation?
    3. How helpful is recursion for evaluating expression?
    4. Ease of programming with automatic creation and destruction of objects.
  3. Functional programming in ML:
    1. Do you think treating functions as first-class values is a useful feature?
    2. Can you think of other problems which need this feature?
    3. (Optional) How do you think ML implements function composition at runtime?
  4. Comparison of representations: In your programs, you used two different representations (expressions and functions) to solve this problem. What are the advantages of each of these representations?
You need not limit yourself to these points. You can discuss any of your other observations.

Submission

You should submit your code using bundleP2 before 7:00 PM on Feb 11, 2000.

You should submit your report, a hard copy of your code and test results, and the self-evaluation form to Renata Teixeira between 6:00 - 7:00 PM on Feb 11, 2000 at APM 3349D.

Additional information

Additional information on search and some example ML code can be found here.

Absolute academic honesty is required.