Multi-Configurable Search Rules in Prolog and Application to Testing

Abstract

Prolog systems traditionally employ leftmost, depth-first search as their execution strategy. This choice is well-justified for efficiency reasons, generally accepted, and useful in practice. However, it is also well-known that it can lead to incompleteness when evaluating programs over infinite search spaces and may not be ideal for complex search spaces. We revisit the role of search strategies in Prolog programs, and present a new approach, that enables programmable and composable control of search. While advanced search strategies can always be programmed in Prolog, we opt instead for an approach that separates the search strategy used from the actual code, so that different strategies can be used on the same set of clauses. We provide constructs for controlling the search strategies that allow adapting the search dynamically. We also illustrate the usefulness of the proposed approach by applying it in the context of testing (constraint) logic programs, showing how composable search parameters enable more controlled and targeted exploration of program behavior. This paper has been accepted at Practical Aspects of Declarative Languages (PADL) 2026.