4 ms·

In practice, though, with BFS you'd run out of memory instead of never finding a solution. Also, there shouldn't be many situations where you'd be able to prod

In practice, though, with BFS you'd run out of memory instead of never finding a solution. Also, there shouldn't be many situations where you'd be able to produce infinite branches in a prolog program. Recursions must have a base case, just like in any other language.

YeGoblynQueenne 2y ago
This has to do with the ordering of search: searching a proof tree (an SLD tree, in SLD-Resolution) with DFS, as in Prolog, can get stuck when there are cycles in the tree. That's especially the case with left-recursion. The article gives an example of a left-recursive program that loops if you execute it with Prolog, but note that it doesn't loop if you change the order of the clauses. This version of the program, taken from the article, loops (I mean it enters an infinite recursion): last([_H|T],E) :- last(T,E). last([E],E). ?- last_(Ls,3). % Loops This one doesn't: last([E],E). last([_H|T],E) :- last(T,E). Ls = [3] ; Ls = [_,3] ; Ls = [_,_,3] ; Ls = [_,_,_,3] ; Ls = [_,_,_,_,3] ; Ls = [_,_,_,_,_,3] . % And so on forever To save you some squinting, that's the same program with the base-case moved before the inductive case, so that execution "hits" the base case when it can terminate. That's half of what the article is kvetching about: that in Prolog, you have to take into account the execution strategy of logic programs and can't just reason about the logical consequences of a program, you also have to think of the imperative meaning of the program's structure. It's an old complain about Prolog, as old as Prolog itself.
- agumonkey 2y ago
  IIRC Markus Triska showed a trick (with a nickname i forgot) to constrain the search space by embedded a variable length into the top level goal.
  - YeGoblynQueenne 2y ago
    I think what you mean is that he adds an argument that counts the times a goal is resolved with, thus limiting the depth of resolution? That works, but you need to give a magic number as a resolution depth limit, and if the number is too small then your program fails to find a proof that it normally should be able to find. It's not a perfect solution.
    - agumonkey 2y ago
      Yes, well not so much a constant value. He added an unbound variable and it was enough to alter the search. Indeed it's still more or a trick, but it got me interested if there were other more fundamental ideas beyond that.
      - YeGoblynQueenne 2y ago
        That sounds like iterative deepening without a lower bound then. I guess that's possible. Maybe if you had a link to Markus' page I could have a look. There are techniques to constraint the search space for _programs_ rather than proofs, that I know from Inductive Logic Programming, like Bottom Clause construction in Inverse Entailment, or the total ordering of the Herbrand Base in Meta-Interpretive Learning (ILP). It would be interesting to consider applying them to constraint the space of proofs in ordinary logic progamming. Refs for the above techniques are here but they're a bit difficult to read if you don't have a good background in ILP: http://wp.doc.ic.ac.uk/arusso/wp-content/uploads/sites/47/2015/01/IE_PROGOL.pdf http://wp.doc.ic.ac.uk/arusso/wp-content/uploads/sites/47/20... https://link.springer.com/content/pdf/10.1007/s10994-014-5471-y.pdf https://link.springer.com/content/pdf/10.1007/s10994-014-547...
        agumonkey 2y ago
        thanks a lot, i'll add a comment with the video I had in mind soon
        jodrellblank 2y ago
        > "Maybe if you had a link to Markus' page I could have a look." e.g. here: https://www.metalevel.at/tist/ https://www.metalevel.at/tist/ solving the Water Jugs problem (search on the page for "We use iterative deepening to find a shortest solution") finding a list of moves emptying and filling jugs, and using `length(Ms, _)` to find shorter list of moves first. or here: https://www.metalevel.at/prolog/puzzles https://www.metalevel.at/prolog/puzzles under "Wolf and Goat" he writes "You can use Prolog's built-in search strategy to search for a sequence of admissible state transitions that let you reach the desired target state. Use iterative deepening to find a shortest solution. In Prolog, you can easily obtain iterative deepening via length/2, which creates lists of increasing length on backtracking."

YeGoblynQueenne 2y ago

This has to do with the ordering of search: searching a proof tree (an SLD tree, in SLD-Resolution) with DFS, as in Prolog, can get stuck when there are cycles in the tree. That's especially the case with left-recursion. The article gives an example of a left-recursive program that loops if you execute it with Prolog, but note that it doesn't loop if you change the order of the clauses. This version of the program, taken from the article, loops (I mean it enters an infinite recursion): last([_H|T],E) :- last(T,E). last([E],E). ?- last_(Ls,3). % Loops This one doesn't: last([E],E). last([_H|T],E) :- last(T,E). Ls = [3] ; Ls = [_,3] ; Ls = [_,_,3] ; Ls = [_,_,_,3] ; Ls = [_,_,_,_,3] ; Ls = [_,_,_,_,_,3] . % And so on forever To save you some squinting, that's the same program with the base-case moved before the inductive case, so that execution "hits" the base case when it can terminate. That's half of what the article is kvetching about: that in Prolog, you have to take into account the execution strategy of logic programs and can't just reason about the logical consequences of a program, you also have to think of the imperative meaning of the program's structure. It's an old complain about Prolog, as old as Prolog itself.

agumonkey 2y ago
IIRC Markus Triska showed a trick (with a nickname i forgot) to constrain the search space by embedded a variable length into the top level goal.
- YeGoblynQueenne 2y ago
  I think what you mean is that he adds an argument that counts the times a goal is resolved with, thus limiting the depth of resolution? That works, but you need to give a magic number as a resolution depth limit, and if the number is too small then your program fails to find a proof that it normally should be able to find. It's not a perfect solution.
  - agumonkey 2y ago
    Yes, well not so much a constant value. He added an unbound variable and it was enough to alter the search. Indeed it's still more or a trick, but it got me interested if there were other more fundamental ideas beyond that.
    - YeGoblynQueenne 2y ago
      That sounds like iterative deepening without a lower bound then. I guess that's possible. Maybe if you had a link to Markus' page I could have a look. There are techniques to constraint the search space for _programs_ rather than proofs, that I know from Inductive Logic Programming, like Bottom Clause construction in Inverse Entailment, or the total ordering of the Herbrand Base in Meta-Interpretive Learning (ILP). It would be interesting to consider applying them to constraint the space of proofs in ordinary logic progamming. Refs for the above techniques are here but they're a bit difficult to read if you don't have a good background in ILP: http://wp.doc.ic.ac.uk/arusso/wp-content/uploads/sites/47/2015/01/IE_PROGOL.pdf http://wp.doc.ic.ac.uk/arusso/wp-content/uploads/sites/47/20... https://link.springer.com/content/pdf/10.1007/s10994-014-5471-y.pdf https://link.springer.com/content/pdf/10.1007/s10994-014-547...
      - agumonkey 2y ago
        thanks a lot, i'll add a comment with the video I had in mind soon
      - jodrellblank 2y ago
        > "Maybe if you had a link to Markus' page I could have a look." e.g. here: https://www.metalevel.at/tist/ https://www.metalevel.at/tist/ solving the Water Jugs problem (search on the page for "We use iterative deepening to find a shortest solution") finding a list of moves emptying and filling jugs, and using `length(Ms, _)` to find shorter list of moves first. or here: https://www.metalevel.at/prolog/puzzles https://www.metalevel.at/prolog/puzzles under "Wolf and Goat" he writes "You can use Prolog's built-in search strategy to search for a sequence of admissible state transitions that let you reach the desired target state. Use iterative deepening to find a shortest solution. In Prolog, you can easily obtain iterative deepening via length/2, which creates lists of increasing length on backtracking."