Thursday, May 23, 2024

Rewrite rules

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.