# Pattern

**Warning:** *Not implemented yet. However, you can use queries in the current version.*

## Contents |

## What is a pattern?

A pattern is like a term except that some of its subterms may be variables. For example, in an inference rule like

pathto(V) min= pathto(U)+edge(U,V).

the consequent `pathto(V)`

is an item pattern, and the antecedent is an expression pattern. When a Dyna program runs, it does a lot of pattern matching.

As an advanced feature, you can also specify patterns directly

- to create subtypes (as usual, strong typing is both safer and more efficient)
- to specify program transformations (in which the pattern is replaced by a specialized structure type, for efficiency)
- to enable the C++ driver program to
- do pattern matching against existing terms
- retract axioms that match a pattern
- represent and manipulate antecedent expressions
- run powerful queries against items and expressions in the chart

## Declaring patterns

You can declare patterns in a Dyna program as follows.

:- pattern(mypattern, constit(np,I,I)). :- pattern(lengthtwo, edge(U,V)+edge(V,W)). :- pattern(deep, foo(X,Y,yada(yada(yada(X))))).

Some patterns are automatically declared for you. The inference rule shown earlier, `pathto(V) min= pathto(U)+edge(U,V)`

,
results in the following automatic declarations of antecedent and consequent patterns.
These are used as the return types of the antecedent and consequent iterators. For example,
if you ask for the antecedents of a particular `pathto`

item, then you will get
back an iterator over terms of type `pathto::antecedent`

.

:- pattern('pathto::antecedent', pathto(U)+edge(U,V)).

:- pattern('pathto::consequent', pathto(V)). :- pattern('edge::consequent', pathto(V)).

*Only antecedent patterns are implemented so far.*

## Patterns as subtypes

Just as a `union`

declaration creates a new supertype,
a `pattern`

declaration creates a new subtype. Thus,
once `mypattern`

is declared, you can use it like other types:

:- structure(foo(mypattern p)). :- union(bar,[mypattern,string]).

so that `foo(constit(np,5,5))`

is a legal term but
`foo(constit(s,0,8))`

is not. Note that `mypattern`

is
a subtype of both `constit`

(a structure type) and `bar`

(a union type).

Similarly, `pathto::antecedent`

is a subtype of `expr_double`

(an expression type). (Assuming that `pathto`

is a subtype of `item_double`

, i.e., has been declared with `:- item(pathto,double,0)`

.)

Like structure types, pattern types have constructors. The constructor arguments are the variable bindings, in order of first (leftmost) mention. Thus, given the declarations from above,

:- pattern(mypattern, constit(np,I,I)). :- pattern(lengthtwo, edge(U,V)+edge(V,W)). :- pattern(deep, foo(X,Y,yada(yada(yada(X))))).

you can write

mypattern(5) % constit(np,5,5) lengthtwo("a","b","c") % edge("a","b")+edge("b","c") deep([1,2],3) % foo([1,2],3,yada(yada(yada([1,2]))))

Note that what you are constructing is not a pattern (which is a type), but a term matching that pattern (which is an instance of the type).

## Patterns with type restrictions

You can restrict a pattern by specifying types for its variables. For example,

:- structure(foo(int i, list l)). :- pattern(zerolist, foo(0,L)). :- pattern(zerocons, foo(0,cons L))).

Now `zerocons`

is a subtype of `zerolist`

, which in turn
is a subtype of `foo`

.
Both `foo(0,[])`

and `foo(0,[3,4])`

are `zerolist`

s,
but only the latter is a `zerocons`

.

As an alternative, `zerocons`

can be defined as a pattern that
matches against the one-argument `zerolist`

constructor:

:- pattern(zerocons, zerolist(cons L)). % equivalent to previous definition

## Circular declarations using patterns

As with unions, circular declarations are allowed. Here is an ordinary binary tree type that stores an element at each leaf (external node) and each branch (internal node):

:- union(tree,[leaf,branch]). :- structure(leaf(term element)). :- structure(branch(term element, tree left, tree right)).

Using patterns, we can define *symmetric* trees, in which the left
branch equals the right branch:

:- union(symmtree,[leaf,symmbranch]). :- pattern(symmbranch, branch(Element, symmtree Subtree, symmtree Subtree)).

In other words, a symmetric tree is either a leaf, or a branch whose
left and right children are *equal* symmetric trees. `symmtree`

is a subtype of `tree`

, but the compiler can take advantage of the restrictions
to store and process it more efficiently than an arbitrary tree.

Note that the following constructors can be used:

symmbranch(1,symmbranch(2,leaf(3))) % yields branch(1,branch(2,leaf(3),leaf(3)), branch(2,leaf(3),leaf(3))) symmtree(1,symmtree(2,symmtree(3))) % same thing, thanks to constructor overloading

These constructions look a lot like constructing a list [1,2,3]. Indeed the compiler is free to transform the program so that symmtrees are stored like lists. (Even if not, it can still store them in linear space with structure sharing.)

*In general, once patterns are fully implemented, checking whether a term is an element of a type (as is done by checked downcast methods in C++) will require testing it with a (hardcoded) nondeterministic top-down tree automaton. Type intersection (during declaration inference) becomes intersection of tree automata. That notion of subtyping seems to have been invented before: for some starting points (slides in 2003) see [1]. Notice that we can't define a type that matches any constant list (e.g.,*`[4,4,4,4,4]`

, but we can define a type that matches any list of constant type (e.g.,`[four,four,four,four,four]`

where`four`

is an atom). The difference is that the set of types (but not the set of terms) forms a finite alphabet for the automaton.

## Multi-line pattern declarations

Recall that if you declare multiple structures with the same name, you get a union type over anonymous structure types (see functor overloading). Similarly, if you declare multiple patterns with the same name, you get a union type over anonymous pattern types.

For example, the `symmtree`

example above could have been
written directly as a multiline pattern:

:- pattern(symmtree,leaf(Element)). :- pattern(symmtree,branch(Element, symmtree Subtree, symmtree Subtree)).

This compiles into a union `[symmtree1,symmtree2]`

(although not
sure whether you'll be able to count on those names), which is equivalent to the
explicit union `[leaf,symmbranch]`

given above.

One use is in the automatically declared pattern types for antecedents and consequents.
If you have two inference rules that yield `constit`

,

constit(X,I,J) += rewrite(X,W) * word(W,I,J). constit(X,I,K) += rewrite(X,Y,Z) * constit(Y,I,J) * constit(Z,J,K).

then the automatically declared `constit::antecedent`

pattern
will have two lines:

:- pattern('constit::antecedent', rewrite(X,W)*word(W,I,J)). :- pattern('constit::antecedent', rewrite(X,Y,Z)*constit(Y,I,J)*constit(Z,J,K)).