Pattern

From Dyna

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

Contents 1 What is a pattern? 2 Declaring patterns 3 Patterns as subtypes 4 Patterns with type restrictions 5 Circular declarations using patterns 6 Multi-line pattern declarations

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 zerolists, 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)).