Matching Techniques: Structures

Variables

Match variables can be classified by the number of items that can replace them (one or more than one). An open variable can be replaced by a single item, while a segment variable can be replaced by zero or more items. Open variables are labeled with a preceding question mark (?x, ?y, etc.). They may match or assume the value of any single string element or word, but they are sometimes subject to consistency constraints. For example, to be consistent, the variable ?x , can be bound only to the same top level element in any single structure. Thus (a ?x d ?x e) may match (a b d b e), but not (a b d a e). Segment variable types are preceded with an asterisk (*x, *z, etc.). It can match an arbitrary number or segment of contiguous atomic elements (any sublist including the empty list). For example, (*x d (e i) *y) will match the patterns:

(a (b c) d (e f) g h), (d (e f) (g))

or other similar patterns. Segment variables may also be subject to consistency constraints similar to open variables.

Variable Binding

Q. State what variable binding, if any, will make the following lists match.

1. (*x d (e f) *y) and (a (b c) d (e f) g h) (Dec. 00)
2. (?x *y a b c (d e)) and (a (j k (f)) a b c *z) (June 00, Dec. 01, Dec. 02)
3. (a b c (d a) f) and (?x b c (d ?y) ?z) (Dec. 98, June 00, Dec. 01, Dec. 02)
4. (*x a b (c d) *x) and ((e f) a b *y e f) (June 00, June 01, Dec. 01, Dec. 02)

i) The variable bindings that will match the lists are:
*x = a (b c)
*y = g h

ii) The variable bindings that will match the lists are:
?x = a
*y = (j k (f))
*z = (d e)

iii) The variable bindings that will match the lists are:
?x = a = ?y
?z = f
However, if ?x cannot be equated to ?y, the lists will not match.

iv) This list cannot match because of consistency constraints. We cannot equate *x = (e f) and then again *x = e f.
NOTE: (e f) is a sublist and e f are independent elements.