Rethinking Prolog [pdf]

http://okmij.org/ftp/kakuritu/rethinking.pdf

by lelf • 12 years ago

113 34 12 years ago

okmij.org

rdtsc• 12 years ago

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.

MonkeyIsNull3• 12 years ago

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.

seanmcdirmid• 12 years ago

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.

craigching3• 12 years ago

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.

mjn• 12 years ago

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

toolslive• 12 years ago

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

GregBuchholz• 12 years ago

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/

lars5122• 12 years ago

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

MonkeyIsNull3• 12 years ago

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

juliangoldsmith• 12 years ago

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.

lars5122• 12 years ago

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/

PaulHoule• 12 years ago

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

sklogic• 12 years ago

Thanks to PAIP, they usually come together anyway.

zura4• 12 years ago

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

craigching3• 12 years ago

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

akkartik• 12 years ago

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.

DonHopkins• 12 years ago

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

fspeech• 12 years ago

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.

pjmlp2• 12 years ago

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.

zura4• 12 years ago

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

dragonwriter2• 12 years ago

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

pjmlp2• 12 years ago

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

malkia• 12 years ago

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

ggchappell• 12 years ago

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?

tel• 12 years ago

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

Rethinking Prolog [pdf]

Related Stories