![[CS Dept., U Chicago]](http://www.cs.uchicago.edu/i/header_background.jpg)
Courses
Assignment # is due at 11:59 PM on Wednesday, 8 October
2003. Submit your work with the handin command, as
described in the
general instructions.
This assignment is an exercise in recursive and iterative definitions. As I wrote it, it turned into a textbook section with the assignment buried inside. I will summarize the things that you need to hand in at the end, so you don't have to search for them. But I think you will need to read the whole text to understand what's up.
The assignment compares 3 different ways to compute a Fibonacci series. The ideas come from S&IoCP by Abelson & Sussman. I tried to describe them in a different style from S&IoCP. You may read their presentation too if you find it helpful.
In this assignment, there is essentially one correct solution for each function definition that I require. I have given you the structure of each definition, with blanks to fill in. Except for a bit of variation in the order of variables and operations, there is essentially one sensible thing to fill in each spot, and you want to find it. Later assignments will constrain you less, and you will have to decide on some design and stylistic questions for yourself. But programming is not like poetry or artistic writing. Whimsical cleverness is almost always harmful. Fitting perfectly into the style of expression used by others in your project is almost always a big win. In this course, I will establish a lot of the design structure and programming style. It's not supposed to be a uniquely correct style, but you should follow it as a good exercise in fitting in.
One or more sensible test suites form part of every assignment in this class. There are many different sorts of software testing, and huge research projects that try, with limited success, to characterize their value. We will only do a relatively simple and small sort of testing, but we will try to do it very well by about the 4th week. I don't even like the work "testing" for what we will do, since it suggests a process that either certifies the quality of a program or uncovers a flaw. I prefer to call our form of exercising programs "demonstrating." It will often uncover flaws (which you will normally fix before submitting). But "demonstrating your programs" focuses on exercising them in a way that illuminates their purpose and actual behavior. Detection of flaws is a very common sort of illumination of behavior, but not the only one.
Testing/demonstrating the behavior of programs is a difficult and somewhat controversial problem in general, and we can't discuss it in detail during our first quarter. But it's important to get a bit of preliminary experience with demonstrations. Unguided, many students (and more experienced people as well) tend to cook up peculiar pseudorandom sets of test cases with whimsical numbers and names in them. Sensible choice of test cases for demonstrations depends on lots of things:
Right now, you are writing small simple programs to demonstrate and strengthen your understanding of Scheme. The structure of each program should be determined by very precise mathematical reasoning about the problem. The main value of test cases as tests is to provide a sanity check against the sorts of little errors that are easy to overlook when you stare at the program. The main value as demonstrations is to illustrate the consequences of the program structure by example.
You should always demonstrate your programs on the smallest trivial case, which is typically empty rather than size 1. Errors on such cases are remarkably common and tend to have strange consequences as you build on your programs. Then do just enough small but nonempty cases to cover the basic iterative or recursive steps in your programs. If the behavior of the program depends on particular characteristics of the input (e.g., odd size vs. even size), cover all of the variations that make a serious difference.
There is a great general principle that determines (in principle) how to demonstrate/test a program:
This is a great principle in principle, but impossible to apply rigorously in practice. You aren't sure that you have the program you intended to write. All you have is one of those nasty variants. You also don't know the detailed psychological process by which you make errors, so even if you had the intended program, you couldn't reliably generate the variants.
Nonetheless, you can use the mutation principle to stimulate your thinking about good test cases for a program. Often the rough structure of your program puts the function(s) that it computes into some particular class(es), such as linear functions or polynomials (usually other classes for which we don't have good names, but which we know fairly well intuitively). You can cook up test cases that distinguish all members of that class.
Someone actually wrote a dissertation on the use of "mutant analysis" to generate test cases, and created a working application. It's a very interesting idea, and will probably bear practical fruit someday. But as far as I know, there is no practical automated test generator based on this idea so far.
Our project this quarter involves implementing and evaluating a prototype Perfectly Accurate Calculator (PAC) to perform exact calculations on real numbers. It's widely known in CS that this is impossible, which is why we live with the roundoff errors in floating point calculations. Like so many widely known facts, that one is false. A real number can be represented with perfect accuracy by a function that produces rational numbers approaching that value in the limit. Of course, there's no completely general way of printing out those values in a nice readable finite form. But, once you have such an exact real number cum function, you can decide how much accuracy to print out, change your mind as many times as you like, and view the approximate results with confidence that you know exactly how far off they might be.
This week's assignment will fit into the calculator project, but I decided to reserve the fitting part for a later week.
The Fibonacci series, starting with the integers a and b, is defined mathematically by
F(a,b,0) = a F(a,b,1) = b F(a,b,i+2) = F(a,b,i) + F(a,b,i+1)
For example, the series F(0,1,i) starts out 0, 1, 1, 2, 3, 5, 8, 13, .... Fibonacci series is often described as keeping track of the population of rabbits, who supposedly have a 2-year breeding career. The rabbit application is mostly bogus, but Fibonacci numbers come up in nature and in computer science quite a bit.
Translate the mathematical definition above directly into a recursive definition in Scheme, using as little cleverness as possible. Here is my definition, with key parts replaced by ellipses ("...").
;; Fibonacci Series ;; ;; Mike O'Donnell ;; 1 October 2003; revised 2 October 2003 ;; fib_1: integer integer integer -> integer ;; ;; (fib_1 a b i) is the ith number in the Fibonacci series ;; starting with a and b. The first element in the series is ;; numbered 0 (i=0). (define (fib_1 a b i) (cond ( ... ) ( ... ) (else ... ) ) )
Use exactly the same form for your definition---clever variation
has no value at this stage. The "_1" is just there so we
can compare this definition of the Fibonacci series with two others
later in the assignment. You should read the Scheme
definition almost directly from the mathematical definition, adjusting
for Scheme's notation for function application, and for the
fact that the sequence number is given always by the variable
i, rather than 0, 1, and i+2.
Demonstrate your definition on a test suite containing a very small
well-chosen set of test cases. With such a simple definition, there
isn't a lot to demonstrate. Always demonstrate a recursion on the base
cases: i=0 and i=1 in this case. Here is a
rationale that you may follow in constructing your test cases. If you
think of another rationale, explain it.
(fib_1 m n i)
has to do with selecting either a, or b, or
a pair of earlier elements in the series to add.i to cover the basic
alternatives:
a,b,a to b,b to a computed element of the series,i, and probably with only one test case for each
appropriate value of i.a and b should distinguish
all of the 4 alternatives above. You can probably do this with only
one pair of values for a and b.One might argue for a test case that distinguishes addition from multiplication, since a mistyped operation symbol is a natural sort of mistake. I'm inclined to leave that out in this simple case. But if the definition were a bit more complicated, and in particular if both addition and multiplication were involved, I would probably look for test cases that distinguished correct deployment of the operations from accidental misplacements.
Roughly how many times is the definition of fib_1
invoked in order to calculate (fib_1 m n i)? The answer
clearly depends on the value of i, but not on the values
of a and b, so the answer should be a (very
simple) mathematical expression involving i.
The word "roughly" can be given a very precise mathematical meaning here, which you will study if you go on to the algorithm analysis course. For now, you can work roughly with "roughly", by considering that we want to distinguish between expressions
i, i^2, i^3, i^4, ..., 2^i, 3^i, ...but not between
i^2, i^2+100, 100i^2, ...
It turns out that the first set of distinctions is very robust---they remain valid on different computers, different implementations of the programming language, and different degrees of cleverness in filling in the details of a program. The second set of distinctions is not robust. With a more complex program, a bit of extra care in the details can easily divide the time required to compute by 100. Buying a faster computer can have an even bigger impact. So we are "roughly" capturing the impact of the basic technique used in our program, and ignoring the impact of both programming details and the choice of computer.
Promote yourself to the "Intermediate Student" language, so you can
check a few examples of the time taken to compute Fibonacci
numbers. Try a sequence of examples of the form (time (fib_1 0 1
i)). For very small values of i (0, 1, 2),
the time tends to round to 0, with occasional inconsistent quirks due
to things we might learn about later. Up around 20 you should get
interesting results. Time the same computation several times---the
results may vary. Around 100, you may have to hit the "Break" button
to stop the computation before you starve waiting for it.
The number of steps taken by fib_1, and the time
required to do so, are in the horrificly bad category
according to CS and geeky tastes in such things. fib_1 is
still perfectly usable for reasonably early elements of the series,
but we can do much better.
Most of the steps taken by (fib_1 m n i) on medium to
large values of i are repetitions. Here is the sequence
of function invocations to compute (fib_1 0 1 6):
(fib_1 0 1 6) (fib_1 0 1 5) (fib_1 0 1 4) (fib_1 0 1 3) (fib_1 0 1 2) (fib_1 0 1 1) (fib_1 0 1 0) (fib_1 0 1 1) (fib_1 0 1 2) (fib_1 0 1 1) (fib_1 0 1 0) (fib_1 0 1 3) (fib_1 0 1 2) (fib_1 0 1 1) (fib_1 0 1 0) (fib_1 0 1 1) (fib_1 0 1 4) (fib_1 0 1 3) (fib_1 0 1 2) (fib_1 0 1 1) (fib_1 0 1 0) (fib_1 0 1 1) (fib_1 0 1 2) (fib_1 0 1 1) (fib_1 0 1 0)
If you work this out on your own, you might think of these invocations in a different order, but you should get the same ones. Notice how many times each value is computed:
expression number (fib_1 0 1 6) 1 (fib_1 0 1 5) 1 (fib_1 0 1 4) 2 (fib_1 0 1 3) 3 (fib_1 0 1 2) 5 (fib_1 0 1 1) 8 (fib_1 0 1 0) 5
The repetition gets much worse as you go farther down the Fibonacci series. (You should recognize a familiar pattern in the numbers, in spite of one funny glitch.)
We can speed up the computation a lot, while getting the same results, if we make sure to compute each of these values only once. That's not hard to do, if we just notice that
F(a,b,i+1) = F(b,a+b,i)
Here's the structure of my solution.
;; fib_2: integer integer integer -> integer ;; ;; (fib_2 a b i) is the ith number in the Fibonacci series ;; starting with a and b. The first element in the series is ;; numbered 0 (i=0). (define (fib_2 a b i) (cond ( ... ) (else (fib_2 ... (- i 1)) ) ) )
Fill in the 2 missing parts, shown by ellipses, to get a much more
efficient definition of the Fibonacci series. Notice that this form of
the definition only needs one base case for i=0.
Demonstrate your definition on a small, well crafted test suite.
You should use your already correct fib_1 to express the
"Expected" values for your tests of fib_2.
Roughly how many times is the definition of
fib_2 invoked in order to calculate (fib_2
m n i)? In this case, it's quite easy to figure out the
exact number, but it's still better to simplify the
expression and only worry about the "rough" level of accuracy. Compare
the speed of fib_1 and fib_2 using the
time function. You should see a dramatic
difference.
In many programming languages, such as Fortran,
Algol, Pascal, C, the essential
computational steps in fib_2 are described with a
structure called a loop, and the computation is called an
iteration. Iterations are nice because the number of steps
and amount of work per step are often rather easy to observe and
control. In Scheme, iterations are expressed as a special
form of recursive definition, in which there can only be one recursive
invocation of a function, and that must be the last thing done in the
function definition. That form of recursion is often called tail
recursion. Scheme, and a number of similar languages
today, make a point of implementing tail recursions internally as
iterations. We will see later in the quarter how the iterative form
saves a certain amount of effort per step, and a lot of storage space,
over a recursion, even when the number of steps is the same. There is
a variation on fib_2 that makes the recursive
call first, instead of last. That variation achieves the same number
of steps, but Scheme cannot do each step quite as
efficiently.
It was really just a lucky stroke that the general Fibonacci series could be defined directly in an iterative form. Usually, we must define a slightly different (and more general) function in order to use iteration. For example, if our desired function was intended to compute only the standard Fibonacci series, starting with 0 and 1, we would have been forced to generalize it to the series with arbitrary starting values in order to use iteration, then define the standard Fibonacci series in terms of the general function. When we define a different function than the one we really want, in order to use a particular programming technique, people often call the different function a "helper" function. I don't find the term "helper" very helpful, but you should recognize it when it comes up in books and articles and documentation.
Everybody should get the naive recursion and simple iteration pretty briskly. The WOW iteration is a bit more challenging. If you think you're an A student, you should definitely do it briskly. And everyone should go as far as they can on it. But if you don't get it entirely, you don't need to drop the course.
The efficiency of fib_2 is in the pretty good
category, compared to fib_1's horrificly
bad. But we can do even better, and qualify for the WOW
category.
Think about a Fibonacci series based on unknown seed values a and b as two interacting series:
a b b a+b a+b a+2b a+2b 2a+3b 2a+3b 3a+5b 3a+5b 5a+8b 5a+8b 8a+13b ...
You should notice that the coefficients multiplying a and b above also form a Fibonacci series. But we don't want to just calculate coefficients with a previous method for Fibonacci series, because that certainly won't be any faster.
The key point about the interacting series above, which we can exploit in a WOW Fibonacci program, is the fact that each element in each sequence is determined as a linear combination of the immediately previous elements in both series. In this case, the left series is determined by the linear combination 0*left+1*right, and the right series is determined by 1*left+1*right. The coefficients 0, 1, 1, 1 determine these two series, and the left one is just the Fibonacci series starting with a and b.
Now, the ith elements of the two series are also defined by linear combinations of the starting values a and b, resulting from composing the 0, 1 and 1, 1 transformations with themselves i times. We can drop the as and bs in the symbolic series above, leaving just the sequences of coefficients:
1 0 0 1 0 1 1 1 1 1 1 2 1 2 2 3 2 3 3 5 3 5 5 8 5 8 8 13
Notice that the right two columns are easily determined from the left two. If the values in the left two columns are p and q, then the values in the right two columns are q and p+q. The first line does not show the coefficients 0, 1, 1, 1 because it corresponds to the 0-step linear combination. The second line gives the 1-step combination, with coefficients 0, 1, 1, 1.
So, instead of computing just Fibonacci series, we will compute an arbitrary series defined by such a pair of linear transformations with coefficients p, q, q, p+q. Let G(a,b,p,q,i) be the ith element in the first series in the pair defined above by the coefficients p and q. The rules for i=0, and for advancing the value of i by 1, are easy:
G(a, b, p, q, 0) = a G(a, b, p, q, i+1) = G(pa+qb, qa+(p+q)b, p, q, i)
But we may also derive a much more powerful rule, determining G(...,2i) from G(...,i):
G(a, b, p, q, 2i) = G(a, b, pp+qq, qp+(p+q)q, i) [corrected 5/10/2003]
You probably have to think a while to be sure this one is right. Check it out against some examples in the sequence of coefficients above. Then make sure it's totally right by noticing what happens when the linear combination determined by p and q is applied twice:
a b pa+qb qa+(p+q)b p(pa+qb)+q(qa+(p+q)b) q(pa+qb)+(p+q)(qa+(p+q)b)
Rearrange the two expressions in the last line to
(pp+qq)a + (qp+(p+q)q)b (qp+(p+q)q)a + (pp+qq+qp+(p+q)q)b
The formula on the left verifies the rule, and the formula on the right confirms that the coefficients for the right series are still derivable from the coefficients for the left series. You might find the form in which I expressed the coefficients peculiar. I chose that particular form, because it displays the similarity between the use of p and q to determine new values in the two series, and their use to modify the coefficients to produce a series that develops twice as fast.
So here's the structure of the program:
;; fib_3: integer integer integer -> integer ;; ;; (fib_3 a b i) is the ith number in the Fibonacci series ;; starting with a and b. (define (fib_3 a b i) (repeat_lin_comb a b 0 1 i) ) ;; repeat_lin_comb: integer integer integer integer integer -> integer ;; ;; (repeat_lin_comb a b p q i) is A_i, the ith element in the first of ;; the two mutually recursive series: ;; ;; a pa+qb ... A_i ;; b qa+(p+q)b ... B_i ;; ;; In general, ;; ;; A_0 = a B_0 = b ;; ;; A_i+1 = pA_i + qB_i B_i+1 = qA_i + (p+q)B_i (define (repeat_lin_comb a b p q i) (cond ((= i 0) ... ) ((even? i) (repeat_lin_comb ... (/ i 2) )) (else (repeat_lin_comb ... (- i 1) )) ) )
You know the drill. Fill in the parts I left out. This time, I
specified the use of repeat_lin_comb in the definition of
fib_3, because I don't want you to deal with the
confusion that you can generate by simultaneously goofing up the
definition and the use of the function. When you're good at this (and
having a good day, and not too uptight, and not too close to a
deadline), you'll inspect and test the definition of the function
repeat_lin_comb so thoroughly before trying
fib_3 that such confusion will not arise.
If you grok matrices, you can figure out how the whole shebang above is essentially raising the 2x2 matrix
( 0 1 ) ( 1 1 )
to the ith power, using the clever fast exponentiation that we looked at in class, taking advantage of the fact that all powers of this matrix have the form
( p q ) ( q p+q )
so you only have to keep track of 2 elements of the matrix, not all 4.
Roughly how many times is the definition of
repeat_lin_comb invoked in order to calculate
(fib_3 m n i)? You need to use the logarithm
function to express your formula. Compare the speed of
fib_3 with fib_1 and fib_2
using the time function. You should see another
dramatic difference.
Because it is iterative, lots of people (including Abelson and
Sussman) tend to call our repeat_lin_comb function
something like "fib-iter". Others use even less
informative names, such as "fib-helper", or the
abominable "foo". In this class, we will always try to
choose names for functions that indicate the values computed by
the functions. "fib-helper" suggests, in a rather
vague way, the intended use of the function, which you can
see by observing how it is indeed used. "fib-iter" is a
bit better, suggesting the programming technique by which it was
derived. But it's usually pretty easy to see that the definition is
iterative, so that doesn't help a lot. And there are lots of different
iterations that compute Fibonacci numbers, including the ones in our
fib_1 and repeat_lin_comb definitions as
well as a number of others. So we'd like a function name to give us a
hint which iterative definition it is.
"repeat_lin_comb" tells us something about the fact
that the value computed by the function is the result of repeating a
certain linear combination. In this case, that's only a small part of
the information needed to understand the function completely, but at
least it might help a reader remember that information, having read
the fuller description in the header once. Whenever we look at an
invocation of a function, such as the use of
repeat_lin_comb in the definition of fib_3,
the main thing that we need to know is what value does the function
compute on a given sequence of arguments. The best name for the
function is generally the one that helps the reader most to remember
that. In a recursively defined function, even when it's
tail-recursive/iterative, the value computed by the recursive
invocation is also what we need to know when trying to decide whether
the function is correct.
Hand in three items, each one consisting of at least one file:
fibonacci.scm containing your
definitions of the functions described above;fibonacci.stuff.tst.scm, where you can put in different
stuff depending on how you like to organize the test
suites. For example, each stuff could be the name of one
of the functions you defined.discussion.txt (or
discussion.ps, ... if you like to use another format),
containing
 | |