Problem Set — Pattern Matching and Unification
In this problem set, you will construct a series of procedures which take a "pattern" (defined below) and an arbitrary 3-lisp structure, and return information about whether they "match" (also defined below).
Match-1
Define:
An atom is a pattern.
’(?) is a pattern.
A sequence of patterns is a pattern.
The atom x matches the structure y iff y is the same atom as x.
’(?) matches any structure.
The sequence x matches the structure y iff
y is a sequence of the same length, and
the corresponding elements match.
Write a procedure (match-1 pattern structure) which returns $T if structure matches pattern, and $F otherwise.
Examples:
(match-1 ’x ’y) => $F
(match-1 [’a []] [’a []]) => $T
(match-1 [’a ’(?)] [’a []]) => $T
(match-1 [’(?)] []) => $F
Match-2
Add the definitions:
[-a- ’(*) -b-] is a pattern, where -a- and -b- are each zero or more patterns.
[-a- ’(*) -b-] matches y iff
y is a sequence
y can be written [-u- -v- -w-], where each of -u-, -v-, and -w- are zero or more structures, and [-a-] matches [-u-], and [-b-] matches [-w-].
Write a procedure (match-2 pattern structure), an extension of match-1 which handles these extended patterns.
Examples:
(match-2 [’(*)] [’a]) => $T
(match-2 [’(*)] ’a) => $F
(match-2 [’(*) ’u ’(*)] [’a ’u ’b ’c]) => $T
Match-3
Add the definitions:
’(? x) and ’(* x) are patterns, where x is an atom. x is said to be a pattern variable.
A sequence of bindings b is a sequence of the form [[x1 v1] ... [xn vn]] where the xi are atoms, and the vi are arbitrary structures, with n > 0, and the xi’s distinct. The binding of an atom y in b is vi if y=xi, and undefined if y=xi for any i.
If an atom, ’(?), or ’(*) matches structure, then it matches it with any sequence of bindings; otherwise it does not match it with any sequence of bindings.
A sequence of patterns matches y with bindings b iff
y is a sequence of the same length, and
the corresponding elements of the sequences match with bindings b.
’(? x) matches y with bindings b iff x is bound to y in b.
[-a- ’(* x) -b-] matches y iff
y is a sequence
y can be written [-u- -v- -w-], where each of -u-, -v-, and -w- are zero or more structures, and [-a-] matches [-u-] with bindings b, and [-b-] matches [-w-] with bindings b, and x is bound to [-v-] in b.
Write a procedure (match-3 pattern structure bindings), which returns $T if structure matches pattern with bindings bindings, and $F otherwise.
Examples:
(match-3 [’(* a)] [’x ’y] [[’a [’x ’y]]]) => $T
(match-3 [’(* a) ’(* a)] [’x] [[’a []]]) => $F
(match-3 [’(*) ’(? a) ’(*)] [’u ’v ’w] [[’a ’w]]) => $T
Match-4
When pattern matches structure with bindings b, b is said to be minimal if there exists no shorter sequence b’ such that pattern matches structure with bindings b’.
Note that b is minimal iff b contains a binding for each variable in pattern, and no others.
Write a procedure (match-4 pattern structure), which returns $F if pattern will not match structure with any sequence of bindings, and otherwise returns a minimal sequence of bindings.
Examples:
(match-4 [’(* a) ’x ’(? b) ’(*)] [’u ’x ’v ’w ’z]) =>
[[’a [’u]] [’b ’v]], or
[[’b ’v] [’a [’u]]]
(match-4 [’(*) ’(? x) ’(*)] []) => $F
(match-4 [’(*) ’(? a) ’(*) ’(? a) ’(*)] [’u ’v ’v ’w ’u]) =>
[[’a ’u]], or
[[’a ’v]]
Match-5
Add the definitions:
A form is a pattern without any ’(*) or ’(* x) patterns.
A sequence of bindings b is a unifier if
each variable in b is bound to a form, and
when the relation w is defined on the variables of b by awb iff a is bound to a form containing ’(? b), then the transitive closure w* of w is a strict partial order.
A unifier b unifies two forms x and y iff
x and y are the same atom, or
x and y are sequences of the same length, and b unifies each pair of corresponding elements, or
either x or y is a ’(?), or
both x and y are ’(? a) for some atom a, or
x is ’(? a), and a is bound to z in b, and b unifies z and y, or
y is ’(? a), and a is bound to z in b, and b unifies z and x.
Write a procedure (match-5 a b bindings), which returns $T if bindings unifies a and b, and $F otherwise.
Examples:
(match-5 ’(? x) ’(? x) []) => $T
(match-5 [’(? x)] ’(? x) b) => $F (for any unifier b)
(match-5 ’(? x) [’a] [[’x [’(? y)]] [’y ’a]]) => $T
Match-6
If b unifies a and b, b is a most general unifier (MGU) (i.e. minimal) if no unifier b’ containing only a proper subset of the bindings in b unifies a and b.
Write a procedure (match-6 a b), which returns $F if there is no unifier of a and b, and otherwise returns a most general unifier.
Examples:
(match-6 [’(? x) ’(? y) ’(? y)] [’a ’b ’(? x)]) => $F
(match-6 [’(? x) [’(? y)] ’(? y)] [’a [’a] ’(? x)]) returns a unifier b with two bindings, such that
(match-5 [’(? x) ’(? x)] [’(? y) ’a] b) => $T