I like rewrite rules. They are simple to understand and easy to implement. If you have a rewrite rule (or a set of them) that makes incremental progress in making an expression "simpler" in some sense, you can keep applying it (or them) repeatedly until you have finished the calculation.

If a function directly returns the result of calling another function,
we say that the call is in "tail position". We can view this as a
simple rewrite rule. Consider the `fact-mul`

function
which computes the factorial of a number n and multiplies it by
another number m:

fact-mul (n, m) = n! * m

We can define two rewrite rules for this function. If n is 0, then
the factorial is 1, so we just rewrite this as m. If n is not 0, we
can rewrite this as `fact-mul (n-1, n*m)`

. This translates directly
into Lisp:

(defun fact-mul (n m) (if (zerop n) m (fact-mul (- n 1) (* n m))))

The rewrite rule doesn't have to rewrite into the same function.
For instance, we can rewrite `odd? (x)`

to `even? (x-1)`

and `even? (x)`

to `odd? (x-1)`

:

(defun odd? (x) (if (zerop x) nil (even? (1- x)))) (defun even? (x) (if (zerop x) t (odd? (1- x))))

Yes, this is bog-simple tail recursion, but somehow it seems even simpler to me if I think of it as a rewrite rule.

Even if you don't have tail recursion, or if you have disabled it, it still works, but the number of rewrites is limited by the stack depth.

## No comments:

Post a Comment