AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java [pdf] | Hacker News Reader

AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java [pdf]

wps.aw.com

109 pointsdavidroberts14 comments

If you don't know Prolog, I can give a very warm recommendation to spend some time and get familiar with Prolog. It's an extremely simple programming language that is a good example of taking a formal abstraction (predicate logic) and turning it into a practical programming language.

Prolog is also a very good example of the power of the unification algorithm. Unification is also used in e.g. type inference algorithms in programming languages like ML or Haskell.

Prolog is also homoiconic ("code is data", like Lisp) so it's very well suited for doing experiments in languages. A commonly used example is to create a Prolog dialect with fuzzy logic semantics.

Finally, while you might never get a chance to use Prolog in your day job, it's a programming language that will expand your horizons and learning it will, in my opinion, make you a better programmer.

I've been told Prolog is used quite a lot by financial institutions. In fact, one of them bought a whole Prolog company (I forgot the name, sorry).

I agree prolog is quite simple and nice but that is true mostly for the pure prolog subset. The actual programming language with cuts and all the complexity is not so simple anymore - it's not purely declarative (e.g. semantics of the program depends on the order of the clauses).

EDIT: it is Experian (a credit analysis company) that bought Prologia, the Prolog company that was founded by Alain Colmerauer, who designed and implemented the first version of Prolog.

http://www.experianplc.com/news/company-news/2005/25-10-2005...

It's hard to use Prolog without understanding its evaluation strategy, but what trips up beginners coming from other programming language is mostly getting the declarative reading correct. Ordering effects are not, in my experience, all that counter-intuitive, but Mercury removed multiple clauses to solve this problem.

The actual language certainly does have a lot of complexity and mastery depends on understanding it, but this isn't really all that different from other systems, it just presents a very early stumbling block to seasoned programmers. You could still stuff fifteen Prolog's worth of complexity into C++.

I haven't used Prolog for about 10 years (and then only used it at uni) - this is my memory of it too. You could specify the rules for your problem very succinctly and naturally but the devil was in the detail. You'd spend all your time making sure the ordering and cuts were right - which at the time felt non-intuitive (though maybe now with more software experience it would be easier).

Isn't there some alternative varient where the ordering of the rules don't matter? (if that's even possible)

Edit: not to put people off - all alternative software paradigms are worth experimenting with

I'm not sure you can avoid the dependency on the rules order, and having to understand how the Prolog engine works. But I found there is a rather intuitive way to deal with it: think of the Prolog engine as searching a space of possibilities for a goal (expressed by the rules). Then you must order the rules to narrow the search space as quickly as possible. In other words, try to make the first rules as selective as possible to quickly reduce the search space.

That's how you can get fast Prolog programs. But you have to be careful. It's been a long time since I played with Prolog, but I remember a case where reordering two lines would make the solution reached below 1 second from over 15 minutes. That kind of thing is part of the charm and frustration of Prolog. It can be a nice brain teaser.

I like to think of Prolog as an "intellectual diversion."

Just finished a 2 months module on Prolog in my 'Programming Paradigm' course.

It's true that in the basics, it's very simple... but it quickly becomes very complex and twisted as soon as you try to do something non-trivial. Also, the 'cut' operator surely doesn't help in keeping things understandable!

To 'learn' Prolog was a fun experience but honestly I'm glad we switched to something new (scheme), I was getting tired of it. My conclusion is that Prolog is quite good at building expert-systems (duh) but for anything more usual, it's too hard to comprehend.

I definitely plan to learn some Prolog, but I don't know when. For now I plan on learning Datalog because it is used (or a variation on it is used) in Datomic.

The relation between Prolog, Datalog and the "Datalog-like" query language used by Datomic is still not clear at all to me but hopefully soon the picture shall get clearer.

I know it's OT but that's what I really like about Clojure: Clojure taught me about Lisp (even if it's not a 100% pure Lisp), functional programming (even if it's not 100% purely functional), lazyness, monads (yup, really) and now it's probably going to introduce me, thanks to Datomic, to Datalog...

Datalog is really a theoretical basis for declarative query languages. It amounts to a Horn-clause subset of predicate logic and in that it is similar to Prolog. One of the substantial differences is that Datalog doesn't allow functions in terms. That makes Datalog strictly less expressive but it also gives you a guarantee that a Datalog program will always terminate. In comparison, it is trivial to write even a simple Prolog program that does not terminate.

Datalog is really almost just a special syntax for Horn-clauses; it is purely declarative. Prolog is much more than that in that it adds features like cuts, arithmetic, built-in functions, and everything else that's needed in a practical programming language.

Also, a Prolog interpreter implements a sophisticated backward-chaining algorithm. So Prolog basically means backward-chaining. In comparison, I would say there is no default evaluation strategy for Datalog. You (resp. the interpreter) can use backward-chaining, forward-chaining, a combination of both (such as the magic-sets method) - the designer of the Datalog-based query language decides what's best.

Wow! Am I the only one reading this book? No comments so far about the book. I don't remember how I ended up reading this book for past an hour or so. I know Lisp so jumped on Part III after reading the Chapter 1. This really looks like a gem I have never heard of. Anyone already read this? Any comments? Not much in Amazon Reviews.

Thanks for sharing!

This is on the publisher's website, so I assume there are no copyright issues.

For anyone looking to learn prolog, I highly recommend the ciao [1] system. It has many features that help both with exploring the language and with solving actual problems. It also supports some additional constraint programming stuff that I think is really cool.

[1] - http://ciao-lang.org/

prolog is also on my list of "to learns", and just this week i threw "progol" on there, too. i explored datalog a few weeks ago and enjoyed it, and like martinced notes i'm also eying datomic.

i have been bitten by the AI bug.

I "learned" the gist of Prolog in one day. Same as Lisp & Smalltalk. Of course, it takes years to master, as in Lisp & Smalltalk, but you can get a taste of the magic fairly quickly.

A highly recommended book is The Art of Prolog, the "PAIP" of Prolog. But unlike PAIP I have managed only a chapter or two, though it's on my list of "to reads" ;-)

Reply on news.ycombinator.com