Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

www-ps.informatik.uni-kiel.de

Post reply on HN
Print view View original

61–70 of 102 posts

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

#61

Post by YeGoblynQueenne »

agumonkey wrote: post #53
YeGoblynQueenne wrote: post #35

Earlier quoted context omitted.

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, t…

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.

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.

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

#62

Post by nextos »

YeGoblynQueenne wrote: post #60
agumonkey wrote: post #50

Earlier quoted context omitted.

seconded

I use the SWI-Prolog IDE: https://www.swi-prolog.org/PceEmacs.html I suppose it is a bit spartan, but it has a ton of functionality that I find indispensable [1]. For example, when I place my cursor on a variable in the editor it highlights all the variables that unify with it in the same clause, and it will highlight singleton variables in a different colour so you can catch errors caused by typos easily. It is also…

Do you use Prolog in Academia or you have moved to Industry?

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

#63

Post by cryptonector »

xelxebar wrote: post #2

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…

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.

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

#64

Post by cryptonector »

YeGoblynQueenne wrote: post #29

[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…

Incidentally, SQL's recursive queries completely solve the cycle problem by essentially keeping track of the results as a database, which then allows it to prune search results that have already been seen. That's what you get when using UNION in a recursive query, but don't use UNION ALL, as that turns off that pruning effect. This is elegant, but not online.

That's the problem with breadth-first search though: how to make it online?

Conversely, that's the advantage of DFS: it's online because the only state it needs is a search path, and the search path is O(log N), which is small enough to consider online.

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

#65

Post by agumonkey »

YeGoblynQueenne wrote: post #61
agumonkey wrote: post #53

Earlier quoted context omitted.

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.

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.

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.

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

#66

Post by agumonkey »

YeGoblynQueenne wrote: post #60
agumonkey wrote: post #50

Earlier quoted context omitted.

seconded

I use the SWI-Prolog IDE: https://www.swi-prolog.org/PceEmacs.html I suppose it is a bit spartan, but it has a ton of functionality that I find indispensable [1]. For example, when I place my cursor on a variable in the editor it highlights all the variables that unify with it in the same clause, and it will highlight singleton variables in a different colour so you can catch errors caused by typos easily. It is also…

ha, yet another emacs derivative I didn't know of

thanks for your help

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

#67

Post by dragonwriter »

YeGoblynQueenne wrote: post #30
PaulHoule wrote: post #27

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…

> But let's instead compare the incomplete declarativeness of Prolog to a fully-imperative, zero-declarative language like Python or C#.

There's no such thing as "fully-imperative, zero-declarative language" -- at least not one as high level C# or Python -- because declarative/imperative are programming styles, which languages can make more natural but which are used with all (well, higher-level than assembly) languages.

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

#68

Post by upghost »

YeGoblynQueenne wrote: post #57
upghost wrote: post #41

Earlier quoted context omitted.

Serious question, how do you deal with typos in functors? And is your techniques specific to the implementation of Prolog you use? Recently I had a maddening experience chasing this down: result(World0, move(robot(R), Dir), World) :- dissoc(World0, at(robot(R), X0), World1), direction_modifier(Dir, Modifier), X #= X0+Modifier, conj(World1, at(robot(R), X), World). result(World0, drop_rock(robot(R), Place), World) :-…

>> Right now this seems to have all the downsides of programming exclusively with "magic strings", and I haven't been able to find any cure for it or even seen this problem discussed elsewhere. The cure is to not try to program with "magic strings". You don't need to, and if you really want to, then you should try to understand what exactly it is that you're doing, and do it right. Specifically, what you call "magic…

First of all let me say a big thank you for this extremely thoughtful and well crafted response, I genuinely appreciate it.

On mobile and I want to dig into this some more tomorrow but let me start by addressing the last two points.

"Defaulty representation" is described here by Marcus Triska (towards the bottom of the page): https://www.metalevel.at/prolog/data

The terminology of linearizing the arguments I lifted from the SICStus IDE features page: https://sicstus.sics.se/spider/index.html

Thanks again and I'm reviewing your thoughtful comments, thank you again.

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

#69

Post by rebanevapustus »

convolvatron wrote: post #47
lapinot wrote: post #20

Earlier quoted context omitted.

Datalog is a nice query language but it is far more limited than prolog or general purpose logic programming.

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

That's why embedded Datalog is so good. You can delegate all that to the host language.

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

#70

Post by Guthur »

woolion wrote: post #12

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 programmin…

It's possible that new execution models can be found. Tabling is one such execution strategy that many prolog implementationsc already provide.
Post reply on HN