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.