search

ztangent / Julog.jl

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

Fixed DFS traversal #18

Open sebdumancic opened 2 years ago

sebdumancic commented 2 years ago

The DFS traversal did not return the answers in the same order as a Prolog implementation like SWIPL. This is now fixed.

ztangent commented 2 years ago

Getting to this a bit slow because I was on vacation last week! Thanks for fixing the DFS issue -- I have a couple of questions before merging, just to make sure I understand what's going on, will ask in them in a PR review.

ztangent commented 2 years ago

After some further thought, I realized that the real reason why Julog's depth-first search order differs from SWI-Prolog is because it's not actually implementing backtracking search.

As far as I can tell, in standard implementations of Prolog, you're supposed to immediate start working on the next goal once you find a matching clause, and only move on to the next matching clause (trying to unify it with the goal, etc.) once you're done with the current clause.

What Julog is currently doing in DFS is that it's adding iterating through all matching clauses, checking if they unify, and adding them to the queue, before popping goals off from the end of the queue --- i.e., it adds all children to the queue, before descending to the next level.

To fix this, I think I'll have to reimplement the search procedure so that backtracking search is actually possible. This will hopefully lead to some memory improvements as well, but it'll take a bit of work and refactoring.