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

Mikael mikael.rcv at gmail.com
Sat Mar 31 07:23:37 EDT 2012


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 at 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))
>      , 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
>
>
> _______________________________________________
> Gambit-list mailing list
> Gambit-list at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20120331/b7fc30ba/attachment.htm>


More information about the Gambit-list mailing list