ps-3.temp!1 (original) (raw)

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 Tifstructurematchespattern,andT if structure matches pattern, and Tifstructurematchespattern,andF 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 Tifstructurematchespatternwithbindingsbindings,andT if structure matches pattern with bindings bindings, and Tifstructurematchespatternwithbindingsbindings,andF 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 Tifbindingsunifiesaandb,andT if bindings unifies a and b, and Tifbindingsunifiesaandb,andF 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