Can logic programming be liberated from predicates and backtracking? [pdf]
www-ps.informatik.uni-kiel.de
Can logic programming be liberated from predicates and backtracking? [pdf]
1–10 of 102 posts
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#2Abstract. 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.
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#3Man, 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!
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#4The Curry language (https://www.curry-language.org) does look interesting. Does anybody have practical experience with it?
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#5Abstract . 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.
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#6Yes, it's called functional programming and it's been around for a while
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#7Abstract . 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.
functional logic programming is not equivalent to functional programming.
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#8[deleted]
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#9Man, 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…
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...
Re: Can logic programming be liberated from predicates and backtracking? [pdf]
#10Abstract . 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…
isn't backtracking a complete search strategy?