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

71–80 of 102 posts

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

#71

Post by YeGoblynQueenne »

agumonkey wrote: post #65
YeGoblynQueenne wrote: post #61

Earlier quoted context omitted.

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.

That sounds like iterative deepening without a lower bound then. I guess that's possible. Maybe if you had a link to Markus' page I could have a look.

There are techniques to constraint the search space for _programs_ rather than proofs, that I know from Inductive Logic Programming, like Bottom Clause construction in Inverse Entailment, or the total ordering of the Herbrand Base in Meta-Interpretive Learning (ILP). It would be interesting to consider applying them to constraint the space of proofs in ordinary logic progamming.

Refs for the above techniques are here but they're a bit difficult to read if you don't have a good background in ILP:

http://wp.doc.ic.ac.uk/arusso/wp-content/uploads/sites/47/20...

https://link.springer.com/content/pdf/10.1007/s10994-014-547...

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

#72

Post by YeGoblynQueenne »

082349872349872 wrote: post #49
YeGoblynQueenne wrote: post #31

Earlier quoted context omitted.

No, it's SLD -Resolution :P

"Susie in the Lye with Diamonds" Picture yourself as the goal of a problem With cut-driven search and definite clause Somebody calls you, you answer quite "no"-ly A girl with Kowalskified eyes...

Thanks, I'll treasure that :)

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

#73

Post by YeGoblynQueenne »

nextos wrote: post #62
YeGoblynQueenne wrote: post #60

Earlier quoted context omitted.

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?

I moved to academia, after six years of working in the industry mainly with C# and SQL. It was a deliberate attempt to find a way to work with Prolog. I guess that's a bit immature of me but I fell in love with Prolog in the second year of my CS degree and I couldn't get over it so here I am.

I did an MSc in data science first, then started a PhD to study Inductive Logic Programming (ILP), which is basically machine learning × Prolog (although there's also ASP ILP these days). I got my PhD last summer and I'm now doing a post-doc on a robotics project with Meta-Interpretive Learning (MIL), a recent form of ILP. Here's my latest publication:

https://github.com/stassa/ijclr_2024_experiments

Which is still a bit proof-of-concept. We're still at the very early stages of practical applications of MIL and so there's a lot of foundation work to do. Bliss :)

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

#74

Post by YeGoblynQueenne »

agumonkey wrote: post #66
YeGoblynQueenne wrote: post #60

Earlier quoted context omitted.

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

Right, it's an emacs clone. There's also Sweep, an emacs mode for Prolog.

https://eshelyaron.com/sweep.html

When I grow up, I'll give it a try :)

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

#75

Post by YeGoblynQueenne »

dragonwriter wrote: post #67
YeGoblynQueenne wrote: post #30

Earlier quoted context omitted.

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) langua…

I think there are declarative elements in various high-level languages, e.g. Linq queries in C# so I guess it is an exageration to say "zero-declarative", but in general the level of declarative-ness is tiny compared to Prolog.

Did I misunderstand what you mean?

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

#76

Post by YeGoblynQueenne »

skybrian wrote: post #45
YeGoblynQueenne wrote: post #30

Earlier quoted context omitted.

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 agree that not being fully declarative is okay. But lots of pure functions are written in languages like Python and C#. “Fully-imperative, zero-declarative” seems like a bit of an exaggeration? (I’m generally of the opinion that both laziness and backtracking are bad defaults for general-purpose programming, but they’re handy when you need them.)

See sibling comment to dragonwriter- maybe I'm exaggerating a bit, but I think it's only a bit. It's been a while since I've programmed a lot in anything but Prolog so maybe I should be a little more circumspect.

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

#77

Post by YeGoblynQueenne »

upghost wrote: post #68
YeGoblynQueenne wrote: post #57

Earlier quoted context omitted.

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

Thanks for clarifying. I didn't know those terms, they're probably Markus Triskas' and Sicstus' inventions. Nothing wrong with that. I couldn't find anything about linearized arguments in Sicstus' pages though, they probably changed their docs since you 've seen it.

The "defaulty representation" Markus Triska discusses is indeed something to be avoided, but if compound terms start to proliferate the chance of typos causing problems like the one you had increases. The solution is ad-hoc typing as recommended by Covington et al.

The balance I think, between a "defaulty representation" and an explosion of "magic strings" is to make sure there are only a handful of predicates that expect their arguments to be typed as compound terms and that those predicates are at the base of a hierarchy of calls that pass those arguments around. Those predicates are responsible for reasoning about those typed arguments and they raise errors if something is off. That way you know quickly when there's a mistake, and where it is.

Another thing to keep in mind is that it's easy to test your Prolog predicates in isolation and check that they do what you think they do. This is the best way to catch errors that have to do with argument structure. What I mean is that you can run each predicate on its own, without having to start from the top of your program. You go to your repl and make some queries to the predicate you want to test with different arguments and see how it behaves. That will help catch errors. Unit tests can also help, if you have the patience to write them.

To be honest, I'm not going to defend Prolog for making this kind of thing easy to hurt yourself with. I love Prolog but it's not friendly to newcomers, exactly because of things like that, which you only learn with experience. Even now, after using it for ... 14 years or so, it still finds ways to hurt me. You gotta be careful with it.

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

#78

Post by YeGoblynQueenne »

cryptonector wrote: post #64
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 t…

My SQL is rusty after years of misuse, but what you describe is similar to tabled Prolog. "Tabling" or SLG-Resolution, basically uses memoization to avoid having to re-derive parts of a proof tree that have already been traversed (that's useful because in a proof tree there are often many identical sub-trees under different branches). It also switches the execution strategy from DFS to BFS and delays the execution of goals until they can be proved. That way it avoids infinite left-recursions.

But there's no way to always ensure termination unless one restricts expressivity. Right? Halting problem and all that. Recursion, like iteration, must always risk going infinite, else it is not complete.

The tradeoff between DFS and BFS is like you say and as the article above points out that's the reason DFS was chosen as the original execution strategy for Prolog. Tabling on the other hand can be very memory-hungry (in my applications I often run out of tabling space on my 64GB RAM laptop). In the end, with languages like Prolog, it's the old joke: "sound, complete, efficient- choose two".

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

#79

Post by upghost »

YeGoblynQueenne wrote: post #77
upghost wrote: post #68

Earlier quoted context omitted.

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

Thanks for clarifying. I didn't know those terms, they're probably Markus Triskas' and Sicstus' inventions. Nothing wrong with that. I couldn't find anything about linearized arguments in Sicstus' pages though, they probably changed their docs since you 've seen it. The "defaulty representation" Markus Triska discusses is indeed something to be avoided, but if compound terms start to proliferate the chance of typos c…

Apologies, it was on the tips and tricks page. I'll repost here:

  Linearize Arguments
  Ensures that each argument position is a variable that does not occur elsewhere in the clause head. As an example,
  
  foo(a, p(X1), X) :-
        body(a, X2, X2).

  would become:

  foo(A, A1, X) :-
        A = a,
        A1 = p(X1),
        body(a, X2, X2).
https://sicstus.sics.se/spider/tips.html

I'm really enjoying the convington et al read, cool to see that O'Keefe is an author too!

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

#80

Post by cryptonector »

YeGoblynQueenne wrote: post #78
cryptonector wrote: post #64

Earlier quoted context omitted.

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

My SQL is rusty after years of misuse, but what you describe is similar to tabled Prolog. "Tabling" or SLG-Resolution, basically uses memoization to avoid having to re-derive parts of a proof tree that have already been traversed (that's useful because in a proof tree there are often many identical sub-trees under different branches). It also switches the execution strategy from DFS to BFS and delays the execution of…

Thanks for confirming this. With your reply in mind I think there is no reasonable way to make BFS the default for a logic language, and the programmer will just have to choose between BFS and DFS.

In other words, the answer to TFA's title question is, I think, "no" as to backtracking/DFS.

Post reply on HN