[NEXT] [PREV]    HANDBOOK / GENTLE PRIMER / Optimal Rule Selection /

Well-formed Rules


The typical structure of rules describing code selection is as follows.

The predicate has a distinguished input argument (the first one) that represents the construct to be translated; we call it the primary argument.

If the rule invokes conditions, this is to test certain properties of the primary argument (such as IsSuitableScaleFactor in the example above).

If the rule invokes predicates of the category choice, this is to translate constituents of the primary argument, e.g.

   'rule' StackCode(plus(X,Y)):
      $ 20
In some cases, the argument is simply passed as a whole to the invoked predicate, e.g.

   'rule' StackCode(X):
      $ 10
Since choice predicates were introduced to specify code selection, we can restrict ourselves to this form in order to support an efficient implementation.

Rules of choice predicates must obey the following restrictions:

The first input argument (the primary argument) of a choice must be of a type that is defined with functors.

If condition or choice predicates are invoked in the rule body, then the input arguments of condition predicates and the primary arguments of choice predicates are given by constituents of the primary argument of the rule heading (or by that argument as a whole).

Rule selection does not depend on the output values of predicates in the rule body.

These restrictions make it possible to avoid an exponential search and to use a linear-time algorithm to find optimal rules.