Hygienic macro

Hygienic macros are macros whose expansion is guaranteed not to cause the accidental capture of identifiers. They are a feature of programming languages such as Scheme[1] and Dylan.[2] The general problem of accidental capture was well known within the Lisp community prior to the introduction of hygienic macros. Macro writers would use language features that would generate unique identifiers (e.g., gensym) or use obfuscated identifiers in order to avoid the problem. Hygienic macros are a programmatic solution to the capture problem that is integrated into the macro expander itself. The term "hygiene" was coined in Kohlbecker et al.'s 1986 paper that introduced hygienic macro expansion, inspired by the terminology used in mathematics.[3]

The hygiene problem

In programming languages that have non-hygienic macro systems, it is possible for existing variable bindings to be hidden from a macro by variable bindings that are created during its expansion. In C, this problem can be illustrated by the following fragment:

#define INCI(i) {int a=0; ++i;}
int main(void)
{
    int a = 0, b = 0;
    INCI(a);
    INCI(b);
    printf("a is now %d, b is now %d\n", a, b);
    return 0;
}

Running the above through the C preprocessor produces:

int main(void)
{
    int a = 0, b = 0;
    {int a=0; ++a;};
    {int a=0; ++b;};
    printf("a is now %d, b is now %d\n", a, b);
    return 0;
}

The variable a declared in the top scope is shadowed by the a variable in the macro, which introduces a new scope. As a result, it is never altered by the execution of the program, as the output of the compiled program shows:

a is now 0, b is now 1

The simplest solution is to give the macros variables names that do not conflict with any variable in the current program:

#define INCI(i) {int INCIa=0; ++i;}
int main(void)
{
    int a = 0, b = 0;
    INCI(a);
    INCI(b);
    printf("a is now %d, b is now %d\n", a, b);
    return 0;
}

Until a variable named INCIa is created, this solution produces the correct output:

a is now 1, b is now 1

The problem is solved for the current program, but this solution is not robust. The variables used inside the macro and those in the rest of the program have to be kept in sync by the programmer. Specifically, using the macro INCI on a variable INCIa is going to fail in the same way that the original macro failed on a variable a.

The "hygiene problem" can extend beyond variable bindings. Consider this Common Lisp macro:

 (defmacro my-unless (condition &body body)
  `(if (not ,condition)
     (progn
       ,@body)))

While there are no references to variables in this macro, it assumes the symbols "if", "not", and "progn" are all bound to their usual definitions. If, however the above macro is used in the following code:

 (flet ((not (x) x))
   (my-unless t
     (format t "This should not be printed!")))

The definition of "not" has been locally altered and so the expansion of my-unless changes. (Redefining standard functions and operators, globally or locally, actually invokes undefined behavior according to ANSI Common Lisp. Such usage can be diagnosed by the implementation as erroneous.)

On the other hand, hygienic macro systems preserve the lexical scoping of all identifiers (such as "if" and "not") automatically. This property is called referential transparency.

Of course, the problem can occur for program-defined functions which are not protected in the same way:

 (defmacro my-unless (condition &body body)
  `(if (user-defined-operator ,condition)
     (progn
       ,@body)))

 (flet ((user-defined-operator (x) x))
   (my-unless t
     (format t "This should not be printed!")))

The Common Lisp solution to this problem is to use packages. The my-unless macro can reside in its own package, where user-defined-operator is a private symbol in that package. The symbol user-defined-operator occurring in the user code will then be a different symbol, unrelated to the one used in the macro.

Meanwhile, languages such as Scheme that use hygienic macros prevent accidental capture and ensure referential transparency automatically as part of the macro expansion process. In cases where accidental capture is desired, some systems allow the programmer to explicitly violate the hygiene mechanisms of the macro system.

For example, the following Scheme implementation of my-unless will have the desired behavior:

 (define-syntax my-unless
   (syntax-rules ()
     [(_ condition body)
      (if (not condition)
          body
          (void))]))

  (let ([not (lambda (x) x)])
    (my-unless #t
      (displayln "This should not be printed!")))

Strategies used in languages that lack hygienic macros

In some languages such as Common Lisp, Scheme and others of the Lisp language family, macros provide a powerful means of extending the language. Here the lack of hygiene in conventional macros is resolved by several strategies.

Obfuscation
If temporary storage is needed during the expansion of a macro, unusual variable names can be used in hope that the same names will never be used in a program that uses the macro.
Temporary symbol creation
In some programming languages, it is possible for a new variable name, or symbol, to be generated and bound to a temporary location. The language processing system ensures that this never clashes with another name or location in the execution environment. The responsibility for choosing to use this feature within the body of a macro definition is left to the programmer. This method was used in MacLisp, where a function named gensym could be used to generate a new symbol name. Similar functions (usually named gensym as well) exist in many Lisp-like languages, including the widely implemented Common Lisp standard[4] and Elisp.
Read-time Uninterned Symbol
This is similar to the first solution in that a single name is shared by multiple expansions of the same macro. Unlike an unusual name, however, a read time uninterned symbol is used (denoted by the #: notation), for which it is impossible to occur outside of the macro.
Packages
Instead of an unusual name or an uninterned symbol, the macro simply uses a private symbol from the package in which the macro is defined. The symbol will not accidentally occur in user code. User code would have to reach inside the package using the double colon (::) notation to give itself permission to use the private symbol, for instance cool-macros::secret-sym. At that point, the issue of accidental lack of hygiene is moot. Thus the Lisp package system provide a viable, complete solution to the macro hygiene problem, which can be regarded as an instance of name clashing.
Hygienic transformation
The processor responsible for transforming the patterns of the input form into an output form detects symbol clashes and resolves them by temporarily changing the names of symbols. This kind of processing is supported by Scheme's let-syntax and define-syntax macro creation systems. The basic strategy is to identify bindings in the macro definition and replace those names with gensyms, and to identify free variables in the macro definition and make sure those names are looked up in the scope of the macro definition instead of the scope where the macro was used.
Literal objects
In some languages the expansion of a macro does not need to correspond to textual code; rather than expanding to an expression containing the symbol f, a macro may produce an expansion containing the actual object referred to by f. Similarly if the macro needs to use local variables or objects defined in the macro's package, it can expand to an invocation of a closure object whose enclosing lexical environment is that of the macro definition.

Implementations

Macro systems that automatically enforce hygiene originated with Scheme. The original algorithm (KFFD algorithm) for a hygienic macro system was presented by Kohlbecker in '86.[3] At the time, no standard macro system was adopted by Scheme implementations. Shortly thereafter in '87, Kohlbecker and Wand proposed a declarative pattern-based language for writing macros, which was the predecessor to the syntax-rules macro facility adopted by the R5RS standard.[1][5] Syntactic closures, an alternative hygiene mechanism, was proposed as an alternative to Kohlbecker et al.'s system by Bawden and Rees in '88.[6] Unlike the KFFD algorithm, syntactic closures require the programmer to explicitly specify the resolution of the scope of an identifier. In 1993, Dybvig et al. introduced the syntax-case macro system, which uses an alternative representation of syntax and maintains hygiene automatically.[7] The syntax-case system can express the syntax-rules pattern language as a derived macro.

The term macro system can be ambiguous because, in the context of Scheme, it can refer to both a pattern-matching construct (e.g., syntax-rules) and a framework for representing and manipulating syntax (e.g., syntax-case, syntactic closures). Syntax-rules is a high-level pattern matching facility that attempts to make macros easier to write. However, syntax-rules is not able to succinctly describe certain classes of macros and is insufficient to express other macro systems. Syntax-rules was described in the R4RS document in an appendix but not mandated. Later, R5RS adopted it as a standard macro facility. Here is an example syntax-rules macro that swaps the value of two variables:

(define-syntax swap!
  (syntax-rules ()
    ((_ a b)
     (let ((temp a))
       (set! a b)
       (set! b temp)))))

Due to the deficiencies of a purely syntax-rules based macro system, low-level macro systems have also been proposed and implemented for Scheme. Syntax-case is one such system. Unlike syntax-rules, syntax-case contains both a pattern matching language and a low-level facility for writing macros. The former allows macros to be written declaratively, while the latter allows the implementation of alternative frontends for writing macros. The swap example from before is nearly identical in syntax-case because the pattern matching language is similar:

(define-syntax swap!
  (lambda (stx)
    (syntax-case stx ()
      ((_ a b)
       (syntax
        (let ((temp a))
          (set! a b)
          (set! b temp)))))))

However, syntax-case is more powerful than syntax-rules. For example, syntax-case macros can specify side-conditions on its pattern matching rules via arbitrary Scheme functions. Alternatively, a macro writer can choose not to use the pattern matching frontend and manipulate the syntax directly. Using the datum->syntax function, syntax-case macros can also intentionally capture identifiers, thus breaking hygiene. The R6RS Scheme standard adopted the syntax-case macro system.[8]

Syntactic closures and explicit renaming[9] are two other alternative macro systems. Both systems are lower-level than syntax-rules and leave the enforcement of hygiene to the macro writer. This differs from both syntax-rules and syntax-case, which automatically enforce hygiene by default. The swap examples from above are shown here using a syntactic closure and explicit renaming implementation respectively:

;; syntactic closures
(define-syntax swap!
   (sc-macro-transformer
    (lambda (form environment)
      (let ((a (close-syntax (cadr form) environment))
            (b (close-syntax (caddr form) environment)))
        `(let ((temp ,a))
           (set! ,a ,b)
           (set! ,b temp))))))

;; explicit renaming
(define-syntax swap!
 (er-macro-transformer
  (lambda (form rename compare)
    (let ((a (cadr form))
          (b (caddr form))
          (temp (rename 'temp)))
      `(,(rename 'let) ((,temp ,a))
           (,(rename 'set!) ,a ,b)
           (,(rename 'set!) ,b ,temp))))))

Languages with hygienic macro systems

See also

Notes

  1. 1 2 Richard Kelsey; William Clinger; Jonathan Rees; et al. (August 1998). "Revised5 Report on the Algorithmic Language Scheme". Higher-Order and Symbolic Computation 11 (1): 7–105. doi:10.1023/A:1010051815785.
  2. ↑ Feinberg, N.; Keene, S. E.; Matthews, R. O.; Withington, P. T. (1997), Dylan programming: an object-oriented and dynamic language, Addison Wesley Longman Publishing Co., Inc.
  3. 1 2 Kohlbecker, E.; Friedman, D. P.; Felleisen, M.; Duba, B. (1986). "Hygienic Macro Expansion" (PDF). ACM conference on LISP and functional programming.
  4. ↑ http://www.lispworks.com/documentation/HyperSpec/Body/f_gensym.htm#gensym
  5. ↑ Kohlbecker, E; Wand, M (1987). "Macro-by-example: Deriving syntactic transformations from their specifications". Symposium on Principles of Programming Languages.
  6. ↑ Bawden, A; Rees, J (1988). "Syntactic closures". Lisp and Functional Programming.
  7. ↑ Dybvig, K; Hieb, R; Bruggerman, C (1993). "Syntactic abstraction in Scheme" (PDF). Lisp and Symbolic Computation.
  8. ↑ Sperber, Michael; Dybvig, R. Kent; Flatt, Matthew; Van Straaten, Anton; et al. (August 2007). "Revised6 Report on the Algorithmic Language Scheme (R6RS)". Scheme Steering Committee. Retrieved 2011-09-13.
  9. ↑ Clinger, Will (1991). "Hygienic macros through explicit renaming". ACM SIGPLAN Lisp Pointers.
  10. ↑ Skalski, K.; Moskal, M; Olszta, P, Metaprogramming in Nemerle (PDF)
  11. ↑ http://elixir-lang.org/getting-started/meta/macros.html#macros-hygiene
  12. ↑ http://docs.julialang.org/en/latest/manual/metaprogramming/#hygiene
  13. ↑ http://perlcabal.org/syn/S06.html#Macros

References

This article is issued from Wikipedia - version of the Friday, May 06, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.