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)
      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)
      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.

No comments:

Post a Comment

It's OK to comment on old posts.