From posting-system@google.com Tue Sep 30 19:07:16 2003
Date: Tue, 30 Sep 2003 12:03:44 -0700
From: oleg@pobox.com (oleg@pobox.com)
Newsgroups: comp.lang.scheme
Subject: How to write symbol? with syntax-rules
Message-ID: <7eb8ac3e.0309301103.5200afbf@posting.google.com>
Status: OR

We show a syntax-rule macro-predicate that can be applied to _any_
expression and can soundly and reliably determine if that expression
is a symbol/literal (as opposed to a pair, a vector, a literal string,
a literal number, etc). The mere existence of such a predicate is
surprising and counter-intuitive. For completeness and reference, we
also show two macro-identity predicates on identifiers: id-eq?? and
id-eqv??.

It is well-known that syntax-rules are limited in expressive
power. For example, we can easily write a low-level macro that can
tell the literal type of its argument -- whether the argument a
symbol/identifier, a literal string, a literal character, or a literal
number:

	(define-macro (typeof x)
	   (cond
	     ((integer? x) "an integer")
	     ((symbol? x)  "a symbol/identifier")
	     ((pair? x)    "a pair")
	     ((string? x)  "a string")))

(typeof "str") ==> "a string"
(typeof xxx)   ==> "a symbol/identifier"

We can write a similar discriminator with syntax-case. The syntax-case
macro system has "guards" specifically for that purpose:

	(define-syntax typeof
	  (lambda (x)
	   (syntax-case x ()
	     ((typeof x) (integer? (syntax-object->datum #'x)) "an integer")
	     ((typeof x) (identifier? #'x) "an identifier")
	     ((typeof x) (pair? (syntax-object->datum #'x)) "a pair")
	     ((typeof x) (string? (syntax-object->datum #'x)) "a string"))))
	

(typeof "str")   ==> "a string"
(typeof 1)       ==> "an integer"
(typeof typeof)  ==> "an identifier"

The latter example runs on Petite Chez Scheme.

Syntax-rules can determine the literal type of some arguments: a pair, a
vector, an empty list, a boolean:

	(define-syntax typeof
	  (syntax-rules ()
	    ((typeof (x . y)) "a pair")
	    ((typeof #(x ...)) "a vector")
	    ((typeof #f)  "a boolean")
	    ((typeof #t)  "a boolean")
	    ))

We can also write a syntax-rule that tests if its argument is _the_
specific number, _the_ specific character, _the_ specific string. A
syntax-rule cannot determine if its argument is _a_ string or _an_
integer.


For a long time I used to think that we cannot write a syntax-rule
that tests if its argument is _a_ symbol. In particular, I wanted a
macro-expand-time equivalent of the library function symbol?. We will
call that macro symbol?? to avoid the confusion with the library
function. That macro should take three arguments: any syntactic form
plus two continuations, kt and kf. The macro symbol?? will expand to kt
if and only if its first argument is a symbol. The macro would expand
to kf if its argument is _anything_ other than a symbol. I believed
such a macro symbol?? is impossible with syntax-rules -- until about a
month ago I wrote it.

(define-syntax symbol??
  (syntax-rules ()
    ((symbol?? (x . y) kt kf) kf)	; It's a pair, not a symbol
    ((symbol?? #(x ...) kt kf) kf)	; It's a vector, not a symbol
    ((symbol?? maybe-symbol kt kf)
      (let-syntax
	((test
	   (syntax-rules ()
	     ((test maybe-symbol t f) t)
	     ((test x t f) f))))
	(test abracadabra kt kf)))))

The macro is based on the observation that if a form F is an
identifier and a syntax-rule pattern P is anything but a literal
identifier, then P can match F if and only if P is an identifier
(symbol). The final form of this macro incorporates an improvement by
Al Petrofsky.

As a bonus, the following two macros, id-eq?? and id-eqv??, test the
equivalence of identifiers. Both macros take two identifiers, and two
continuations, kt and kf. The macros expand into kt if the two
identifiers are equivalent. The macros expand into kf otherwise.

(define-syntax id-eq??
  (syntax-rules ()
    ((id-eq?? id b kt kf)
      (let-syntax
	((id (syntax-rules ()
	       ((id) kf)))
	 (ok (syntax-rules ()
	       ((ok) kt))))
	(let-syntax
	  ((test (syntax-rules ()
		   ((_ b) (id)))))
	  (test ok))))))

(define-syntax id-eqv??
  (syntax-rules ()
    ((id-eqv?? a b kt kf)
      (let-syntax
	((test (syntax-rules (a)
	      ((test a) kt)
	      ((test x) kf))))
	(test b)))))

For the macro id-eq??, two identifiers are equivalent if only if they
have the same color, or to put it differently, are two occurrences of
the same identifier. In other words, the two identifiers must be
inter-changeable at macro-expand time. This is the strictest notion of
equivalence. For a macro id-eqv??, the identifiers are equivalent if
they refer to the same binding (or both identifiers are unbound and
have the same spelling). Thus macro id-eqv?? can find two identifiers
equivalent even if they have different colors. The last two test cases
show the distinction.


Appendix A. Test cases for symbol??
The test cases are tried on SCM, Petite Chez Scheme, Scheme48 and
Bigloo.

(display (symbol?? a 'yes #f))
(newline)
(display (symbol?? 34 'yes #f))
(newline)
(display (symbol?? #xff 'yes #f))
(newline)
(display (symbol?? () 'yes #f))
(newline)
(display (symbol?? quote 'yes #f))
(newline)
(symbol?? display (display 'yes) (display #f))
(newline)
(symbol?? (x x x x) (display 'yes) (display #f))
(newline)
(symbol?? (() . 1) (display 'yes) (display #f))
(newline)
(symbol?? (x ... x) (display 'yes) (display #f))
(newline)
(display (symbol?? x '... #f))
(newline)
(let ((yes 'yes) (no 'no))
  (display (symbol?? yes yes no))
  (newline))

Appendix B. Test cases for id-eq?? and id-eqv??

(display "id-eq??") (newline)

(display (id-eq?? foo foo 'yes #f))
(newline)
(display (id-eq?? foo bar 'yes #f))
(newline)

(let ((foo 'yes))
  (display (id-eq?? foo foo foo #f)))
(newline)

(display "id-eqv??") (newline)
(display (id-eqv?? foo foo 'yes #f))
(newline)
(display (id-eqv?? foo bar 'yes #f))
(newline)

(let ((foo 'yes))
  (display (id-eqv?? foo foo foo #f)))
(newline)

(define-syntax mfoo
  (syntax-rules ()
    ((mfoo tester a)
      (tester foo a 'yes 'no))))

; expected answer: (id-eq??:  no no)
(display
  (list "id-eq??: "
    (mfoo id-eq?? foo)
    (let ((foo 1)) (mfoo id-eq?? foo))))
(newline)

; expected answer: (id-eqv??:  yes no)
(display
  (list "id-eqv??: "
    (mfoo id-eqv?? foo)
    (let ((foo 1)) (mfoo id-eqv?? foo))))
(newline)