31–40 of 102 posts
Man, lately, I feel like this stuff has been following me around. I'd really like to deep-dive into logic programming and related paradigms. Just recently came across Answer Set Programming[0] (via Potassco's clingo[1]), and it has made me realize just how ignorant I am of the design space that's being explored here. More personally, I recently spent enough time with first Scheme and then APL that the paradigms click…
Could have been an LSD trip description
There already is a pretty major effort around the prolog community to build everything as much as possible around pure, monotonic prolog, and to provide a means to support multiple search strategies depending on the best fit for the problem. CLP libraries are also pretty common and the go-to for representing algebraic expressions relationally and declaratively. I wouldn't say that the logic or relational way of descr…
https://www.swi-prolog.org/pldoc/doc_for?object=section(%27p...
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 inven…
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.
For that you want tabled Prolog, or in other words Prolog executed by SLG-Resolution. The paradigmatic implementation is XSB Prolog:
SWI-Prolog also supports tabling but I think the XSB implementation is more mature.
Earlier quoted context omitted.
isn't backtracking a complete search strategy?
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.
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.
Earlier quoted context omitted.
Depth first search is not complete if branches can be infinitely deep. Therefore if you're in the wrong infinite branch the search will never finish. Breadth first search is complete even if the branches are infinitely deep. In the sense that, if there is a solution it will find it eventually.
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.
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
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
There's an insightful critique of the paper on Reddit: https://www.reddit.com/r/ProgrammingLanguages/comments/1g1su... ...agree that it's weird the paper doesn't mention constraint logic programming, but it's perhaps pointing at it implicitly by saying "Replacing backtracking by complete search strategies"
Earlier quoted context omitted.
Depth first search is not complete if branches can be infinitely deep. Therefore if you're in the wrong infinite branch the search will never finish. Breadth first search is complete even if the branches are infinitely deep. In the sense that, if there is a solution it will find it eventually.
Hrm. I guess the converse applies if nodes can have infinite children. That said, even if your tree is infinitely wide and deep, we're only dealing with countable children, right? Thus a complete traversal has to exist, right? For example, each node has unique path to root, so write where each ni is the sibling ordinal of the node at depth i in that path, i.e. it's the ni-th sibling of the n(i-1)st node. Raising each…
Breadth first search would visit every node breadth first, so given infinite time, the solution would eventually be visited.
Meanwhile, say a branch had a cycle in it, even given infinite time, a naive depth first search would be trapped there, and the solution would never be found.
Earlier quoted context omitted.
The way you write imperative programs in Prolog by exploiting the search order, using cuts, etc. seems clever when you see it in school and do a few assignments for a comparative programming languages class (the only 3 credit CS course I took) but it is painfully awkward if you have to do very much of it.
It isn't. I do most of my programming in Prolog, I write oodles of it daily, and it's not a problem. You learn to think that way easily. The argument is basically that Prolog is not 100% declarative and that if we jump through a few hoops, and translate it all to functional notation, we can make it "more declarative". But let's instead compare the incomplete declarativeness of Prolog to a fully-imperative, zero-decla…
I was quite hooked to Prolog in a previous life. Then the limiting factor was the tooling, for really practical use.
Could you tell a bit about your Prolog environment?
Earlier quoted context omitted.
Hrm. I guess the converse applies if nodes can have infinite children. That said, even if your tree is infinitely wide and deep, we're only dealing with countable children, right? Thus a complete traversal has to exist, right? For example, each node has unique path to root, so write where each ni is the sibling ordinal of the node at depth i in that path, i.e. it's the ni-th sibling of the n(i-1)st node. Raising each…
No breadth first search is still complete given an infinite branching factor (i.e. a node with infinite children). "Completeness" is not about finishing in finite time, it also applies to completing in infinite time. Breadth first search would visit every node breadth first, so given infinite time, the solution would eventually be visited. Meanwhile, say a branch had a cycle in it, even given infinite time, a naive d…
Or, suppose that a node has infinitely many children, but the first child has its own child. A BFS would get stuck going through all the first-level children and never reach the second-level child.
A BFS-like approach could work for completeness, but you'd have to put lower-level children on the same footing as newly-discovered higher-level children. E.g., by breaking up each list of children into additional nodes so that it has branching factor 2 (and possibly infinite depth).