A Short Introduction to Prolog

[microtonal]

Good follow-up literature:

- Learn Prolog Now! by Patrick Blackburn, Johan Bos, and Kristina Striegnitz provides an introduction to Prolog:

http://www.learnprolognow.org/

- Prolog and Natural-Language Analysis by Fernando C. N. Pereira and Stuart M. Shieber provides an introduction to Prolog, and applies it to natural language processing. The book is more difficult than Learn Prolog Now!, but if you enjoy SICP, you will enjoy this book.

http://www.mtome.com/Publications/PNLA/pnla-digital.html

- The Craft of Prolog by Richard O'Keefe is a must to learn writing correct efficient Prolog code. Many eye-openers.

http://www.amazon.com/Craft-Prolog-Logic-Programming/dp/0262...

- Warren's Abstract Machine: A Tutorial Reconstruction by Hassan Ait-Kaci is a thorough overview of David Warren's abstract machine for executing of Prolog code. Since modern Prolog implementations are often based on WAM, it helps in understanding how to design efficient Prolog programs.

http://wambook.sourceforge.net/

[mhd]

Don't forget Sterling and Shapiro's "Art of Prolog"

http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&...

[JadeNB]

The Craft of Prolog is a beautiful book; it's one of those SICP-style books that doesn't just teach you a programming language, but changes your way of thinking about programming. I am also amused by the sly (and not-so-sly) digs that O'Keefe gets in at, well, everyone else who writes Prolog.

[mindcrime]

FWIW, I compiled a list of freely available Prolog resources a while back. Anyone looking to learn Prolog might find some of this useful, even though it is a few years old now:

http://www.jroller.com/openqabal/entry/prolog_i_m_going_to

[bulte-rs]

Perhaps a little bit specific, but definitely worth the read: "Prolog Programming for Artificial Intelligence" by Ivan Bratko (0321417461)

[swannodette]

After learning a bit of Prolog and seeing its beauty you may wonder how to leverage the paradigm in your own work. Lispers in particular have pondered this for nearly 3 decades - Peter Norvig's Paradigms of Artificial Intelligence famously includes a Prolog interpreter/compiler.

The Reasoned Schemer also continues in this tradition. I used that as my introduction into the beauty of Prolog and created core.logic - https://github.com/clojure/core.logic

If you're interested in being able to mix functional, object-oriented, and logic programming techniques in a single practical language - I think Clojure is a great place to start (yes, yes, Mozart/Oz is good too ;).

[kunley]

On your last sentence: well, dataflow variables plus backtracing are crucial things in Prolog; Mozart/Oz has dataflow vars right away and backtracing can be called on demand.

How exactly would you do this in Closure? I'm a big fan of this platform, but can't see how to easily apply above-mentioned techniques. Dataflow library in clojure-contrib seems to have very narrow scope AFAIR.

[barik]

I'll also chime in and say that Prolog is an interesting language to experiment with even if you don't use it for anything else later. It is said that there are some languages that change the way that you think about programming -- Prolog is definitely one of these.

It is one of the few languages where the majority of the work is done through pattern matching (unification), rather than explicit algorithms.

[JadeNB]

> It is said that there are some languages that change the way that you think about programming

These are also sometimes called 'Perlis languages'. LtU has a nice thread at http://lambda-the-ultimate.org/node/3464 about other examples.

[chipmunkninja]

Haha, in University, on a project with a friend, we ended up re-writing cpp (the C-compiler preprocessor) in Prolog. We got an A- and "I'm not sure why you'd do this … " on the project.

Good times, good times.

[datadon]

I did a university module in Prolog (for programming intelligent systems). Although I have not used it since, I always remember it fondly. It is a totally different paradigm to the Pythons/Rubies/Cs/Javas and really quite refreshing when you get in to it.

Unfortunately I now struggle to think of a use for it on a day to day basis.

[ses]

I think Prolog still has a place in modern software development. It provides a natural way of carrying out a backwards chaining depth first search through a state space (good for game AI, planning and scheduling etc). Also constraint solving is a very useful feature built into most logic programming languages now.

Prolog pureists argue that the whole of Prolog can be used for applications, but I tend to take a different approach that integration of Prolog with other languages can help you to do the things its really good and you can get the best out of multiple languages.

That's why I developed a (now open source) platform for integrating Prolog with other applications via web services... see http://kms.intelligent-architectures.co.uk/

[bulte-rs]

Same here, all University of Amsterdam CS students (informatics, AI and information sciences) took a compulsory course in Prolog.

Except I was lucky enough to have a use for it after uni (about two years ago), writing generators for various puzzle games. It's one of the tasks that has Prolog written all over it.

[microtonal]

Our (natural language) parser/generator is for the largest part written in Prolog (the rest is C/C++/Tcl):

http://www.let.rug.nl/vannoord/alp/Alpino/

Prolog matches very well with the grammar formalism that we use (attribute-value grammars), since attribute-value structures with arbitrary depth and re-entrancy can easily be represented as Prolog terms and larger analyses can be constructed through unification.

E.g. the grammar rules are plain Prolog rules where one argument argument is a list that represents the right hand side of a grammar rule, and another argument is the left-hand side. The rule goals define relations between the RHS and LHS by unifying parts of the RHS structures with the LHS structure. For instance, the rule for np -> det, n is this:

  grammar_rule(np_det_n, NP, [ Det, N ] ) :-
      np_det_n_struct(NP,Det,N).

Where np_det_n_struct unifies paths between NP <-> Det, NP <-> N, and unifies some paths with atoms. Completing a grammar rule is simply a matter of unifying members of the RHS list.

[alexholehouse]

I did a module in logic and prolog for a CS masters and agree it's very refreshing. I actually got a lot more out of it as a language in the context of predicate logic (which I started hating but by the end really enjoyed).

[andrewcooke]

so can you define something like

  transitive(X) :- [ X(A,C) :- X(A,B), X(B,C) ]

(which generalises the decendent example)? more generally, i guess i am asking whether those horn clause things are first class.

[JadeNB]

A different problem to the 'non-first-class-ness' of clauses that others have mentioned is that Prolog is really just a unification engine, not a reasoning engine. Thus, even a manual definition

    x(A, C) :- x(A, B), x(B, C).

is not always a good idea. For example, if you put this clause first (in the definition of `x`), it'll always try to reason by transitivity, rather than ever checking directly. The sub-clauses will then be checked by transitivity, &c. This is easy to fix by not putting this clause first; but then you run into further problems if `x` is reflexive; consider

    le(1, 1).
    le(A, C) :- le(A, B), le(B, C).

Now

    ?- le(1, 0).

will unify with `le(A, C)` by `A = 1`, `C = 0`, and then search for `B` such that `le(A, B)`. It'll put `B = 1`, and then try to solve `le(B, C)`, i.e., just `le(1, 0)` --and you're at the first stage of an infinite loop.

[_delirium]

Unfortunately, no. The names of predicates---functors in Prolog-speak---have to be symbols, not variables, and Horn clauses themselves aren't first-class either.

You can do it via metaprogramming; a functor can be converted to a list [name, param1, param2, ...], and then you can write normal Prolog operations on the list that bind variables and such, and then convert back. This page shows how to use that to build a higher-order map function: http://en.wikibooks.org/wiki/Prolog/Higher_Order_Programming

Here's a paper on other approaches; I'm not sure if any of the higher-order Prolog approaches ever caught on, though: http://www.cs.umbc.edu/courses/771/papers/mu_96_02.pdf

[sp332]

Nope, in vanilla Prolog you'd have to type "X(A,C) :- X(A,B), X(B,C)." for every single X you want to be transitive.

In formal logic, "A if B" is just syntactic sugar for "(B && A) || (!B)" or in English: when B is true, A is true. (But when B is false, A could be either true or false.) So you could rewrite your expression as (edit: fixed):

  transitive(X, A, B, C) :- (X(A,B), X(B,C), X(A,C)); not(X(A,B), X(B,C)).

[route66]

The problem is that transitive builds up a relationship between a functor and it's variables by trying to unify them with already known facts. But no new fact is generated.

     transitive(Functor) :-
       Rel1 =.. [Functor,A,B],
       Rel2 =.. [Functor,B,C],
       Rel3 =.. [Functor,A,C],
       call(Rel1),call(Rel2),call(Rel3).
 
     descendant(a,b).  #fact1
     descendant(b,c).  #fact2
     transitive(descendant) ;; says 'no'
     descendant(a,c).
     transitive(descendant) ;; says 'yes'

This functor only tells us if the database has a transitive relationship recorded.

If one wants the truth to be derived from the first two facts one would have to say

     transitive(F,A,B,C) :-
       R1 =.. [F,A,B],
       R2 =.. [F,B,C],
       call(R1),call(R2).

which derives transitivity from the first two facts, the last relationship (R3) is what we want to conclude, not what we want to find in the database.

Neither call though, will derive from fact1 and fact2 that "descendant(a,c)." is true. To arrive there you would have to "assert" these (new) facts explicitly in the transitive(...) definition.

But Prolog is not my comfort zone, there might be (and probably is) a way out of that dilemma.

[arethuza]

As far as I recall you can add new facts easily enough using asserta or assertz but I'm pretty sure this approach doesn't work for rules.

[cHalgan]

The reason why prolog is important to learn and play with it is to understand and learn concept of declarative programming as programming paradigm.

That is very important skill when designing system because you learn how to define what the system should accomplish, rather than describing how to go about accomplishing it.

[ranman]

This is a great follow up article as well: http://www.amzi.com/AdventureInProlog/

Create a text adventure game in Prolog. A great class project. See if you can get them to add networking to it and you can make a MUD!

[metaobject]

Ok, let's get it out of the way right now: no.