### A combinator for a familiar operation

While playing with an interpreter, I noticed I had several functions that iterated some operation until they reached a fixed point, the way `macroexpand` repeats `macroexpand-1` until its return value is `eq` to the original form. [1] You can capture this behaviour for any function by a simple combinator:

``````iterate-until-fixed f x =
let x' = f x in
if (eq x' x)
x
iterate-until-fixed f x'``````

(I used `eq` instead of some other equality test because it avoids the difficulty of comparing arbitrary or circular structures.)

I was going to ask if anyone had a better name for this function, but `iterate-until-fixed` is not bad. Unfortunately it's not as useful as I thought. Most of these iterated operations (macroexpansion, many optimizations, etc.) are most useful when they're recursively applied to subforms, not just to the top level. This is much uglier, and it depends on the specific language, so it doesn't make a very reusable combinator. The language could be parameterized out by taking a `map-subforms` function as an argument, which makes it a little less ugly:

``````;map-subforms f exp -> another similar exp
recurse-until-fixed f map-subforms exp =
let results = map-subforms
(λ x → recurse-until-fixed f map-subforms x)
(iterate-until-fixed f exp) in
if (every eq results form)
form
recurse-until-fixed f map-subforms results``````

This has some holes - it doesn't handle environments, and the `every eq` test doesn't work for forms with non-top-level subforms (e.g. `let`). But (given a suitable `map-subforms`) it makes a nice simple `macroexpand-all`:

``````macroexpand-all exp =
recurse-until-fixed macroexpand-1 map-subforms exp``````

[1] In Common Lisp, `macroexpand` returns a second value to indicate whether it did anything, for historial reasons: in some ancient lisps, macroexpansion could side-effect forms, so mere equality didn't mean nothing had changed. The side effects were only done for performance reasons, and are not present in any modern lisp, so the second return value is not necessary. It is helpful at the REPL though.