From Dyna
Jump to: navigation, search

See here for some future features concerning queries.

One thing that makes Dyna fast is that when an inference rule is triggered, it can quickly look up the items that it needs in the chart. A compiled Dyna program maintains special indices for this purpose.

This lookup facility is also made public for your use. Your C++ driver program can issue arbitrary queries against a chart -- as long as your Dyna program has declared the form of these queries in advance.

Declaring queries

Here is how you declare a query in your dyna program:

:- structure(constituent(string label, int from, int to)).
:- query(constituent("NP", 0, _)).

This makes it possible for your C++ driver program to iterate over all constituents with the label "NP" that start at position 0. The end point is unspecified, using the underscore: NPs from 0 to 1, 0 to 2, 0 to 3, ... can be found.

Another example could be:

:- structure(rewrite(string x, string y)).
:- query(x, _).

Declaring a query in your Dyna program has no effect on the semantics of the Dyna program. However, it makes dynac generate a C++ iterator class that you can use to issue queries.

Declaring a query may also make dynac generate extra code to maintain indices on the chart. That makes the query fast; on the other hand, be warned that maintaining these indices costs time and space.

Using queries

If you have defined a query like this:

:- query(my_nps, constituent("NP", 0, _)).

dynac will define a constituent::iterator class which you can use in your C++ driver program. Here's a typical loop, that prints out all matching expressions in the chart:

for (my_nps::iterator iter(mychart); iter; ++iter){
  cout << *iter << endl;   // *iter is an instance of class constituent

You can also use queries with arguments:

:- query(my_constits, constituent(X, _, _)).

The corresponding loop in the C++ code is:

string x = "NP"; // or any other string
for (my_constits::iterator iter(mychart, x); iter; ++iter){
  cout << *iter << endl;   // prints out all x's

That's all there is to it!

Iterator objects

As the loop above illustrates, a Dyna iterator is a bit simpler than a C++ STL random or bidirectional iterator. It is only intended to support forward iteration through a list.

An iterator instance iter either points to some element of the list, in which case (bool)iter is true and *iter returns the element, or else it points past the end of the list, in which case (bool)iter is false and *iter is an error (typically a segmentation fault). Notice that the (bool) cast is implicit in the context of a loop test, as shown above.

When constructed, iter points to the first element in the list (if any). Each call to ++iter advances it to point to the next element (if any). Eventually, it will point past the end of the list (if finite). Once that happens, continuing to call ++iter has undefined behavior.

An iterator object has one additional method: iter.restart() makes iter point to the first element again. This is especially useful during training, when one wants to iterate over the axioms during each training pass.

Iterators are fail-fast. That is, if the chart changes during the lifetime of the iterator, then the next call to *iter or ++iter will throw an exception.

The fail-fast feature hasn't been implemented yet, and perhaps should be reconsidered or made optional, since it adds a bit of overhead. Also, it is not clear whether the iterator should fail if the chart has changed, or only if the particular list has changed.
Personal tools