20 ms·

Can logic programming be liberated from predicates and backtracking? [pdf]

197 points by matt_d 2y ago

xelxebar 2y ago
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.
xelxebar 2y ago
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 clicked for me, and the effect that had on the entirety of my outlook on work was dramatically changed as a result. For whatever reason, I feel like breaking down my ingrained technical paradigms has allowed me to integrate and strengthen my soft skills. Plus, mind-expanding experiences are just plain fun. Looking for more of that juice! [0]:https://en.wikipedia.org/wiki/Answer_set_programming https://en.wikipedia.org/wiki/Answer_set_programming [1]:https://potassco.org/ https://potassco.org/
- gnulinux 2y ago
  I strongly recommend checking Souffle programming language. It's a dialect of Datalog that can output bulk CSV data that can be easily imported into other databases (like Duckdb or Excel etc). It creates an extremely intuitive framework for logical programming. I.e. you can visualize logical programming as each relation being a giant table of elements, "or" operation being akin to SQL `union all`, "and" operation being akin to SQL `join`, "not" operation being akin to `outer join ... where joined isnull` etc...
  - PaulHoule 2y ago
    The tragedy of RDF and OWL is that people don’t perceive the connection between logic and databases.
- szundi 2y ago
  Could have been an LSD trip description
  - YeGoblynQueenne 2y ago
    No, it's SLD-Resolution :P
tempodox 2y ago
The Curry language (https://www.curry-language.org https://www.curry-language.org) does look interesting. Does anybody have practical experience with it?
- mdaniel 2y ago
  while I was trying to track down the license for it[1], I found https://git.ps.informatik.uni-kiel.de/curry/curry2go https://git.ps.informatik.uni-kiel.de/curry/curry2go (also BSD-3) which says "A compiler and run-time system to compile and run Curry programs as Go programs" 1: maybe this is it? it does include a lot of curry named submodules; anyway, BSD-3-Clause https://git.ps.informatik.uni-kiel.de/curry/pakcs/-/blob/v3.7.0/LICENSE https://git.ps.informatik.uni-kiel.de/curry/pakcs/-/blob/v3....
HeralFacker 2y ago
Yes, it's called functional programming and it's been around for a while
deleted 2y ago
[deleted]
woolion 2y ago
This is a reference to the "Can programming be liberated from the von Neumann style?" from 1977. It argues for functional programming, making the point that the imperative style is more common for efficiency reasons, as the programming model is close to the computer architecture. It aims to be a general thought framework inviting to step a step back on some notions that have been (hastily?) accepted in the programming world. It makes the same analogy that Prolog (or logic programming languages in general) have been strongly influenced by the resolution algorithm. In practice that means that if you write a non-trivial program, if performance is not right you'll need to understand the execution model and adapt to it, mainly with the pruning operator (!). So while the promise is to "declare" values and not think about the implementation details, you're railroaded to think in a very specific way. I personally found that frustrating to find good solutions essentially unworkable because of this, in comparison with either imperative or functional paradigms that are significantly more flexible. As a result, Prolog-style programming feels limited to the small problems for which it is readily a good fit, to be integrated into a general program using a general-purpose language. I may be wrong on this, but of the 50 people that learned Prolog around the same time as me, none kept up with it. Meanwhile, other niche languages like Ocaml, Haskell and Scheme had good success. Rethinking the language foundation could remove these barriers to give the language a broader user base.
- PaulHoule 2y ago
  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.
  - YeGoblynQueenne 2y ago
    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-declarative language like Python or C#. We'll find I believe that most programmers are perfectly fine programming completely non-declaratively and don't have any trouble writing very complex programs in it, and that "OMG my language is not purely declarative" is the least of their problems. I hear some old, wizened nerds even manage to program in C where you actually can drop to the hardware level and push bits around registers entirely by hand O.o
amboo7 2y ago
https://icfp24.sigplan.org/home/minikanren-2024#event-overview https://icfp24.sigplan.org/home/minikanren-2024#event-overvi... is related. There has been work on turning slow bidirectional code into faster functional code (in 2023, reachable from this url).
2-3-7-43-1807 2y ago
Is this about the problem that Prolog tends to ping pong infinitely between leafs? I wrote a fully declarative solitaire game solver and remember this being a big issue forcing me to memorize past states of the backtracking and basically exclude them by another predicate. This is obviously slow. I thought, why not at least have a plugin to avoid trivial cases where backtracking gets stuck switching between A and B. Or a plugin for a stochastic traversal of the solution tree.
- usgroup 2y ago
  There are. Tabling (available in most mature implementations) helps when recalculation of the same states is a problem. Meanwhile, custom search strategy is always an option to implement directly in Prolog. You'll see this in many Advent of Code solutions in Prolog when it is applied to path finding puzzles, in which depth first search is rarely a workable solution.
jkbyc 2y ago
There's an insightful critique of the paper on Reddit: https://www.reddit.com/r/ProgrammingLanguages/comments/1g1su6c/can_logic_programming_be_liberated_from/ 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"
- YeGoblynQueenne 2y ago
  That's a good critique.
rebanevapustus 2y ago
Datalog does not use backtracking, and is getting ever increasingly more popular. See: - The fastest non-incremental embedded Datalog engine https://github.com/s-arash/ascent https://github.com/s-arash/ascent - The state-of-the-art non-embedded and non-incremental Datalog engine https://github.com/knowsys/nemo https://github.com/knowsys/nemo - A python library that contains an embedded incremental Datalog engine https://github.com/brurucy/pydbsp https://github.com/brurucy/pydbsp - A Rust library that provides a embedded incremental Datalog engine over property graphs https://github.com/brurucy/materialized-view https://github.com/brurucy/materialized-view
- lapinot 2y ago
  Datalog is a nice query language but it is far more limited than prolog or general purpose logic programming.
  - convolvatron 2y ago
    there is a really interesting space between queries and prolog which includes mundane junk like encoding and rendering and data formatting changes that benefits in evaluation from having less power but maintains the lovely expressibility and analysis that we get from 'real' logic programming. there's lots of exploring left to do
    - rebanevapustus 2y ago
      That's why embedded Datalog is so good. You can delegate all that to the host language.
ristos 2y ago
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 describing effects is a bad thing either. By design it allows for multiple return values (foo/1, foo/2, ...) you can build higher level predicates that return multiple resources, which is pretty common for many programs. It makes concatenative (compositional) style programming really straightforward, especially for more complex interweaving, which also ends up being quite common. Many prolog implementations also support shift/reset, so that you can easily build things like conditions and restarts, algebraic effects, and/or debugging facilities on top. Prolog is also homoiconic in a unique way compared to lisp, and it's quite nice because the pattern matching is so powerful. Prolog really is one of the best languages I ever learned, I wish it was more popular. I think prolog implementations need a better C FFI interop and a nicer library ecosystem. Trealla has a good C FFI. I think logic programming is the future, and a lot of these problems with prolog are fixable. If it's not going to be prolog, it'll probably be something like kanren and datalog within a lisp like scheme or clojure(script). This is a great resource for getting a good feel of prolog: https://www.youtube.com/@ThePowerOfProlog/videos https://www.youtube.com/@ThePowerOfProlog/videos
- YeGoblynQueenne 2y ago
  SWI-Prolog has a robust and very mature foreign interface to C++: https://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/pl2cpp.html%27) https://www.swi-prolog.org/pldoc/doc_for?object=section(%27p...
- klausnrooster 2y ago
  Out of my depth here, but I do have 5 Prolog books I can't seem to let go of. I used to dabble. A lot. Out of all my numerous prog-lang infatuations, only 3 have stuck: Erlang, Prolog and Picolisp. At most, 2 degrees of separation between those 3. No one mentioned Picolisp yet, so I have to, because it has a Prolog embedded in it. This seems like an appropriate place to do it. https://software-lab.de/doc/ref.html#pilog https://software-lab.de/doc/ref.html#pilog
PaulHoule 2y ago
Reminded me of the “rules and schemes” concept I was thinking of about 10 years ago that would separate “pure logical” rules from the stuff it takes to turn them into a program that runs by either forward chaining (production rules) or backwards chaining (like prolog). I got so far as writing a macro compiler that would let you write a base set of rules and rewrite them for different purposes such as transforming document A into document B or going in the opposite direction. I like how they let you write functions to control the search order because boy that is essential.
YeGoblynQueenne 2y ago
[Note I'm sick and tired; literally. I may not be firing on all cylinders in the following.] The article is fudging things with its use of "backtracking" as a stand-in for backtracking Depth First Search (DFS)- the latter is the search strategy that is "fixed" in Prolog. And it's not really fixed. Prolog programs can also be executed by "tabling" a.k.a. SLG-Resolution, which basically replaces DFS with Breadth-First Search modulo momoization. Tabling avoids an important source of "incompleteness" in Prolog, that of non-terminating left-recursions. To clarify, that is what makes Prolog "incomplete": that executing Prolog programs by DFS makes Prolog loop infinitely when encountering some left-recursions. The article gives the example of a last/2 predicate: last([_H|T],E) :- last(T,E). last([E],E). This does indeed loop. But this one doesn't: last([E],E). last([_H|T],E) :- last(T,E). ?- last_(Ls,3). Ls = [3] ; Ls = [_,3] ; Ls = [_,_,3] ; Ls = [_,_,_,3] ; Ls = [_,_,_,_,3] ; Ls = [_,_,_,_,_,3] . And that's what the article is pointing out with the allusion to "a higher, declarative programming style which frees the programmer from thinking about low-level control details". With such a "higher declarative programming style" the programmer does not have to think about program structure or execution strategy and can write whatever, however, and still get results! The problem with that argument, which is as old as Prolog and possibly even older than that, is that it's an argument from taste, or, indeed, "style", to use the article's terminology. More specifically, for every non-terminating Prolog program that can be written, we can most likely write a Prolog program that does terminate, and that is (success-set) equivalent to the non-terminating program, by keeping in mind the structure of the search space for proofs traversed by ordinary Prolog with DFS, or tabling. And possibly with a few cuts here and there (oh, the humanity!). The article is simply arguing that it is "more declarative" to not have to do that. But, why is "more declarative" better? It's style all the way down. As to the second axis of the argument, the horror of predicates that do not neatly map to "many" real world problems that are better represented as functions, asking whether we can liberate logic programming from predicates is like asking whether we can liberate the First Order Predicate Calculus from predicates, or, equivalently, make ice cream without the ice or the cream. Sure we can. The question is again: why? I don't see a clear justification for that. In particular, setting implementation details aside (as the article does on this point) SLD-Resolution is already sound and refutation-complete, or complete with subsumption. That is the best that can ever be achieved, and the article doesn't seem to claim anything else (or the ghosts of Alonzo Church and Alan Turing would be very, very sad). So this, too, seems to be a matter of taste: functions are more stylish than predicates. M'kay. In fact, if I may blaspheme a little, this is what Church did with his Lambda calculus: he turned everything into typed functions to extend First Order Logic (FOL) into a higher order. And in the process completely destroyed the simple elegance of FOL. Why?
deleted 2y ago
[deleted]
carapace 2y ago
I'm not an expert, and I've only just skimmed the paper, but it seems to me that this is a kind of partial evaluation for Prolog, eh? (Perhaps "partial resolution" is more technically correct?) I think some Prolog systems do something like this already as an optimization, but I could be totally off on that.

197 points by matt_d 2y ago

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.

xelxebar 2y ago

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 clicked for me, and the effect that had on the entirety of my outlook on work was dramatically changed as a result. For whatever reason, I feel like breaking down my ingrained technical paradigms has allowed me to integrate and strengthen my soft skills. Plus, mind-expanding experiences are just plain fun. Looking for more of that juice! [0]:https://en.wikipedia.org/wiki/Answer_set_programming https://en.wikipedia.org/wiki/Answer_set_programming [1]:https://potassco.org/ https://potassco.org/

gnulinux 2y ago
I strongly recommend checking Souffle programming language. It's a dialect of Datalog that can output bulk CSV data that can be easily imported into other databases (like Duckdb or Excel etc). It creates an extremely intuitive framework for logical programming. I.e. you can visualize logical programming as each relation being a giant table of elements, "or" operation being akin to SQL `union all`, "and" operation being akin to SQL `join`, "not" operation being akin to `outer join ... where joined isnull` etc...
- PaulHoule 2y ago
  The tragedy of RDF and OWL is that people don’t perceive the connection between logic and databases.
szundi 2y ago
Could have been an LSD trip description
- YeGoblynQueenne 2y ago
  No, it's SLD-Resolution :P

tempodox 2y ago

The Curry language (https://www.curry-language.org https://www.curry-language.org) does look interesting. Does anybody have practical experience with it?

mdaniel 2y ago
while I was trying to track down the license for it[1], I found https://git.ps.informatik.uni-kiel.de/curry/curry2go https://git.ps.informatik.uni-kiel.de/curry/curry2go (also BSD-3) which says "A compiler and run-time system to compile and run Curry programs as Go programs" 1: maybe this is it? it does include a lot of curry named submodules; anyway, BSD-3-Clause https://git.ps.informatik.uni-kiel.de/curry/pakcs/-/blob/v3.7.0/LICENSE https://git.ps.informatik.uni-kiel.de/curry/pakcs/-/blob/v3....

HeralFacker 2y ago

Yes, it's called functional programming and it's been around for a while

deleted 2y ago

[deleted]

woolion 2y ago

This is a reference to the "Can programming be liberated from the von Neumann style?" from 1977. It argues for functional programming, making the point that the imperative style is more common for efficiency reasons, as the programming model is close to the computer architecture. It aims to be a general thought framework inviting to step a step back on some notions that have been (hastily?) accepted in the programming world. It makes the same analogy that Prolog (or logic programming languages in general) have been strongly influenced by the resolution algorithm. In practice that means that if you write a non-trivial program, if performance is not right you'll need to understand the execution model and adapt to it, mainly with the pruning operator (!). So while the promise is to "declare" values and not think about the implementation details, you're railroaded to think in a very specific way. I personally found that frustrating to find good solutions essentially unworkable because of this, in comparison with either imperative or functional paradigms that are significantly more flexible. As a result, Prolog-style programming feels limited to the small problems for which it is readily a good fit, to be integrated into a general program using a general-purpose language. I may be wrong on this, but of the 50 people that learned Prolog around the same time as me, none kept up with it. Meanwhile, other niche languages like Ocaml, Haskell and Scheme had good success. Rethinking the language foundation could remove these barriers to give the language a broader user base.

PaulHoule 2y ago
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.
- YeGoblynQueenne 2y ago
  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-declarative language like Python or C#. We'll find I believe that most programmers are perfectly fine programming completely non-declaratively and don't have any trouble writing very complex programs in it, and that "OMG my language is not purely declarative" is the least of their problems. I hear some old, wizened nerds even manage to program in C where you actually can drop to the hardware level and push bits around registers entirely by hand O.o

amboo7 2y ago

https://icfp24.sigplan.org/home/minikanren-2024#event-overview https://icfp24.sigplan.org/home/minikanren-2024#event-overvi... is related. There has been work on turning slow bidirectional code into faster functional code (in 2023, reachable from this url).

2-3-7-43-1807 2y ago

Is this about the problem that Prolog tends to ping pong infinitely between leafs? I wrote a fully declarative solitaire game solver and remember this being a big issue forcing me to memorize past states of the backtracking and basically exclude them by another predicate. This is obviously slow. I thought, why not at least have a plugin to avoid trivial cases where backtracking gets stuck switching between A and B. Or a plugin for a stochastic traversal of the solution tree.

usgroup 2y ago
There are. Tabling (available in most mature implementations) helps when recalculation of the same states is a problem. Meanwhile, custom search strategy is always an option to implement directly in Prolog. You'll see this in many Advent of Code solutions in Prolog when it is applied to path finding puzzles, in which depth first search is rarely a workable solution.

jkbyc 2y ago

There's an insightful critique of the paper on Reddit: https://www.reddit.com/r/ProgrammingLanguages/comments/1g1su6c/can_logic_programming_be_liberated_from/ 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"

YeGoblynQueenne 2y ago
That's a good critique.

rebanevapustus 2y ago

Datalog does not use backtracking, and is getting ever increasingly more popular. See: - The fastest non-incremental embedded Datalog engine https://github.com/s-arash/ascent https://github.com/s-arash/ascent - The state-of-the-art non-embedded and non-incremental Datalog engine https://github.com/knowsys/nemo https://github.com/knowsys/nemo - A python library that contains an embedded incremental Datalog engine https://github.com/brurucy/pydbsp https://github.com/brurucy/pydbsp - A Rust library that provides a embedded incremental Datalog engine over property graphs https://github.com/brurucy/materialized-view https://github.com/brurucy/materialized-view

lapinot 2y ago
Datalog is a nice query language but it is far more limited than prolog or general purpose logic programming.
- convolvatron 2y ago
  there is a really interesting space between queries and prolog which includes mundane junk like encoding and rendering and data formatting changes that benefits in evaluation from having less power but maintains the lovely expressibility and analysis that we get from 'real' logic programming. there's lots of exploring left to do
  - rebanevapustus 2y ago
    That's why embedded Datalog is so good. You can delegate all that to the host language.

ristos 2y ago

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 describing effects is a bad thing either. By design it allows for multiple return values (foo/1, foo/2, ...) you can build higher level predicates that return multiple resources, which is pretty common for many programs. It makes concatenative (compositional) style programming really straightforward, especially for more complex interweaving, which also ends up being quite common. Many prolog implementations also support shift/reset, so that you can easily build things like conditions and restarts, algebraic effects, and/or debugging facilities on top. Prolog is also homoiconic in a unique way compared to lisp, and it's quite nice because the pattern matching is so powerful. Prolog really is one of the best languages I ever learned, I wish it was more popular. I think prolog implementations need a better C FFI interop and a nicer library ecosystem. Trealla has a good C FFI. I think logic programming is the future, and a lot of these problems with prolog are fixable. If it's not going to be prolog, it'll probably be something like kanren and datalog within a lisp like scheme or clojure(script). This is a great resource for getting a good feel of prolog: https://www.youtube.com/@ThePowerOfProlog/videos https://www.youtube.com/@ThePowerOfProlog/videos

YeGoblynQueenne 2y ago
SWI-Prolog has a robust and very mature foreign interface to C++: https://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/pl2cpp.html%27) https://www.swi-prolog.org/pldoc/doc_for?object=section(%27p...
klausnrooster 2y ago
Out of my depth here, but I do have 5 Prolog books I can't seem to let go of. I used to dabble. A lot. Out of all my numerous prog-lang infatuations, only 3 have stuck: Erlang, Prolog and Picolisp. At most, 2 degrees of separation between those 3. No one mentioned Picolisp yet, so I have to, because it has a Prolog embedded in it. This seems like an appropriate place to do it. https://software-lab.de/doc/ref.html#pilog https://software-lab.de/doc/ref.html#pilog

PaulHoule 2y ago

Reminded me of the “rules and schemes” concept I was thinking of about 10 years ago that would separate “pure logical” rules from the stuff it takes to turn them into a program that runs by either forward chaining (production rules) or backwards chaining (like prolog). I got so far as writing a macro compiler that would let you write a base set of rules and rewrite them for different purposes such as transforming document A into document B or going in the opposite direction. I like how they let you write functions to control the search order because boy that is essential.

YeGoblynQueenne 2y ago

[Note I'm sick and tired; literally. I may not be firing on all cylinders in the following.] The article is fudging things with its use of "backtracking" as a stand-in for backtracking Depth First Search (DFS)- the latter is the search strategy that is "fixed" in Prolog. And it's not really fixed. Prolog programs can also be executed by "tabling" a.k.a. SLG-Resolution, which basically replaces DFS with Breadth-First Search modulo momoization. Tabling avoids an important source of "incompleteness" in Prolog, that of non-terminating left-recursions. To clarify, that is what makes Prolog "incomplete": that executing Prolog programs by DFS makes Prolog loop infinitely when encountering some left-recursions. The article gives the example of a last/2 predicate: last([_H|T],E) :- last(T,E). last([E],E). This does indeed loop. But this one doesn't: last([E],E). last([_H|T],E) :- last(T,E). ?- last_(Ls,3). Ls = [3] ; Ls = [_,3] ; Ls = [_,_,3] ; Ls = [_,_,_,3] ; Ls = [_,_,_,_,3] ; Ls = [_,_,_,_,_,3] . And that's what the article is pointing out with the allusion to "a higher, declarative programming style which frees the programmer from thinking about low-level control details". With such a "higher declarative programming style" the programmer does not have to think about program structure or execution strategy and can write whatever, however, and still get results! The problem with that argument, which is as old as Prolog and possibly even older than that, is that it's an argument from taste, or, indeed, "style", to use the article's terminology. More specifically, for every non-terminating Prolog program that can be written, we can most likely write a Prolog program that does terminate, and that is (success-set) equivalent to the non-terminating program, by keeping in mind the structure of the search space for proofs traversed by ordinary Prolog with DFS, or tabling. And possibly with a few cuts here and there (oh, the humanity!). The article is simply arguing that it is "more declarative" to not have to do that. But, why is "more declarative" better? It's style all the way down. As to the second axis of the argument, the horror of predicates that do not neatly map to "many" real world problems that are better represented as functions, asking whether we can liberate logic programming from predicates is like asking whether we can liberate the First Order Predicate Calculus from predicates, or, equivalently, make ice cream without the ice or the cream. Sure we can. The question is again: why? I don't see a clear justification for that. In particular, setting implementation details aside (as the article does on this point) SLD-Resolution is already sound and refutation-complete, or complete with subsumption. That is the best that can ever be achieved, and the article doesn't seem to claim anything else (or the ghosts of Alonzo Church and Alan Turing would be very, very sad). So this, too, seems to be a matter of taste: functions are more stylish than predicates. M'kay. In fact, if I may blaspheme a little, this is what Church did with his Lambda calculus: he turned everything into typed functions to extend First Order Logic (FOL) into a higher order. And in the process completely destroyed the simple elegance of FOL. Why?

deleted 2y ago

[deleted]

carapace 2y ago

I'm not an expert, and I've only just skimmed the paper, but it seems to me that this is a kind of partial evaluation for Prolog, eh? (Perhaps "partial resolution" is more technically correct?) I think some Prolog systems do something like this already as an optimization, but I could be totally off on that.