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)) ,@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)) ,@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
Afficher les réponses par date
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Hi Per,
On 20-03-12 20:34, Per Eckerdal wrote:
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.
Indeed.
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
According to that paper, symbol macros aka identifier macros are needed to make this work.
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.
Almost stopped reading after that last sentence there!
Auto-aliasing bindings
Fortunately then my eye caught sight of the below and I continued reading...
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.
I would love to hear what you think about this.
I would be interested in knowing how this proposal compares with implementing a low-level hygienic macro system such as syntactic closures or explicit renaming macros. Actually now that I said that this proposal sounds very much like a (partial?) implementation of explicit renaming macros on top of the defmacro system. Doesn't the paper you referenced mention something like that as well?
Marijn
Hallo,
On Mon, Mar 26, 2012 at 6:01 PM, Marijn hkBst@gentoo.org wrote:
I would be interested in knowing how this proposal compares with implementing a low-level hygienic macro system such as syntactic closures or explicit renaming macros. Actually now that I said that this proposal sounds very much like a (partial?) implementation of explicit renaming macros on top of the defmacro system. Doesn't the paper you referenced mention something like that as well?
I would rather have syntactic closures as well. The paper contribution seems to be focused on the fact that it's possible to write hygienic macros on top of unhygienic macros and symbol macros, which is what Common Lisp has. Besides it says that a code walker is not needed, but that is not a necessity if the macro system would be integrated in Gambit.
Cheers,
Hi,
On Monday 26 March 2012 at 18:10, Alex Queiroz wrote:
On Mon, Mar 26, 2012 at 6:01 PM, Marijn <hkBst@gentoo.org (mailto:hkBst@gentoo.org)> wrote:
I would be interested in knowing how this proposal compares with implementing a low-level hygienic macro system such as syntactic closures or explicit renaming macros. Actually now that I said that this proposal sounds very much like a (partial?) implementation of explicit renaming macros on top of the defmacro system. Doesn't the paper you referenced mention something like that as well?
I would rather have syntactic closures as well.
Syntactic closures are much more complex, both conceptually and in practise to implement. The purpose of the designed outlined in this proposal is to not require to augment the language with a highly complex new identifier type that is distinct from symbols.
With this proposal, no new data type is required. You can write macros that only accept pure s-expressions (as they are parsed) as input, and only return pure s-expressions (that are pretty-printable without losing information, so it's easy to understand exactly what the return value means)
The paper contribution seems to be focused on the fact that it's possible to write hygienic macros on top of unhygienic macros and symbol macros, which is what Common Lisp has. Besides it says that a code walker is not needed, but that is not a necessity if the macro system would be integrated in Gambit.
It is true that the paper is written in that context. I believe its ideas are more broadly applicable than what the paper describes.
Cheers,
Per
Looks like the only necessary primitive is something like ##namespace-resolve which takes an symbol as the argument and return a full current-namespace#symbol as the result. Then we can build the whole "alias" based system with it.
Does gambit have it internal?
Meng
On Tue, Mar 27, 2012 at 12:31 AM, Per Eckerdal per.eckerdal@gmail.comwrote:
Hi,
On Monday 26 March 2012 at 18:10, Alex Queiroz wrote:
On Mon, Mar 26, 2012 at 6:01 PM, Marijn hkBst@gentoo.org wrote:
I would be interested in knowing how this proposal compares with implementing a low-level hygienic macro system such as syntactic closures or explicit renaming macros. Actually now that I said that this proposal sounds very much like a (partial?) implementation of explicit renaming macros on top of the defmacro system. Doesn't the paper you referenced mention something like that as well?
I would rather have syntactic closures as well.
Syntactic closures are much more complex, both conceptually and in practise to implement. The purpose of the designed outlined in this proposal is to not require to augment the language with a highly complex new identifier type that is distinct from symbols.
With this proposal, no new data type is required. You can write macros that only accept pure s-expressions (as they are parsed) as input, and only return pure s-expressions (that are pretty-printable without losing information, so it's easy to understand exactly what the return value means)
The paper contribution seems to be focused on the fact that it's possible to write hygienic macros on top of unhygienic macros and symbol macros, which is what Common Lisp has. Besides it says that a code walker is not needed, but that is not a necessity if the macro system would be integrated in Gambit.
It is true that the paper is written in that context. I believe its ideas are more broadly applicable than what the paper describes.
Cheers,
Per
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On Wednesday 28 March 2012 at 04:08, Meng Zhang wrote:
Looks like the only necessary primitive is something like ##namespace-resolve which takes an symbol as the argument and return a full current-namespace#symbol as the result. Then we can build the whole "alias" based system with it.
Well… while it is possible to do with only a ##namespace-resolve form (assuming that the namespace expansion process is indeed part of the macro expansion process and not processed strictly before or after the macros), building the system with only that would not result in a particularly smoothly functioning system. It really depends on how well you want the system to work.
To work well, all code that uses macros that use |alias| must use the auto-aliasing binding forms. Doing the auto-aliasing automatically and involuntarily, in Gambit core, would remove the requirement of all code, even code that does not directly use hygiene features, to import a special "hygiene" macro package.
Also, while the generalized (quasiquote-ish) alias could be implemented outside of Gambit core, it just seems wasteful, since it would have to reimplement much of the quasiquote machinery. Doing the same in Gambit core ought to be quite easy, because all of the functionality is already there.
I've thought some more about the requirement that all globals must have a namespace prefix, and I don't think it's strictly necessary if you have auto-aliasing. It doesn't really solve any name clash problems anyways. But if you don't have a namespace prefix on all globals, you need a way to refer to names without a prefix. An easy solution would be to have |#car| refer to the non namespace prefixed (standard) car function.
The reason that one must allow something like |#car| is that (alias car) must be able to expand do |#car|, having (alias car) expand into car would be unhygienic.
The main drawback of allowing prefix-less global names is that it requires *all* local bindings to be renamed by the auto aliasing, because you can't predict if a local binding will shadow a global one. If all globals had a namespace prefix, auto aliasing would only have to rename bindings that shadow other local bindings, which is fairly rare. This would result in prettier macroexpanded code.
The main advantage of not requiring all globals to have a namespace prefix is that it works better with the way Gambit works now, which I think is important.
To summarize: It would be possible to implement this system with only a ##namespace-resolve form, but I think this system would work best if three things were added to Gambit core:
1. The |alias| form, including the generalized quasiquote functionality. 2. Do auto-aliasing in Gambit core. Even ##let and friends should do it, there should be no way of avoiding it. Local bindings with namespace prefixes, like (let ((a#b 'a)) …) should be disallowed because it introduces unhygiene (and I can't imagine a situation where that type of unhygiene would be helpful). 3. Let symbols prefixed with only a # refer to symbols without namespace prefix, ie |#car| should be equivalent to the current system's (##let () (##namespace ("" car)) car). The fact that #car is not valid Scheme syntax (you have to write |#car|) doesn't really matter, since it would only be done indirectly through the alias form most of the time anyways.
Best,
Per Eckerdal
Den 30 mars 2012 15:39 skrev Per Eckerdal per.eckerdal@gmail.com:
The main drawback of allowing prefix-less global names is that it requires *all* local bindings to be renamed by the auto aliasing, because you can't predict if a local binding will shadow a global one. If all globals had a namespace prefix, auto aliasing would only have to rename bindings that shadow other local bindings, which is fairly rare. This would result in prettier macroexpanded code.
Very nice post. Can you give an example that illustrates what you meant with this paragraph?
On Friday 30 March 2012 at 15:30, Mikael wrote:
Den 30 mars 2012 15:39 skrev Per Eckerdal <per.eckerdal@gmail.com (mailto:per.eckerdal@gmail.com)>:
The main drawback of allowing prefix-less global names is that it requires *all* local bindings to be renamed by the auto aliasing, because you can't predict if a local binding will shadow a global one. If all globals had a namespace prefix, auto aliasing would only have to rename bindings that shadow other local bindings, which is fairly rare. This would result in prettier macroexpanded code.
Very nice post. Can you give an example that illustrates what you meant with this paragraph?
Consider the following code:
ten-times.scm:
(define a-name 10)
ten-times#.scm:
(define-macro (ten-times code) (let ((loop (gensym)) (i (gensym))) (alias (let ,loop ((,i a-name)) (if (positive? ,i) (begin ,code (,loop (+ ,i 1))))))))
main.scm:
(##include "ten-times#.scm")
(let ((a-name 5)) (execute-ten-times ;; A macro defined somewhere else (println "Five is " a-name)))
(This is, if memory serves me, the way separate compilation and macros are normally done in Gambit today)
Let's compile this program
gsc -c ten-times.scm gsc -c main.scm gsc -o a.out -exe ten-times.c main.c
The |a-name| global in ten-times.scm will not have any prefix, because the file does not contain any namespace declaration.
The |a-name| local binding in main.scm will not have any prefix, because the compiler does not know anything about any global or local in the current scope named |a-name| so it believes it's safe to not prefix that particular local binding.
This results in unhygiene, and the program will only print five lines, instead of the intended ten.
Because of this, all local bindings must be prefixed by auto-aliasing, even ones that seemingly don't require it, because there is no way to predict if a local binding will shadow a global one.
If auto-aliasing would rename all local bindings, this code would work. There would still be name clash hazards, but those name clash issues only happen with globals, and are present in Gambit already.
Regards,
Per
Hi Marijin,
On Monday 26 March 2012 at 18:01, Marijn wrote:
According to that paper, symbol macros aka identifier macros are needed to make this work.
Yes, some form of symbol macros are required to make it work. Gambit's namespace mechanism is similar to symbol macros, and is actually sufficient.
In fact, in my experiments with this type of macro system, I have found that it is easier to reason about the hygienic properties of the system if you have a limited symbol macro system, one where symbols must expand to "qualified" symbols, and where only "non-qualified" symbols can be declared as symbol macros. Which is exactly how Gambit's namespace system works.
So Gambit's namespace system is in a sense even better than symbol macros for this particular purpose.
To work, the namespace mechanism has to run as part of (as opposed to before or after) the macro expander, that is, namespace "expansions" have to be able to happen in between macro invocations. I'm not sure if it works like that right now, but it should be possible to change it if it doesn't.
To make this possible, defining a name that is already defined must be disallowed. I would make it a compilation error.
Almost stopped reading after that last sentence there!
Oops. I should have been clearer.
I would love to hear what you think about this.
I would be interested in knowing how this proposal compares with implementing a low-level hygienic macro system such as syntactic closures or explicit renaming macros. Actually now that I said that this proposal sounds very much like a (partial?) implementation of explicit renaming macros on top of the defmacro system. Doesn't the paper you referenced mention something like that as well?
I am familiar with syntactic closures, since that's what Black Hole's macro system is based on. I am less familiar with explicit renaming, but I think the same applies to them:
Syntactic closures (the type of object returned by |make-syntactic-closure|) are a special form of identifier, one that is not a symbol; it's a symbol (or sexp) together with some opaque information about the hygienic environment. Syntactic closures can not be compared like symbols (because they aren't symbols), you have to use a special |identifier=?| function.
In a similar way, explicit renaming requires you to compare identifiers with a special comparison predicate.
So: Both explicit renaming and syntactic closures introduce some kind of new, opaque object type for identifiers; symbols are not enough.
The system in this proposal does not require a separate "identifier" type; plain symbols are enough. In my opinion this makes the system much easier to reason about, I find it quite difficult to understand the concept of passing around hygienic environments as first class values.
This was what I was talking about when I said this in the summary: "[The system] has semantics that is very easy to reason about and does not introduce any fundamentally new concepts [symbols are no longer the only type of identifier] to the language"
Regards,
Per
Hi Per,
What's |alias|' scope - just to doublecheck I got your point, is it, that it expands the passed identifier to the fully qualified name form (i.e. the complete and non-overlappable form), of the identifier with that name that is defined the most closely upwards in the lexical scope from the point where |alias| is used?
I suppose that's how it is. So the following
(define a 0) (alias a) (define a -1) (alias a) (let ((a 0)) (define-macro (somename) (alias a)) (define a 1) (define-macro (somename) (alias a) (let ((a 2)) (alias a)))) (define a 3) (define-macro (b) (alias a)) (let ((a 4)) (alias a) (b))))
would expand to (a functional equivalent of)
(define 0#a 0) 0#a (define 1#a -1) 1#a (let ((2#a 0)) (define-macro (somename) 2#a) (define 3#a 1) (define-macro (somename) 3#a (let ((4#a 2)) 4#a))) (define 5#a 3) (define-macro (somename) 5#a) (let ((6#a 4)) 6#a 5#a)))
?
Are there any key aspects of |alias|' renaming function that the above example does not illustrate, if so which?
And thus, we get a mechanism for syntax-rules-style hygiene i.e.
; (Here neither cons nor error are overlapped, but Gambit's defaults) (define-syntax real-cons (syntax-rules () ((real-cons a b) (cons a b)))) (define cons error) (real-cons 1 2)
can as well be written
; (Here neither cons nor error are overlapped, but Gambit's defaults) (define-macro (real-cons a b) `(,(alias cons) ,a ,b)) (define cons error) (real-cons 1 2)
, both expanding to (a functional equivalent of)
(define 2#cons #error) ; #error as in, Gambit's standard |error| (#cons 1 2) ; #cons as in, Gambit's standard |cons|
Correct?
Mikael
Den 20 mars 2012 21:34 skrev Per Eckerdal per.eckerdal@gmail.com:
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)) ,@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:
- When writing macros, use gensym to avoid unintentional variable capture
wherever necessary and possible.
- 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)).
- 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)) ,@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
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On Saturday 31 March 2012 at 13:23, Mikael wrote:
Hi Per,
What's |alias|' scope - just to doublecheck I got your point, is it, that it expands the passed identifier to the fully qualified name form (i.e. the complete and non-overlappable form), of the identifier with that name that is defined the most closely upwards in the lexical scope from the point where |alias| is used?
Yeah.. I think that's right. |alias| uses the same scope as where the form is written.
I suppose that's how it is. So the following
(define a 0) (alias a) (define a -1) (alias a) (let ((a 0)) (define-macro (somename) (alias a)) (define a 1) (define-macro (somename) (alias a) (let ((a 2)) (alias a)))) (define a 3) (define-macro (b) (alias a)) (let ((a 4)) (alias a) (b))))
would expand to (a functional equivalent of)
(define 0#a 0) 0#a (define 1#a -1) 1#a (let ((2#a 0)) (define-macro (somename) 2#a) (define 3#a 1) (define-macro (somename) 3#a (let ((4#a 2)) 4#a))) (define 5#a 3) (define-macro (somename) 5#a) (let ((6#a 4)) 6#a 5#a)))
?
Almost, but not quite. Duplicate definitions on the top level in the REPL should overwrite each other, not create separate bindings. So if you're in the "mod#" namespace, both top level definitions of a should expand into (define mod#a …). This is consistent with Gambit's current behavior.
Multiple defines of the same variable name within a scope, like 3#a and 5#a in your example, is not legal Scheme. If Black Hole allows this syntax, it's a bug in Black Hole. Gambit rejects the code with a "Duplicate definition of a variable" message.
Other than that, yes, that's how it should work.
Are there any key aspects of |alias|' renaming function that the above example does not illustrate, if so which?
No. The rules are really simple. The cases that you bring up that are non-obvious are not legal Scheme, so they don't need to be considered.
And thus, we get a mechanism for syntax-rules-style hygiene i.e.
; (Here neither cons nor error are overlapped, but Gambit's defaults) (define-syntax real-cons (syntax-rules () ((real-cons a b) (cons a b)))) (define cons error) (real-cons 1 2)
can as well be written
; (Here neither cons nor error are overlapped, but Gambit's defaults) (define-macro (real-cons a b) `(,(alias cons) ,a ,b)) (define cons error) (real-cons 1 2)
, both expanding to (a functional equivalent of)
(define 2#cons #error) ; #error as in, Gambit's standard |error| (#cons 1 2) ; #cons as in, Gambit's standard |cons|
Correct?
Yes, both the syntax-rules macro and the define-macro macro would be equivalent (possibly except for error handling and source code location information).
Your statement about this being syntax-rules-style hygiene isn't really correct, though: One of the main points with syntax-rules is that you don't need gensym. With this macro system, you still need to explicitly use gensym.
The reason for this is that you can't use |alias| when you bind names:
(define-macro (mac code) `(,(alias let) ((,(alias a) 'a)) ,code ,(alias a)))
The code snippet above isn't necessarily hygienic. You need gensyms for hiding any names that macros bind. And AFAIK there is no way of doing that automatically with this system: For that you need to introduce a new identifier data type, like syntactic closures, explicit renaming and syntax-case do.
Per
-
Alex Queiroz -
Marijn -
Meng Zhang -
Mikael -
Per Eckerdal