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

41–50 of 102 posts

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

#41

Post by upghost »

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…

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) :-
        dissoc(World0, capacity(Place, Capacity0), World1),
        dissoc(World1, carring_rock(robot(R)), World2),
        Capacity #= Capacity0 + 1,
        conj(World2, capacity(Place, Capacity), World).
  result(World0, pickup_rock(robot(R), Place), World) :-
        dissoc(World0, capacity(Place, Capacity0), World1),
        Capacity #= Capacity0 - 1,
        conj(World1, capacity(Place, Capacity), World2),
        conj(World2, carrying_rock(robot(R)), World).
See if you can spot the bug.

...

...

...

  carrying_rock vs carring_rock
Because the typo was in a functor (not predicate or singleton variable) there was no IDE or language support, Prolog assumed that I wanted an reported the wrong answer. of course the snippet I showed was part of a larger example. In other languages it would've taken me 5 minutes to bisect the program or debug and find the error but it took me 3-4 hours. I ended up needing to write a lot of error correcting code, basically a half-assed type system, and that code ended up being more substantial than the actual program logic. Is this common? Am I "doing it wring"?

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.

*Edit:*

I even rewrote it for SICStus and downloaded their IDE and taught myself Eclipse just to use their IDE plugin, and found that setting breakpoints didn't help the problem, because naturally due to the fact that the functor is in the predicate signature, the predicate is never stepped into in the first place!

I could linearize the arguments and include them in the body but this destroys the indexing and can put me into "defaulty representation" territory.

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

#42

Post by carapace »

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.

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

#43

Post by tannhaeuser »

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 might be a reference to that 1977 paper in name, but unlike that Backus paper using math to make its point, this reads like a shallow ad for using the Curry language. The central (and only) point is merely an example of rewriting a Prolog predicate for appending lists into Curry but without even the claim of generality. The rewritten Curry functions however trivially fix determinacy and variables to input and output roles when the entire point of logic variables in Prolog is that they're working either when bound to a value upon entering a predicate call, or can get bound to as many values indeterministically as needed until the procedure terminates succesfully (and then even more on backtracking over failed subsequent goals). The paper also glosses over the concept of unification here. I sure hope the referenced detail papers come with more substance.

The paper title doesn't even make sense? So he wants to "liberate" Logic Programming from predicates? Predicate Logic is First-Order Logic ... ie what YeGoblynQueenne says in another comment.

From a mere practical PoV, who is the author even addressing? Prolog, from the get go, was introduced with NLP, planning problems, and similar large combinatorical search spaces in mind and is used for the convenience it brings to these applications. That FP could theoretically be more broadly used is completely besides the point; Prolog's focus is its strength.

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

#44

Post by gatane »

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…

At Uni, we had to implement the same project on different paradigms/languages.

We had to do goddamn Paint on Prolog. Yup.

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

#45

Post by skybrian »

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…

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

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

#46

Post by mdaniel »

tempodox wrote: post #4

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

while I was trying to track down the license for it[1], I found 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....

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

#47

Post by convolvatron »

lapinot wrote: post #20
rebanevapustus wrote: post #19

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 - The state-of-the-art non-embedded and non-incremental Datalog engine https://github.com/knowsys/nemo - A python library that contains an embedded incremental Datalog engine https://github.com/brurucy/pydbsp - A Rust library that provides a emb…

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

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

#48

Post by usgroup »

LegionMammal978 wrote: post #40
usgroup wrote: post #37

Earlier quoted context omitted.

No breadth first search is still complete given an infinite branching factor (i.e. a node with infinite children). "Completeness" is not about finishing in finite time, it also applies to completing in infinite time. Breadth first search would visit every node breadth first, so given infinite time, the solution would eventually be visited. Meanwhile, say a branch had a cycle in it, even given infinite time, a naive d…

Suppose you have a node with two children A and B, each of which has infinitely many children. If you performed an ordinary BFS, you could get trapped in A's children forever, before ever reaching any of B's children. Or, suppose that a node has infinitely many children, but the first child has its own child. A BFS would get stuck going through all the first-level children and never reach the second-level child. A BF…

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

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

#49

Post by 082349872349872 »

YeGoblynQueenne wrote: post #31
szundi wrote: post #11

Earlier quoted context omitted.

Could have been an LSD trip description

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...

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

#50

Post by agumonkey »

Pearledlang wrote: post #39
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…

Really interesting to hear! I was quite hooked to Prolog in a previous life. Then the limiting factor was the tooling, for really practical use. Could you tell a bit about your Prolog environment?

seconded
Post reply on HN