A production rule is a special kind of object method which creates new properties from the existing ones. The definition of a production rule in a rule file starts with a header resembling the old good Makefile syntax:
SOURCE are the input properties of the algorithm. The rule algorithm can assume that all input properties exist when it starts to run. It is the job of the rule scheduler to provide this. If for some reason a source property will be nevertheless lacking, the algorithm will die by the first attempt to access it.
The SOURCE may be written as a list of alternatives: PROPERTY_1 | PROPERTY_2 ... , if the rule can go with each of these properties equally good. The rule scheduler will then provide one of them.
The rule algorithm is allowed to access other properties, not declared as sources, as well. But it must take precautions for the case they don't exist, that is, it must use the lookup method instead of give or direct accessors. Otherwise it risks to die with an exception.
TARGET are the new properties promised by the algorithm. They must be created in the course of its execution. "Forgotten" targets will be automatically created with an undefined value.
LABEL are optional. They allow to define several algorithms with the same (or very similar) sets of sources and targets and let the user to choose between them using the preference mechanism.
The header is followed by the rule body, implementing the algorithm. The body is a usual perl subroutine taking one argument,
namely the reference to the object. For historical reasons, the surrounding sub { ... } frame as well as argument
extraction into my $this
are appended automatically, so you must not write it. The return value is ignored.
The rule body gets the source properties using the direct access methods: $x=$this->SOURCE_PROPERTY_NAME; The value type depends on the declared property type: it will be either a scalar or an array reference. Note that the original property values are write-protected; if you want to transform them, make a copy.
The alternative sources are accessed using the same syntax as the declaration in the header: $this->PROPERTY_1 | PROPERTY_2 . Pay attention to the single arrow operator!
The targets are stored via the direct access methods too: $this->TARGET_PROPERTY_NAME=$value; The rule should never try to create properties not announced in the header; an attempt to do so will lead to an exception.
If the production rule has supplementary rules such as preconditions or dynamic weight (which are described below), they are placed between the header and the body. In this case the body must be started with a special line
BODY:
Precondition is a little rule-in-rule, which is evaluated prior to the main rule. It must return a boolean value. If it returns TRUE, the production rule can be applied to the object. It it returns FALSE or dies with an exception, the production rule is discarded. If a production rule has multiple preconditions, they are tested one after another until one fails.
The SOURCE syntax and the conventions about the data access in the body are the same as for the production rule, except that the precondition rule is not allowed to create any new properties. The list of the precondition rule sources is fully independent on the main rule sources, they may coincide, have some common properties, or be totally different.
The decision when to execute the precondition rule is up to the rule scheduler. It can run them in the first planning phase, when the viable rules are gathered, or later, when the rule chain is built up. Note that in the so-called dry run mode the preconditions are not executed at all, but rather assumed to be satisfied.
The algorithms inherently have different computational complexity. The production rules may have an optional weight declaration which should give an estimation of the complexity.
There are two kinds of weight declarations: static (constant) and dynamic.
is a static declaration. The major number is a complexity grade in the following scale:
0 | constant time, trivial operation |
1 | linear time |
2 | quadratic time |
3 | polynomial time of degree > 2 |
4 | nearly exponential time |
>= 5 | the algorithm should be avoided whenever possible |
The notions "linear", "quadratic", etc. should be understood as related to some common abstract measure for the object, not from the "selfish" point of view of the individual algorithm. For example, if some algorithm deals with a complete face lattice, it should be classified as "nearly exponential", even if visits each face only once, since the size of the face lattice usually grows exponentially related to other object complexity measures such as dimension or number of vertices.
The minor number is an additive weight in the chosen complexity grade. The minor weights of the rules comprising a chain are summed in each grade separately. The scheduler compares the weights of two chains starting with the heaviest grade and chooses the one with smaller weight.
The default rule weight in polymake is arbitrarily adopted to be 2.10.
is a dynamic weight rule. As for preconditions, the rule body is executed at some moment during the rule chain construction. It must return a reference to an array with two integer elements: [ major, minor ] which are interpreted as in the static case.
If the dynamic weight rule returns undef or dies with an exception, it is treated as a failed precondition, that is, the production rule is discarded.
The dynamic weight rules should not be misused for heavy computations. They are primarily intended for easy-to-check heuristics, like checking for break-even points between two competing algorithms based on object dimension or number of vertices.
Like preconditions, dynamic weight rules are not executed in the dry run mode. The rule planner assumes the [0, 0] result.
There is also a mixed form of weight declaration:
where the output of the dynamic rule is added to the static weight. This allows the rule planner to better estimate the needs of evaluating the dynamic weight and thus reduces the overall time spent for the rule chain construction.
Rule scheduler is one of the core components of polymake. It comes into action as soon as the user (or user's script) asks for one or more object properties which are not present so far. The scheduler's output is a chain (sequence) of production rules, eventually creating all required properties, and possibly some other by-products. Here we give a short overview of its algorithm.
In the first phase the scheduler performs the top-down search of the feasible production rules. A rule is feasible if the following criteria are met:
About the last point: each object keeps track of production rules applied to it. If a rule has once failed (that is, died with an exception, interrupted by the user or by the alarm clock), it comes on the "black list" for this object and becomes infeasible until the session end.
The result of the first phase is a directed graph with nodes corresponding to the feasible rules and arcs describing the "supplier - customer" relations between the rules. This graph is built only implicitly. The sink node corresponds to the user request. There must be also source nodes (without ingoing arcs) corresponding to the immediately applicable rules; if not, the user's request is infeasible (unrealizable) and the scheduler can't do anything else than to raise an exception.
Then, if some user preferences are active, the preferred rules are determined and the "loosing" rules temporarily disabled.
In the second phase the scheduler finds the shortest path connecting the set of the source nodes with the sink node. It uses the standard Dijkstra algorithm, adapted for the implicit graph representation. The distance measure is the sum weight of the visited rules calculated as described above. If the scheduler happens to visit a rule with feasible preconditions and the resulting rule chain still remains the cheapest one, it executes the partial rule chain in order to check the preconditions, truncates the graph (removing the executed rules as well as those no more needed) and restarts the shortest path search.
Having obtained the optimal rule chain, the scheduler calls the methods one after another. If all rules successfully finish, the scheduler is done. Otherwise it discards the failed rule, truncates the rule graph, and restarts the shortest path search again. If the failed rule was a preferred one, the competing rules of the next preference order are re-enabled.
If no feasible rules are left, it raises an exception.