Friday, March 25, 2005

Binding abstractions, binding polymorphism

I think I understand better what Clinger and Rees meant in Macros that Work about binding abstractions. Here's their quote again:
The distinction between binding occurrences and other uses of identifiers should be determined by a particular syntactic abstraction, not predetermined by the parser.
I thought they were claiming that the binding properties of identifiers in a macro could never be determined statically. As I've said, I believe that in the vast majority of cases, the binding properties of identifiers are a part of the static interface between a macro definition and its clients, so I would disagree with such a claim. (It's worth noting that you probably couldn't infer binding properties in general, since syntax-rules is Turing-complete. But you could certainly imagine a type system for macros that captured these properties, and/or a restricted sub-language of syntax-rules where inference is possible.)

But that's not their claim. They are simply motivating the need for delaying the renaming decisions. Because they don't have any static mechanism for determining the binding properties of identifiers, and because macros can abstract over other macros that bind identifiers, the algorithm is simply incapable of determining the binding properties until the very end of expansion.

Incidentally, Sam has given me a perfect example of a useful macro that is binding polymorphic. He has recently enhanced the PLT Scheme match library, which provides ML-like pattern matching, to allow arbitrary extensions to the pattern matching clauses. Because various subexpressions of a matching clause may or may not contain binding occurrences of variables, the match macro must be polymorphic with respect to the binding properties of its arguments. Beautiful!

No comments: