COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	DRAFT	  The Pattern Match Compiler       Page 1
C00004 00003	DRAFT	  The Pattern Match Compiler       Page 2
C00008 00004	DRAFT	  The Pattern Match Compiler       Page 3
C00010 00005	DRAFT	  The Pattern Match Compiler       Page 4
C00012 00006	DRAFT	  The Pattern Match Compiler       Page 5
C00019 ENDMK
C⊗;
DRAFT	  The Pattern Match Compiler       Page 1


This is  a preliminary writeup  of the pattern  match compiler  to be
embeded as part  of the CLISP feature of BBN-LISP. It's purpose is to
make easier the writing of complicated tests by specifying  a pattern
which some  data structure  is supposed to  match. The  pattern match
compiler  will, upon  encountering a  "match" type construction  in a
user's code,  will substitute  an appropriate  expression which  will
perform that  match.  This feature  is not intended to  be as general
purpose as many pattern match oriented languages and features  (FLIP,
pattern matching in PLANNER, etc.), but rather,  as a convenience for
specifying  simple tests  which might otherwise  be clumsy  to write,
and not as intelligible.


PATTERN ELEMENTS

A  pattern consists  of  a list  of  pattern elements.  Each  pattern
element is  said to match either an element of  a data structure or a
segment.  (cf  the  editor's  pattern  matcher,    "--"  matches  any
arbitrary segment of a list, while  & or a subpattern, match only one
element  of a list).  Those patterns which  may match a  segment of a
list are called SEGMENT  patterns; those that match a  single element
are called ELEMENT patterns.

DRAFT	  The Pattern Match Compiler       Page 2

ELEMENT PATTERNS:

There are several types of element patterns, best given
by their syntax:

    PATTERN			MEANING

     $1, or &		 matches any arbitrary element of a list

     's-expression       matches only an element which is EQUAL
			 to the given s-expression.

    =expression		matches only an element which is EQUAL to
			the value of the computation "expression"

    ==expression 	same as =, but uses EQ

			(note that 'FOO is really just a short hand
			 for ='FOO

    (sub-pattern)	this will match any element which matches
			the given sub-pattern




      :function-name	    matches only an element for which the named
                       	    function returns non-NIL when applied to
                            it.


	*		the * pattern will match any arbitrary element;
			if the entire match succeeds, however, the element
			which matched the * will be returned as the value
			of the match.  Note that usually the pattern match
			compiler will construct an expression which returns
			either NIL if the match fails, or non-NIL if it suceeds;
			however, if a * occurs, this is overridden, and the
			expression generated will either return NIL if the
			match fails, or WHATEVER MATCHED THE * (even though
			that may be NIL.)
DRAFT	  The Pattern Match Compiler       Page 3

        	SEGMENT PATTERNS

PATTERN				MEANING

  $, or --		This pattern will match any segment of a list
			(even one of zero length)

  $2, $3, ...		These will match a segment of the given length
			note that $1 is not a segment pattern.  (later
			in the discussion of "←", the distinction be-
			tween a segment of length 1 and an element will
			be made clear)




  ! element pattern     This matches any segment which the given element
			pattern would match-- i.e. 

			   !&  =  $
			   !=FOO, if the value of FOO is (A B C) will match
				the segment ... A B C ... etc.
			   !* is like  valueofmatch←$

			! and . are interchangeable;  that is, the atom
			%. is treated exactly like !; and patterns which
			end with ...  . atom)  are translated to
			... ! atom) first.

   NOTE:  A ! pattern is always valid as the LAST pattern element;
	(... !=FOO) checks for the appropriate tail being FOO. However,
	in general, only the following ! patterns are implemented (the
	others will cause an error):

	!*
	! (subpattern)



DRAFT	  The Pattern Match Compiler       Page 4

	SETS and REPLACES

Any pattern element may  be preceded by <VARIABLE>←,   or followed by
←<expression>.

The former  means that, if  the match succeeds  (everything matches),
the  variable  given  is  to be  set  to  WHAT  MATCHED that  pattern
element.  In the case of  element patterns, this will be simply  some
CAD...DR; for segment patterns, this will be some LDIFF.

In the  latter  case, (i.e.  patelt←expression), this  means that  if
everything matches the  part of the data that matched is to RPLAC'ed.
For segment  replaces, this  means a  construction  like (RPLAC  data
(APPEND expression data))

WARNING:
    (1) segment replaces are not currently supported:
	(... $←expr ...) will currently cause an error

DRAFT	  The Pattern Match Compiler       Page 5

		EXAMPLES


($ 'A $)     The $ matches any arbitrary segment, 'A matches
	     only an A, and the 2nd $ is again an arbitrary 
	     segment; thus this translates to
		(MEMB (QUOTE A) expression)

($ 'A)	     Again, the $ is an arbitrary segment; however, since
	     their is no $ after the 'A, it must be the last element
	     of the list; thus this translates to

		(EQ (CAR (LAST expression)) (QUOTE A]


('A 'B $ 'C $3 $)   (AND (EQ (CAR expression) (QUOTE A))
			 (EQ (CADR expression) (QUOTE B))
			 (CDDDR (MEMB (QUOTE C) (CDDR expression))))

		the car must be A, the cadr B, and there must be at
		least 3 elements after the first C in the CDDR.
		Note that it is assumed that one is matching lists
		which end in NIL rather than in other atoms, so that
		it is assumed that if the (CDDDR (MEMB --)) is non-
		NIL, it is actually LISTP.

(('A 'B) 'C Y←$1 $)   (COND ((AND (EQ (CAAR expression) (QUOTE A))
				  (EQ (CADAR expression) (QUOTE B))
				  (NULL (CDDAR expression))
				  (EQ (CADR expression) (QUOTE C))
				  (CDDR expression)
				(SETQ Y (CADDR expression))
				T))

		Since the ('A 'B) part does not end in $,
		(CDDAR expression) must be NULL.