Rethinking Prolog [pdf] | Hacker News Reader

Rethinking Prolog [pdf]

okmij.org

113 pointslelf34 comments

The best thing about prolog is how naturally search happens: state facts and rules once, then query them in many different ways. The worst part is, as the paper describes, constantly having to curb this search so that Prolog runs efficiently for normal deterministic code.

Another missing piece that this paper picks up: in the real world we want to generate options in order of likelihood. The Alchemy project for AI incorporates probability this way. My understanding is that it doesn't unfortunately doesn't scale well.

http://alchemy.cs.washington.edu/

Shameless plug: I revisited Prolog in recent times and wrote Marelle, a tool for test-driven sysadmin. The language is clunky by today's standards, but I still haven't seen nicer syntax for writing non-determinism.

https://github.com/larsyencken/marelle

Thanks for posting this, it's for projects like this that I always look through the comments. :)

Have you seen any good Prolog tutorials for programmers? I've played with Prolog a little bit, but I've never understood how you'd really use it.

You could try Learn Prolog Now:

http://www.learnprolognow.org/lpnpage.php?pageid=online

My feeling is that prolog as a language hasn't aged as well as it could have, so learning it now is mainly as a mental exercise. Something like Mercury shows more of the potential of logic programming, seating it properly alongside functional programming as it should be.

https://mercurylang.org/

In my experience Prolog is best as a user interface. The ability to explore through querying the clauses database and compose and explore different modes without writing throw away code is a real pleasure. Imagine a Prolog style command shell: the datalog semantics compose really well (basis of database queries), the naive search obviates writing throw away functions just for command line use, two way data flow through logical variable and unification significantly reduce the mental load needed to remember variations of function names etc.

It is a pity this is not done more often in practice. It is rather easy to write FFI functions for Prolog if efficiency is a concern. Embedding Prolog style computation inside another language, as the paper has done, seems to me to miss the point. It is the Prolog programming environment that I appreciate the most.

When wondering about Prolog and types one should mention Mercury -- Prolog's typed cousin.

http://mercurylang.org/

Paper already mentions -- Haskell with logic extensions:

http://www-ps.informatik.uni-kiel.de/currywiki/

The problem with Prolog is the need to rewire your brain to think in Prolog. I remember struggling for many hours to solve a problem and hitting a wall. But then when it is solved in Prolog it would be something like 10 lines of code.

It kind of reminds of understanding and writing math formulas. It would take days to decipher a one-line formula.

Same experience with Prolog: I feel like I have to re-wire my brain every time I come back to it. Completely different way of solving problems.

The problem with programming in Prolog after learning how to think in Prolog is the need to remaster control of the search space via cut.

This. I'm no Prolog expert, but every time I come back to it I remember how elegant canonical problems are to solve with it. I absolutely love the declarative style. More languages need to have logic extensions a la core.logic for Clojure, various Kanrens for Scheme. I would love to see computer scientists make advancements in logic programming.

Amen

Just a nitpick, but core.logic is a version of Kanren[0].

[0] https://github.com/clojure/core.logic

I'm aware of that, I wasn't aware that I said otherwise ;) I just meant that more implementations in more languages would be a good thing

It's just the way you phrased it, core.logic for Clojure, various Kanrens for Scheme, as opposed to, implementations for Kanren in Clojure and Scheme such as core.logic.

There's a fairly large part of the ex-Prolog community that decided to go all-in on the declarative part, partly in reaction to that, and partly in reaction to other warts in Prolog's semantics, like the fact that statement order is significant. There was a period when logic-programming theorists were trying to come up with what Prolog's semantics would be, if you assumed it was possible to give it a vaguely logic-style semantics versus defining its semantics as "whatever SLDNF gives you". One of the proposals that came out that was the "stable model semantics". And that gave rise to a purely declarative logic-programming paradigm, answer-set programming. That has then turned out to mesh well with modern developments in SAT/SMT/etc. solver-style systems, instead of Prolog's more classic backtracking search, so sits at some kind of intermediate space where it's about equally influenced by the logic-programming heritage and the "solver" heritage.

A well-maintained / open-source implementation: http://potassco.sourceforge.net

An introductory paper: http://www.aaai.org/Papers/AAAI/2008/AAAI08-270.pdf

Let me add another good entry point to answer set programming. http://www.kr.tuwien.ac.at/staff/tkren/pub/2009/rw2009-asp.p...

mercury is really nice. For example, it has uniqueness typing for IO combined with syntactic sugar to make all of this rather terse.

Everything by Oleg Kiselyov is great. Here's the link to the slides for the talk, and code for the examples in the paper:

http://okmij.org/ftp/kakuritu/logic-programming.html#vs-prol...

...and to his home page:

http://okmij.org/ftp/

I wish Prolog got 1/10 the interest from people that Lisp gets.

Thanks to PAIP, they usually come together anyway.

I always mention Art Of Prolog along with SICP, when asked about good books.

I just picked this up a couple of weeks ago:

http://www.amazon.com/Programming-Artificial-Intelligence-In...

Came highly recommended by David Nolen on his blog. Appears to have a good section on CLP.

EDIT: And completely agree with you on "The Art of Prolog", I have that too and have read most of it. Need to get back to finishing that up some day ;)

Yes, Bratko's book is on my reading list but never got to it so far ;)

As a lisp enthusiast for the last five years, I'm starting to have the same reaction. This paper's been a light-bulb moment.

I thought Prolog was just a Japanese joke that American Lisp programmers played along with in order to get US Government funding.

Looks like a nice article.

Every time I mess with Prolog [which is once a year, as I cover it in my Programming Languages class] I have the same two thoughts:

(1) This is nifty stuff, but I wouldn't want to program this way all the time. Rather, Prolog-ish computing should be available as a library in some more conventional language.

It's nice to see that the authors of this article are thinking at least somewhat the same way.

(2) This isn't really logic programming. A Prolog predicate with no inputs and one output is a stream. A predicate with one input and one output is a parametrized stream. A predicate with one input and no outputs is a filter for a stream.

Streams are everywhere in modern PL design: Python iterables and Haskell lists for example. C++ seems to be moving slowly in the direction of some kind of coherent stream spec. (think about range-based for loops). And Prolog has some really nice stream-handling ideas that other languages would do well to adopt.

But Prolog people don't think that way. Instead of seeing Prolog as a stream-based language, they see it as a sort of rough draft of a logic-based language, and they wonder how to move it more in the direction of pure logic. Could this be a misguided idea?

(Infinite) streams can be seen as really fundamental codata constructions as well. They're `nu (a )`, so if you believe that both codata and products are necessary then you have streams.

A lot* of people have rejected the first of those for most of the history of mathematics, but nobody rejects the second. Thus, streams are exactly as popular as codata/anti-foundation is.

Loved Prolog, pity that it stayed mostly in academia.

Even got 3rd place on the Portuguese Logic Programming Contest.

I guess Erlang might be the way of keeping it somehow alive in the industry.

Well, besides that Erlang was initially implemented in Prolog, I don't think these languages have much in common except punctuation symbols :)

Then again... http://danlucraft.com/blog/2007/08/comparing-erlang-and-prol...

As for binding, yes, you can come up with similarly looking examples, but they are different in essence: Erlang has pattern matching, while Prolog has unification.

"Erlang has pattern matching, while Prolog has unification."

Ah, yes. My first reaction to seeing pattern matching in ML: "Hey, this is literally half of unification."

I'm kind of wondering why we haven't seen any notable (unless I've missed something) languages with full unification escape from academia into wider use since Prolog -- I know on the academic side there is Oz, which is a very interesting language, but I don't get the impression that its seen much, if any, use in industry.

Yes you are right, that is why I said "somehow".

This completely muddled my understanding of determinism and non-determinism. Time to go back to the books....

Reply on news.ycombinator.com