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