t3x.org / sketchy / sk05.html
SketchyLISP
Reference
  Copyright (C) 2007
Nils M Holm

5 Syntax Transformation

Syntax transformation takes place between reading and evaluating an expression. Whenever the SketchyLISP interpreter finishes reading a form, it compares all its subforms against a set of syntax rules.

A syntax rule consists of a pattern and an associated template. When a pattern matches the application of a syntax transformer, the application is rewritten using the associated template.

The following syntax rules implement a simple when syntax, which is basically an if without an alternative:

(define-syntax when
  (syntax-rules ()
    ((_ condition command)
       (if condition command (void)))))

In this example

(_ condition command)

is a pattern (_ matches when) and

(if condition command (void))

is a template.

After adding the when syntax definition, whenever the interpreter finds an application of when, it transforms it to an application of if:

(when (f x) (display "f returned truth"))

is rewritten as

(if (f x) (display "f returned truth") (void))

Of course when is an imperative construct, so it should accept multiple commands. Here is a better version:

(define-syntax when
  (syntax-rules ()
    ((_ condition command ...)
       (if condition (begin command ...)
                     (void)))))

The ellipsis is a special symbol that indicates that more subforms may follow. These subforms replace the ellipsis in the template. Using the improved version of when, you can write, for instance:

(when (f x) (display "ok")
            (newline))

The result of a syntax transformation is once again searched for applications of syntax transformers. This way recursive syntax rules can be resolved. Here is a definition of let* that uses recursion:

(define-syntax let*
  (syntax-rules ()
    ((_ () x)                       ; rule 1
       (let () x))
    ((_ ((n v)) x)                  ; rule 2
       (let ((n v)) x))
    ((_ ((n1 v1) (n2 v2) ...) x)    ; rule 3
       (let ((n1 v1))
         (let* ((n2 v2) ...) x)))))

These rules transform an application of let* to a series of nested applications of let (a-->b denotes a syntax transformation from a to b):

(let* ((a 1)
       (b (+ 1 a))
       (c (+ 1 b))) c)
--> (let ((a 1))
      (let* ((b (+ 1 a))
             (c (+ 1 b))) c))       ; rule 3
--> (let ((a 1))
      (let ((b (+ 1 a)))
        (let* ((c (+ 1 b))) c)))    ; rule 3
--> (let ((a 1))
      (let ((b (+ 1 a)))
        (let ((c (+ 1 b))) c)))     ; rule 2

5.1 Procedures

5.1.1 define-syntax

(define-syntax sym1 (syntax-rules (sym2 ...) ...)) => #<void>

Define-syntax introduces a new keyword sym1 and binds a syntax transformer returned by syntax-rules to that keyword.

See syntax-rules for further details.

Applications of define-syntax are limited to the top level of a program.

The define-syntax syntax conforms to R5RS.

5.1.2 syntax->list

(syntax->list form) => list|#f

If form is a syntax transformer or a symbol bound to a syntax transformer, syntax->list returns a list containing the name, the keywords, and the syntax rules of that transformer.

If form is neither a syntax transformer nor a symbol bound to a syntax transformer, syntax->list returns #f.

Given the definition

(define-syntax when
  (syntax-rules ()
    ((_ when pred expr)
      (if pred expr #f))))

the following rules apply:

(syntax->list when)
    => (when () (((_ when pred expr) (if pred expr #f))))
(syntax->list 'when)
    => (when () (((_ when pred expr) (if pred expr #f))))
(syntax->list 'not-a-transformer)
    => #f

The syntax->list function a SketchyLISP extension.

5.1.3 syntax-rules

(syntax-rules (keyword1 ...) rule1 ...) => #<void>

Applications of syntax-rules evaluate to syntax transformers, which are bound to keywords using define-syntax. Syntax-rules is limited to the scope of define-syntax:

(syntax-rules () ((_) #f)) => bottom
(define-syntax foo (syntax-rules () ((_) #f))) => #<void>

Each rule of syntax-rules consists of a pattern and a template:

(pattern template)

The list forming the first argument of syntax-rules is a list of additional keywords that may occur inside of patterns.

See the following subsection for details on patterns, templates, and syntax transformation.

The syntax-rules pseudo function implements a subset of R5RS syntax-rules.

5.2 Pattern Matching and Substitution

The first stage in the transformation of syntax is the detection of syntax transformers. A syntax transformer is a set of syntax rules that is bound to a keyword using define-syntax. When the SketchyLISP interpreter finds a keyword, it attempts to transform the application of that keyword using the syntax rules bound to that keyword.

It finds out which rule to apply by matching the pattern of each rule against the application to transform. When multiple rules exist, it tries all patterns in sequence and proceeds with the first match. When no rules match, a syntax error is reported. In this case, the application of the keyword is neither rewritten nor evaluated.

Pattern matching is performed as follows:

Whenever a symbol that is not contained in the keyword list of syntax-rules is matched against a form, the symbol is bound to that form.

Here is a sample match of an application of let*:
(See the beginning of this section for the rules of let*.)

application: (let* ((a 1 ) (b (+ a 1))) b)
pattern 1:   (_    ()                   x)

The first pattern does not match, because () does not match ((a 1) (b (+ a 1))).

The second pattern does not match either:

application: (let* ((a 1 ) (b (+ a 1))) b)
pattern 2:   (_    ((n v))              x)

But the third one does:

application: (let* ((a  1 ) (b  (+ a 1))    ) b)
pattern 3:   (_    ((n1 v1) (n2 v2     ) ...) x)

The match results in the following associations:

((n1 . a) (v1 . 1) (n2 . b) (v2 . (+ a 1)) (x . b))

To rewrite an application, the associations resulting from the match are substituted in the template associated with the matched pattern. Substituting the above associations in the template

(let ((n1 v1)) (let* ((n2 v2) ...) x))

gives:

(let ((a 1)) (let* ((b (+ a 1))) b))

Note that ... is bound to nothing in the above match, so it simply vanishes when substituting its value in the template.

The result contains another application of let*. This application is also matched:

application: (let ((a 1)) (let* ((b (+ a 1))) b))
pattern 2:                (_    ((n v      )) x)

Substituting

((n . b) (v . (+ a 1)) (x . b))

in the associated template

(let ((n v)) x)

finally gives:

(let ((a 1)) (let ((b (+ a 1))) b))

Because this form does not contain any further applications of syntax transformers, it is the final result of the transformation.

5.2.1 Ellipses

An Ellipsis (...) matches any number of forms, including zero. Given the definition

(define-syntax when
  (syntax-rules ()
    ((_ condition command ...)
       (if condition (begin command ...)

the expression

(when #t (f) (g) (h))

generates the following bindings:

((condition . #t) (command . (f)) (... . ((g) (h))))

When substituting ... in a template, the ellipsis is replaced with all of the forms that it matched, so the template

(begin command ...)

becomes

(begin (f) (g) (h))

But ... does more than that. In the above example, there was a command in the pattern and a command in the template, so the value matched by command was just copied to the template.

When an ellipsis in a template is preceded by a structure that is more complex than just a variable name, an interesting property of ... is revealed. The following syntax serves as an example:

(define-syntax dup
  (syntax-rules ()
    ((_ x ...) (list (cons x x) ...))))

In this example, the form matched by x is substituted in (cons x x). When substituting the subsequent ellipsis, the transformation

x --> (cons x x)

is applied to each form that is bound to ..., so

(dup 'x 'y 'z) => ((x . x) (y . y) (z . z))