What's the lowdown on scheme48's define-syntax?

[Andy Gaynor]

I'd appreciate it if someone would post or send me pointers,
hints, or examples concerning the workings of scheme48's
low-level macro facility, eg,

(define-syntax foo (lambda (form rename compare) ...))

Thanks, [Ag] sil...@mail.webspan.net

[Joseph Allen Dane]

Andy Gaynor <sil...@mail.webspan.net> writes:

> I'd appreciate it if someone would post or send me pointers,
> hints, or examples concerning the workings of scheme48's
> low-level macro facility, eg,
>
> (define-syntax foo (lambda (form rename compare) ...))
>

I don't think the s48 distribution has anything at all on this.
I do have a few papers which may help, including

William Clinger & Jonathan Rees
Macros that work.
1991 POPL Proceedings

and particularly

William Clinger
Hygenic Macros Through Explicit Renaming

The second paper describes the particular details of the facility. I
don't know where the paper was published, but I seem to have a
postscript copy of it from somewhere. I can mail it to you if you
like, or maybe Will Clinger, who appears in this forum now and then,
can provide a reference.

--

joe

[Michael Sperber [Mr. Preprocessor]]

>>>>> "Andy" == Andy Gaynor <sil...@mail.webspan.net> writes:

Andy> I'd appreciate it if someone would post or send me pointers,
Andy> hints, or examples concerning the workings of scheme48's
Andy> low-level macro facility, eg,

Andy> (define-syntax foo (lambda (form rename compare) ...))

The electronic version of Will Clinger's paper on this is

/ftp.cs.indiana.edu:/pub/scheme-repository/doc/prop/exrename.ps.gz

--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla

[Andy Gaynor]

The PostScript version was starting to annoy me. It's short, I'm a quick
typist, and the document is already available publicly. Light enough so
that even humans can read it, and yet useful. Here it is...

Regards, [Ag] sil...@mail.webspan.net
_______________________________________________________________________________

Hygienic Macros through Explicit Renaming

William Clinger

This paper describes an alternative to the low-level macro facility
described in the _Revised^4_Report_on_the_Algorithmic_Language_Scheme_ [1].
The facility described here is based on explicit renaming of identifiers, and
was developed for the first implementation of the hygienic macro expansion
algorithm described in [2]. It was the first low-level macro facility to be
designed for compatibility with a high-level hygienic macro system, and it
remains one of the easiest to understand.
Whereas the low-level macro facility described in the Revised^4 Report
renames identifiers automatically, so that hygienic macros are obtained by
default, the facility described here requires that identifiers be renamed
explicitly in order to maintain hygiene.
Another difference is that, as originally implemented and as described
here, there is no way to define certain hygienic macros that define other
hygienic macros. The problem is that the transformation procedure for the
defined macro may need to compare pieces of its first argument with the
denotation of an identifier, but the only way for the defining macro to pass
that denotation along to the defined macro is as part of the code for the
defined macro. This problem can be solved by introducing SYNTAX expressions as
in the Revised^4 Report. SYNTAX is like QUOTE, except that the denotation of
an identifier quoted by SYNTAX is preserved as part of the quoted value.
As with the low-level macro facility based on syntactic closures [3], the
explicit renaming facility adds a new production for <transformer spec>:

<transformer> --> (TRANSFORMER <expression>)

The <expression> is expanded in the syntactic environment of the
TRANSFORMER expression, and the expanded expression is evaluated in the
standard transformer environment to yield a _transformation_procedure_. The
transformation procedure takes an expression and two other arguments and
returns a transformed expression. For example, the transformation procedure
for a CALL macro such that (CALL proc arg ...) expands into (proc arg ...) can
be written as

(lambda (exp rename compare)
(cdr exp))

Expressions are represented as lists in the traditional manner, except that
identifiers may be represented by objects other than symbols. Transformation
procedures may use the predicate IDENTIFIER? to determine wither an object is
the representation of an identifier.
The second argument to a transformation procedure is a renaming procedure
that takes the representation of an identifier as its argument and returns the
representation of a fresh identifier that occurs nowhere else in the program.
For example, the transformation procedure for a simplified version of the LET
macro might be written as

(lambda (exp rename compare)
(let ((vars (map car (cadr exp)))
(inits (map cadr (cadr exp)))
(body (cddr exp)))
`((lambda ,vars ,@body)
,@inits)))

This would not be hygienic, however. A hygienic LET macro must rename the
identifier LAMBDA to protect it from being captured by a local binding. The
renaming effectively creates a fresh alias for LAMBDA, one that cannot be
captured by any subsequent binding:

(lambda (exp rename compare)
(let ((vars (map car (cadr exp)))
(inits (map cadr (cadr exp)))
(body (cddr exp)))
`((,(rename 'lambda) ,vars ,@body)
,@inits)))

The expression returned by the transformation procedure will be expanded in
the syntactic environment obtained from the syntactic environment of the macro
application by binding any fresh identifiers generated by the renaming
procedure to the denotations of the original identifiers in the syntactic
environment in which the macro was defined. This means that a renamed
identifier will denote the same thing as the original identifier unless the
transformation procedure that renamed the identifier placed an occurrence of it
in a binding position.
The renaming procedure acts as a mathematical function in the sense that
the identifiers obtained from any two calls with the same argument will be the
same in the sense of EQV?. It is an error if the renaming procedure is called
after the transformation procedure has returned.
The third argument to a transformation procedure is a comparison predicate
that takes the representations of two identifiers as its arguments and returns
true if and only if they denote the same thing in the syntactic environment
that will be used to expand the transformed macro application. For example,
the transformation procedure for a simplified version of the COND macro can be
written as

(lambda (exp rename compare)
(let ((clauses (cdr exp)))
(if (null? clauses)
`(,(rename 'quote) unspecified)
(let* ((first (car clauses))
(rest (cdr clauses))
(test (car first)))
(cond ((and (identifier? test)
(compare test (rename 'else)))
`(,(rename 'begin) ,@(cdr first)))
(else `(,(rename 'if)
,test
(,(rename 'begin) ,@(cdr first))
(cond ,@rest))))))))

In this example, the identifier ELSE is renamed before being passed to the
comparison predicate, so the comparison will be true if and only if the test
expression is an identifier that denotes the same thing in the syntactic
environment of the expression being transformed as ELSE denotes in the
syntactic environment in which the COND macro was defined. If ELSE were not
renamed before being passed to the comparison predicate, then it would match a
local variable that happened to be named ELSE, and the macro would not be
hygienic.
Some macros are non-hygienic by design. For example, the following defines
a loop macro that implicitly binds EXIT to an escape procedure. The binding of
EXIT is intended to capture free references to EXIT in the body of the loop, so
EXIT is not renamed.

(define-syntax loop
(transformer
(lambda (x r c)
(let ((body (cdr x)))
`(,(r 'call-with-current-continuation)
(,(r 'lambda) (exit)
(,(r 'let) ,(r 'f) () ,@body (,(r 'f)))))))))

Suppose a WHILE macro is implemented using LOOP, with the intent that EXIT
may be used to escape from the while loop. The WHILE macro cannot be written
as

(define-syntax while
(syntax-rules ()
((while test body ...)
(loop (if (not test) (exit #f))
body ...))))

because the reference to EXIT that is inserted by the WHILE macro is intended
to be captured by the binding of EXIT that will be inserted by the LOOP macro.
In other words, this WHILE macro is not hygienic. Like LOOP, it must be
written using the transformer syntax:

(define-syntax while
(transformer
(lambda (x r c)
(let ((test (cadr x))
(body (cddr x)))
`(,(r 'loop)
(,(r 'if) (,(r 'not) ,test) (exit #f))
,@body)))))

References

[1] William Clinger and Jonathan Rees, editors
Revised^4 Report on the Algorithmic Language Scheme
To appear in the previous issue of _Lisp_Pointers_

[2] William Clinger and Jonathan Rees
Macros that Work
_1991_ACM_Conference_on_Principles_of_Programming_Languages_

[3] Chris Hanson
A Syntactic Closures Macro Facility
To appear in this issue of _Lisp_Pointers_

[Andy Gaynor]

Oh, rude me: Thanks for your help, Joe and Mike.

Regards, [Ag] sil...@mail.webspan.net

[Andy Gaynor]

I grinded some macros with explicit renaming in scheme48/scsh.
Nothing spectacular, rest arguments for labeled lets
and a case specialized for working with characters.

(let (copy . (more 1 2 3 4 5))
(if (null? more)
'()
(cons (car more) (apply copy (cdr more)))))

(character-case #\a
(#\a ...)
("bcd" ...)
(eof ...) ;; The eof can go anywhere in the guard.
((#\e #\f "ghi" (#\j #\k)) ...)
(else ...))

Enjoy, [Ag] sil...@mail.webspan.net
_______________________________________________________________________________

;; This version of let allows the traditional forms:
;;
;; (let ((variable value) ...) body ...)
;; (let label ((variable value) ...) body ...)
;;
;; In addition, the binding list may be `improper', eg,
;;
;; ((variable value) ... . (rest-variable rest-value ...))
;;
;; While this no bearing on the unlabeled form,
;; it allows the labeled form to have a rest argument.
;;
;; Second, the label may appear as the
;; leading element of the binding list, eg,
;;
;; (let (label (variable argument) ...)
;; body ...)
;;
;; This is reminiscent of define's format,
;; which seems more appropriate.
(define-syntax let
(lambda (form rename compare)
(call-with-current-continuation
(lambda (error)
(define (vars bindings)
(cond ((null? bindings) '())
((pair? (car bindings)) (cons (caar bindings) (vars (cdr bindings))))
((symbol? (car bindings)) (car bindings))
(else (error form))))
(define (vals bindings)
(cond ((null? bindings) '())
((pair? (car bindings)) (cons (cadar bindings) (vals (cdr bindings))))
((symbol? (car bindings)) (cdr bindings))
(else (error form))))
(define (expand-let bindings body)
`((,(rename 'lambda) ,(vars bindings) ,@body)
,@(vals bindings)))
(define (expand-label label bindings body)
`((,(rename 'letrec)
((,label (,(rename 'lambda) ,(vars bindings) ,@body)))
,label)
,@(vals bindings)))
(define (expand bindings . body)
(cond ((symbol? bindings) (expand-label bindings (car body) (cdr body)))
((null? bindings) (expand-let bindings body))
((symbol? (car bindings)) (expand-label (car bindings) (cdr bindings) body))
(else (expand-let bindings body))))
(apply expand (cdr form))))))

;; This version of case is customized for
;; common character-oriented processing tasks.
;;
;; (character-case value
;; (guard body ...)
;; ...)
;;
;; Guard matching:
;;
;; Guard: Matches when:
;; character (eqv? value guard)
;; string (member value (string->list guard))
;; integer (eqv? (integer->char value) guard)
;; list An element of the guard matches value
;; 'eof (eof-object? value)
;;
;; This expands to a single case expression.
;; The eof-object? test is done in the else clause.
(define-syntax character-case
(lambda (form rename compare)
(call-with-current-continuation
(lambda (error)
(define (expand value . clauses)
(let ((eof-body #f)
(else-body #f))
;; Since there is some clause shuffling
;; (else clause, clauses with empty guards)
;; this returns a list of 0 or 1 clauses.
;; The return values are then appended.
(define (case-clauses clause)
(define (case-guard guard)
(if (compare 'else (car clause))
(begin (set! else-body (cdr clause))
#f)
(let recurse ((guard (car clause)))
(cond ((char? guard) (list guard))
((string? guard) (string->list guard))
((integer? guard) (list (integer->char guard)))
((list? guard) (apply append (map recurse guard)))
((eq? 'eof guard) (if eof-body (error form))
(set! eof-body (cdr clause))
#f)
(else (error form))))))
(let ((cg (case-guard (car clause))))
(if cg (list (cons cg (cdr clause))) '())))
;;`(let ((value ,value))
;; (case value
;; ,@(apply append (map case-clauses clauses))
;; (else (cond ,@(if eof-body
;; `(((eof-object? value) ,@eof-body))
;; '())
;; (else ,@(or else-body '()))))))
;; The case and cond always has an else clause.
;; Errors in generated clauses should be caught by case.
`(,(rename 'let) ((,(rename 'value) ,value))
(,(rename 'case) ,(rename 'value)
,@(apply append (map case-clauses clauses))
(,(rename 'else)
(,(rename 'cond)
,@(if eof-body
`(((,(rename 'eof-object?) ,(rename 'value))
,@eof-body))
'())
(,(rename 'else) ,@(or else-body '()))))))))
(apply expand (cdr form))))))