[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

SELECTP -- a useful new utility for pattern-matching (long)

Living in LMLIB;SELECT is a new macro called SELECTP, which is sort of a
generalization of SELECTQ.  I have found it extremely useful in writing
compilers and that sort of thing.  Here's an example of its use from the file
AGRE;SCDP, where many more examples can be found:

(defun unary-operation (command)
  (selectp command
    ((#?op #?r) (memq op '(push pop)) t)
    ((assign #?r1 #?r2) (symbolp r2) (eq r1 r2))
    ((assign #?r (continuation-pointer #?label)) t t)
    ((assign #?r1 (#?ignore #?r2 #?r3)) t
     (or (and (eq r1 r2) (eq r2 r3))
	 (and (constant-register-p r2) (constant-register-p r3))
	 (and (eq r1 r2) (constant-register-p r3))
	 (and (eq r1 r3) (constant-register-p r2))))
    ((assign #?r1 (#?ignore #?r2)) t (or (eq r1 r2) (constant-register-p r2)))
    ((#?ignore #?x #?y) (and (register-p x) (register-p y))
     (or (eq x y) (constant-register-p x) (constant-register-p y)))
    ((#?ignore #?x) (register-p x) t)
    (otherwise (ferror nil "Unrecognized command format: ~A" command))))

The syntax is 
   (SELECTP <object>
     (<pattern> <condition> <sexp> ... <sexp>)
     (<pattern> <condition> <sexp> ... <sexp>)
     (<pattern> <condition> <sexp> ... <sexp>)
     (OTHERWISE <sexp> <sexp>))

The value of <object> is matched against the <pattern>s one at a time until a
match succeeds and the accompanying <condition> evaluates to something
non-null, at which point the <sexp>'s associated with the <pattern> and
<condition> are evaluated one at a time and the last value is returned.  The
<pattern>s can be arbitrary s-expressions, with variables signified by
#?variable.  When the pattern is matched against the <object>'s value, the
variables are to bound to their matched values.  Different occurences of the
same variable in a given pattern must match to the same thing, so that

    (SELECTP '(A B C) 
      ((#?X B #?X) T 'LOSE)
      ((#?X B #?Y) T 'WIN)

returns WIN.  The variables mentioned in the <pattern>s need not be bound by
the user; they are bound by the expression resulting from the expansion of the
macro.  (The variable #?IGNORE matches everything and doesn't become bound.
Using #?IGNORE for a variable you don't intend to make any use of avoids
"bound but not used" warnings from the compiler.) There is no actual pattern
matcher involved in the matching process; rather, an s-expression is consed up
by the macro which has the same effect.  For example, the call to SELECTP just
presented expands to:

                 (LISTP (CDR OBJECT)) (EQ (CAR (CDR OBJECT)) 'B)
                 (LISTP (CDR (CDR OBJECT))) (EQUAL X (CAR (CDR (CDR OBJECT))))
                 (NULL (CDR (CDR (CDR OBJECT)))))
                 (LISTP (CDR OBJECT)) (EQ (CAR (CDR OBJECT)) 'B)
                 (LISTP (CDR (CDR OBJECT)))
	         (PROGN (SETQ Y (CAR (CDR (CDR OBJECT)))) T)
                 (NULL (CDR (CDR (CDR OBJECT)))))
           (T 'LOSE-BIG)))
 '(A B C))

(In case your terminal lost, those control characters are greek letters.)

It seems to work in all Lisp Machine systems.  Bugs/suggestions to AGRE@MIT-AI.