Next: Rewrites Tutorial Exercise 3, Previous: Rewrites Tutorial Exercise 1, Up: Answers to Exercises [Contents][Index]

Here is the rule set:

[ fib(n) := fib(n, 1, 1) :: integer(n) :: n >= 1, fib(1, x, y) := x, fib(n, x, y) := fib(n-1, y, x+y) ]

The first rule turns a one-argument `fib`

that people like to write
into a three-argument `fib`

that makes computation easier. The
second rule converts back from three-argument form once the computation
is done. The third rule does the computation itself. It basically
says that if ‘`x`’ and ‘`y`’ are two consecutive Fibonacci numbers,
then ‘`y`’ and ‘`x+y`’ are the next (overlapping) pair of Fibonacci
numbers.

Notice that because the number ‘`n`’ was “validated” by the
conditions on the first rule, there is no need to put conditions on
the other rules because the rule set would never get that far unless
the input were valid. That further speeds computation, since no
extra conditions need to be checked at every step.

Actually, a user with a nasty sense of humor could enter a bad
three-argument `fib`

call directly, say, ‘`fib(0, 1, 1)`’,
which would get the rules into an infinite loop. One thing that would
help keep this from happening by accident would be to use something like
‘`ZzFib`’ instead of `fib`

as the name of the three-argument
function.