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.
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. Read More
Related posts:
Teaching pure LP with prolog and a fair search rule.
Extending the FSyntax/Hiord approach with imperative notation
Some thoughts on how to teach prolog
Theory and Practice in Sixteenth-Century Stonecutting. The ‘Bóveda de Murcia’ in the Manuscript of Alonso de Vandelvira
An s(CASP) in-browser playground based on Ciao Prolog
Sonoran University Begins Search for New President