[gambit-list] Proposal for lightweight real hygienic macros in Gambit

Per Eckerdal per.eckerdal at gmail.com
Tue Mar 20 15:34:04 EDT 2012


Hi, 


Background

A few years ago, I started working on a module system for Gambit called Black Hole. I have still not managed to make it work well, and I do not have time to work on it right now, but my work on Black Hole has taught me quite a bit about Gambit and Scheme, and macro systems in particular.

Most of my Gambit related work has been centered around Black Hole, and I have made no attempts to push ideas in Black Hole back to Gambit, mostly because I have felt that Black Hole has a narrower scope than Gambit.

I recently realized that some of the ideas that I have stumbled upon might actually be useful for the Gambit community as a whole. This email is about one of them.


Gambit and hygienic macros

Gambit ships with a generic implementation of syntax-case hygienic macros, psyntax, but in practise it does not work very well, especially in conjunction with features that are specific to Gambit.

Marc has repeatedly stated that he does not intend to add syntax-case to the default Gambit language, not only because of the aforementioned reasons but also because it would increase the size of the Gambit system unacceptably.

syntax-case is a rather large piece of software, and is also IMO bloated conceptually. (I should add that my Black Hole system is not much better in this regard.) In fact, most Scheme macro systems that address the hygiene problem, especially the modern ones, as defined by R6RS and related systems, add a huge amount of conceptual overhead to the language.


The Gambit way of things

My impression of Gambit is that it's spirit is fairly "close-to-the-metal", being a tightly integrated system that works well on a wide variety of platforms including ones with limited resources.

The mechanisms provided by Gambit for organizing code into modules and writing macros match this thinness: |define-macro| is a very simple construct for non-hygienic macros and |##namespace| is a fairly low level tool for avoiding name clashes.


Proposal

This is more of a straw man than a proper proposal, and I am fully aware that this will probably conflict with many ideas that R7RS introduces.

This proposal is about a way of achieving hygienic macros that is far more lightweight than any other hygienic Scheme macro system that I know of. In fact, Gambit already includes most of the machinery that is required by this system.

I did not invent this technique myself. The basic idea is described here: http://www.p-cos.net/documents/hygiene.pdf

Here's a description of the two related, but separate, issues that hygienic macro systems try to solve: http://pereckerdal.com/2010/05/18/the-two-faces-of-the-hygiene-problem/ If you are not familiar with hygienic macro systems, reading this blog post might make it easier to understand this proposal.

In order to explain the concepts as clearly as possible, I will begin with explaining the core problem, then describe way to write macros with the current Gambit system that ensures hygiene, and then continue to generalize the approach.


A quick summary of the two hygiene problems

As the blog post I linked to earlier describes, there are two distinct types of unhygiene in macros. One of them can be avoided through careful use of |gemsym|, but the other cannot. Here's an illustrative example:

(define-macro (ten-times . x)
  `(let loop ((i 10))
     , at x
     (if (> i 1)
         (loop (- i 1)))))


This code defines a macro that makes a piece of code run ten times. An example use is  (ten-times (println "Hello")). The definition has two different kinds of errors in it.

The first one shows up if you try to do (let ((i "i")) (ten-times (println "The letter i: " i))). The code is intended to print "The letter i: i" ten times, but instead it counts from ten to one. This problem can be solved by replacing |i| in the macro with a gensym.

The second problem shows up if you try to do (let ((if list)) (ten-times (println "Hi"))). The code is intended to print "Hi" ten times, but instead it prints nothing.

This second problem what this proposal addresses. I think that's enough, because I don't think the "gemsym fixable" problem is that serious. Not making gensym mistakes is fairly easy, but there is no obvious way to circumvent the second problem.


Manually emulating hygiene with Gambit's current define-macro macros

With these two problems in mind, we can define three rules for writing Gambit code:

1. When writing macros, use gensym to avoid unintentional variable capture wherever necessary and possible.

2. In all code, not just macros, never lexically bind an identifier with a # in it. For instance, even though Gambit would not reject it, never write (let ((##let 3)) (code-goes-here)).

3. Qualify every function, macro or global variable that you use in a macro expansion with its namespace (that is, all names that you use must contain a #). For instance, instead of writing (define-macro (two-list a b) `(list ,a ,b)), write (define-macro (two-list a b) `(##list ,a ,b)).

If these rules are observed, you will have full hygiene.

The rest of the email is dedicated to describing how one could change Gambit to perform this process in a semi-automatic way.


This does not really work with the current version of Gambit

A minor sidetrack about how this would work with Gambit in practise:

Doing this with the current version of Gambit is not quite possible, even if you do it fully manually. The main problem is that not all of Gambit's built in functions have a version with a namespace prefix. To be able to apply this systematically, all built-in functions would have to be renamed to get a namespace prefix.

The namespace system would then make sure to expand all occurrences of eg |car| to |g#car| or something similar.

If all other names are prefixed (including local bindings), one can get away with not adding a namespace prefix to Gambit's built in functions. Black Hole works this way, but it would nicer if Gambit also followed the convention.


The alias macro

To avoid having to type namespace prefixes all over macro code, and also as a basis for further helper macros, I propose to add a new special form called |alias|. What it does is that it takes an unqualified symbol and expands it into a quoted fully qualified symbol with a namespace prefix, according to the namespace declarations that are currently in scope.

For instance, assuming that Gambit's built-in functions use the "g#" namespace and a fresh REPL:

> (alias car)
g#car
> `(,(alias if) #t 'yes 'no)
(##if #t 'yes 'no)

When writing macros, it would be used like this:

(define-macro (add a b) `(,(alias +) ,a ,b))

Note that |add| is a fully hygienic macro. The call to |+| will expand into |g#+|, which always has the same meaning. If we would have omitted |alias|, and just written |+|, the macro would not have worked in lexical environments where |+| means something different from what it means in the context where the macro is defined.

Implementing |alias| in Gambit should be trivial, since Gambit already does this transformation internally with its namespace machinery.


Restrictions on name binding

For hygiene to work, shadowing bindings must be disallowed. This code snippet illustrates the problem:

(let ((a 0))
  (define-macro (mac name) `(list ,(alias a) ,name))
  (let ((a 1))
    ;; This should return (0 1), but it will return (1 1).
    (mac a)))


To make this possible, defining a name that is already defined must be disallowed. I would make it a compilation error.


Auto-aliasing bindings

The restriction of not being allowed to bind a name that's already bound is clearly too limiting; we want the code above with the two |a|s to work.

To circumvent this, we introduce auto-aliasing to all binding language constructs. Auto-aliasing means that binding a name, for instance

(let ((a 0))
  (code-goes-here))


is internally expanded to becoming equivalent to

(let ((0#a 0))
  (##namespace "0#" a)
  (code-goes-here))


The choice of "0#" as a namespace prefix is arbitrary, any prefix could be chosen, as long as all bindings end up unique. In fact, I think it should be possible to not prefix the first occurence of each name in the scope, so that only bindings that shadow another binding is prefixed. This might reduce clutter. (Note that this only works if *all* top level bindings are namespaced, though. I'm not even sure if just looking up the name in the global namespace on macro expansion time and prefixing if a global variable with that name is found is sufficient)

Auto-aliasing should, like |alias|, be fairly straightforward to implement.

Note that it is sufficient to implement auto-aliasing in the built-in binding special forms (like let, lambda, parameterize), any user-defined macro that does name binding must use the underlying special forms and will thus automatically be auto-aliasing.

Normally, the programmer will not have to think about the auto-aliasing. The only time it will be visible is when inspecting code in the REPL/debugger. If the aliasing turns out to be too invasive, it should be possible to do some lower-level magic to properly hide this from the user. I personally think it is not without benefit to have shadow-free code: You will always be able to access all variables from the debugger.

Note that Gambit's current #!key argument implementation makes it impossible to implement auto-aliasing as a macro, because renaming keyword arguments changes the procedure's interface. But then again I have never seen code with #!key arguments that shadow each other. Simply ignoring to auto-alias #!key parameters, and emitting a compiler error when they shadow each other (according to the name binding restriction rule) might be sufficient.


Namespaces

Probably the largest difference this would do to the Gambit language is that it would require all code to specify a namespace. I'm not sure about how to best do this.

One possibility might be to implicitly prepend a |##namespace| directive to all files, with the namespace matching the file name. The file could then override the default if desired.

The REPL could have its own reserved "r#" namespace.


Generalized alias

It is possible to expand the definition of |alias| so that it can take an arbitrary s-expression as argument. The semantics would be like quasiquote, except that all symbols on the first quasiquotation level would be alias-expanded.

Some examples:

(alias +) => g#+
(alias (+ 1 2)) => (g#+ 1 2)
(alias (eq? 'a a)) => (g#eq? 'a current-namespace#a)
;; Note that quasiquote is a macro, with a corresponding g#quasiquote fully qualified name, while unquote is not actually a macro, so it does not have a fully qualified name
(alias (list 'a a `(a b ,c))) => (g#list 'a current-namespace#a (g#quasiquote a b (unquote current-namespace#c)))

|quasiquote| like functionality is nontrivial to implement, but it should be possible to implement |alias| like this by piggybacking on the |quasiquote| implementation, so it should not be that difficult to do.

Another option is to let |alias| remain as taking a single symbol as argument, and instead call the quasiquoting alias |alias-quasiquote| or something similar.

Here's a more intricate (and properly hygienic) example of the |ten-times| macro, implemented with the generalized |alias| and |gensym|:

(define-macro (ten-times . x)
  (let ((loop-gs (gensym))
        (i-gs (gensym)))
    (alias
     (let ,loop-gs ((,i-gs 10))
        , at x
        (if (> ,i-gs 1)
            (,loop-gs (- ,i-gs 1)))))))


This is how a typical macro definition will look like.

It is also possible to give |alias| a syntactic shortcut, like what has been done to quote, quasiquote and unquote.


Summary

In this email I have described a hygienic macro system that is easy to use, is very similar to the current non-hygienic system (it is, in fact, source level compatible), allows the user to choose whether to break hygiene or not, is lightweight, has semantics that is very easy to reason about and does not introduce any fundamentally new concepts to the language. Furthermore, it is very simple to implement and no special algorithmic tricks are required to implement a macro expander that takes linear time with respect to code size.

Making the changes I suggest to Gambit would make it possible and easy to write truly hygienic macros in Gambit, without compromising what I feel is the spirit of the Gambit system.

The main problem with this system is that, just like Gambit's current define-macro macros, it discards source code location information. Furthermore, writing macros that give good looking error messages on incorrect inputs is tedious. I can think of a couple of ways to work around these problems, though. But solving this is necessarily a bit complicated, so I will not discuss that here. Fortunately, these issues are orthogonal to the hygiene problem.


I would love to hear what you think about this.


Best Regards,

Per Eckerdal

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20120320/e4ae5052/attachment.htm>


More information about the Gambit-list mailing list