Page Numbers: Yes X: 306 Y: 0.9" First Page: 1
Margins: Top: 1.0" Bottom: 1.2"
Heading:

PROBLEM SET #3 LISP: LANGUAGE AND LITERATURE June 7, 1984
————————————————————————————————————————————

Problem Set #3:

Pattern Matching, Unification, and (a little) Logic Programming

Distributed:June 7, 1984
Solutions due:We will try (no promises) to grade any solutions submitted during summer 1984

Filed as:[phylum]<3-lisp>course>problem-sets>ps-3.bravo
User.cm:[phylum]<BrianSmith>system>user.classic
Last edited:June 7, 1984 12:44 PM

————————————————————————————————————————————

3-1. Introduction

Over the last few weeks we have talked about implementing other architectures or abstract machines on top of 3-LISP. Among other things, an implementer must develop techniques for dealing effectively with expressions or structures in the language being implemented. The implementation of 3-LISP, for example, is based on an INTERLISP-D program that constructs and manipulates 3-LISP structures in particular specified ways.

One obvious task such a designer must face is that of recognizing the "structure" or organization of some incoming expression, and of deciding what to do based on that structure. Since the designer will probably write code to do this recognition, the task often reduces to one of comparing an expression or structure against a template or pattern, to see whether they match. In problem set #2, for example, in exploring issues of parsing and recognition, we required routines that were able to match incoming expressions against various forms of grammar rules. In general, the goal is to extract, from the combination of pattern and incoming expression, some sort of information that they have in common.

Simple parsers of the sort we explored in the last problem set, and simple "natural-language" interfaces to data bases, command processors, etc., often use a simple pattern-matcher to recognize inputs. Similarly, many compilers and tree-walking systems use pattern-matching to recognize or trigger specific procedures of one sort or another, as do some editors and other programming utilities. Finally, again as mentioned in class, pattern matching can play a more fundamental role in the definition of a language than 3-LISP, as it does for example in PROLOG.

In this problem set you will define a graded series of pattern matching procedures, each slightly more powerful than the last. The first one is not much more complex than the matcher used to bind LAMDBA variables in 3-LISP; the final one is a full-scale unification procedure. Although the examples we will use as test cases are very simple, and although the routines would have to be extended in simple ways before they were generally useful for data base systems or natural language query systems, the main ideas would carry through to such "real-world" situations.

3-2. Simple Matchers

In each of the following problems, you will construct a procedure that takes a pattern (patterns are structures of a certain kind, defined below) and another arbitrary 3-LISP structure, and returns information about whether they match (also defined below). In the simplest case, the information will be a simple yes/no answer; as the complexity progresses, you will provide information about variable bindings and other intricacies.

Note: Although it doesn’t really matter much, we will say that a pattern matches a structure, rather than the other way around. 1

Define a pattern (recursively) to be any of:

P1.any atom is a pattern;

P2.the pair (?) is a pattern; and

P3.any rail of patterns is a pattern.

Thus for example the following are all valid patterns:

foo
[[] a b c [d]]
[a (?) (?)]

Patterns match structures according to the following rules:

M1.an atom P matches a structure S just in case S is the same atom as P;

M2.the pair (?) matches any structure S;

M3.a rail P matches a structure S just in case S is a rail of the same length, and each element of P matches the corresponding element of S.

In other words, atom patterns are essentially constants, matching things that are identical to them; the pair (?) is a kind of wild-card, matching any structure at all; and rails provide the ability to have compositionally defined patterns.

Question 3-2-a. Define a procedure MATCH-1, so that

(MATCH-1 pattern structure)

returns $TRUE just in case the pattern designated by pattern matches the structure designated by structure. For example, your definition should support (remember ‘g’ means ‘normalises to’):

(match-1 ’x ’y)g$FALSE
(match-1 ’[a []] ’[a []])g$TRUE
(match-1 ’[a (?)] ’[a []])g$TRUE
(match-1 ’[(?)] ’[])g$FALSE
(match-1 ’[(?) (?)] ’[a [b c d]])g$TRUE

Note: MATCH-1 is already more powerful, in two obvious ways, than the variable binding procedures used in 3-LISP. Can you say what these ways are? 1

Add the following definition and corresponding rule:

P4.The pair (*) is a pattern if it occurs within a rail (i.e., a rail [−a− (*) −b−] is a pattern, if −a− and −b−, respectively, are zero or more patterns).

M4.A rail [−a− (*) −b−] matches a structure S iff:

a.S is a rail

b.S can be "written" [−x− −y− −z−], where each of −x−, −y−, and −z− are zero or more structures, and [−a−] matches [−x−] and [−b−] matches [−z−].

For example, the pattern [(*) a (*) a (*)] will match any rail containing at least two occurences of the atom a.

The pattern (*) is rather like (?) except that it is a multi-element wild-card; it matches any number of consecutive elements within a rail (as opposed to (?), which matches exactly one).

Question 3-2-b. Write a MATCH-2, like MATCH-1 except extended to handle these extended patterns. Your definition should support:

(match-2 ’[(*)] ’[a])g$TRUE
(match-2 ’[(*)] ’a)g$FALSE

(match-2 ’[(*) hello (*)]
’[this is a test of hello there somebody])g$TRUE

(match-2 ’[(*) u (*)]
’[a [u] b c])g$FALSE

(match-2 ’[(*) a (?) c (*)]
’[a a b c])g$TRUE

The patterns we have defined so far are still limited in a number of ways. For one thing, we have no way to coordinate information about what a structure is like in one place and what it is like in another. For example, we have no way to define a pattern that will match just those rails consisting of a single atom repeated three times (i.e., that would match [a a a], [this this this], and so forth, but that would fail to match [b b] and [a b a]). To correct these sorts of deficiencies, we introduce pattern variables. First we add a new kind of pattern:

P5.The pairs (? x) and (* x) are patterns, where x is an atom, called a pattern variable. Note: like (*), the pattern (* x) can only occur within a rail pattern.

Then some definitions:

D1.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 are distinct. The binding of an atom y in b is vi if y=xi, and undefined if y=xi for any i<n.

D2.If an atom, (?), or (*) matches a structure S, then it matches it with any sequence of bindings; otherwise it does not match it with any sequence of bindings.

Then we add the following three match rules:

M5.A rail pattern P matches a structure S with bindings b iff S is a rail of the same length as P, and each element of P matches the corresponding element of S with bindings b.

M6.The pattern (? x) matches S with bindings b if x is bound to S in b.

M7.The rail pattern [−a− (* x) −b−] matches S with bindings b iff:

a.S is a rail

b.S can be written [−x− −y− −z−], where each of −x−, −y−, and −z− are zero or more structures, and [−a−] matches [−x−] with bindings b, [−b−] matches [−z−] with bindings b, and x is bound to [−y−] in b.

Question 3-2-c. Write a procedure MATCH-3, so that (MATCH-3 pattern structure bindings) returns $TRUE if pattern matches structure with bindings bindings, and $FALSE otherwise. Your definition should support:

(match-3 ’[(* a)]
’[x y]
[[’a ’[x y]]])g$TRUE

(match-3 ’[(* a) (* a)]
’[x]
[[’a ’[]]])g$FALSE

(match-3 ’[(* a)]
’[x]
[[’a ’x]])g$FALSE

(match-3 ’[(* a) (*) (* a)]
’[x y z x y z x y]
[[’a ’[x y]]])g$TRUE

It is clear that the matcher ought itself to be able to construct the bindings, rather than us having to provide them as an explicit argument. In order to define such an extended version, we need the following definition: when a pattern matches a structure with bindings b, b is said to be minimal if there exists no shorter sequence b’ such that the pattern matches the structure with bindings b’. In other words, a minimal set of bindings b will contain a binding for each variable in the pattern, but will not contain other gratuitous bindings for any variables not used in the pattern.

Question 3-2-d. Write a procedure MATCH-4, so that (MATCH-4 pattern structure) returns $FALSE if pattern does not match structure, and returns a minimal sequence of bindings otherwise. Your definition should support:

(match-4 ’[(* a) x (? b) (*)]
’[u x v w z])g[[’a ’[u]] [’b ’v]] or [[’b ’v] [’a ’[u]]]

(match-4 ’[(*) (? x) (*)]
’[])g$FALSE

(match-4 ’[(*) (? a) (*) (? a) (*)]
’[u v v w u])g[[’a ’u]] or [[’a ’v]]

(match-4 ’[(* x) (? x)]
’[a b [a b]])g[[’x ’[a b]]]

(match-4 ’[(*) [(? a) (? a)]]
’[[x y] [z z]])g[[’a ’z]]

Note: In some of these examples more than one answer is possible. It is likely that you have written your code to yield as an answer the first set of bindings that works, rather than searching for all of them. In problem set #2 we created a parser that searched for all possible parses, and it is straightforward to build matchers that return all possible bindings as well. If you are feeling ambitious, you might want to define a matcher that generates all possible different binding sets. 1

3-3. Unification

In the examples in the previous section there was a distinction between a pattern and a structure; the former contains all of the special pattern variables, wild-cards, etc. It is possible, however, to define matching procedures in which both structures potentially contain patterns. Rather than calling such a procedure a matcher, we call it a unification procedure. As a first step towards building such a unification procedure, we need some new definitions (note: for simplicity we will abandon the multi-element (*) and (* x) patterns in what follows, although there is no inherent reason they could not be included):

D3.A form is a pattern without any (*) or (* x) patterns.

D4.A sequence of bindings b is a unifier if:

a.each variable in b is bound to a form, and

b.there are no binding cycles in the unifier (formally: when the relation w is defined on the variables of b by the rule awb iff a is bound to a form containing ’(? b), then the transitive closure w* of w is a strict partial order).

D5.A unifier b unifies two forms x and y iff:

a.x and y are the same atom, or

b.x and y are rails of the same length, and b unifies each pair of correspnding elements, or

c.either x or y is ’(?), or

d.both x and y are ’(? a) for some atom a, or

e.x is ’(? a), and a is bound to z in b, and b unifies z and y, or

f.y is ’(? a), and a is bound to z in b, and b unifies z and x.

Note: Definition D4 is necessary in order to avoid circular bindings. For example, without it, the sequence of bindings represented by [[’x ’[y]] [’y ’[x]]] would be a unifier. The problems that stem from such circularities are complex — even analysing what the problems are is complex in its own right. The difficulty is not simply one of having two pattern variables bound together (either of the simpler binding sequences [[’x ’[y]]] or [[’y ’[x]]] would accomplish that), but rather of engendering unwanted infinite structures of various sorts. Although structures that designate infinite entities are not necessarily a problem, infinite structures themselves are outside the compass of implementable languages (PROLOG, because it is based on so-called term or Herbrand models, unfortunately doesn’t distinguish the two cases very clearly). In addition, if infinitely-designating structures were allowed, there would be a danger that in using such structures the unification procedures we will employ would be sent off on infinite computations. 1

Question 3-3-a. Write a procedure MATCH-5, so that (MATCH-5 a b bindings) returns $TRUE if bindings unifies a and b, and $FALSE otherwise. Your definition should support:

(match-5 ’(? x) ’(? x) [])g$TRUE

(match-5 ’(? a) ’(?) [])g$TRUE

(match-5 ’[(? x)] ’(? x) b)g$FALSE for any unifier b

(match-5 ’(? x)
’[a]
[[’x ’[(? y)]] [’y ’a]])g$TRUE

As before, we would rather have a unifier that generates the proper bindings, rather than having to supply them explicitly. We define:

D6.If b unifies a and b, b is a most general unifier (MGU) if no unifier b’ containing only a proper subset of the bindings in b unifies a and b.

A most general unifier is minimal, because it contains the least possible information (less information generally means more things are allowed).

Question 3-3-b. Write a procedure MATCH-6, so that (MATCH-6 a b) returns $FALSE if there is no unifier of a and b, and which otherwise returns a most general unifier (note that it won’t necessarily be unique). Your definition should support:

(match-6 ’[(? x) (? y) (? y)]
’[a b (? x)])g$FALSE

(match-6 ’[(? x) [(? y)] (? y)]
’[a [a] (? x)])ga unifier b with two bindings, such that

(match-5 ’[(? x) (? x)]
’[(? y) a]
b)
returns $TRUE.

(match-6 ’(? x) ’[(? x)])g$FALSE

Note in particular the last example, which is ruled out by the requirement D4, above.

Tiny hint: Define a procedure (UNIFY a b unifier), and then define MATCH-6 as follows:

(define MATCH-6
(lambda [a b]
(unify a b [])))

3-4. Logic Programming

Using the unifier you defined in question 3-2-f, we can implement a miniscule version of PROLOG. We will not explain PROLOG here; you should consult local CSLI PROLOG programmers, or look in various references such as Clocksin and Mellish. PROLOG claims to provide a clean mix of declarative semantics (based on a Horn-clause subset of first-order logic) and procedural semantics (based on a back-tracking reduction regimen), a full reconstruction of which in our Q/F/Y framework would take some time to develop.

The code listed in the next section, which can be loaded by typing:

(load "{turing}<3-lisp.problem-sets>ps-3.3-lisp")

is code for what we will call nano-PROLOG, a version that uses full backtracking and doesn’t provide the user with any control primitives (such as PROLOG’s normal "cut" and "fail" operators).

This implementation is used as follows: you type an expression of the following form:

1> (nano-prolog goal data-base)

where goal designates a pair, the procedure part of which is a relation name (an atom), and the arguments of which are patterns to be used to match against the data base, and data-base designates a sequence of nano-PROLOG clauses. Each clause consists of a sequence of structures, the first element of which is the left-hand side of the PROLOG clause, and the remaining are the elements of the right hand side. For example, we can write down the following two rules to axiomatize the APPEND relationship:

(APPEND [] x x)

(APPEND [x y] z [x u]) if (APPEND y z u)

Note: This APPEND is a three-element relationship, not a two-argument function. Also, we represent (model) sequences, for the purposes of the example, as two-element tuples, the first element of the tuple being the first element of the sequence, and the second element of the tuple representing the remainder of the sequence. Thus the four-element sequence [1 2 3 4] in this example would be represented as [1 [2 [3 [4 []]]]]. 1

These two rules could be coded in a nano-PROLOG data base as follows:

1> (set db-1 ’[[(append [] (? x) (? x))]
[(append [(? x) (? y)]
(? z)
[(? x) (? u)])
(append (? y) (? z) (? u))]])
1= ...

Then, if we were to type the following:

1> (nano-prolog ’(append [] [hello []] (? x))
db-1)

we would have the following "answer" printed out on the screen:

--: ’(append []
[hello []]
[hello []])

where an "answer" is the original goal except with all bindings filled in.

Note: the fact that the answer is printed out explicitly, and then that the simple ’ok is returned, is because of the rather simple implementation code presented below; a more naturally behaving implementation is actually trickier to write. (Extra credit: can you say why?). 1

Similarly we would have:

1> (nano-prolog ’(append [a []] [] (? x))
db-1)
--: ’(append [a []]
[]
[a []])
1= ’done

And of course the relationship can be "run" the other way:

1> (nano-prolog ’(append (? x) [b [c []]] [a [b [c []]]]) db-1)
--: ’(append [a []]
[b [c []]]
[a [b [c []]]])
1= ’done

A slightly more complex example:

1> (nano-prolog ’(append [a [b [c []]]] [d []] (? x))
db-1)
--: ’(append [a [b [c []]]]
[d []]
[a [b [c [d []]]]])
1= ’done

Another example, axiomatizing membership, and illustrating the back-tracking mechanism’s returning multiple possible answers:

1> (set db-2 ’[[(member (? x) [(? x) (?)])]
[(member (? x) [(?) (? y)]) (member (? x) (? y))]])
1= ...

1> (nano-prolog ’(member (? x)
[a [b [c [d []]]]])
db-2)
--: ’(member a
[a [b [c [d []]]]])
--: ’(member b
[a [b [c [d []]]]])
--: ’(member c
[a [b [c [d []]]]])
--: ’(member d
[a [b [c [d []]]]])
1= ’done

Finally, an extension of the membership example to do lookup in a pair-wise dictionary:

1> (set db-3 (append db-2
’[[(lookup (? x) (? y) (? z))
(member [(? x) (? z)] (? y))]]))
1= ...

1> (nano-prolog ’(lookup b [[a eh] [[b bee] [[c sea] []]]] (? x)) db-3)
--: ’(lookup b
[[a eh]
[[b bee]
[[c sea]]]]
bee)
1= ’done

3-5. An Implementation of Nano-PROLOG

The following code makes use of various procedures that we defined in developing our versions of MATCH-1 through MATCH-6, above (you will likely have defined procedures of roughly this functionality, in your own solutions). Specifically, we rely on definitions meeting the following specifications:

(UNNAMED-WILD pattern)—true just in case pattern designates the pattern (?)

(NAMED-WILD pattern)—true just in case pattern designates the pattern (? x) for some atom x.

(PATTERN-NAME pattern)—designates the pattern-variable x in the pattern of the form (? x) designated by pattern.

(BOUND named-pattern bindings)—true just in case the pattern-variable in the named-wild pattern (of the form (? x)) designated by named-pattern is bound in the sequence of bindings designated by bindings.

(THE-BINDING named-pattern bindings)—designates the structure to which the pattern-variable in the named-wild pattern (of the form (? x)) designated by named-pattern is bound in the sequence of bindings designated by bindings.

(UNIFY a b unifier)—explained above.

Given these six utility procedures, the following is a complete implementation of nano-PROLOG. If, in other words, you define the six procedures just specified (using, in particular, your definition of UNIFY from question 3-3-b), and load in the file containing the following definitions (how to do so was described above), you will be able to run nano-PROLOG, as indicated in the examples listed in the last section.

(define NANO-PROLOG
(lambda [goal defns]
(solve [goal] [] defns [] goal)))

(define SOLVE
(lambda [goals bindings defns stack original-goal]
(if (null goals)
(begin (print primary-stream " --: ")
(print primary-stream (update original-goal bindings))
(print primary-stream cr)
(backtrack stack defns original-goal))
(let [[goal (first goals)]]
(solve-goal (pargs goal)
(lookup (pproc goal) defns)
(rest goals)
bindings stack defns original-goal)))))

(define BACKTRACK
(lambda [stack defns original-goal]
(if (null stack)
’done
(solve-goal . (append stack [defns original-goal])))))

(define SOLVE-GOAL
(lambda [args clauses goals bindings stack defns original-goal]
(if (null clauses)
(backtrack stack defns original-goal)
(letseq [[clause (clone (first clauses))]
[r (unify (first clause) args bindings)]]
(if (sequence r)
(solve (append (rest clause) goals)
r
defns
[args (rest clauses) goals bindings stack]
original-goal)
(solve-goal args (rest clauses) goals bindings
stack defns original-goal))))))

(define UPDATE
(lambda [goal bindings]
(cond [(atom goal) goal]
[(rail goal)
(if (null goal)
goal
(cons (update (first goal) bindings)
(update (rest goal) bindings)))]
[(unnamed-wild goal) goal]
[(named-wild goal)
(if (bound goal bindings)
(update (the-binding goal bindings) bindings)
goal)]
[(pair goal) (pcons (pproc goal) (update (pargs goal) bindings))])))

(define CLONE
(lambda [clause]
(first (cloner clause []))))

(define CLONER
(lambda [s b]
(cond [(atom s) [s b]]
[(rail s)
(if (null s)
[s b]
(letseq [[r (cloner (first s) b)]
[r2 (cloner (rest s) (second r))]]
[(cons (first r) (first r2)) (second r2)]))]
[(unnamed-wild s) [s b]]
[(named-wild s)
(if (bound s b)
[(the-binding s b) b]
(let [[new ’(? ,(acons))]]
[new (cons [(pattern-name s) new] b)]))]
[(pair s)
(let [[r (cloner (pargs s) b)]]
[(pcons (pproc s) (first r)) (second r)])])))

(define LOOKUP
(lambda [name defns]
(cond [(null defns) ’[]]
[(= name (pproc (first (first defns))))
(cons (cons (pargs (first (first defns)))
(rest (first defns)))
(lookup name (rest defns)))]
[$T (lookup name (rest defns))])))