tions. The interpreted predicates may act as filters on the previous variables or introduce new variables (and compute new values for them). For example, the user-defined predicate possibly-adjacent in the rules in Figure 6 ensures that the steps are consecutive in some linearization of the plan. 9 For the plan in Figure 4 the extension of the possibly-adjacent predicate is: (0 4), (0 5), (4 5), (5 4), (4 1), (5 1), (1 2), (2 3), and (3 Goal).

The user can easily add interpreted predicates by including a function definition that implements the predicate. During rule matching our algorithm passes arguments and calls such functions when appropriate. The current plan is passed as a default first argument to the interpreted predicates in order to provide a context for the computation of the predicate
(but it can be ignored). Figure 11 show a skeleton for the (Lisp) implementation of the possibly-adjacent and less-than interpreted predicates.

| (defun possibly-adjacent (plan nodel node2)   | (defun less-than (plan n1 n2)         |
|-----------------------------------------------|---------------------------------------|
| (not (necessarily-not-adjacent                | (declare (ignore plan))               |
| node 1                                        | (when (and (numberp n1) (numberp n2)) |
| node 2                                        | (if (< n1 n2)                         |
| i accesses the current plan                   | '(nil) ;; true                        |
| nil))) ;; false                               |                                       |
| (plan-ordering plan)))                        |                                       |

Figure 11: Sample Implementation of Interpreted Predicates The consequent is composed of the :replace and :with fields. The :replace field specifies the subplan that is going to be removed from the plan, which is a subset of the steps and links identified in the antecedent. If a step is removed, all the links that refer to the step are also removed. The :with field specifies the replacement subplan. As we will see in Sections 3.1.2 and 3.1.3, the replacement subplan does not need to be completely specified. For example, the : with field of the avoid-move-twice rule of Figure 6 only specifies the addition of a stack step but not how this step is embedded into the plan. The links to the rest of the plan are automatically computed during the rewriting process.

## 3.1.2  P Lan - R Ewriting  R U L E S :  F U L  V E R S U S  P A R T A L  S P E C I F I C A T I O N

PbR gives the user total flexibility in defining rewriting rules.  In this section we describe two approaches to guaranteeing that a rewriting rule specification preserves plan correctness, that is, produces a valid rewritten plan when applied to a valid plan.

In the full-specification approach the rule specifies all steps and links involved in a rewriting. The rule antecedent identifies all the anchoring points for the operators in the consequent, so that the embedding of the replacement subplan is unambiguous and results in a valid plan. The burden of proving the rule correct lies upon the user or an automated rule defining procedure (cf. Section 6). These kind of rules are the ones typically used in graph rewriting systems (Schürr, 1997).

In the partial-specification approach the rule defines the operators and links that constitute the gist of the plan transformation, but the rule does not prescribe the precise