Pattern

From Dyna

relvie cataortro racaloloelt relvin alzelnogetge delletova lic4tc racmono 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

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))) %