4 ms·

Abstract. Logic programming has a long history. The representative of logic programming in practice, the language Prolog, has been introduced more than 50 years

Abstract. Logic programming has a long history. The representative of logic programming in practice, the language Prolog, has been introduced more than 50 years ago. The main features of Prolog are still present today: a Prolog program is a set of predicate definitions executed by resolution steps with a backtracking search strategy. The use of back- tracking was justified by efficiency reasons when Prolog was invented. However, its incompleteness destroys the elegant connection of logic pro- gramming and the underlying Horn clause logic and causes difficulties to teach logic programming. Moreover, the restriction to predicates hinders an adequate modeling of real world problems, which are often functions from input to output data, and leads to unnecessarily inefficient exe- cutions. In this paper we show a way to overcome these problems. By transforming predicates and goals into functions and nested expressions, one can evaluate them with a demand-driven strategy which might re- duce the number of computation steps and avoid infinite search spaces. Replacing backtracking by complete search strategies with new imple- mentation techniques closes the gap between the theory and practice of logic programming. In this way, we can keep the ideas of logic program- ming in future programming systems.

bradley13 2y ago
I didn't read past the abstract, but it sounds like they are just transforming logic-based programs into function-based programs. But: if I wanted functional programming, I wouldn't be writing in Prolog. What would be interesting, would be to replace depth-first search while remaining in the world of predicates and Horn clauses.
- usgroup 2y ago
  functional logic programming is not equivalent to functional programming.
- harperlee 2y ago
  Naïvely, writing only one logic relation of n parameters is about equivalent to writing n^2 functions (just decide for each parameter whether you give it or not as input). So there clearly is value there. I say naïvely because on one hand you might not need all versions of the function, but on the other one you can also provide partial values, so it’s not either input or output.
- YeGoblynQueenne 2y ago
  >> What would be interesting, would be to replace depth-first search while remaining in the world of predicates and Horn clauses. For that you want tabled Prolog, or in other words Prolog executed by SLG-Resolution. The paradigmatic implementation is XSB Prolog: https://xsb.com/xsb-prolog/ https://xsb.com/xsb-prolog/ SWI-Prolog also supports tabling but I think the XSB implementation is more mature.
cerved 2y ago
isn't backtracking a complete search strategy?
- desdenova 2y ago
  That phrase was badly written. Backtracking is a complete search of the problem-space. What is incomplete is the Horn-SAT problem space, which is a subset of SAT, that can be solved in polynomial time, and is what Prolog is based on. A complete logic system would have to solve SAT, which is NP-complete. At least that's what I understood they meant by that.
  - YeGoblynQueenne 2y ago
    Yeah, it's confusing. The article is referring to the incompleteness of Prolog implemented using Depth First Search. That's what the author means by "backtracking". I know this because I know "backtracking" is used in the logic programming community to stand for DFS, but if you don't know the jargon you'd be right to be confused. You can kind of, er, glean, that meaning in the article if you see how they refer to a "fixed" search strategy, and also notice that "backtracking" is not normally a search strategy since it can't search on its own. "Backtracking" is really "DFS with backtracking". The article is pointing out that Prolog with backtracking DFS is incomplete with respect to the completeness of SLD-Resolution. To clarify, SLD-Resolution is complete for refutation, or with subsumption. Prolog is an implementation of SLD-Resolution using DFS with backtracking. DFS is incomplete in the sense that it gets stuck in infinite loops when an SLD tree (the structure searched by DFS in Prolog) has cycles, especially left-recursive cycles. The article gives an example of a program that loops forever when executed with DFS with backtracking, in ordinary Prolog. SLD-Resolution's completeness does not violate the Church-Turing thesis, so it's semi-decidable: SLD-trees may have infinite branches. To be honest I don't know about the equivalence with Horn-SAT, but Resolution, restricted to definite clauses, i.e. SLD-Resolution, is complete (by refutation and subsumption, as I say above, and respecting some structural constraints to do with the sharing of variables in heads and bodies of clauses). We got several different proofs of its completeness so I think we can trust it's true. Edit: where does this knowledge about Horn-Sat come from? Do you have references? Gimme gimme gimme.
cryptonector 2y ago
Depth-first backtracking is trivial to implement, and it's trivial to blend into the language. Breadth-first backtracking is much harder to implement, and I'm not sure that it's trivial to build into a language (though this may be a lack of imagination). Icon had both, but depth-first backtracking was the default and trivial to use, while breadth-first backtracking required using "co-expressions" (co-routines), though at least Icon had a trivial syntax for causing procedure argument expressions to be made into co-expressions. But Icon's approach does not make breadth-first backtracking be a first-class language feature like depth-first backtracking, and this is where my imagination gets stuck. To be fair, I've not truly thought much about this problem.

bradley13 2y ago

I didn't read past the abstract, but it sounds like they are just transforming logic-based programs into function-based programs. But: if I wanted functional programming, I wouldn't be writing in Prolog. What would be interesting, would be to replace depth-first search while remaining in the world of predicates and Horn clauses.

usgroup 2y ago
functional logic programming is not equivalent to functional programming.
harperlee 2y ago
Naïvely, writing only one logic relation of n parameters is about equivalent to writing n^2 functions (just decide for each parameter whether you give it or not as input). So there clearly is value there. I say naïvely because on one hand you might not need all versions of the function, but on the other one you can also provide partial values, so it’s not either input or output.
YeGoblynQueenne 2y ago
>> What would be interesting, would be to replace depth-first search while remaining in the world of predicates and Horn clauses. For that you want tabled Prolog, or in other words Prolog executed by SLG-Resolution. The paradigmatic implementation is XSB Prolog: https://xsb.com/xsb-prolog/ https://xsb.com/xsb-prolog/ SWI-Prolog also supports tabling but I think the XSB implementation is more mature.

cerved 2y ago

isn't backtracking a complete search strategy?

desdenova 2y ago
That phrase was badly written. Backtracking is a complete search of the problem-space. What is incomplete is the Horn-SAT problem space, which is a subset of SAT, that can be solved in polynomial time, and is what Prolog is based on. A complete logic system would have to solve SAT, which is NP-complete. At least that's what I understood they meant by that.
- YeGoblynQueenne 2y ago
  Yeah, it's confusing. The article is referring to the incompleteness of Prolog implemented using Depth First Search. That's what the author means by "backtracking". I know this because I know "backtracking" is used in the logic programming community to stand for DFS, but if you don't know the jargon you'd be right to be confused. You can kind of, er, glean, that meaning in the article if you see how they refer to a "fixed" search strategy, and also notice that "backtracking" is not normally a search strategy since it can't search on its own. "Backtracking" is really "DFS with backtracking". The article is pointing out that Prolog with backtracking DFS is incomplete with respect to the completeness of SLD-Resolution. To clarify, SLD-Resolution is complete for refutation, or with subsumption. Prolog is an implementation of SLD-Resolution using DFS with backtracking. DFS is incomplete in the sense that it gets stuck in infinite loops when an SLD tree (the structure searched by DFS in Prolog) has cycles, especially left-recursive cycles. The article gives an example of a program that loops forever when executed with DFS with backtracking, in ordinary Prolog. SLD-Resolution's completeness does not violate the Church-Turing thesis, so it's semi-decidable: SLD-trees may have infinite branches. To be honest I don't know about the equivalence with Horn-SAT, but Resolution, restricted to definite clauses, i.e. SLD-Resolution, is complete (by refutation and subsumption, as I say above, and respecting some structural constraints to do with the sharing of variables in heads and bodies of clauses). We got several different proofs of its completeness so I think we can trust it's true. Edit: where does this knowledge about Horn-Sat come from? Do you have references? Gimme gimme gimme.

cryptonector 2y ago

Depth-first backtracking is trivial to implement, and it's trivial to blend into the language. Breadth-first backtracking is much harder to implement, and I'm not sure that it's trivial to build into a language (though this may be a lack of imagination). Icon had both, but depth-first backtracking was the default and trivial to use, while breadth-first backtracking required using "co-expressions" (co-routines), though at least Icon had a trivial syntax for causing procedure argument expressions to be made into co-expressions. But Icon's approach does not make breadth-first backtracking be a first-class language feature like depth-first backtracking, and this is where my imagination gets stuck. To be fair, I've not truly thought much about this problem.