search

ztangent / Julog.jl

A Julia package for Prolog-style logic programming.
Apache License 2.0
170 stars 11 forks source link

References on breadth-first logic programming #19

Open chalst opened 2 years ago

chalst commented 2 years ago

The README states:

cut causes the current goal to succeed and suppresses all other goals. However, this does not have the same effects as in Prolog because Julog uses breadth-first search during SLD-resolution, unlike most Prolog implementations, which use depth-first search.

No reason for this unusual choice is given, however I'm aware that there are good reasons why one might prefer breadth-first semantics. Three doctoral dissertations explore this choice; in the first and last, the researchers have implemented a breadth-first LPL, while the second explores expressions in Haskell using Wadler's 'list of successes' paradigm:

  1. Richard McPhee, 2000. Compositional Logic Programming. DPhil thesis, Programming Research Group, University of Oxford.
  2. Silvijia Seres, 2001. The Algebra of Logic Programming. DPhil thesis, Programming Research Group, University of Oxford. http://silvija.net/0000OxfordPublications/seres_thesis.pdf
  3. Görkem Paçaci, 2017. Representation of Compositional Relational Programs. PhD thesis, Department of Informatics and Media, Uppsala University.

The issue that drives the preference comes from algebraic semantics: if you regard the semantics of a query as a collection of satisfiers, left-to-right depth-first search gives conjunction a bias where (A,B) might not terminate if A gives an unbounded search, even if B has only finitely many satisfiers consistent with A; the requirement that the semantics lacks this kind of biases is called fairness, and breadth-first search makes this easier to achieve.

It might be worth adding a paragraph to the README mentioning the idea of fairness in logic-programming semantics and gesturing at the literature.

ztangent commented 2 years ago

Thanks for these references! Julog.jl actually supports a version of DFS search now, but it looks like I forget to update the README. I didn't implement BFS for any strong reason, and I'm actually thinking of switching the default behavior to DFS eventually. Per the following comment however, it looks like I'll have to refactor how the code is written to reproduce the same DFS algorithm that, e.g., SWI-Prolog uses, which may take me a while to get to: https://github.com/ztangent/Julog.jl/pull/18#issuecomment-1108095933