How to build "identifiers" with syntax-rules: define-structure as a R5RS macro
ol...@pobox.com
apparent inability to construct identifiers whose names follow a
desired pattern. For example, R5RS macros are believed to be incapable
of implementing a define-structure form, such as the one described in
the Gambit-C 3.0 manual:
<blockquote>
special form: define-structure name field...
The define-structure expands into a set of definitions of the
following procedures:
- make-name -- A k argument procedure which constructs a new record
from the value of its k fields.
- name? -- A procedure which tests if its single argument is of the
given record type.
- name-field -- For each field, a procedure taking as its single
argument a value of the given record type and returning the content of
the corresponding field of the record.
- name-field-set! -- For each field, a two argument procedure taking as
its first argument a value of the given record type. The second
argument gets assigned to the corresponding field of the record and the
void object is returned.
For example:
> (define-structure point x y color)
> (define p (make-point 3 5 'red))
> (point-x p)
3
> (point-color p)
red
> (point-color-set! p 'black)
</blockquote>
The expansion of (define-structure point x y color) contains
identifiers such as point-x and point-color-set! These identifiers did
not exist before. Furthermore, their names are _derived_ from the
arguments of the define-structure form. R5RS macros seemingly cannot
synthesize identifiers.
Sometimes we do want to write a macro whose expansion contains
identifiers with the names based off the arguments of a macro. For
example, Peter Keller wished precisely that, in the message he posted
on comp.lang.scheme on Dec 14, 2002. He received the standard reply:
parameterized identifiers are not possible in the R5RS macro system.
Aren't they really? In this message we will show how to write a
syntax-rule macro that is almost identical to Gambit's
define-structure. The field access expression looks almost the same as
(point-x p) -- with the difference of only *one* character!
Furthermore, getting and setting of the fields in our structure is
just as efficient as the corresponding operations in Gambit. Our
getters and setters are first-class values. Our define-structure is a
syntactic sugar over a define-record-type: We will rely on SRFI-9 to
actually implement record data types.
We begin with the eternal question: "What's in the name?" The name for
a field accessor such as 'point-x' stands for a value; to be more
precise, the name stands for a procedural value: a structure accessor
procedure. It is this value that we apply, store in a data structure,
pass as an argument or the result. Surely there are other ways of
referring to that value, for example, as the result of a higher-order
procedure dispatcher. To access a field 'x' of a structure 'point', we
may write
((point-dispatcher 'x) p)
((point-dispatcher 'x 'set!) 5.0)
This notation looks a bit ugly, with an extra pair of parentheses and
quotation marks. Furthermore, it involves a run-time overhead: the
dispatch to an accessor procedure is now done at run time. That's
where macros come in.
Appendix A defines these macros and two examples. The first one is:
(display "Example from Gambit-C") (newline)
(define-structure point x y color)
(let ((p (make point 3 5 'red))) ; cf (make-point 3 5 'red)
(display (point x p)) ; cf (point-x p)
(newline)
(display (point color p)) ; cf (point-color p)
(newline)
(point color set! p 'black) ; (point-color-set! p 'black)
(display (point color p)) ; cf (point-color p)
(newline)
)
To access the fields of a point, we write (point x p) and (point color
p) rather than (point-x p) and (point-color p) as in Gambit. The
difference is only in one character, as promised. We also write "make
point" rather than "make-point". Our setter also looks similar to the
one in Gambit, with spaces replacing the dashes.
The getters and the setters are first-class values, as promised:
(display "Example with higher-order functions") (newline)
(define-structure wish adj noun punct)
(let ((w (make wish #f #f #f)))
(for-each
(lambda (setter value) (setter w value))
(list (wish adj set!) (wish noun set!) (wish punct set!))
(list "Happy" "Holidays" "!"))
(for-each
(lambda (pred getter)
(if (pred w) (display (getter w)) (display #\space)))
`(,(wish ?) ,(lambda (_) #f) ,(wish ?) ,(wish ?))
`(,(wish adj) #f ,(wish noun) ,(wish punct)))
(newline)
)
This, second, example demonstrates that getters, setters, and the
predicate are indeed higher-order functions, which can be stored in a
data structure and passed as arguments to procedures. The evaluation
of the above code prints the desired result.
The examples run with Scheme48. See below about running the examples on
other Scheme systems.
To see what is going on, we should take a look at the expansion of the
macro (define-structure point x y color). The macro expands into the
definition of a macro 'point' and the declaration of the point
record type:
(define-record-type rectype
(maker~2 x y color) predicate~3
(x getter~4 setter~4)
(y getter~5 setter~5)
(color getter~6 setter~6)
)
(define-syntax point
(syntax-rules (set!~1 color y x ?~3 *make*~2)
((point color set!~1) setter~6)
((point color set!~1 rec~6 new-val~6) (setter~6 rec~6 new-val~6))
((point color) getter~6)
((point color arg~6) (getter~6 arg~6))
((point y set!~1) setter~5)
((point y set!~1 rec~5 new-val~5) (setter~5 rec~5 new-val~5))
((point y) getter~5)
((point y arg~5) (getter~5 arg~5))
((point x set!~1) setter~4)
((point x set!~1 rec~4 new-val~4) (setter~4 rec~4 new-val~4))
((point x) getter~4)
((point x arg~4) (getter~4 arg~4))
((point ?~3) predicate~3)
((point ?~3 arg~3) (predicate~3 arg~3))
((point *make*~2) maker~2)
((point *make*~2 . args~2) (maker~2 . args~2))))
Scheme48, among other system, let us look at the expansion of a macro:
> ,expand (point x p)
'(#{Generated getter 252} p)
that is, (point x p) is expanded into the invocation of the
appropriate getter procedure. The dispatch to the getter has happened
at the _macro-expand_ time. Therefore, our (point x p) form is just as
efficient at run time as (point-x p) in Gambit.
> ,expand (point x)
#{Generated getter 252}
yields an _identifier_, which is bound to the getter procedure. We can
use the latter value to store in data structures and to pass as
arguments and results.
We should also mention other approaches. A discussion with Al
Petrofsky about CooL symbols introduced one approach:
http://pobox.com/~oleg/ftp/Scheme/universally-CooL-symbols.html
The end of the presentation
http://pobox.com/~oleg/ftp/papers/Dirty-Macros-talk.pdf
shows how to truly concatenate 'identifiers' with syntax rules. The
latter approach poses a question 'what is an identifier' -- the
question that was discussed in many papers on hygienic macros. The
approach is a logical outgrowth of the Kohlbecker renaming
algorithm. Perhaps the approach should be explained in more detail.
Alas, the example as stated above runs only on Scheme48. It seems we
have encountered a dark, under-specified corner of R5RS macro
system. Appendix C gives more detail and an a simple illustrative
test.
If we forgo the treacherous and under-specified top level, we can make
the example run on any R5RS system (at least on four R5RS systems
installed on my computer). The changes are minor, and documented in
Appendix B. The Appendix also shows how to load and run the code
on Scheme48, SCM, Bigloo, and Chez Scheme. The example now has the
form
(define-structure wish (adj noun punct)
(let ((w (make wish #f #f #f)))
(for-each
(lambda (setter value) (setter w value))
(list (wish adj set!) (wish noun set!) (wish punct set!))
(list "Happy" "Holidays" "!"))
(for-each
(lambda (pred getter)
(if (pred w) (display (getter w)) (display #\space)))
`(,(wish ?) ,(lambda (_) #f) ,(wish ?) ,(wish ?))
`(,(wish adj) #f ,(wish noun) ,(wish punct)))
(newline)
))
which differs from the earlier code only in the placement of one
parenthesis. It portably prints the desired result.
Appendix A.
; How to build "identifiers" with syntax-rules: define-structure as a
; R5RS macro
; How to run this code
;
; Save this code into a file, for example, def-struct.scm
;
; $ scheme48
; > ,open srfi-9
; > ,load def-record.scm
; The following is a set of CPS macros for 'define-structure'
; All the build macros can be made internal and thus hidden.
; Top-level macros are more lucid however.
(define-syntax define-structure
(syntax-rules (set!)
((_ name field ...)
(build-maker name (field ...) (set!) () () ))))
; The creator of the structure will be bound to a fresh, colored identifier
; 'maker'
; Generate rules to expand (name *maker*) to that identifier
; Generate rules to expand (name *maker* fld1 fld2 ...) to (maker fld1 fld2...)
(define-syntax build-maker
(syntax-rules (*make*)
((_ name fields (set!-lit . literals) rules defines)
(build-predicate
name fields
(set!-lit *make* . literals) ; add *make* to list of literal symbs
( ((name *make*) maker)
((name *make* . args) (maker . args))
. rules)
((maker . fields) . defines)))))
; The predicate of the structure will be bound to a fresh, colored identifier
; 'predicate'
; We generate expansion rules for the 'name' macro to be defined later
(define-syntax build-predicate
(syntax-rules (?)
((_ name fields (set!-lit . literals) rules defines)
(build-field
name fields (set!-lit ? . literals)
( ((name ?) predicate)
((name ? arg) (predicate arg))
. rules)
(predicate . defines)))))
; The getter and the setter for a field will be bound to a fresh,
; colored identifiers 'getter' and 'setter'. The names are the same for
; all fields, but the colors are different.
(define-syntax build-field
(syntax-rules ()
((_ name (field . fields) (set! . literals) rules defines)
(build-field
name fields (set! field . literals)
; expansion rules for the 'name' macro regarding field access
( ; Order is important! match for set! first
((name field set!) setter)
((name field set! rec new-val) (setter rec new-val))
((name field) getter)
((name field arg) (getter arg))
. rules)
((field getter setter) . defines)))
; no more fields, we're almost finished. Reverse the defines first
((_ name () literals rules defines)
(reverse-cps defines () (build-finish () name literals rules)))))
; (reverse-cps lst () k) reverses lst and passes the result to k
(define-syntax reverse-cps
(syntax-rules ()
((_ () accum (head () . args))
(head accum . args))
((_ (x . rest) accum k)
(reverse-cps rest (x . accum) k))))
; Finish the processing of 'define-structure'
; Generate 'define-record-type' form and a 'define-syntax' for the name
; macro
(define-syntax build-finish
(syntax-rules ()
((_ defines name literals rules)
(begin
(define-record-type rectype . defines)
(define-syntax name
(syntax-rules literals . rules))))))
; Redirect (make name args) to (name *maker* args)
; I think in C++ parlance, this trick is called a secondary dispatch
(define-syntax make
(syntax-rules (*make*)
((_ name . args) (name *make* . args))))
; examples
(display "Example from Gambit-C") (newline)
(define-structure point x y color)
(let ((p (make point 3 5 'red))) ; cf (make-point 3 5 'red)
(display (point x p)) ; cf (point-x p)
(newline)
(display (point color p)) ; cf (point-color p)
(newline)
(point color set! p 'black) ; (point-color-set! p 'black)
(display (point color p)) ; cf (point-color p)
(newline)
)
(display "Example with higher-order functions") (newline)
(define-structure wish adj noun punct)
(let ((w (make wish #f #f #f)))
(for-each
(lambda (setter value) (setter w value))
(list (wish adj set!) (wish noun set!) (wish punct set!))
(list "Happy" "Holidays" "!"))
(for-each
(lambda (pred getter)
(if (pred w) (display (getter w)) (display #\space)))
`(,(wish ?) ,(lambda (_) #f) ,(wish ?) ,(wish ?))
`(,(wish adj) #f ,(wish noun) ,(wish punct)))
(newline)
)
Appendix B.
; How to build "identifiers" with syntax-rules: define-structure as a
; R5RS macro. A portable version that does not rely on the
; under-specified top level.
; The following is a set of _changes_ to the code in Appendix A.
(define-syntax define-structure
(syntax-rules (set!)
((_ name (field ...) . body)
(build-maker name (field ...) (set!) () (body) ))))
; Finish the processing of 'define-structure'
; a 'letrec-syntax' for the dispatcher macro 'name'
;
; make-record-type, record-constructor, record-predicate,
; record-accessor and record-modifier are defined in
; the reference implementation of SRFI-9.
(define-syntax build-finish
(syntax-rules ()
((_ (body
(constructor constructor-tag ...)
predicate
(field-tag getter setter) ...)
name literals rules)
(let
((type
(make-record-type 'name '(field-tag ...))))
(letrec
((constructor
(record-constructor type '(constructor-tag ...)))
(predicate
(record-predicate type))
(getter (record-accessor type 'field-tag)) ...
(setter (record-modifier type 'field-tag)) ...
)
(letrec-syntax
((name (syntax-rules literals . rules)))
. body))))))
; All other definitions are the same as in Appendix A.
; examples
(display "Example from Gambit-C") (newline)
(define-structure point (x y color)
(let ((p (make point 3 5 'red))) ; cf (make-point 3 5 'red)
(display (point x p)) ; cf (point-x p)
(newline)
(display (point color p)) ; cf (point-color p)
(newline)
(point color set! p 'black) ; (point-color-set! p 'black)
(display (point color p)) ; cf (point-color p)
(newline)
))
(display "Example with higher-order functions") (newline)
(define-structure wish (adj noun punct)
(let ((w (make wish #f #f #f)))
(for-each
(lambda (setter value) (setter w value))
(list (wish adj set!) (wish noun set!) (wish punct set!))
(list "Happy" "Holidays" "!"))
(for-each
(lambda (pred getter)
(if (pred w) (display (getter w)) (display #\space)))
`(,(wish ?) ,(lambda (_) #f) ,(wish ?) ,(wish ?))
`(,(wish adj) #f ,(wish noun) ,(wish punct)))
(newline)
))
; How to run this code
;
; First, save this code into a file, for example,
; def-struct1.scm
; Next, fetch the reference implementation of SRFI-9 from srfi.schemers.org
; and save it into a file srfi-9.scm
;
; Scheme48:
; $ scheme48
; > ,load srfi-9.scm
; > ,load def-struct1.scm
;
; SCM (5d6):
; $ scm -r5 -l srfi-9.scm -l def-struct1.scm
;
; Bigloo (2.4b):
; $ bigloo -hygien -i srfi-9.scm def-struct1.scm
;
; Petite Chez Scheme (download from www.scheme.com):
; $ /usr/local/src/csv6.0a/bin/i3le/scheme.exe \
; -h /usr/local/src/csv6.0a/bin/i3le/petite.heap
; Petite Chez Scheme Version 6.0a
; Copyright (c) 1998 Cadence Research Systems
; > (cd "/home/oleg/croot/scheme")
; > (load "srfi-9.scm")
; > (load "def-struct1.scm")
;
Appendix C.
; A dark, under-specified corner of R5RS macros
; Alas, the behavior of syntax-rules -- in particular, the renaming of
; identifiers that will appear at the top level -- is not completely
; specified in R5RS. Different implementations of macro-expanders vary
; widely in this respect.
; The following is an illustrative test. It is a syntax-rules
; implementation of 'letrec' (taken verbatim from Section 7.3 of R5RS)
; with only one change:
; (let ((var1 <undefined>) ...)
; (let ((temp1 init1) ...)
; (set! var1 temp1)
; ...
; body ...)
; is replaced by the "equivalent" code marked below.
; We also changed the name to letrec1 to avoid confusion with the
; standard letrec.
(define-syntax letrec1
(syntax-rules ()
((letrec1 ((var1 init1) ...) body ...)
(letrec1 "generate_temp_names"
(var1 ...)
()
((var1 init1) ...)
body ...))
((letrec1 "generate_temp_names"
()
(temp1 ...)
((var1 init1) ...)
body ...) ; start the changed code
(begin
(define var1 #f) ...
(define temp1 init1) ...
(set! var1 temp1) ...
body ...)) ; end the changed code
((letrec1 "generate_temp_names"
(x y ...)
(temp ...)
((var1 init1) ...)
body ...)
(letrec1 "generate_temp_names"
(y ...)
(newtemp temp ...)
((var1 init1) ...)
body ...))))
; If we use letrec1 on the top level and overlook the pollution of the
; global namespace, we may expect that letrec1 is semantically
; equivalent to letrec.
; Is it? To test it, we evaluate the following expression:
(letrec1 ((x 1) (y 2)) (display (+ x y)) (newline))
; If we save the code in a file, say, /tmp/a1.scm, and load it into Scheme48,
; we see the number "3" printed.
; Indeed, according to Scheme48, letrec1 at the top level is equivalent to
; letrec.
;
; SCM with a built-in macro-expander (scm -r5 -l /tmp/a1.scm) prints 4.
; Gambit with a preloaded syntax-case.scm (downloaded from Gambit's web
; page) prints 4.
; Gauche Scheme prints 4.
; Al Petrofsky's portable expander gives 4.
;
; SCM using William Clinger's macros that work implementation:
; scm -u -e '(load (in-vicinity (library-vicinity) "macwork"))'\
; -e '(macro:load "/tmp/a1.scm")'
; prints an error:
; "unbound variable: newtemp in (#@set! x newtemp)"
; Petite Scheme 6.0 prints
; "Error: variable newtemp is not bound"
; Bigloo 2.4b prints
; "Unbound variable -- newtemp"
;
; The top level of Scheme is indeed under-specified and treacherous.
; On the bright side, we can now trace the lineage of macro-expanders
; in various implementations of Scheme.
Taylor Campbell
>
> [snip]
>
There are two holes in your implementation of these macro-introduced
identifiers.
The first: one cannot use 'apply' to apply a variable argument list to
the introduced identifiers.
The second: while you can 'construct identifiers,' syntax-rules -still-
isn't as powerful; no processing can be done at compile-time inside
the macro. For example, with syntax-case, I could do, supposing this
were MzScheme (this example allows unquoted keyword data):
(define-syntax #%my-top
(syntax-rules ()
((_ . ?datum)
(let* ((datum-string
(symbol->string
(syntax-object->datum (car (syntax ?datum)))))
(char (string-ref datum-string
(- (string-length datum-string) 1))))
(if (char=? char #\:)
(with-syntax ((?d (car (syntax ?datum))))
(syntax (make-keyword '?d)))
(syntax '?d))))))
(module stuff would also be there)
With syntax-rules, that entire thing must be done at run time, not
macro-expanding time. With syntax-case, explicit renaming, and macros
similar to Common LISP's defmacro, it can be done at macro-expand time.
But other than that I suppose it does point out that syntax-rules
doesn't lack -as- much power as most, including myself, thought it did.
Peter Keller
> One of the often mentioned complaints against syntax rules is their
> apparent inability to construct identifiers whose names follow a
> desired pattern. For example, R5RS macros are believed to be incapable
> of implementing a define-structure form, such as the one described in
> the Gambit-C 3.0 manual:
You know, that's really funny you mention this. What you describe was
extremely near what I had chosen to do. Though I had chosen a different method
of solution.
;; Here's what I ultimately chose to do:
(define-syntax test:gen-stat-API-func
(syntax-rules (set incr decr ref)
((_ set fname idx)
(define fname
(lambda (statobj val)
(vector-set! statobj val idx))))
((_ incr fname idx)
(define fname
(lambda (statobj)
(vector-set! statobj idx (+ (vector-ref statobj idx) 1)))))
((_ decr fname idx)
(define fname
(lambda (statobj)
(vector-set! statobj idx (- (vector-ref statobj idx) 1)))))
((_ ref fname idx)
(define fname
(lambda (statobj)
(vector-ref statobj idx))))))
Then the call to it:
(test:gen-stat-API-func set stat-packages-set! 0)
(test:gen-stat-API-func incr stat-packages-incr! 0)
(test:gen-stat-API-func decr stat-packages-decr! 0)
(test:gen-stat-API-func ref stat-packages-ref 0)
I used the pattern matching nature of syntax-rules to create functions
(that could be apply'ed correctly). I had in fact thought of the system you
mention (re: (make point ...)) but disregarded it because I needed to use
the generated functions in higher order contexts.
Now, I had tried to do this:
;; add this to the bottom of the original macro:
((_ idx set setname incr incrname decr decrname ref rename)
(test:gen-stat-API-func set setname idx)
(test:gen-stat-API-func incr setname idx)
(test:gen-stat-API-func decr setname idx)
(test:gen-stat-API-func ref setname idx))
to implement this next bit(which still is poor, but better than the above):
(test:gen-stat-API-func 0
set stat-packages-set!
incr stat-packages-incr!
decr stat-packages-decr!
ref stat-packages-ref)
But that didn't work at all, and I didn't understand why. I thought the macro
transformations just expanded until there was nothing left.
Thank you.
-pete
Abdulaziz Ghuloum
> ;; add this to the bottom of the original macro:
> ((_ idx set setname incr incrname decr decrname ref rename)
> (test:gen-stat-API-func set setname idx)
> (test:gen-stat-API-func incr setname idx)
> (test:gen-stat-API-func decr setname idx)
> (test:gen-stat-API-func ref setname idx))
>
> to implement this next bit(which still is poor, but better than the above):
>
> (test:gen-stat-API-func 0
> set stat-packages-set!
> incr stat-packages-incr!
> decr stat-packages-decr!
> ref stat-packages-ref)
>
> But that didn't work at all, and I didn't understand why. I thought the macro
> transformations just expanded until there was nothing left.
syntax macros transform one expression into another. What you have up
there is a transformation from one expression to four. Here is one way
to do it:
((_ idx set setname incr incrname decr decrname ref rename)
(begin
(test:gen-stat-API-func set setname idx)
(test:gen-stat-API-func incr incrname idx)
(test:gen-stat-API-func decr decrname idx)
(test:gen-stat-API-func ref rename idx)))
Does this make sense?
Aziz,,,
Joe Marshall
> Appendix C.
>
> ; A dark, under-specified corner of R5RS macros
(define-syntax letrec1
(syntax-rules () <etc. etc. etc.>
(letrec1 ((x 1) (y 2)) (display (+ x y)) (newline))
To summarize:
Scheme48: displays 3
SCM: displays 4
Gauche Scheme: displays 4
Gambit: displays 4
Al Petrofsky's: displays 4
Will Clinger's: unbound variable error
Petite Scheme 6.0: unbound variable error
Bigloo 2.4b: unbound variable error
And two more:
MIT Scheme 7.7.1: displays 3
PLT Scheme 202: displays 4
Al Petrofsky
> syntax macros transform one expression into another. What you have up
> there is a transformation from one expression to four. Here is one
> way to do it:
>
> ((_ idx set setname incr incrname decr decrname ref rename)
> (begin
> (test:gen-stat-API-func set setname idx)
> (test:gen-stat-API-func incr incrname idx)
> (test:gen-stat-API-func decr decrname idx)
> (test:gen-stat-API-func ref rename idx)))
>
> Does this make sense?
Yes, but, to be picky: that begin form is not an expression (it's a
sequence of macro uses that expand into definitions). I think you
meant that macros transform one s-expression into one s-expression.
Another way to say it: they transform one macro use into one macro
use, expression, definition, or begin form.
-al
Al Petrofsky
that r5rs doesn't require that it actually work for top-level
structure types) is that you can't use the field names as local
variables, as in:
(let ((x (point-x foo)))
(if (= x (point-x bar))
<something>))
If macro calls like (point x bar) are going to work, then x must not
be shadowed. Thus, your system is not that much better than plain
srfi-9, at least in so far as you need to use up one name from the
top-level address space for every field of the structure type.
Regarding how to define a top-level variable local to a macro:
> (letrec1 ((x 1) (y 2)) (display (+ x y)) (newline))
>
> ; If we save the code in a file, say, /tmp/a1.scm, and load it into Scheme48,
> ; we see the number "3" printed.
> ; Indeed, according to Scheme48, letrec1 at the top level is equivalent to
> ; letrec.
> ;
> ; SCM with a built-in macro-expander (scm -r5 -l /tmp/a1.scm) prints 4.
> ; Gambit with a preloaded syntax-case.scm (downloaded from Gambit's web
> ; page) prints 4.
> ; Gauche Scheme prints 4.
> ; Al Petrofsky's portable expander gives 4.
> ;
> ; SCM using William Clinger's macros that work implementation:
> ; scm -u -e '(load (in-vicinity (library-vicinity) "macwork"))'\
> ; -e '(macro:load "/tmp/a1.scm")'
> ; prints an error:
> ; "unbound variable: newtemp in (#@set! x newtemp)"
> ; Petite Scheme 6.0 prints
> ; "Error: variable newtemp is not bound"
> ; Bigloo 2.4b prints
> ; "Unbound variable -- newtemp"
The chez scheme expander is supposed to allow this, and I think it can
be considered a bug that petite chez scheme does not. Have you tried
it using a recent version of Dybvig's expander? The comments in the
psyntax.ss source code show a simpler example of this technique, which
does work in petite:
(define-syntax a
(syntax-rules ()
((_ var exp)
(begin
(define secret exp)
(define var
(lambda ()
(set! secret (+ secret 17))
secret))))))
(a x 0)
(x) => 17
(x) => 34
secret => Error: variable secret is not bound
As pointed out in the same comments, this behavior is inconsistent and
fragile, but was chosen because it is more useful than the consistent
behavior of never renaming top-level variables.
My expander enables you to accomplish this sort of thing in a way that
is rather bizarre and incomprehensible, but which I have managed to
convince myself is perfectly logical. (A goal of my expander was to
see how powerful r5rs macros could be made without introducing any new
keywords, but just generalizing in a logical way the allowed uses of
syntax-rules, let-syntax, letrec-syntax, and define-syntax.)
The primary extension in my system is that a let-syntax or
letrec-syntax form whose body is a transformer may be used anywhere
that a transformer may be used:
(let-syntax ((foo (let-syntax ((bar (syntax-rules () ((_ x) (- x)))))
(syntax-rules () ((_) (bar 2))))))
(foo))
=> -2
A feature of r5rs is that if a macro use occurs at top-level then the
macro's output need not be an expression -- it may be anything that's
legal at top level, including definitions and syntax definitions. In
the following, note that bar's binding has a limited lexical scope,
but it can be used in the output of foo, which is allowed to be a
syntax definition (or redefinition):
(define-syntax foo
(let-syntax ((bar (syntax-rules ())))
(syntax-rules (redefine-bar use-bar)
((_ redefine-bar transformer) (define-syntax bar transformer))
((_ use-bar datum ...) (bar datum ...)))))
(define-syntax bar (syntax-rules () ((_) 1)))
(foo redefine-bar (syntax-rules () ((_) 2))) ;; redefines the local bar
(foo use-bar) => 2
(bar) => 1 ;; top-level bar was unaffected.
At top-level we are not only allowed to redefine variables and
keywords, we are allowed to store variable values into bindings that
used to hold syntaxes, and to store syntaxes into bindings that used
to hold values:
(define if 7)
if => 7
(define list (syntax-rules () ((_) 4)))
(list) => 4
Combining these features, we can write Dybvig's A example like so:
(define-syntax a
(let-syntax ((helper (syntax-rules ())))
(syntax-rules ()
((_ var exp)
(begin
(define-syntax helper
(let-syntax ((secret (syntax-rules ())))
(syntax-rules ()
((_ x)
(begin (define secret x)
(define (var)
(set! secret (+ secret 17))
secret))))))
(helper exp))))))
Another obvious extension is to allow transformers to occur directly
in the head position of a macro use, like so:
((syntax-rules ()
((let ((var init) ...) . body)
((lambda (var ...) . body) init ...)))
((x 1) (y 2))
(+ x y))
=> 3
Using that feature, we don't need a helper binding to implement A:
(define-syntax a
(syntax-rules ()
((_ var exp)
((let-syntax ((secret (syntax-rules ())))
(syntax-rules ()
((_ x)
(begin (define secret x)
(define (var)
(set! secret (+ secret 17))
secret)))))
exp))))
Oleg's build-finish can be implemented like so:
(define-syntax build-finish
(let-syntax ((dummy (syntax-rules ())))
(syntax-rules ()
((_ ((maker . fields) pred (field getter setter) ...)
name literals rules)
((letrec-syntax ((getter dummy) ... (setter dummy) ...
(rectype dummy) (maker dummy) (pred dummy))
(syntax-rules ()
((_)
(begin
(define-record-type rectype
(maker . fields) pred (field getter setter) ...)
(define-syntax name (syntax-rules literals . rules)))))))))))
(That used one more extension: that a keyword may be used anywhere a
transformer may be used, e.g. (let-syntax ((i if)) (i #f 1 2)) => 2)
Although these extensions allow programs using only high-level macros
to be compiled unambiguously, they unfortunately conflict with the
restrictions that were introduced into PLT scheme to avoid the
ambiguities of low-level macros that use macros (see "You Want it
When?" by Flatt). I think there might be a graceful set of rules that
would allow these high-level macros that use local high-level macros,
while still being restrictive enough to prevent the surprises that PLT
seeks to prevent. I haven't found such a set of rules yet.
-al
Al Petrofsky
> There are two holes in your implementation of these macro-introduced
> identifiers.
>
> The first: one cannot use 'apply' to apply a variable argument list to
> the introduced identifiers.
You can do this:
(define-structure point x y color)
(make point 3 5 'red) => a point
(apply (make point) '(3 5 red)) => an equivalent point
I think your concern is precisely what Oleg was addressing with all
the talk about the functions being first-class values.
A problem is that in this example:
(define-structure pointless)
(make pointless)
It's ambiguous whether you want the pointless maker, or a made
pointless. Oleg's implementation gives you the maker, and you have to
use ((make pointless)) to make your pointless.
-al
Taylor Campbell
>
> You can do this:
>
> (define-structure point x y color)
> (make point 3 5 'red) => a point
> (apply (make point) '(3 5 red)) => an equivalent point
>
> I think your concern is precisely what Oleg was addressing with all
> the talk about the functions being first-class values.
>
Whoops, I must have forgotten to read the code quite closely enough.
Looking at it again, I see that that would work. But my second point
still stands.
> A problem is that in this example:
>
> (define-structure pointless)
> (make pointless)
>
> It's ambiguous whether you want the pointless maker, or a made
> pointless. Oleg's implementation gives you the maker, and you have to
> use ((make pointless)) to make your pointless.
>
> -al
>
It really ought to return a maker: how else could the maker be used in
other code? (i.e., if you have some function that takes a maker as an
argument and calls it elsewhere) But I do agree that it appears
ambiguous. Perhaps there should be a different macro, 'maker,' that
returns a maker, and 'make' uses it? That would require the internal
implementation to change as well -- *make* would use *maker*, which
would return the actual maker procedure, perhaps?
Radey Shouman
> I think the biggest drawback to this technique (other than the fact
> that r5rs doesn't require that it actually work for top-level
> structure types) is that you can't use the field names as local
> variables, as in:
>
> (let ((x (point-x foo)))
> (if (= x (point-x bar))
> <something>))
>
> If macro calls like (point x bar) are going to work, then x must not
> be shadowed. Thus, your system is not that much better than plain
> srfi-9, at least in so far as you need to use up one name from the
> top-level address space for every field of the structure type.
Are there reasons that field names cannot be strings, aside from the
purely aesthetic? (One might even conceive of stringhood in an
identifier as a sign that the syntax-rules of hygiene need not be
obeyed).
These can be coerced at run-time to symbols before passing to
make-record-type.
ol...@pobox.com
> The second: while you can 'construct identifiers,' syntax-rules -still-
> isn't as powerful; no processing can be done at compile-time inside
> the macro. For example, with syntax-case, I could do, supposing this
> were MzScheme (this example allows unquoted keyword data):
> powerful; no processing can be done at compile-time inside the macro.
> For example, with syntax-case, I could do, supposing this were
> MzScheme (this example allows unquoted keyword data):
I'd like to note that syntax-rules are Turing complete. Syntax-rules
are capable of any non-generative S-expression transformation that
does not involve a discrimination based on _a_ symbol, _a_ number or
_a_ string (note the indefinite article). By 'non-generative'
transformation I mean a transformation whose result contains only
atomic data present in the source expression and in the
transformer. To be fair, the renaming rules provide a limited form of
generative transformations as well. Several articles posted on this
newsgroup described a number of computationally-intensive R5RS
macros. Performing beta-reduction in normal order, deeply reversing
lists, computing a factorial in arbitrary precision hexadecimal
arithmetic are some of the examples. The latter is by Al Petrofsky. On
some systems, the process of compilation took literally 10 minutes or
more. Thus there is a lot of computation that can be done in the
process of the expansion of a R5RS macro.
Furthermore, surprisingly many problems that appear impossible without
low-level macro facilities are easily solvable once we change the
perspective. Take your example, of introducing self-quoted keywords. Can
we evaluate the following code
(let ((mylist '((foo: 1) (bar: 2))))
(assq foo: mylist))
on a system that does not support keywords? Sure we can: we just need to
define
(define foo: 'foo:)
(define bar: 'bar:)
The (let ((mylist ...))...) form, _as it is_, will evaluate without
any problem. Inlining, which is normally done by almost any compiler,
will eliminate any run-time overhead. This approach is also
_portable_. Al Petrofsky's response to the CooL symbol challenge is
another great example of the benefits of looking at a greater picture.
Can we automatically extract would-be-keywords from an expression such
as (proc foo: 1) and generate the necessary 'define' forms? That is a
transformation based on _a_ symbol (a class of symbols to be precise),
and therefore, cannot be done with R5RS macros. However, we can turn
the problem into a discrimination based on _the_ symbol, the colon
symbol. If we're willing to write our keywords as in (proc foo : 1) then
the problem appears plausible.
There is indeed a difference between the source and the macro-expanded
forms of a program -- the difference that we can turn to our
advantage. For example, identifiers in the source program don't even
have to be symbols! It is also important to realize that the core
evaluator will be just as happy to evaluate this
((lambda (voltage resistance) (/ voltage resistance)) 110 10)
as this
((lambda (i~124~10 i~123~10) (/ i~124~10 i~123~10)) 110 10)
Indeed, programs as closed terms are invariant with respect to
alpha-renaming.
If by "no processing can be done at compile-time inside the macro" you
mean that the expansion of R5RS macros involves no 'eval' -- you are
right. There are people however who believe that the eval-less nature of
R5RS macros is a benefit. For example, R5RS macros have a natural
phase separation: run-time abstractions cannot be used at all at a
syntax-rule macro-expand time. If we limit ourselves only to R5RS
macros, we lose some expressiveness (i.e., general generative
macro-transformations) but we gain in simplifying interactions between
modules and macros. Is it a good trade-off? A good question.
ol...@pobox.com
> You know, that's really funny you mention this [define-structure
> form]. What you describe was extremely near what I had chosen to do.
That was no accident.
> I had in fact thought of the system you mention (re: (make point ...))
> but disregarded it because I needed to use the generated functions in
> higher order contexts.
Please see Al Petrofsky's comment to Taylor Campbell's objection. I'd
also like to stress the line from the second example:
`(,(wish adj) #f ,(wish noun) ,(wish punct))
note that an accessor (wish adj) is a first-class value, which was
stored in a data structure (a list), passed to higher-order
combinators, and applied later.
Eli Barzilay
> I'd like to note that syntax-rules are Turing complete. [...]
> Several articles posted on this newsgroup described a number of
> computationally-intensive R5RS macros. [...]
(As cute as the results may be, computing that factorial in 10 minutes
inevitably limits it to no more than cute. So you have some limited
mechanism that has a `turing-inside' certificate, but you still would
want something that is also practical.)
About this:
> There are people however who believe that the eval-less nature of
> R5RS macros is a benefit. For example, R5RS macros have a natural
> phase separation: run-time abstractions cannot be used at all at a
> syntax-rule macro-expand time. If we limit ourselves only to R5RS
> macros, we lose some expressiveness (i.e., general generative
> macro-transformations) but we gain in simplifying interactions
> between modules and macros. Is it a good trade-off? A good question.
-- if your goal is clear separation between run-time and compile-time
(syntax-expansion-time) by using a different language, then use CPP
for your macros... You could even decide that to make sure you're
speaking about text you will always use Chinese to talk about English.
Obviously, the reason should be that the transformation language
handles these pattern changes much better -- under this view it seems
reasonable to have an additional mechanism that will allow you to do
arbitrary computations without resorting to 10-minute simulations.
I guess that my bottom line here is that the phase separation should
not be taken as an argument for/against additional low-level macro
mechanisms. The PLT syntax system achieves exactly that -- you get
clear phase separation independent of having syntax-case or any other
form of evaluation.
--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
http://www.barzilay.org/ Maze is Life!
ol...@pobox.com
> I think the biggest drawback to this technique (other than the fact
> that r5rs doesn't require that it actually work for top-level
> structure types) is that you can't use the field names as local
> variables, as in:
>
> (let ((x (point-x foo)))
> (if (= x (point-x bar))
> <something>))
>
> If macro calls like (point x bar) are going to work, then x must not
> be shadowed. Thus, your system is not that much better than plain
> srfi-9, at least in so far as you need to use up one name from the
> top-level address space for every field of the structure type.
Actually, that's where "keywords" come in. Given the unmodified code
and the instructions of Appendix B of the original article, the
following fragment runs and prints the expected result on SCM (which
does not have keywords), Petite Chez Scheme (does not support
keywords) and Bigloo (which DOES support keywords). The similar code
runs on Scheme48 (which again does not support keywords).
(define-structure point (x: y: color:)
(let ((p (make point 3 5 'red))) ; cf (make-point 3 5 'red)
(display (point x: p)) ; cf (point-x p)
(newline)
(display (point color: p)) ; cf (point-color p)
(newline)
(point color: set! p 'black) ; (point-color-set! p 'black)
(display (point color: p)) ; cf (point-color p)
(newline)
))
The best part is: you don't need to do anything to the code or to your
top level: you don't have to define macros to enable the keywords, you
don't need to bind the identifiers x:, y:, color: on a system without
the keywords. It "just works". Bonus: in my tweaked gaudy Scheme emacs
mode, "keywords", real or imaginary, really stand out by their pink
color.
felix
The newest version of the portable syntax-case
macro package by Dybvig and Waddel prints 3.
(BTW, this one is used in the current CVS version
of Chicken).
cheers,
felix
Peter Keller
> Yes, but, to be picky: that begin form is not an expression (it's a
> sequence of macro uses that expand into definitions). I think you
> meant that macros transform one s-expression into one s-expression.
> Another way to say it: they transform one macro use into one macro
> use, expression, definition, or begin form.
Thank you for this information. I hadn't realized that this one to one
mapping restriction was in place.
-pete
Peter Keller
> sequence of macro uses that expand into definitions). I think you
> meant that macros transform one s-expression into one s-expression.
> Another way to say it: they transform one macro use into one macro
> use, expression, definition, or begin form.
Thank you for this information. I hadn't realized that this one to one
Richard Kelsey
> ; Alas, the behavior of syntax-rules -- in particular, the renaming of
> ; identifiers that will appear at the top level -- is not completely
> ; specified in R5RS. Different implementations of macro-expanders vary
> ; widely in this respect.
Is the issue here the fact that R5RS doesn't say if top-level
definitions are binding occurances (end of section 5.2.1 'Top
level definitions')? People have been tripped up by this when
defining things like:
(define-syntax define-cell
(syntax-rules ()
((define-cell initial ref set)
(begin
(define value initial)
(define (ref) value)
(define (set new-value)
(set! value new-value))))))
In implementations where all identifiers are implicitly bound at
top-level the identifier VALUE is a reference to a bound identifier
and so it is not renamed, causing all cells to share a single value.
Without SYNTAX-RULES it didn't matter whether DEFINE was a binding
form or not; you got the same answer either way. Now it does. But
I would say that the problem lies with the underspecification of
DEFINE, not with SYNTAX-RULES.
-Richard Kelsey
wni
> ol...@pobox.com (ol...@pobox.com) writes:
>
>
>>I'd like to note that syntax-rules are Turing complete. [...]
>>Several articles posted on this newsgroup described a number of
>>computationally-intensive R5RS macros. [...]
>
>
> (As cute as the results may be, computing that factorial in 10 minutes
> inevitably limits it to no more than cute. So you have some limited
> mechanism that has a `turing-inside' certificate, but you still would
> want something that is also practical.)
>
Agreed.
I always find the claim of "Turing complete" troubling. The definition
itself only considers the algorithmic completeness in the traditional
Church-Turing sense. If I were to implement a Turing complete
environment using C but prohibit this environment from using all the
networking libraries of the underlying operating system. How do I make
an HTTP server out of it?
I think Peter Wegner (http://www.cs.brown.edu/people/pw/) made a point
about the concept of *interaction* and its power. As a small corollary
of his arguments, if you can't get something like interrupts, system
time, external communications, as well as many other environmental
artifacts to help you, you end up with a less powerful system and, even
if you made it, your solution is clumsy. The claims of XSLT and R5RS
macro being Turing complete while people are struggling everyday to
"appreciate" such completeness in their works is tragic.
IMHO, the patching work to R5RS's underpowered macro system has gone too
far that it makes programming these macros a black art when dealing with
such ident-introducing problems. I find myself writing more define-macro
because of this.
wni at attbi dot com
ol...@pobox.com
> (As cute as the results may be, computing that factorial in 10 minutes
> inevitably limits it to no more than cute. So you have some limited
> mechanism that has a `turing-inside' certificate, but you still would
> want something that is also practical.)
I believe a clarification is needed. It might appear that advanced
macro-level programming is too slow to be of any use. The reality is
that the speed of macro-expansion _greatly_ depends on a
macro-expander. Performance of different macro-expanders can vary by as
much as three orders of magnitude! A macro that takes 10 and more
minutes with one Scheme system can be expanded in less than one _second_
on a different system, on the same hardware platform and the OS. A
page
http://pobox.com/~oleg/ftp/Scheme/macros.html#syntax-rule-stress-test
gives a benchmark and discusses its timings for a sample of Scheme
systems. The exact performance differences are of course the function
of a benchmark. Two conclusions are clear however -- advanced R5RS
macros are not inherently slow. There exist Scheme systems that make
the advanced macro-programming practical.
> -- if your goal is clear separation between run-time and compile-time
> (syntax-expansion-time) by using a different language, then use CPP
> for your macros...
I didn't know CPP can preserve hygiene ...
> I guess that my bottom line here is that the phase separation should
> not be taken as an argument for/against additional low-level macro
> mechanisms.
In his paper "23 things I know about modules for Scheme," Christian
Queinnec wrote: "Were not for macros, modules would probably be
standard in Scheme for a long time. Alas!... I tend to think that
macros are probably the best reason for the survival of the Lisp
family but there are the root of the problems for modules!" Therefore,
I believe that evaluating macro systems in the context of modules and
phase separation is a justified line of inquiry.
> The PLT syntax system achieves exactly that -- you get clear phase
> separation independent of having syntax-case or any other form of
> evaluation.
Perhaps a different set of trade-offs might turn out beneficial in
certain circumstances? The existence of one solution (unless it has
made it into a standard) does not close the case, does it? Otherwise
we would have had only one Scheme system.
ol...@pobox.com
> IMHO, the patching work to R5RS's underpowered macro system has gone too
> far that it makes programming these macros a black art when dealing with
> such ident-introducing problems. I find myself writing more define-macro
> because of this.
The thrust of the paper "Macros that Compose: Systematic Macro
Programming" was specifically to make R5RS macro programming more like
a craft rather than a witchcraft. The paper showed how to build macros
systematically, by combining smaller, separately-developed pieces by
functional composition or higher-order combinators:
http://pobox.com/~oleg/ftp/papers/Macros-talk.pdf
There is more: if you can express an S-expression transformation
(which is in the domain of R5RS macros) using ordinary Scheme
functions, you can mechanically transform the functions into the
corresponding R5RS macros. You can thus obtain the benefit of
intuitive Scheme programming and the portability of R5RS macros. If
you use a Scheme system with an efficient macro-expander (there are
already several to choose from), the performance of the resulting
macros is not a problem.
http://pobox.com/~oleg/ftp/Scheme/macros.html#syntax-rules-compiler
Eli Barzilay
> I believe a clarification is needed. It might appear that advanced
> macro-level programming is too slow to be of any use. The reality is
> that the speed of macro-expansion _greatly_ depends on a
> macro-expander. Performance of different macro-expanders can vary by as
> much as three orders of magnitude! A macro that takes 10 and more
> minutes with one Scheme system can be expanded in less than one _second_
> on a different system, on the same hardware platform and the OS. A
> page
> http://pobox.com/~oleg/ftp/Scheme/macros.html#syntax-rule-stress-test
>
> gives a benchmark and discusses its timings for a sample of Scheme
> systems. The exact performance differences are of course the function
> of a benchmark. Two conclusions are clear however -- advanced R5RS
> macros are not inherently slow. There exist Scheme systems that make
> the advanced macro-programming practical.
I'm not disputing anything you said, I just want to add that for
certain purposes you might want to do some computations in your
macros, for example some run time code generation thing might need
this. This is why I think that while we're not stressing efficiency
as a first priority, we should not completely forget about it either.
> > -- if your goal is clear separation between run-time and compile-time
> > (syntax-expansion-time) by using a different language, then use CPP
> > for your macros...
> I didn't know CPP can preserve hygiene ...
Irrelevant -- change my sentence to some imaginary hygienic CPP (maybe
syntax-rules with a CPP syntax...).
> In his paper "23 things I know about modules for Scheme," Christian
> Queinnec wrote: "Were not for macros, modules would probably be
> standard in Scheme for a long time. Alas!... I tend to think that
> macros are probably the best reason for the survival of the Lisp
> family but there are the root of the problems for modules!"
> Therefore, I believe that evaluating macro systems in the context of
> modules and phase separation is a justified line of inquiry.
Definitely.
> > The PLT syntax system achieves exactly that -- you get clear phase
> > separation independent of having syntax-case or any other form of
> > evaluation.
>
> Perhaps a different set of trade-offs might turn out beneficial in
> certain circumstances? The existence of one solution (unless it has
> made it into a standard) does not close the case, does it? Otherwise
> we would have had only one Scheme system.
Out of curiosity, what trade-offs do you see in the PLT module+syntax
system and what different trade-offs are you talking about?