Rules

Rules are the most important part of an application. While the object properties describe the static view on the mathematical model, the rules express the relations between the properties, thus embodying the dynamic part of the model.

Rules are always defined in rulefiles, within the scope of the object type they belong to. A rule working on several levels of object hierarchy (that is, working with properties of subobjects) should be defined in the scope of the topmost object, being the closest common ancestor of all involved properties.

Production rules

A production rule is an algorithm computing one or more target properties of an object, taking one or more source properties as an input. The definition of a production rule has the following form:

rule labels : targets : sources
{
  body
}
adornments

The first line, starting with the reserved word rule, is called the rule header. There should be no empty lines between the header, body, and adornments. Empty lines within body block are, however, allowed. The opening brace or even the whole body (if it is extremely short) is also allowed to be put at the end of the header line.

Sources

Sources is a comma-separated list of properties which constitute the mandatory input of the algorithm. The rule scheduler provides for the existence of all source properties before the rule is executed. Moreover, all source properties are ensured to have defined values.

If a rule can utilize additional source properties, which are however not mandatory, they must not be listed in the header. The rule must access optional properties using lookup() methods.

Several source properties may form a group of alternatives, if the rule can proceed with any one of them. The syntax of the group is similar to the argument of the give() method: PROPERTY_1 | PROPERTY_2 | … The rule must always access these properties as a group and never ask for them separately, because the rule scheduler will in general provide only one of them.

A property of a subobject is specified using dot notation: SUBOBJECT.PROPERTY

Targets

Targets is a comma-separated list of properties that the rule guarantees to create. Properties of subobjects are specified using dot notation; if needed, intermediate subobjects are created prior to calling the rule. If some target property has not been created in the course of the rule execution, it is assigned an undefined value afterwards.

Labels

Labels allow to control the choice of rules by the scheduler via preference lists manipulated by the user. Usually, rules with similar functionality are assigned labels with common tail part and different first limbs. For example, different rules solving LP with the simplex method are labeled with cdd.simplex, lrs.simplex, etc. After the user has issued a command prefer "cdd"; the rule with lrs label is not considered by the scheduler until the cdd rule has failed on the object being processed. In the absence of active preference lists, labeled rules are treated the same way as unlabeled ones.

Besides this, labels are involved in the overriding mechanism, and, finally, there are some special labels completely changing the semantics of the rule. Both are described further on this page.

A rule can have zero, one, or more labels. Several labels are separated with commas. If a rule does not have any labels at all, the colon separating them from the targets must also be omitted.

Body

The rule body may contain arbitrary perl code doing the calculations. The reference to the top-most object is passed as a single argument to the body subroutine and automatically assigned to the lexical variable $this, which has to be used to access all source properties and to create the targets. The return value of the body does not matter. However, if the rule terminates with an exception, it is considered as failed, and the rule scheduler tries to find an alternative.

There are some restrictions in place pertaining to the operations allowed on the $this object and its subobjects:

  • Only properties declared as sources may be accessed directly or via give(). All optional properties must only be accessed via lookup().
  • Only properties declared as targets may be created.
  • The rule body is executed within an own transaction scope. It is not allowed to influence it in any manner from within the rule code.
  • No attachments may be accessed nor created.
  • Mutable properties or multiple subobjects may only be added with temporary flag.

Adornments of production rules

Weight

Rule weight is a very coarse estimation of the complexity of the algorithm. It is the most crucial information for the rule scheduler, because the latter strives to find a chain of rules having minimal weight. The rule weight is specified on a separate line following the body:

weight Major.Minor;

Major is the category of complexity. Currently, the following scheme of categories is adopted:

  • 0 for trivial rules (constant execution time)
  • 1 for linear-time complexity (related to some fundamental metric of the object like the number of points, facets, etc.)
  • 2 for quadratic complexity
  • 3 for higher degree polynomial complexity
  • 4 for algorithms having polynomial complexity in average but (supposedly) exponential in worst case
  • 5 for exponentially complex algortithms
  • 6 for an algorithm to be avoided under all circumstances unless explicitly desired

Minor is the relative weight of the algorithm within its category. The weight of a rule chain is a vector of sums of minor weights of single rules ordered by category. These vectors are then compared lexicographically, that is, from a pair of rule chains the one with smaller weight in the highest unequal category is considered better, regardless of the values in the lower categories.

The default weight for a production rule is 2.10 .

Preconditions

A precondition is a (presumably simple) rule on its own, which detects up front whether the production rule is applicable at all. It is written in the following way:

precondition : sources
{
  body
}

The list of source properties is completely independent of the sources of the main production rule. The precondition does not have any target properties. Instead, the return value of the body subroutine is important. If it is a boolean TRUE value (actually, any non-zero number or a non-empty string), the precondition is considered to be fulfilled.

Precondition rules must be very simple and easy to evaluate. They shouldn't involve any complex computations. The rule scheduler usually evaluates the preconditions as soon as it thinks about the corresponding production rule.

A production rule may have several preconditions, all of them must evaluate to TRUE before the rule is considered applicable.

For preconditions checking boolean properties, there are syntactical abbreviations:

precondition : PROPERTY;
precondition : !PROPERTY;
precondition : PROPERTY_1 && PROPERTY_2;

A precondition may also check for undefined properties:

precondition : defined(PROPERTY1), !defined(PROPERTY2);

Another special form, used primarily in initial rules, may check for a presence or absence of a property or a group of alternatives:

precondition : exists(PROPERTY1 | PROPERTY2), !exists(PROPERTY3);

The preconditions of this kind are always checked at the very beginning of the rule scheduling; whether some of properties in question will be created later by other rules, does not play any role.

precondition override : PROPERTY ...

The option override may only be used for rules defined for restricted specializations of big object types. It signals that this precondition replaces the common preconditions of the specialization. Overriding common preconditions may be necessary for rules capable of checking the common preconditions by themselves more efficiently than if would be done in regular way. Usually this is the case when the rule itself produces the precondition source properties and bails out timely if the precondition is not satisfied.

Overrides

Generally, a production rule behaves much like a method and therefore is inherited by derived object types. Sometimes a derived object type can possess a more efficient implementation of a rule than its base type. Although you may indicate this just by assigning lower weights to the rules in the derived object type, the less efficient rules would still be assessed by the rule scheduler, thus slowing down the process of finding the cheapest rule chain. It is much more efficient to completely disable the inheritance of some rules. To do this, you should place the following line below the definition of a (presumably superior) production rule in the derived object scope:

override ObjectType::label, ...;

ObjectType must name one of the base types. If it is a single ascendant of the current object type, you may simply write SUPER instead. label must match one or more production rules defined for the base object type.

It is sufficient to specify the override clause once per specific label and inheritance line in the whole rule base, even if the set of rules in the derived object type replacing the inherited ones consists of several rules. Repeating the override clause several times does no harm, but slows down the rule loading phase.

Permutations

A production rule can incur a permutation if it produces some properties sensitive to this permutation without reading any other properties being as well sensitive to it. While the threat of triggering could in most cases be detected automatically by analyzing the rule header, we prefer to state this explicitly by putting the following adornment line:

incurs PermutationName;

As a little aid, there is a script list_suspicious_rules which performs the analysis of all production rules in an application and prints the headers of rules which could incur a permutation but does not state it.

Currently, a production rule can't be declared to incur more than one permutation.

Rules operating on multiple subobjects

A production rule consuming properties from multiple subobjects and creating properties in parent objects always works with the default instances, that is, subobjects stored at the 0-th position. The preconditions of such rules can only assess the default instances too - the rule scheduler does not use them for choosing a most suitable instance. The only way to make the rule consume another multiple subobject instance is to set that instance as the default one, permanently or temporarily, before the rule is applied.

A production rule consuming and creating properties in a multiple subobject does not visually differ from any production rule operating on a singular subobject. The scheduler may apply such a rule to any instance whenever a missing property is requested.

A production rule creating properties in an existing multiple subobject instance without consuming any other properties from that instance must be marked with special attribute (any) appended to all occurrences of the multiple subobject among the rule targets. Most often this regards the shortcut rules:

rule TRIANGULATION(any).VERTEX_LABELS = VERTEX_LABELS;

A production rule creating new multiple subobject instances must be marked with special attribute (new) appended to all occurrences of the multiple subobject among the rule targets. The target list should enumerate all atomic properties of the new instance:

rule QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).FACETS, QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).VERTEX_LABELS, \
     QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).PURE,   QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).DIM \
   : VERTICES_IN_FACETS, HASSE_DIAGRAM, QUOTIENT_SPACE.IDENTIFICATION_GROUP { ... }

Note that in this example multiple subobjects occur on two levels. QUOTIENT_SPACE is not marked with any special attribute because it occurs among both sources and targets of the rule. This means that the rule is applied to an existing instance of QUOTIENT_SPACE whenever a property of its subobject SIMPLICIAL_COMPLEX is requested for the first time.

Production rules creating new multiple subobject instances are only executed by rule scheduler when there are no instances of that subobject type at all. However, if such a rule also creates properties in the parent object or in another singular subobject, it can be included in the rule chain even in the presence of multiple subobject instances. In that case the new created multiple subobject is appended at the end of the instance list where it stays invisible to the scheduler until it has been deliberately selected by the user. The same holds if the rule has been forcibly executed by apply_rule.

Shortcuts

Shortcut rule is a special, simplified kind of production rules. It states that the value of one property can simultaneously be accessed via several paths in the object hierarchy. The definition of a shortcut rule looks like

rule target = source;

A shortcut rule does not have a body nor can it possess labels. It is always assumed to have zero weight. It may, however, have preconditions. The result of execution of a shortcut rule is a reference to the source property stored at the target place. Such references behave much like normal, autonomous properties, with the only difference that they are not stored in XML data files. Another specialty of shortcut rules is that they can be applied even when asking for properties with lookup(), while normal production rules are applied only in give() or provide().

Default property values

A property definition may contain a default value which in fact is internally converted into a tiny production rule having no sources and a single target. The definition syntax in this case is as follows:

property NAME : Type = Value;

You can't specify a weight nor any preconditions for such a rule. If you really have to, you must define it as a normal rule having empty list of sources:

rule NAME : { $this->NAME = Value; }
precondition : CONDITION;

Initial rules

Initial rules are defined much like normal production rules, they are distinguished just by a special label initial. The main difference is that they are not considered by the rule scheduler when asked for new properties. They are even allowed to not produce any new properties at all. Instead, all initial rules are executed at the end of the initialization phase of the object, as far as the corresponding source properties are available or can be calculated using normal production rules.

The primary purpose of initial rules is to make sanity checks (e.g. compare the dimensions of coordinate matrices) or compute some properties crucially needed for the whole object's lifetime. A failed sanity check must lead to an exception, after which the object is usually made empty (or even discarded if the variable keeping it goes out of scope prior to catching the exception).

There is also a special kind of exception that can be thrown in an initial rule:

my $obj=Core::Object::Replacement(PROPERTY => value, ...);
die $obj;

Its contents, namely a list of properties, completely replaces the initial data in the object being checked, after this the whole verification procedure is repeated once again (but excluding the very rule having thrown this exception). You can also supply some attachments, if needed, before throwing: $obj->attach("NAME", value);

An initial rule producing some new properties is executed only if none of them already exists in the object. Therefore any sanity checks deemed mandatory should be performed in separate initial rules with empty output list.

Please note that if an object is loaded from an XML data file untouched since having been created by polymake, it is considered trustworthy and so no initial rules are considered. Objects created in C++ clients are always considered “suspicious” and therefore undergo the initial checking.

Non-existing rules

These are rules defined without body and labeled with nonexistent. They are only used in combination with permuted subobjects. Actually, they just tell the rule scheduler that the target property is sensitive to the permutation, but there is no algorithm to recover this property from a permuted subobject.

An example from the application topaz, object type SimplicialComplex:

rule nonexistent : CYCLES : VertexPerm.CYCLES, VertexPerm.PERMUTATION;

indicates that property CYCLES is dependent on the vertex order, and if some other rule (declared as possibly triggering VertexPerm) creates CYCLES while the object already contains other properties depending on the vertex order, it will be completely in vain, because there is no way to rearrange the CYCLES such that they fit the original vertex order. (Actually, the CYCLES could easily be rearranged, but for some political reasons this has not been implemented yet.)

reference/rules.txt · Last modified: 2016/03/14 14:32 by gawrilow
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki