Download Pattern Matching for Program Generation: A User Manual

Transcript
where the $(por …) syntax expresses the pattern alternative via the pattern “or” operator por. This pattern
will match any three (or longer) element list with “a” in the first position, anything in the second position,
and “c” or “d” in the third. The dollar sign syntax identifies the following parenthesized expression as a
computable (i.e., non-literal) pattern operator.
2.3.3.2 Bindvar
Now, after such a match, the program would not know whether the third element matched “c” or “d”. So,
we need a way to bind whichever data value was matched to a pattern variable such as ?y. To achieve this,
we could express the pattern as
(a ?x $(bindvar ?y $(por c d)))
which would match c or d in the third position and then bind the matched value to the pattern variable ?y.
Any pattern or subpattern regardless of its size or complexity can be wrapped with a $(bindvar ?variable
…) expression and the structure matched by that pattern or subpattern will be bound to the pattern variable.
The bindvar operator can be embedded in expressions that are themselves wrapped with a bindvar
operation. It is common practice to bind a structure matching an overall pattern to a variable and at the
same time bind smaller but important pieces of the overall structure to other variables.
2.3.3.3 Testing Properties
Now, matching often depends more on the properties of the data (e.g., type) than it does on the literal
value of the data. Therefore, one might like to match any data item of some type (e.g., number) in the third
position and then bind the value of the number to some pattern variable such as ?y. If the third position
does not contain a number, then the match should fail. The ptest operator provides a way to test the
properties of data items by allowing the pattern writer to supply the name of a Lisp function that when
applied to the data item will succeed if the property is true and fail otherwise. So, now the pattern example
would become
(a ?x $(bindvar ?y $(ptest numberp)))
where “numberp” is the Lisp function that tests a data value to see if it is some form of a number. If this
pattern was matched against the list “(a b 47)”, the match would succeed and return the binding list “((?x b)
(?y 47))”.
2.3.3.4 The And Operator and Lisp Escapes
But, what if we need two or more properties to be simultaneously true (say numberp and a value less than
50)? We can use the pattern “and” operator pand but there is a catch. When the expression $(ptest
numberp) matches the third element, it advances the data pointer so that the pattern matcher is now looking
at the data after the third element. That is, once matched, the data has been consumed and subsequent
matches will be looking at subsequent data. So, we need the ability to perform an arbitrary function that
does no direct matching of the target data string and only serves to determine success or failure of the
matching process using previously bound pattern variables. This is accomplished via a very general
capability. The pattern language allows evaluation of an arbitrary Lisp expression that will cause the match
to fail if it returns nil and to succeed if it returns non-nil. This is the plisp operator. So, the new pattern
could be expressed as
(a ?x $(pand $(bindvar ?y $(ptest numberp))
$(plisp (<= ?y 50))))
However, it could also be expressed in other ways to achieve the same result. Common practice is to match
anything and then use plisp or other operators to test for multiple properties all at once. So, an alternative
form matching the same form of the data is
(a ?x $(pand ?y $(plisp (and (numberp ?y) (<= ?y 50)))))
7