Logic programming, Prolog and P#

Yesterday I passed the exam in Logic Programming: a very interesting declarative programming style based on the foundations of mathematical logic.

Take this as a short, very vague, introduction: logic programming works by defining some logic clauses in your program and then applying a resolution algorithm on a particular query (the logical clause you are trying to "prove" according to logic inference rules). The logic interpret will then determine whether your query is a logical consequence of the program or not, i. e. the query is satisfied and a valid result was found.

The input statements (the code of your program) that are allowed in such interprets are limited to Horn clauses. A Horn clause is essentially a simple logic disjointed clause with only one positive term and any number of negative terms.

¬a ∨ ¬b ∨ ¬c ∨ pos

Which can be rewritten using the "consequence" operator (→) applied to the positive literal and the conjunction of all negative literals:

(a ∧ b ∧ c) → pos

Meaning that, in order for the clause to be true, each term must be true or the (a ∧ b ∧ c) part must be false. In logic programming, such clauses are usually expressed reverting the consequence order:

siblings(X, Y) ← mother(Z, X) ∧ mother(Z, Y)

This clause means that in order to prove that X and Y are siblings, you must first verify that they "share" the same mother Z. In Prolog such statement would be expressed as follows:

mother(serena, lorenz).
mother(serena, lukas).
siblings(X, Y) :- mother(Z, X), mother(Z, Y).

The first two statements are facts and are automatically true. The Prolog interpret can now prove that my brother and I are siblings. By issuing the query:

siblings(lukas, lorenz).

you will get the answer "yes". This is nice, but the really great thing about Prolog is that (in most cases) all statements are reversable and can be queried "in reverse" and the interpret will equally try to find a logic resolution for your query in the program. For instance:

siblings(lorenz, X).

yields the response "X = lukas", while

siblings(X, Y).

returns "X = lukas, Y = lukas". Therefore the interpret just proved that Lukas is his own brother (which is quite correct, given that simple program). This can of course be extended to anything, like the classical list concatenation, which looks very similar to any functional programming language (mind that the '%' character at the start of a line turns the whole line in a comment):

% append(A, B, RESULT)
append([], REST, REST).
append([HEAD | TAIL], LIST_B, [HEAD | REST]) :- append(TAIL, LIST_B, REST).

This couple of statements can be read in an "operational way" (like in Ocaml, for instance): the "append" function has three operands, two input lists and an output list. At each step we take the head of the first input list and push it to the result list, while the rest of the list is built recursively until the first list is empty. At this point, the rest of the result list is simply given by the second list parameter.

This works, but it is very reductive of how Prolog operates. A correct reading of the "append" statement would be "the RESULT parameter is the list given by appending the list B to A". If you see it like that, it's really easy to use the same exact statement in reverse:

append([1, 2, 3], [4, 5, 6], RESULT).
RESULT = [1,2,3,4,5,6]

append(A, [4, 5, 6], [1, 2, 3, 4, 5, 6]).
A = [1,2,3]

append(A, B, [1, 2, 3, 4, 5, 6]).
A = [],
B = [1,2,3,4,5,6]
...

Of course these are just some very basic examples. As mentioned in the logic programming book I used for the exam, Prolog can be adapted for many kinds of applications. In particular to artificial intelligence applications that need to determine the actions of intelligent "agents" by enforcing a declarative list of behaviors and rules. It would be really interesting to try to use Prolog as scripting language in a game: fortunately P#, a Prolog interpret written in C# that runs on .NET, is already available...