Page Numbers: Yes First Page: 1
Heading:

April 26, 1979 7:11 PM[IFS]<KRL>document>match-full-imp-nondet

?. Splitting

There are a number of ways in which the alignment of a pattern structure against a datum structrure can be non-deterministic. At the simplest level, a map descriptor can be aligned with one of several map descriptors with the same prototype and focus (e.g. the datum description contains perspectives \The hometown from a Person that is Danny/, \The hometown from a Person thatIs Henry/, etc.). An enumeration descriptor with "..." can be matched in multiple ways (we won’t provide for more than the most elementary combinatorics), and if Or is being treated logically, it provides branching. In each case, there is a specific single descriptor (goal) in the pattern which is the locus of the splitting. We can distinguish three cases:

1. The pattern involved in splitting contains no bindings or actions.

2. The pattern does include bindings and/or actions, but they do not share binding variables with any parts of the pattern outside of the splitting goal.

3. The pattern includes references (either as binding places, or in actions) to binding variables which appear outside the splitting goal.

Case 1 can be handled with the most obvious kind of disjunctive goal tree -- one subgoal is set up for each alternative, and as soon as one of them succeeds, the others are killed and the parent goal succeeds. Case 2 can be handled with a conjunctive goal tree and a mechanism for accumulating results. One subgoal is set up for each alternative, and when all of them have succeeded, the parent goal succeeds. The bindings or action instantiations for each of them is produced separately, and the parent goal ends up with a list. This must then be integrated properly into the top-level results (e.g. if bindings for x and y are produced on two independent splits, then the set of bindings for the match as a whole is their cross-product).

Case 3 is the hard one. In order to keep the dependencies straight, it is useful to think of the split as creating n copies of the entire match process, one for each alternative. Each of these copies has as its goal set copies of that subset of the goals which share a dependency on one of the bindings inside the split. Conceptually, each one has its own unique copy of all of these goals, and their associated effective descriptions. However, through standard sharing techniques most of the copying can be simulated with shared pointers, and extensions made to effective descriptions do not need to be done separately for each element of the split. The split subgoals are treated conjunctively, and their results are combined in the appropriate combinatorial way when they are done.