Next: , Previous: , Up: stdlib syntax-case   [Index]


5.12.6 Identifier predicates

Identifiers are a basic concept of hygienic macro expansion: it is possible to write macros with confidence only with a through understanding of identifiers. Let’s analyse a simple form, which we can imagine (for now) to appear at the top level of a program body:

(let ((alpha 123))
  alpha)

in it appear two distinct Scheme symbols: ‘let’ once, ‘alpha’ twice; none of them appears in a quoted form, so all of them are identifiers. We have to acknowledge that the number of distinct identifiers is three; the two instances of ‘alpha’ are different identifiers.

Moreover, the first instance of ‘alpha’ appears at the left side of a ?bindings element of the let syntax, so it is said to be in “binding position”; the second instance does not appear in a binding position, so it is said to be in “reference position”. Binding constructs

NOTE In the following descriptions, the procedure arguments with name id are meant to be syntax objects, each holding only an identifier.

Procedure: identifier? obj

Return #t if obj is an identifier, i.e., a syntax object representing an identifier, and #f otherwise.

The identifier? procedure is often used within a fender to verify that certain subforms of an input form are identifiers, as in the definition of rec, which creates self–contained recursive objects, below.

(define-syntax rec
  (lambda (x)
    (syntax-case x ()
      ((_ x e)
       (identifier? #'x)
       #'(letrec ((x e)) x)))))

(map (rec fact
       (lambda (n)
         (if (= n 0)
             1
             (* n (fact (- n 1))))))
     '(1 2 3 4 5))
⇒ (1 2 6 24 120)

(rec 5 (lambda (x) x))
error→ exception &syntax

The procedures bound-identifier=? and free-identifier=? each take two identifier arguments and return #t if their arguments are equivalent and #f otherwise. These predicates are used to compare identifiers according to their intended use as free references or bound identifiers in a given context.

Procedure: bound-identifier=? id1 id2

Return #t if a binding for one would capture a reference to the other in the output of the transformer, assuming that the reference appears within the scope of the binding; return #f otherwise.

In general, two identifiers are bound-identifier=? only if both are present in the original program or both are introduced by the same transformer application (perhaps implicitly, see datum->syntax).

Operationally, two identifiers are considered equivalent by bound-identifier=? if and only if they have the same name and the same marks.

The bound-identifier=? procedure can be used for detecting duplicate identifiers in a binding construct or for other preprocessing of a binding construct that requires detecting instances of the bound identifiers.

For example, let’s consider this macro:

(define-syntax doit
  (lambda (stx)
    (syntax-case stx ()
      ((_ id1 id2)
       (begin
         (display (bound-identifier=? #'id1 #'id2))
         #'(let ((id1 123)) id2))))))

in the following macro use the identifiers are bound-identifier=?:

(doit alpha alpha)
⇒ 123
-| #t

because binding one in the output form of the macro use, “captures” the reference of the other one; in the following macro use the identifiers are not bound-identifier=?:

(let ((beta 456))
  (doit alpha beta))
⇒ 456
-| #f

because binding one does not capture the reference of the other.

Procedure: free-identifier=? id1 id2

Return #t if and only if the two identifiers would resolve to the same binding if both were to appear in the output of a transformer, outside of any bindings inserted by the transformer. Here is an example showing that it is the origin of the bindings that matters, not the actual symbol in the identifier:

(import (rnrs)
  (prefix (only (rnrs) vector) that:))

(define-syntax doit
  (lambda (stx)
    (syntax-case stx ()
      ((_ id1 id2)
       (begin
         (display (free-identifier=? #'id1 #'id2))
         #f)))))

(doit vector that:vector)
-| #t

If neither of two like–named identifiers resolves to a binding, i.e., both are unbound, they are considered to resolve to the same binding; example:

(import (rnrs))

(define-syntax doit
  (lambda (stx)
    (syntax-case stx ()
      ((_ id1 id2)
       (begin
         (display (free-identifier=? #'id1 #'id2))
         #f)))))

;; ALPHA and BETA are unbound here

(doit alpha alpha)
-| #t

(doit alpha beta)
-| #f

Operationally, two identifiers are considered equivalent by free-identifier=? if and only if: the topmost matching substitution for each maps to the same binding or the identifiers have the same name and no matching substitution. Let’s consider this program:

(import (rnrs))
(let ((alpha 123))
  (list alpha alpha))

if we substitute ‘alpha’ with ‘beta’ in the let form:

(import (rnrs))
(let ((beta 123))
  (list beta beta))

we obtain an equivalent program; this is because the two ‘alpha’ identifiers in the list form of the original program are free-identifier=?.

As last examples, notice that in the following program:

(import (rnrs))

(let ((alpha 123))
  (define beta alpha)
  (list alpha beta))

alpha’ and ‘beta’ in the list form are not free-identifiers=?; in the following program:

(import (rnrs))

(let ((alpha 123))
  (let-syntax ((beta (identifier-syntax alpha)))
    (list alpha beta)))

alpha’ and ‘beta’ in the list form are still not free-identifiers=?.

The syntax-case and syntax-rules forms internally use free-identifier=? to compare identifiers listed in the literals list against input identifiers:

(let ((fred 17))
  (define-syntax a
    (lambda (x)
      (syntax-case x ()
        ((_ id) #'(b id fred)))))
  (define-syntax b
    (lambda (x)
      (syntax-case x ()
        ((_ id1 id2)
         #`(list
             #,(free-identifier=? #'id1 #'id2)
             #,(bound-identifier=? #'id1 #'id2))))))
  (a fred))
⇒ (#t #f)

The following definition of unnamed let uses bound-identifier=? to detect duplicate identifiers:

(define-syntax let
  (lambda (x)
    (define (unique-ids? ls)
      (or (null? ls)
          (and (let notmem? ((x  (car ls))
                             (ls (cdr ls)))
                 (or (null? ls)
                     (and (not (bound-identifier=? x (car ls)))
                          (notmem? x (cdr ls)))))
               (unique-ids? (cdr ls)))))
    (syntax-case x ()
      ((_ ((i v) ...) e1 e2 ...)
       (unique-ids? #'(i ...))
       #'((lambda (i ...) e1 e2 ...) v ...)))))

the argument ‘#'(i ...)’ to unique-ids? is guaranteed to be a list by the rules given in the description of syntax.

With this definition of let:

(let ((a 3) (a 4))
  (+ a a))
error→ exception &syntax

however:

(let-syntax
    ((dolet (lambda (x)
              (syntax-case x ()
                ((_ b)
                 #'(let ((a 3) (b 4)) (+ a b)))))))
  (dolet a))
⇒ 7

since the identifier ‘a’ introduced by dolet and the identifier a extracted from the input form are not bound-identifier=?.

Rather than including ‘else’ in the literals list as before, this version of case explicitly tests for ‘else’ using free-identifier=?.

(define-syntax case
  (lambda (x)
    (syntax-case x ()
      ((_ e0 ((k ...) e1 e2 ...) ...
              (else-key else-e1 else-e2 ...))
       (and (identifier? #'else-key)
            (free-identifier=? #'else-key #'else))
       #'(let ((t e0))
           (cond
             ((memv t '(k ...)) e1 e2 ...)
             ...
             (else else-e1 else-e2 ...))))
      ((_ e0 ((ka ...) e1a e2a ...)
              ((kb ...) e1b e2b ...) ...)
       #'(let ((t e0))
           (cond
             ((memv t '(ka ...)) e1a e2a ...)
             ((memv t '(kb ...)) e1b e2b ...)
             ...))))))

With either definition of case, ‘else’ is not recognized as an auxiliary keyword if an enclosing lexical binding for ‘else’ exists. For example,

(let ((else #f))
  (case 0 (else (write "oops"))))
error→ exception &syntax

since ‘else’ is bound lexically and is therefore not the same ‘else’ that appears in the definition of case.


Next: , Previous: , Up: stdlib syntax-case   [Index]