Live data from Hacker News

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

www-ps.informatik.uni-kiel.de

91–100 of 102 posts

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

#91
post #87

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…

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

I'm glad it was of help.

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

I hear you. When I first learned Prolog, in the second year of my CS degree course, the first thing I did was to go to my university's library and gather up all the textbooks I could find about it. I literally came home bent over from the sheer weight of books. It still took me a very long time to learn the ins and outs of it. It doesn't help that Prolog has a small and probably shrinking community and many of the people with long backgrounds and deep knowledge of its practice are starting to retire from public fora; like O'Keefe.

There are only a few resources on the internet that can help you understand Prolog. Markus Triska's as you found out is one of the best (although I have a very different view of many things than he does, there's no doubt he is an expert in the language). When I was learning I got a lot of mileage out of a tutorial on the Amzi Prolog website:

https://amzi.com/AdventureInProlog/index.php

The best thing you can do of course is to keep working with it as much as you can. Things eventually make sense and you learn what works and what doesn't with experience. That's not always easy to do of course. As I say in another comment I had to leave (my lucrative career in) the industry and enter academia (which pays peanuts) to find a place where I could really work as much as I wanted with Prolog.

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

I don't want to sound even more like a zealot than I already do, but the thing is you can do all that in Prolog more easily than in other languages. In general the way I program in Prolog is that I create a language to describe my problem, and then solve my problem in that language. I don't mean that I necessarily design a new programming language and write a parser for it, although you can do that very easily in Prolog with Definite Clause Grammars (you get a decent parser and generator that way though not optimal). I mean that I make up a language to talk about the domain, and use it to describe my problems and their solutions. You do that too, in your solution/3 predicate above, where as far as I can tell you describe resources and actions of a robot etc. Again Prolog lets you do that easily: you can define the abstractions you need. That goes all the way up to the abstractions used in other programming paradigms, like functions or objects etc, and types.

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

Yeah, I tend to ignore those things. I love Prolog but I recognise it's not to everyone's taste. It's quite obvious. It's nice to hear you love it too :)

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

#92

Earlier quoted context omitted.

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.

Why is that? Ultimately someone has to work on the tooling for any project. If you're working in a group in particular, you can have different people working on different parts of the project. If you need a type system, you can have one programmer write it and maintain it, or be the product owner whatever the terminology is these days, then everyone else can use the type system and not have to worry about it any more.

To be clear, there are only some tools, or let's say abstractions, that you need to implement on your own. The good thing about Prolog is that it has a very mature ecosystem of libraries and packages that you can pick off the shelf and work with immediately. Although that is mostly true for SWI-Prolog, where most of those libraries are found. You normally have to write some translation layer to port them over to a different Prolog- and that is totally a PITA. But there's no reason not to use SWI-Prolog, which is free as in speech and as in beer.

For example, SWI-Prolog has http libraries that have everything you need to set up a web app, using Prolog itself as the database and the back-end language both- it's like a LAMP stack except the stack is LP: Prolog running on Linux:

https://us.swi-prolog.org/FAQ/PrologLAMP.md

I reckon the only reason this is not widely used in the industry is because web devs, like everyone else, don't have the time and energy to learn a whole new language, especially one so scary as Prolog. Quoting from the link above:

Our final problem is the lack of masses of Prolog programmers one can easily hire.

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

#93

Earlier quoted context omitted.

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.

Oh, I see Icon is a descendant of SNOBOL. I'll have a look, that seems interesting.

Thanks for the pointer :)

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

#94

Earlier quoted context omitted.

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 "Yo…

Thanks! Yes, it's iterative deepening without a lower bound. The trick is that iterative deepening is used to order the space of proofs so that the shortest proof (path through an SLD-tree) is found first. I use that approach often. The cool thing with it is that it doesn't stop in the first solution and will keep generating new solutions ordered by length of the proof as long as there are any. Some times you really want to know all solutions.

There is a bit of a problem, in that if there is no solution the lack of a lower bound will cause the search to go on forever, or until the search space is exhausted- and you don't want that. If you use a lower bound, on the other hand, you may be cutting the search just short of finding the solution. It's another trade-off.

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

#95

Earlier quoted context omitted.

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.

Oh, I see Icon is a descendant of SNOBOL. I'll have a look, that seems interesting. Thanks for the pointer :)

I hope you enjoy it! I sure did. If you enjoy it, you might also enjoy jq (https://github.com/jqlang/jq), which is also a sort of logic programming language (in that it has pervasive generators and backtracking). Icon has an Algol family syntax, while jq is more... Haskell-ish? in a way if you squint hard? Whereas Prolog is a pile of rules. These differences are very interesting. Verse is another language in this vein, and it seems very interesting as well.

Oh, and yesterday's HN thread about Rama is very interesting as well: https://news.ycombinator.com/item?id=41833629

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

#96

Earlier quoted context omitted.

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…

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

Must be. With UNION you can't end up with an infinite loop unless you have infinite data (or you're implementing a table-valued Ackermann function and so you have... not infinite results but for all practical intents, yeah).

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

#97
post #21

There already is a pretty major effort around the prolog community to build everything as much as possible around pure, monotonic prolog, and to provide a means to support multiple search strategies depending on the best fit for the problem. CLP libraries are also pretty common and the go-to for representing algebraic expressions relationally and declaratively. I wouldn't say that the logic or relational way of descr…

Out of my depth here, but I do have 5 Prolog books I can't seem to let go of. I used to dabble. A lot. Out of all my numerous prog-lang infatuations, only 3 have stuck: Erlang, Prolog and Picolisp. At most, 2 degrees of separation between those 3. No one mentioned Picolisp yet, so I have to, because it has a Prolog embedded in it. This seems like an appropriate place to do it.

https://software-lab.de/doc/ref.html#pilog

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

#98
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…

  > Develop your own ad hoc run-time type and mode checking system.
"Any sufficiently complicated List or Prolog program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Haskell type inference and checking system."

Modelled after Greenspun's Tenth Rule [1].

[1] https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

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

#99

Earlier quoted context omitted.

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

Have you tried Haskell?

For example, it is possible to embed backtracking logic programming [1] into Haskell with not a big effort.

[1] https://hackage.haskell.org/package/logict

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

#100
post #98

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…

> Develop your own ad hoc run-time type and mode checking system. "Any sufficiently complicated List or Prolog program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Haskell type inference and checking system." Modelled after Greenspun's Tenth Rule [1]. [1] https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

I suppose you could hack a bug-ridden implementation of Prolog unification in Prolog but why?

Hindley-Milner type inference is unification over types and unification is built-in to Prolog. Functional programmers ignore this because their textbooks never refer to the original description of unification by Robinson. Wait who? Unification was probably invented by Damas, Hindley or Milner right? Or maybe Haskell Curry? Hey maybe it was John McCarthy?

Post reply on HN