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

81–90 of 102 posts

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

#81

Post by YeGoblynQueenne »

upghost wrote: post #79
YeGoblynQueenne wrote: post #77

Earlier quoted context omitted.

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…

Ah, thanks. There's nothing wrong with that except that it makes code more verbose. An alternative is flattening, where you remove the compound arguments from the heads of predicates by defining them as new predicates.

Let me see if I can apply flattening to the example above:

  % Flattened version:
  foo(a, A1, X) :-
        q(A1)
        ,body(A, X2, X2).

  q(p(X1)):-
    % ... code that binds X1
    .
With flattening only compound terms are replaced, not constants so "a" remains unchanged. It's similar to an ad-hoc type system again, but the cool thing is that it can be done automatically. There's an algorithm for it known to the Inductive Logic Programming (ILP) community. Let me see if I can find that paper... Yep:

Flattening and Saturation: Two Representation Changes for Generalization, Céline Rouveirol, 1994.

https://link.springer.com/content/pdf/10.1023/A:102267821728...

The example is a bit unusual though because it only checks that A1 = p(X1) and doesn't do anything with X1, it even leaves it dangling as a singleton; same with X and X2. That's very unlikely for real-world code where you want to use unification as a mechanism to pass the state of the computation around your program. With flattening you want to have an extra argument in the new predicate that "returns" a value that you want to process further. I think maybe they meant to write it like this:

  foo(a, p(X1), X) :-
        body(a, X1, X).

  foo(A, A1, X) :-
        A = a,
        A1 = p(X1),
        body(a, X1, X).
In which case the flattened version would be like:

  foo(a, A1, X) :-
        q(A1,X1),
        body(a, X1, X).

  q(p(X1),X2):-
    % ... code that binds X2
    .
So, I guess, we see that this is a known gotcha and the logic programming community has different ways to work around it. In the ILP community there's a different motivation (to make a language finite, and therefore decidable, by removing "functions").

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

Yeah. I haven't heard much from O'Keefe lately and I miss his advice. He was a regular contributor to the SWI-Prolog mailing list when I was doing my MSc in 2014. I think there was a bit of a problem with the SWI-Prolog community moving to Google and he hasn't returned since, even though the community is now on Discourse.

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

#82

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…

In SQL you say something like:

  WITH RECURSIVE transitive_closure AS (
      SELECT parent, child FROM things
    UNION
      SELECT tc.parent, t.child
      FROM things t
      JOIN transitive_closure tc ON tc.child = t.parent
  )
  SELECT * FROM transitive_closure;
where `transitive_closure` is a table that gets all the results of the computation. The engine will run the second part of the query repeatedly until no new rows are added to the `transitive_closure` table. (If you change `UNION` to `UNION ALL` and there's circular paths then this will not terminate.)

Sounds a lot like whatever "tabling" is in Prolog.

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

#83

Post by YeGoblynQueenne »

cryptonector wrote: post #80
YeGoblynQueenne wrote: post #78

Earlier quoted context omitted.

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.

To be honest I'd like it to be possible to completely do away with graph search in Resolution-based theorem proving. Resolution itself assumes no search, it's only an inference rule that removes contradictions from a theory. The original paper on Resolution proposes various ways to implement it but they all come down to search of some sort. I guess that's all we know how to do in AI: search :/

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

#84

Post by cryptonector »

YeGoblynQueenne wrote: post #73
nextos wrote: post #62

Earlier quoted context omitted.

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…

You might want to look at the Icon programming language. I fell in love with it long ago, but I did not go the academic route to use it more, I just accepted that it wouldn't be a part of my work life. Later -much later- I found jq, with which I had more success in industry. Both are very much like logic programming languages in that they have pervasive (DFS) backtracking.

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

#85

Post by YeGoblynQueenne »

cryptonector wrote: post #82
YeGoblynQueenne wrote: post #78

Earlier quoted context omitted.

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…

In SQL you say something like: WITH RECURSIVE transitive_closure AS ( SELECT parent, child FROM things UNION SELECT tc.parent, t.child FROM things t JOIN transitive_closure tc ON tc.child = t.parent ) SELECT * FROM transitive_closure; where `transitive_closure` is a table that gets all the results of the computation. The engine will run the second part of the query repeatedly until no new rows are added to the `trans…

Likely. It depends on how the transitive_closure results are computed. In tabling it's still by resolution so you can still get stuck in infinite loops, e.g. on infinite right-recursions. I think maybe that's more similar to UNION ALL?

I should probably read a bit about this again. I rarely used recursive queries in SQL when I worked with it, not least because a couple of times I did, I got into trouble because they went haywire :)

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

#86

Post by agumonkey »

YeGoblynQueenne wrote: post #71
agumonkey wrote: post #65

Earlier quoted context omitted.

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). I…

thanks a lot, i'll add a comment with the video I had in mind soon

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

#87

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…

Let me thank you also for sharing those resources and acknowledging this is a tricky problem for newcomers. I do love Prolog and I used to think I was a very careful coder with significant attention to detail, but Prolog is exposing what a clumsy buffoon I am if I don't have significant IDE support or "crash on typo" support.

I am particularly grateful because most of the books as you know were written a long time ago and tend to focus more on the beauty of the language and tend to gloss over the software engineering or composing large reliable problems. It is very rare to meet someone with significant experience in Prolog that can still remember what it was like to struggle with issues like that. Most "criticism" I read about Prolog are very superficial and are distracting from the more pressing best practices, so I'm extremely grateful that you shared this paper and I am really surprised I've never encountered it before.

I am actually really shocked to hear that the advice is to roll your own type system, and it's really interesting. I wonder if that is also the case for other expressive languages such as Forth/PostScript, etc. Most of the languages I work with more often (Python/JS/TypeScript/Clojure/C# ... but PARTICULARLY Python) tend to view runtime assertions and type-checking as an *anti-pattern*.

So I am really pleased and surprised to hear that a language as expressive and eloquent as Prolog, at least some folks find that writing that sort of code to be acceptable.

I realize this comment is getting long but the technique you mentioned of using goal_expansion/2 to compile away the assertions --

the dang thing about Prolog is the more you look into it, the more powerful you realize it is, but I'll be damned if it's not impossible to find these things out without someone telling you about them. Most languages seem to be possible to self-teach, but if I were to self-teach Prolog I never would've learned about the concept of monotonicity and I'd be using cut operators willy-nilly etc, lucky that I stumbled on Markus's blog/videos and lucky that I bumped into you!

Just like Python dislikes defensive runtime type checking, another interesting thing is that HEAVY use of metaprogramming tends to be viewed disfavorably in lisp, at least in Clojure! It's typically "don't write macros unless you have no other choice, because no one wants to read/learn your damn macros". I assumed it would be the same way in Prolog, but perhaps I'm wrong?

Anyway thanks again for the really patient response and for sharing your experience.

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

#88

Post by jodrellblank »

YeGoblynQueenne wrote: post #71
agumonkey wrote: post #65

Earlier quoted context omitted.

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). I…

> "Maybe if you had a link to Markus' page I could have a look."

e.g. here: https://www.metalevel.at/tist/ solving the Water Jugs problem (search on the page for "We use iterative deepening to find a shortest solution") finding a list of moves emptying and filling jugs, and using `length(Ms, _)` to find shorter list of moves first.

or here: https://www.metalevel.at/prolog/puzzles under "Wolf and Goat" he writes "You can use Prolog's built-in search strategy to search for a sequence of admissible state transitions that let you reach the desired target state. Use iterative deepening to find a shortest solution. In Prolog, you can easily obtain iterative deepening via length/2, which creates lists of increasing length on backtracking."

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

#89

Post by [deleted] »

LegionMammal978 wrote: post #54
usgroup wrote: post #48

Earlier quoted context omitted.

Countable infinity does not work like that: two countable infinities are not more than one countable infinity. I think it falls into the "not even wrong" category of statements. The Wikipedia article is fairly useful: https://en.wikipedia.org/wiki/Countable_set

Yes, if you put two (or three, or countably many) countable sets together, you obtain a set that is also countable. The problem is, we want to explicitly describe a bijection between the combined set and the natural numbers, so that each element is visited at some time. Constructing such a bijection between the natural numbers and a countably-infinite tree is perfectly possible, but it's less trivial than just DFS or…

[deleted]

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

#90

Post by foobiekr »

YeGoblynQueenne wrote: post #59
foobiekr wrote: post #58

Earlier quoted context omitted.

so so so so so so so so so much this. I have tried to make prolog a part of various systems on and off for two decades and the ergonomics and basic practical shit like this is why it never works. the answer is always: do a lot of manual stuff that the language should do for you. I can, but I can't get a team to.

Then don't use Prolog. It's not mandatory. For the record I never have problems like that and I'm sure I'm not special. Well, not in that way. This all comes under the heading of "learn what works". You have to do that with any language. Edit: as a slightly less flippant answer (sorry) Prolog doesn't "do a lot of manual stuff that the language should do for you" because the Prolog community doesn't think the language…

You can never roll your own and have a working ecosystem. This is exactly the problem.
Post reply on HN