source: project/wiki/syntactic-closures @ 4636

Last change on this file since 4636 was 4636, checked in by Jim Ursetto, 13 years ago

Changes applied for zbigniew (67.167.53.235) through svnwiki:

syntactic-closures: mention er-macro-transformer and rsc-macro-transformer on the wiki page

File size: 19.4 KB
Line 
1[[tags: egg]]
2
3== syntactic-closures
4
5An implementation of {{syntax-rules}} and a hygienic low-level
6macro system.
7
8This extension provides {{sc-macro-transformer}}, described below; {{er-macro-transformer}}, as described in ''Hygienic Macros Through Explicit Renaming'' by Will Clinger; and {{rsc-macro-transformer}}, which is like {{sc-macro-transformer}} but with the usage and transformer environments swapped.
9
10=== Usage
11
12 (require-extension syntactic-closures)
13
14== Documentation
15
16                   A Syntactic Closures Macro Facility
17                             by Chris Hanson
18                             9 November 1991
19
20   This document describes "syntactic closures", a low-level macro
21 facility for the Scheme programming language.  The facility is an
22 alternative to the low-level macro facility described in the `Revised^4
23 Report on Scheme.' This document is an addendum to that report.
24
25   The syntactic closures facility extends the BNF rule for TRANSFORMER
26 SPEC to allow a new keyword that introduces a low-level macro
27 transformer:
28
29      TRANSFORMER SPEC := (sc-macro-transformer EXPRESSION)
30
31   Additionally, the following procedures are added:
32      make-syntactic-closure
33      capture-syntactic-environment
34      identifier?
35      identifier=?
36
37   The description of the facility is divided into three parts.  The
38 first part defines basic terminology.  The second part describes how
39 macro transformers are defined.  The third part describes the use of
40 "identifiers", which extend the syntactic closure mechanism to be
41 compatible with `syntax-rules'.
42
43 3.5.1.1 Terminology
44 ...................
45
46 This section defines the concepts and data types used by the syntactic
47 closures facility.
48
49    * "Forms" are the syntactic entities out of which programs are
50      recursively constructed.  A form is any expression, any
51      definition, any syntactic keyword, or any syntactic closure.  The
52      variable name that appears in a `set!' special form is also a
53      form.  Examples of forms:
54
55           17
56           #t
57           car
58           (+ x 4)
59           (lambda (x) x)
60           (define pi 3.14159)
61           if
62           define
63
64    * An "alias" is an alternate name for a given symbol.  It can appear
65      anywhere in a form that the symbol could be used, and when quoted
66      it is replaced by the symbol; however, it does not satisfy the
67      predicate `symbol?'.  Macro transformers rarely distinguish
68      symbols from aliases, referring to both as identifiers.
69
70    * A "syntactic" environment maps identifiers to their meanings.
71      More precisely, it determines whether an identifier is a syntactic
72      keyword or a variable.  If it is a keyword, the meaning is an
73      interpretation for the form in which that keyword appears.  If it
74      is a variable, the meaning identifies which binding of that
75      variable is referenced.  In short, syntactic environments contain
76      all of the contextual information necessary for interpreting the
77      meaning of a particular form.
78
79    * A "syntactic closure" consists of a form, a syntactic environment,
80      and a list of identifiers.  All identifiers in the form take their
81      meaning from the syntactic environment, except those in the given
82      list.  The identifiers in the list are to have their meanings
83      determined later.  A syntactic closure may be used in any context
84      in which its form could have been used.  Since a syntactic closure
85      is also a form, it may not be used in contexts where a form would
86      be illegal.  For example, a form may not appear as a clause in the
87      cond special form.  A syntactic closure appearing in a quoted
88      structure is replaced by its form.
89
90
91 3.5.1.2 Transformer Definition
92 ..............................
93
94 This section describes the `sc-macro-transformer' special form and the
95 procedures `make-syntactic-closure' and `capture-syntactic-environment'.
96
97  -- Syntax: transformer expression
98      Syntax: It is an error if this syntax occurs except as a
99      TRANSFORMER SPEC.
100
101      Semantics: The EXPRESSION is evaluated in the standard transformer
102      environment to yield a macro transformer as described below.  This
103      macro transformer is bound to a macro keyword by the special form
104      in which the `sc-macro-transformer' expression appears (for example,
105      `let-syntax').
106
107      A "macro transformer" is a procedure that takes two arguments, a
108      form and a syntactic environment, and returns a new form.  The
109      first argument, the "input form", is the form in which the macro
110      keyword occurred.  The second argument, the "usage environment",
111      is the syntactic environment in which the input form occurred.
112      The result of the transformer, the "output form", is automatically
113      closed in the "transformer environment", which is the syntactic
114      environment in which the `sc-macro-transformer' expression occurred.
115
116      For example, here is a definition of a push macro using
117      `syntax-rules':
118
119           (define-syntax  push
120             (syntax-rules ()
121               ((push item list)
122                (set! list (cons item list)))))
123
124      Here is an equivalent definition using `sc-macro-transformer':
125           (define-syntax push
126             (sc-macro-transformer
127              (lambda (exp env)
128                (let ((item
129                       (make-syntactic-closure env '() (cadr exp)))
130                      (list
131                       (make-syntactic-closure env '() (caddr exp))))
132                  `(set! ,list (cons ,item ,list))))))
133
134      In this example, the identifiers `set!' and `cons' are closed in
135      the transformer environment, and thus will not be affected by the
136      meanings of those identifiers in the usage environment `env'.
137
138      Some macros may be non-hygienic by design.  For example, the
139      following defines a loop macro that implicitly binds `exit' to an
140      escape procedure.  The binding of `exit' is intended to capture
141      free references to `exit' in the body of the loop, so `exit' must
142      be left free when the body is closed:
143
144           (define-syntax loop
145             (sc-macro-transformer
146              (lambda (exp env)
147                (let ((body (cdr exp)))
148                  `(call-with-current-continuation
149                    (lambda (exit)
150                      (let f ()
151                        ,@(map (lambda  (exp)
152                                  (make-syntactic-closure env '(exit)
153                                                          exp))
154                                body)
155                        (f))))))))
156
157      To assign meanings to the identifiers in a form, use
158      `make-syntactic-closure' to close the form in a syntactic
159      environment.
160
161  -- Function: make-syntactic-closure environment free-names form
162      ENVIRONMENT must be a syntactic environment, FREE-NAMES must be a
163      list of identifiers, and FORM must be a form.
164      `make-syntactic-closure' constructs and returns a syntactic closure
165      of FORM in ENVIRONMENT, which can be used anywhere that FORM could
166      have been used.  All the identifiers used in FORM, except those
167      explicitly excepted by FREE-NAMES, obtain their meanings from
168      ENVIRONMENT.
169
170      Here is an example where FREE-NAMES is something other than the
171      empty list.  It is instructive to compare the use of FREE-NAMES in
172      this example with its use in the `loop' example above: the examples
173      are similar except for the source of the identifier being left
174      free.
175           (define-syntax let1
176             (sc-macro-transformer
177              (lambda (exp env)
178                (let ((id (cadr exp))
179                      (init (caddr exp))
180                      (exp (cadddr exp)))
181                  `((lambda (,id)
182                      ,(make-syntactic-closure env (list id) exp))
183                    ,(make-syntactic-closure env '() init))))))
184
185      `let1' is a simplified version of `let' that only binds a single
186      identifier, and whose body consists of a single expression.  When
187      the body expression is syntactically closed in its original
188      syntactic environment, the identifier that is to be bound by
189      `let1' must be left free, so that it can be properly captured by
190      the `lambda' in the output form.
191
192      To obtain a syntactic environment other than the usage
193      environment, use `capture-syntactic-environment'.
194
195  -- Function: capture-syntactic-environment procedure
196      `capture-syntactic-environment' returns a form that will, when
197      transformed, call PROCEDURE on the current syntactic environment.
198      PROCEDURE should compute and return a new form to be transformed,
199      in that same syntactic environment, in place of the form.
200
201      An example will make this clear.  Suppose we wanted to define a
202      simple `loop-until' keyword equivalent to
203
204           (define-syntax loop-until
205             (syntax-rules ()
206               ((loop-until id init test return step)
207                (letrec ((loop
208                          (lambda (id)
209                            (if test return (loop step)))))
210                  (loop init)))))
211
212      The following attempt at defining `loop-until' has a subtle bug:
213           (define-syntax loop-until
214             (sc-macro-transformer
215              (lambda (exp env)
216                (let ((id (cadr exp))
217                      (init (caddr exp))
218                      (test (cadddr exp))
219                      (return (cadddr (cdr exp)))
220                      (step (cadddr (cddr exp)))
221                      (close
222                       (lambda (exp free)
223                         (make-syntactic-closure env free exp))))
224                  `(letrec ((loop
225                             (lambda (,id)
226                               (if ,(close test (list id))
227                                   ,(close return (list id))
228                                   (loop ,(close step (list id)))))))
229                     (loop ,(close init '())))))))
230
231      This definition appears to take all of the proper precautions to
232      prevent unintended captures.  It carefully closes the
233      subexpressions in their original syntactic environment and it
234      leaves the `id' identifier free in the `test', `return', and
235      `step' expressions, so that it will be captured by the binding
236      introduced by the `lambda' expression.  Unfortunately it uses the
237      identifiers `if' and `loop' within that `lambda' expression, so if
238      the user of `loop-until' just happens to use, say, `if' for the
239      identifier, it will be inadvertently captured.
240
241      The syntactic environment that `if' and `loop' want to be exposed
242      to is the one just outside the `lambda' expression: before the
243      user's identifier is added to the syntactic environment, but after
244      the identifier loop has been added.
245      `capture-syntactic-environment' captures exactly that environment
246      as follows:
247
248           (define-syntax loop-until
249             (sc-macro-transformer
250              (lambda (exp env)
251                (let ((id (cadr exp))
252                      (init (caddr exp))
253                      (test (cadddr exp))
254                      (return (cadddr (cdr exp)))
255                      (step (cadddr (cddr exp)))
256                      (close
257                       (lambda (exp free)
258                         (make-syntactic-closure env free exp))))
259                  `(letrec ((loop
260                             ,(capture-syntactic-environment
261                               (lambda (env)
262                                 `(lambda (,id)
263                                    (,(make-syntactic-closure env '() `if)
264                                     ,(close test (list id))
265                                     ,(close return (list id))
266                                     (,(make-syntactic-closure env '()
267                                                               `loop)
268                                      ,(close step (list id)))))))))
269                     (loop ,(close init '())))))))
270
271      In this case, having captured the desired syntactic environment,
272      it is convenient to construct syntactic closures of the
273      identifiers `if' and the `loop' and use them in the body of the
274      `lambda'.
275
276      A common use of `capture-syntactic-environment' is to get the
277      transformer environment of a macro transformer:
278
279           (sc-macro-transformer
280            (lambda (exp env)
281              (capture-syntactic-environment
282               (lambda (transformer-env)
283                 ...))))
284
285 3.5.1.3 Identifiers
286 ...................
287
288 This section describes the procedures that create and manipulate
289 identifiers.  Previous syntactic closure proposals did not have an
290 identifier data type - they just used symbols.  The identifier data
291 type extends the syntactic closures facility to be compatible with the
292 high-level `syntax-rules' facility.
293
294   As discussed earlier, an identifier is either a symbol or an "alias".
295 An alias is implemented as a syntactic closure whose "form" is an
296 identifier:
297
298      (make-syntactic-closure env '() 'a)
299         => an "alias"
300
301   Aliases are implemented as syntactic closures because they behave just
302 like syntactic closures most of the time.  The difference is that an
303 alias may be bound to a new value (for example by `lambda' or
304 `let-syntax'); other syntactic closures may not be used this way.  If
305 an alias is bound, then within the scope of that binding it is looked
306 up in the syntactic environment just like any other identifier.
307
308   Aliases are used in the implementation of the high-level facility
309 `syntax-rules'.  A macro transformer created by `syntax-rules' uses a
310 template to generate its output form, substituting subforms of the
311 input form into the template.  In a syntactic closures implementation,
312 all of the symbols in the template are replaced by aliases closed in
313 the transformer environment, while the output form itself is closed in
314 the usage environment.  This guarantees that the macro transformation
315 is hygienic, without requiring the transformer to know the syntactic
316 roles of the substituted input subforms.
317
318  -- Function: identifier? object
319      Returns `#t' if OBJECT is an identifier, otherwise returns `#f'.
320      Examples:
321
322           (identifier? 'a)
323              => #t
324           (identifier? (make-syntactic-closure env '() 'a))
325              => #t
326           (identifier? "a")
327              => #f
328           (identifier? #\a)
329              => #f
330           (identifier? 97)
331              => #f
332           (identifier? #f)
333              => #f
334           (identifier? '(a))
335              => #f
336           (identifier? '#(a))
337              => #f
338
339      The predicate `eq?' is used to determine if two identifers are
340      "the same".  Thus `eq?' can be used to compare identifiers exactly
341      as it would be used to compare symbols.  Often, though, it is
342      useful to know whether two identifiers "mean the same thing".  For
343      example, the `cond' macro uses the symbol `else' to identify the
344      final clause in the conditional.  A macro transformer for `cond'
345      cannot just look for the symbol `else', because the `cond' form
346      might be the output of another macro transformer that replaced the
347      symbol `else' with an alias.  Instead the transformer must look
348      for an identifier that "means the same thing" in the usage
349      environment as the symbol `else' means in the transformer
350      environment.
351
352  -- Function: identifier=? environment1 identifier1 environment2
353           identifier2
354      ENVIRONMENT1 and ENVIRONMENT2 must be syntactic environments, and
355      IDENTIFIER1 and IDENTIFIER2 must be identifiers.  `identifier=?'
356      returns `#t' if the meaning of IDENTIFIER1 in ENVIRONMENT1 is the
357      same as that of IDENTIFIER2 in ENVIRONMENT2, otherwise it returns
358      `#f'.  Examples:
359
360           (let-syntax
361               ((foo
362                 (sc-macro-transformer
363                  (lambda (form env)
364                    (capture-syntactic-environment
365                     (lambda (transformer-env)
366                       (identifier=? transformer-env 'x env 'x)))))))
367             (list (foo)
368                   (let ((x 3))
369                     (foo))))
370              => (#t #f)
371
372           (let-syntax ((bar foo))
373             (let-syntax
374                 ((foo
375                   (sc-macro-transformer
376                    (lambda (form env)
377                      (capture-syntactic-environment
378                       (lambda (transformer-env)
379                         (identifier=? transformer-env 'foo
380                                       env (cadr form))))))))
381               (list (foo foo)
382                     (foobar))))
383              => (#f #t)
384
385 The syntactic closures facility was invented by Alan Bawden and Jonathan
386 Rees.  The use of aliases to implement `syntax-rules' was invented by
387 Alan Bawden (who prefers to call them "synthetic names").  Much of this
388 proposal is derived from an earlier proposal by Alan Bawden.
389
390=== Authors
391
392Alan Bawden and Chris Hanson, ported to CHICKEN by Taylor Campbell and [[felix winkelmann]]
393
394=== License
395
396Copyright (c) 1989-91 Massachusetts Institute of Technology
397
398This material was developed by the Scheme project at the
399Massachusetts Institute of Technology, Department of Electrical
400Engineering and Computer Science.  Permission to copy and modify
401this software, to redistribute either the original software or a
402modified version, and to use this software for any purpose is
403granted, subject to the following restrictions and understandings.
404
4051. Any copy made of this software must include this copyright
406notice in full.
407
4082. Users of this software agree to make their best efforts (a) to
409return to the MIT Scheme project any improvements or extensions
410that they make, so that these may be included in future releases;
411and (b) to inform MIT of noteworthy uses of this software.
412
4133. All materials developed as a consequence of the use of this
414software shall duly acknowledge such use, in accordance with the
415usual standards of acknowledging credit in academic research.
416
4174. MIT has made no warranty or representation that the operation
418of this software will be error-free, and MIT is under no
419obligation to provide any services, by way of maintenance, update,
420or otherwise.
421
4225. In conjunction with products arising from the use of this
423material, there shall be no use of the name of the Massachusetts
424Institute of Technology nor of any adaptation thereof in any
425advertising, promotional, or sales literature without prior
426written consent from MIT in each case.
427
428=== History
429
430; 0.983 : added curried {{define}} (zbigniew)
431; 0.982 : added {{rsc-macro-transformer}}; {{define-macro}} now non-hygienic (zbigniew)
432; 0.981 : added {{optional}} as a replacement for {{:optional}}
433; 0.98 : uses hygienic implementation of {{condition-case}}
434; 0.97 : bugfix by Taylor Campbell
435; 0.96 : {{define-record-type}} doesn't bind record identifier anymore
436; 0.95 : fixed bug in {{let-optionals}}
437; 0.94 : empty list isn't quoted by default anymore
438; 0.93 : added {{fluid-let}}
439; 0.92 : {{include}} shows message in verbose mode
440; 0.91 : renamed {{transformer}} to {{sc-macro-transformer}} for compatibility with MIT-Scheme [suggested by Taylor Campbell]
441; 0.9 : added SRFI-17 support
442; 0.8 : removed (probably) overly restrictive check [suggested by Taylor Campbell]
443; 0.7 : added support for line-number info in debug traces by Alex Shinn
444; 0.6 : added bugfix for let-syntax by Taylor Campbell, and vector matching by Alex Shinn
445; 0.5 : added bugfix by Taylor Campbell
446; 0.4 : added {{cond-expand}}
447; 0.3 : actually works now, thanks to Taylor Campbell
448; 0.2 : added suppoer for DSSSL lambda lists (but needs {{let-optionals}} yet)
449; 0.1 : Initial release
Note: See TracBrowser for help on using the repository browser.