{Begin SubSec Pattern Match Compiler}
{Title Pattern Match Compiler}
{Text
{note The pattern match compiler was written by L. M. Masinter.}
{it
Note: The pattern match compiler is a LispUsers package which can be loaded from the file {lisp MATCH.DCOM}. The entries have a {prop FILEDEF} property (see {PageRef Prop FILEDEF}), so simply using a pattern match construct will cause the file to be loaded automatically.
}
{index *BEGIN* pattern match compiler}
{Tag PatternMatch}
The pattern match compiler provides a fairly general pattern match facility within CLISP. This facility allows the user to specify certain tests that would otherwise be clumsy to write, by giving a pattern which the datum is supposed to match. Essentially, the user writes "Does the (expression) X look like (the pattern) P?" For example, {lisp X:(& 'A -- 'B)} asks whether the second element of {lisp X} is an {lisp A}, and the last element a {lisp B}. The implementation of the matching is performed by computing (once) the equivalent Interlisp expression which will perform the indicated operation, and substituting this for the pattern, and {it not} by invoking each time a general purpose capability such as that found in FLIP or PLANNER. For example, the translation of {lisp X:(& 'A -- 'B)} is:
{lispcode
(AND (EQ (CADR X) 'A)
(EQ (CAR (LAST X)) 'B))}
Thus the CLISP pattern match facility is really a Pattern Compiler, and the emphasis in its design and implementation has been more on the efficiency of object code than on generality and sophistication of its matching capabilities.
The goal was to provide a facility that could and would be used even where efficiency was paramount, e.g., in inner loops. As a result, the CLISP pattern match facility does not contain (yet) some of the more esoteric features of other pattern match languages, such as repeated patterns, disjunctive and conjunctive patterns, recursion, etc. However, the user can be confident that what facilities it does provide will result in Interlisp expressions comparable to those he would generate by hand.{foot
Wherever possible, already existing Interlisp functions are used in the translation, e.g., the translation of {lisp ($ 'A $)} uses {fn MEMB}, {lisp ($ ('A $) $)} uses {fn ASSOC}, etc.
}{comment endfootnote}
The syntax for pattern match expressions is {lisp {arg FORM}:{arg PATTERN}}, where {arg PATTERN} is a list as described below. As with iterative statements, the translation of patterns, i.e., the corresponding Interlisp expressions, are stored in the hash array {index CLISPARRAY Var}{var CLISPARRAY} (see {PageRef Var CLISPARRAY}). The original expression, {lisp {arg FORM}:{arg PATTERN}}, is replaced by an expression of the form {index MATCH (use in pattern match in CLISP)}{lisp (MATCH {arg FORM} WITH {arg PATTERN})}.
CLISP also recognizes expressions input in this form.
If {arg FORM} appears more than once in the translation, and it is not either a variable, or an expression that is easy to (re)compute, such as {lisp (CAR Y), (CDDR Z)}, etc., a dummy variable will be generated and bound to the value of {arg FORM} so that {arg FORM} is not evaluated a multiple number of times.
For example, the translation of {lisp (FOO X):($ 'A $)} is simply {lisp (MEMB 'A (FOO X))}, while the translation of {lisp (FOO X):('A 'B --)} is:
{lispcode
[PROG ($$2)
(RETURN
(AND (EQ (CAR (SETQ $$2 (FOO X)))
'A)
(EQ (CADR $$2) 'B]}
In the interests of efficiency, the pattern match compiler assumes that all lists end in {lisp NIL}, i.e., there are no {fn LISTP} checks inserted in the translation to check tails. For example, the translation of {lisp X:('A & --)} is {lisp (AND (EQ (CAR X) (QUOTE A)) (CDR X))}, which will match with {lisp (A B)} as well as {lisp (A . B)}. Similarly, the pattern match compiler does not insert
{fn LISTP} checks{indexX {Name LISTP checks} {Type (in Pattern Match Compiler)} {Text {lisp LISTP} checks} } on elements, e.g., {lisp X:(('A --) --)} translates simply as {lisp (EQ (CAAR X) 'A)}, and {lisp X:(($1 $1 --) --)} as {lisp (CDAR X)}.{foot
The insertion of {fn LISTP} checks for {it elements} is controlled by the variable {var PATLISTPCHECK}.{index PATLISTPCHECK Var}
When {var PATLISTPCHECK} is {lisp T}, {fn LISTP} checks are inserted, e.g., {lisp X:(('A --) --)} translates as:
{lisp (EQ (CAR (LISTP (CAR (LISTP X)))) 'A)}.
{var PATLISTPCHECK} is initially {lisp NIL}.
Its value can be changed within a particular function by using a local CLISP declaration (see {PageRef Tag CLISPLocalDeclarations}).
}{comment endfootnote}
Note that the user can explicitly insert {fn LISTP} checks himself by using {lisp @}, as described below, e.g., {lisp X:(($1 $1 --)@LISTP --)} translates as {lisp (CDR (LISTP (CAR X)))}.
{Begin SubSec Pattern Elements}
{Title Pattern Elements}
{Text
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, "{lisp --}" matches any arbitrary segment of a list, while {lisp &} or a subpattern match only one element of a list.) Those patterns which may match a segment of a list are called {it segment} patterns; those that match a single element are called {it element} patterns.
}{End SubSec Pattern Elements}
{Begin SubSec Element Patterns}
{Title Element Patterns}
{Text
{indexX {Name element patterns} {Type (in Pattern Match Compiler)}
{Info *BEGIN*} {Text element patterns} }
There are several types of element patterns, best given by their syntax:
{Begin LabeledList several types of element patterns}
{Label {lisp $1} or {lisp &}}
{Item
{index $1 (in Pattern Match Compiler)}{index & (in Pattern Match Compiler)}Matches an arbitrary element of a list.
}
{Label {lisp '{arg EXPRESSION}}}
{Item
{index ' (in Pattern Match Compiler)}Matches only an element which is equal to the given expression e.g., {lisp 'A}, {lisp '(A B)}.
{fn EQ}, {fn MEMB}, and {fn ASSOC} are automatically used in the translation when the quoted expression is atomic, otherwise {fn EQUAL}, {fn MEMBER}, and {fn SASSOC}.
}
{Label {lisp ={arg FORM}}}
{Item
{index = (in Pattern Match Compiler)}Matches only an element which is {fn EQUAL} to the value of {arg FORM}, e.g., {lisp =X}, {lisp =(REVERSE Y)}.
}
{Label {lisp =={arg FORM}}}
{Item
{index == (in Pattern Match Compiler)}Same as {lisp =}, but uses an {fn EQ} check instead of {fn EQUAL}.
}
{Label {arg ATOM}}
{Item
The treatment depends on setting of {var PATVARDEFAULT}.{index PATVARDEFAULT Var}
If {var PATVARDEFAULT} is {lisp '} or {lisp QUOTE}, same as {lisp '{arg ATOM}}. If {var PATVARDEFAULT} is {lisp =} or {lisp EQUAL},
same as {lisp ={arg ATOM}}. If {var PATVARDEFAULT} is {lisp ==} or {lisp EQ}, same as {lisp =={arg ATOM}}. If {var PATVARDEFAULT} is {lisp ←} or {lisp SETQ}, same as {lisp {arg ATOM}←&}. {var PATVARDEFAULT} is initially {lisp '}.
{var PATVARDEFAULT} can be changed within a particular function by using a local CLISP declaration (see {PageRef Tag CLISPLocalDeclarations}).
Note: numbers and strings are always interpreted as though {index PATVARDEFAULT Var}{var PATVARDEFAULT} were {lisp =}, regardless of its setting. {fn EQ}, {fn MEMB}, and {fn ASSOC} are used for comparisons involving small integers.
}
{Label {lisp ({arg PATTERN{sub 1}} {ellipsis} {arg PATTERN{sub N}})}
{arg N}{GE}1}
{Item
Matches a list which matches the given patterns, e.g., {lisp (& &)}, {lisp (-- 'A)}.
}
{Label {lisp {arg ELEMENT-PATTERN}@{arg FN}}}
{Item
{index @ (in Pattern Match Compiler)}Matches an element if {arg ELEMENT-PATTERN} matches it, and {arg FN} (name of a function or a {lisp LAMBDA} expression) applied to that element returns non-{lisp NIL}. For example, {lisp &@NUMBERP} matches a number and {lisp ('A --)@FOO} matches a list whose first element is {lisp A}, and for which {lisp FOO} applied to that list is non-{lisp NIL}.
For "simple" tests, the function-object is applied before a match is attempted
with the pattern, e.g., {lisp ((-- 'A --)@LISTP --)} translates as {lisp (AND (LISTP (CAR X)) (MEMB 'A (CAR X)))}, not the other way around. {arg FN} may also be a {arg FORM} in terms of the variable {lisp @}, e.g., {lisp &@(EQ @ 3)} is equivalent to {lisp =3}.
}
{Label {lisp *}}
{Item
{index * (in Pattern Match Compiler)}Matches any arbitrary element. If the entire match succeeds, the element which matched the {lisp *} will be returned as the value of the match.
Note: Normally, the pattern match compiler constructs an expression whose value is guaranteed to be non-{lisp NIL} if the match succeeds and {lisp NIL} if it fails. However, if a {lisp *}{index * (in Pattern Match Compiler)} appears in the pattern, the expression generated could also return {lisp NIL} if the match succeeds and {lisp *} was matched to {lisp NIL}. For example, {lisp X:('A * --)} translates as {lisp (AND (EQ (CAR X) 'A) (CADR X))}, so if {lisp X} is equal to {lisp (A NIL B)} then {lisp X:('A * --)} returns {lisp NIL} even though the match succeeded.
}
{Label {lisp ~{arg ELEMENT-PATTERN}}}
{Item
{index ~ (in Pattern Match Compiler)}Matches an element if the element is {it not} matched by {arg ELEMENT-PATTERN}, e.g., {lisp ~'A}, {lisp ~=X}, {lisp ~(-- 'A --)}.
}
{Label {lisp (*ANY* {arg ELEMENT-PATTERN} {arg ELEMENT-PATTERN} {ellipsis})}}
{Item
Matches if any of the contained patterns match.
}
{End LabeledList several types of element patterns}
{indexX {Name element patterns} {Type (in Pattern Match Compiler)}
{Info *END*} {Text element patterns} }
}{End SubSec Element Patterns}
{Begin SubSec Segment Patterns}
{Title Segment Patterns}
{Text
{indexX {Name segment patterns} {Type (in Pattern Match Compiler)}
{Info *BEGIN*} {Text segment patterns} }
{Begin LabeledList Segment Patterns}
{Label {lisp $} or {lisp --}}
{Item
{index $ (dollar) (in Pattern Match Compiler)}{index -- (in Pattern Match Compiler)}Matches any segment of a list (including one of zero length).
}
{End LabeledList Segment Patterns}
The difference between {lisp $} and {lisp --} is in the type of search they generate. For example, {lisp X:($ 'A 'B $)} translates as {lisp (EQ (CADR (MEMB 'A X)) 'B)}, whereas {lisp X:(-- 'A 'B $)} translates as:
{lispcode
[SOME X
(FUNCTION (LAMBDA ($$2 $$1)
(AND (EQ $$2 'A)
(EQ (CADR $$1) 'B]}
Thus, a paraphrase of {lisp ($ 'A 'B $)} would be "Is the element following the {it first} {lisp A} a {lisp B}?", whereas a paraphrase of {lisp (-- 'A 'B $)} would be "Is there {it any} {lisp A} immediately followed by a {lisp B}?"
Note that the pattern employing {lisp $} will result in a more efficient
search than that employing {lisp --}. However, {lisp ($ 'A 'B $)} will not match with {lisp (X Y Z A M O A B C)}, but {lisp (-- 'A 'B $)} will.
Essentially, once a pattern following a {lisp $} matches, the {lisp $} never resumes searching, whereas {lisp --} produces a translation that will always continue searching until there is no possibility of success. However, if the pattern match compiler can deduce from the pattern that continuing a search after a particular failure cannot possibly succeed, then the translations for both {lisp --} and {lisp $} will be the same. For example, both {lisp X:($ 'A $3 $)} and {lisp (-- 'A $3 --)} translate as {lisp (CDDDR (MEMB (QUOTE A) X))}, because if there are not three elements following the first {lisp A}, there certainly will not be three elements following subsequent {lisp A}'s, so there is no reason to continue searching, even for {lisp --}. Similarly, {lisp ($ 'A $ 'B $)} and {lisp (-- 'A -- 'B --)} are equivalent.
{Begin LabeledList More Segment Patterns}
{Label {lisp $2}, {lisp $3}, etc.}
{Item
{index $n (in Pattern Match Compiler)}Matches a segment of the given length.
Note that {lisp $1} is not a segment pattern.
}
{Label {lisp !{arg ELEMENT-PATTERN}}}
{Item
{index ! (in Pattern Match Compiler)}Matches any segment which {arg ELEMENT-PATTERN} would match as a list. For example, if the value of {lisp FOO} is {lisp (A B C)}, {lisp !=FOO} will match the segment {lisp {ellipsis} A B C {ellipsis}} etc. Note that {lisp !*} is permissible and means {lisp {arg VALUE-OF-MATCH}←$}, e.g., {lisp X:($ 'A !*)} translates to {lisp (CDR (MEMB 'A X))}.
}
{UnIndented
Note: since {lisp !} appearing in front of the last pattern specifies a match with some {it tail} of the given expression, it also makes sense in this case for a {lisp !} to appear in front of a pattern that can only match with an atom, e.g., {lisp ($2 !'A)} means match if {fn CDDR} of the expression is the atom {lisp A}.
Similarly, {lisp X:($ ! 'A)} translates to {lisp (EQ (CDR (LAST X)) 'A)}.
}
{Label {lisp !{arg ATOM}}}
{Item
{index ! (in Pattern Match Compiler)}treatment depends on setting of {var PATVARDEFAULT}.{index PATVARDEFAULT Var}
If {var PATVARDEFAULT} is {lisp '} or {lisp QUOTE},
same as {lisp !'{arg ATOM}} (see above discussion).
If {var PATVARDEFAULT} is {lisp =} or {lisp EQUAL},
same as {lisp !={arg ATOM}}.
If {var PATVARDEFAULT} is {lisp ==} or {lisp EQ},
same as {lisp !=={arg ATOM}}.
If {var PATVARDEFAULT} is {lisp ←} or {lisp SETQ},
same as {lisp {arg ATOM}←$}.
}
{Label {lisp .}}
{Item
{index . (in Pattern Match Compiler)}The atom "{lisp .}" is treated {it exactly} like "{lisp !}". In addition, if a pattern ends in an atom, the "{lisp .}" is first changed to "{lisp !}", e.g., {lisp ($1 . A)} and {lisp ($1 ! A)} are equivalent, even though the atom "{lisp .}" does not explicitly appear in the pattern.
One exception where "{lisp .}" is not treated like "{lisp !}": "{lisp .}" preceding an assignment does not have the special interpretation that "{lisp !}" has preceding an assignment (see below). For example, {lisp X:('A . FOO←'B)} translates as:
{lispcode
(AND (EQ (CAR X) 'A)
(EQ (CDR X) 'B)
(SETQ FOO (CDR X)))}
but {lisp X:('A ! FOO←'B)} translates as:
{lispcode
(AND (EQ (CAR X) 'A)
(NULL (CDDR X))
(EQ (CADR X) 'B)
(SETQ FOO (CDR X)))}
}
{Label {lisp {arg SEGMENT-PATTERN}@{arg FUNCTION-OBJECT}}}
{Item
{index @ (in Pattern Match Compiler)}Matches a segment if the segment-pattern matches it, and the function object applied to the corresponding segment (as a list) returns non-{lisp NIL}. For example, {lisp ($@CDDR 'D $)} matches {lisp (A B C D E)} but not {lisp (A B D E)}, since {lisp CDDR} of {lisp (A B)} is {lisp NIL}.
Note: an {lisp @} pattern applied to a segment will require {it computing} the corresponding structure (with {fn LDIFF}) each time the predicate is applied (except when the segment in question is a tail of the
list being matched).
}
{End LabeledList More Segment Patterns}
{indexX {Name segment patterns} {Type (in Pattern Match Compiler)}
{Info *END*} {Text segment patterns} }
}{End SubSec Segment Patterns}
{Begin SubSec Assignments}
{Title Assignments}
{Text
Any pattern element may be preceded by {index ← (in Pattern Match Compiler)}"{lisp {arg VARIABLE}←}", meaning that if the match succeeds (i.e., everything matches), {arg VARIABLE} is to be set to the thing that matches that pattern element.{indexX {Name assignments} {Type (in Pattern Match Compiler)} {Text assignments} } For example, if {lisp X} is {lisp (A B C D E)}, {lisp X:($2 Y←$3)} will set {lisp Y} to {lisp (C D E)}. Note that assignments are not performed until the entire match has succeeded, so assignments cannot be used to specify a search for an element found earlier in the match, e.g., {lisp X:(Y←$1 =Y --)}{foot
The translation of this pattern is: {lisp (COND ((AND (CDR X) (EQUAL (CADR X) Y)) (SETQ Y (CAR X)) T))}. The {lisp AND} is used because if {lisp Y} is {lisp NIL}, the pattern should match with {lisp (A NIL)}, but not with just {lisp (A)}. The {lisp T} is because {lisp (CAR X)} might be {lisp NIL}.
}{comment endfootnote}
will {it not} match with {lisp (A A B C ...)}, unless, of course, the value of {lisp Y} was {lisp A} before the match started. This type of match is achieved by using place-markers, described below.
If the variable is preceded by a {lisp !},{index ! (in Pattern Match Compiler)} the assignment is to the {it tail} of the list as of that point in the pattern, i.e., that portion of the list matched by the remainder of the pattern. For example, if {lisp X} is {lisp (A B C D E)}, {lisp X:($ !Y←'C 'D $)} sets {lisp Y} to {lisp (C D E)}, i.e., {fn CDDR} of {lisp X}. In other words, when {lisp !} precedes an assignment, it acts as a modifier to the {lisp ←}, and has no effect whatsoever on the pattern itself, e.g., {lisp X:('A 'B)} and {lisp X:('A !FOO←'B)} match identically, and in the latter case, {lisp FOO} will be set to {lisp CDR} of {lisp X}.
Note: {lisp *←{arg PATTERN-ELEMENT}} and {lisp !*←{arg PATTERN-ELEMENT}} are acceptable, e.g., {lisp X:($ 'A *←('B --) --)} translates as:
{lispcode
[PROG ($$2)
(RETURN
(AND (EQ (CAADR (SETQ $$2 (MEMB 'A X))) 'B)
(CADR $$2]}
}{End SubSec Assignments}
{Begin SubSec Place-Markers}
{Title Place-Markers}
{Text
{indexX {Name place-markers} {Type (in Pattern Match Compiler)}
{Text place-markers} }
{indexX {Name #} {Type (in Pattern Match Compiler)}
{Text {lisp #{arg N}} ({arg N} a number)} }
Variables of the form {lisp #{arg N}}, {arg N} a number, are called place-markers, and are interpreted specially by the pattern match compiler.
Place-markers are used in a pattern to mark or refer to a particular pattern element. Functionally, they are used like ordinary variables, i.e., they can be assigned values, or used freely in forms appearing in the pattern, e.g.,
{lisp X:(#1←$1 =(ADD1 #1))} will match the list {lisp (2 3)}. However, they are not really variables in the sense that they are not bound, nor can a function called from within the pattern expect to be able to obtain their values.
For convenience, regardless of the setting of {var PATVARDEFAULT}, the first appearance of a defaulted place-marker is interpreted as though
{var PATVARDEFAULT} were {lisp ←}.
Thus the above pattern could have been written as {lisp X:( 1 =(ADD1 1))}. Subsequent appearances of a place-marker are interpreted as though {var PATVARDEFAULT} were {lisp =}.
For example, {lisp X:(#1 #1 --)} is equivalent to {lisp X:(#1←$1 =#1 --)}, and translates as {lisp (AND (CDR X) (EQUAL (CAR X) (CADR X))}. (Note that {lisp (EQUAL (CAR X) (CADR X))} would incorrectly match with {lisp (NIL)}.)
}{End SubSec Place-Markers}
{Begin SubSec Replacements}
{Title Replacements}
{Text
{indexX {Name replacements} {Type (in Pattern Match Compiler)}
{Text replacements} }
The construct {lisp {arg PATTERN-ELEMENT}←{arg FORM}} specifies that if the match succeeds, the part of the data that matched is to be {it replaced} with the value of {arg FORM}. For example, if {lisp X =(A B C D E)}, {lisp X:($ 'C $1←Y $1)} will replace the third element of {lisp X} with the value of {lisp Y}.
As with assignments, replacements are not performed until after it is determined that the entire match will be successful.
Replacements involving segments splice the corresponding structure into the list being matched, e.g., if {lisp X} is {lisp (A B C D E F)} and {lisp FOO} is {lisp (1 2 3)}, after the pattern {lisp ('A $←FOO 'D $)} is matched with {lisp X}, {lisp X} will be {lisp (A 1 2 3 D E F)}, and {lisp FOO} will be {fn EQ} to {lisp CDR} of {lisp X}, i.e., {lisp (1 2 3 D E F)}.
Note that {lisp ($ FOO←FIE $)} is ambiguous, since it is not clear whether {lisp FOO} or {lisp FIE} is the pattern element, i.e., whether {lisp ←} specifies assignment or replacement. For example, if {index PATVARDEFAULT (in Pattern Match Compiler)}{var PATVARDEFAULT} is {lisp =}, this pattern can be interpreted as {lisp ($ FOO←=FIE $)}, meaning search for the value of {lisp FIE}, and if found set {lisp FOO} to it, or {lisp ($ =FOO←FIE $)} meaning search for the value of {lisp FOO}, and if found, store the value of {lisp FIE} into the corresponding position. In such cases, the user should disambiguate by not using the {var PATVARDEFAULT} option, i.e.,
by specifying {lisp '} or {lisp =}.
Note: Replacements are normally done with {lisp RPLACA} or {lisp RPLACD}. The user can specify that {fn /RPLACA} and {fn /RPLACD} should be used, or {fn FRPLACA} and {fn FRPLACD}, by means of CLISP declarations (see {PageRef Tag CLISPdeclarations}).
}{End SubSec Replacements}
{Begin SubSec Reconstruction}
{Title Reconstruction}
{Text
{indexX {Name reconstruction} {Type (in Pattern Match Compiler)}
{Text reconstruction} }
{index => (in Pattern Match Compiler)}
The user can specify a value for a pattern match operation other than what is returned by the match by writing {lisp {arg FORM{sub 1}}:{arg PATTERN}=>{arg FORM{sub 2}}}.{foot
The original CLISP is replaced by an expression of the form {lisp (MATCH {arg FORM{sub 1}} WITH {arg PATTERN} => {arg FORM{sub 2}})}.
CLISP also recognizes expressions input in this form.
}{comment endfootnote}
For example, {lisp X:(FOO←$ 'A --) => (REVERSE FOO)} translates as:
{lispcode
[PROG ($$2)
(RETURN
(COND ((SETQ $$2 (MEMB 'A X))
(SETQ FOO (LDIFF X $2))
(REVERSE FOO]}
Place-markers in the pattern can be referred to from within {arg FORM}, e.g., the above could also have been written as {lisp X:(!#1 'A --)=>(REVERSE #1)}.
If {lisp ->}{index -> (in Pattern Match Compiler)} is used in place of {lisp =>}, the expression being matched is also {it physically changed} to the value of {arg FORM}. For example, {lisp X:(#1 'A !#2) -> (CONS #1 #2)} would
remove the second element from {lisp X}, if it were equal to {lisp A}.
In general, {lisp {arg FORM{sub 1}}:{arg PATTERN}->{arg FORM{sub 2}}} is translated so as to compute {arg FORM{sub 2}} if the match is successful, and then smash its value into the first node of {arg FORM{sub 1}}. However, whenever possible, the translation does not actually require {arg FORM{sub 2}} to be computed in its entirety, but instead the pattern match compiler uses {arg FORM{sub 2}} as an indication of what should be done to {arg FORM{sub 1}}. For example, {lisp X:(#1 'A !#2) -> (CONS #1 #2)} translates as {lisp (AND (EQ (CADR X) 'A) (RPLACD X (CDDR X)))}.
}{End SubSec Reconstruction}
{Begin SubSec Examples}
{Title Examples}
{Text
{Begin LabeledList Examples}
{Label {lisp X:(-- 'A --)}}
{Item
{lisp --} matches any arbitrary segment. {lisp 'A} matches only an {lisp A}, and the second {lisp --} again matches an arbitrary segment; thus this translates to {lisp (MEMB 'A X)}.
}
{Label {lisp X:(-- 'A)}}
{Item
Again, {lisp --} matches an arbitrary segment; however, since there is no {lisp --} after the {lisp 'A}, {lisp A} must be the last element of {lisp X}.
Thus this translates to: {lisp (EQ (CAR (LAST X)) 'A)}.
}
{Label {lisp X:('A 'B -- 'C $3 --)}}
{Item
{fn CAR} of {lisp X} must be {lisp A}, and {fn CADR} must be {lisp B}, and there must be at least three elements after the first {lisp C},
so the translation is:
{lispcode
(AND (EQ (CAR X) 'A)
(EQ (CADR X) 'B)
(CDDDR (MEMB 'C (CDDR X))))}
}
{Label {lisp X:(('A 'B) 'C Y←$1 $)}}
{Item
Since {lisp ('A 'B)} does not end in {lisp $} or {lisp --},
{lisp (CDDAR X)} must be {lisp NIL}.
{lispcode
(COND
((AND (EQ (CAAR X) 'A)
(EQ (CADAR X) 'B)
(NULL (CDDAR X))
(EQ (CADR X) 'C)
(CDDR X))
(SETQ Y (CADDR X))
T))}
}
{Label {lisp X:(#1 'A $ 'B 'C #1 $)}}
{Item
{lisp #1} is implicitly assigned to the first element in the list. The {lisp $} searches for the first {lisp B} following {lisp A}. This {lisp B} must be followed by a {lisp C}, and the {lisp C} by an expression equal to the first element.
{lispcode
[PROG ($$2)
(RETURN
(AND (EQ (CADR X) 'A)
(EQ [CADR (SETQ $$2 (MEMB 'B (CDDR X] 'C)
(CDDR $$2)
(EQUAL (CADDR $$2) (CAR X]}
}
{Label {lisp X:(#1 'A -- 'B 'C #1 $)}}
{Item
Similar to the pattern above, except that {lisp --} specifies a search for {it any} {lisp B} followed by a {lisp C} followed by the first element, so the translation is:
{lispcode
[AND (EQ (CADR X) 'A)
(SOME (CDDR X)
(FUNCTION (LAMBDA ($$2 $$1)
(AND (EQ $$2 'B)
(EQ (CADR $$1) 'C)
(CDDR $$1)
(EQUAL (CADDR $$1) (CAR X]}
}
{End LabeledList Examples}
}{End SubSec Examples}
{index *END* pattern match compiler}
}{End SubSec Pattern Match Compiler}