Telecom Paris Dep. Informatique & Réseaux Nils Holzenberger ← Home page November 2024

Neuro-Symbolic Artificial Intelligence

with

Simon Coumes

and

Zacchary Sadeddine

➜            other AI courses

The Prolog programming language was designed to simulate human reasoning, or at least the logical part of it. First attempts, in the 1950’s, for instance the Logic Theorist, proved disappointing. The machine could prove many correct results, but virtually all of them were devoid of interest. One would rather have asked the machine: ‘Is this statement true?’ in the hope of getting an answer in reasonable time. This time constraint remained unrealistic for long. The problem was not how to perform blind forward deduction from the axioms, as the Logic Theorist did. The problem was to go backwards in a clever way, starting from the question asked and arriving at the base axioms. Computer scientists succeeded in designing a theoretical backward search method with Robinson’s resolution algorithm (1965). Prolog is built on this algorithm.

Two French computer scientists working in Marseille, Alain Colmerauer and Philippe Roussel implemented Prolog for the first time in the 1970s. This new language offered the possibility of expressing knowledge in a declarative form that was close to the way logical formulas are written. The machine could use this knowledge to solve problems. They gave Prolog its name (ProLog = "Programmation en Logique").

Since that time, the language knew various developments. One of them is the creation of Prolog versions that can deal with numerical constraints (they are beyond the scope of this course - Have a look at this freely available book by Antoni Niederlinski if interested). Thanks to its unique properties, Prolog is used in combination with other programming languages in many AI projects. One (fairly) recent example is given by IBM Watson’s use of Prolog to process natural language.

A subset of Prolog, Datalog, is commonly used in database querying and information extraction. Its Python implementation achieves a good integration of logic programming into Python.

Various Prolog interpreters are available, such as Sicstus Prolog, Eclipse Prolog, SWI-Prolog. We will use the latter. It can be freely downloaded for various plateforms. SWI-Prolog is available on most machines at Telecom ParisTech. You may install it on your own machine (light installation).

To use Prolog:

• Create a file such as myfile.pl (with extension .pl).
• Run the SWI-Prolog interpreter by clicking on the file or else through the appropriate command (usually swipl, sometimes pl). In that case, load the file by typing [myfile]. (don’t forget the trailing dot). If your file name starts with a capital letter, you have to put the name within single quotes: ['Myfile'].
• Reload the file each time you modify it in your favourite editor.
• To exit, type: halt. or Ctrl-D.
• Help on commands can be obtained through the command help. or help(pred/arity). where pred is the predicate for which you need help and arity is the number of its arguments. An online reference manual is available on the SWI-Prolog Website. You will find a list of predefined predicates there or else there.

Introduction to Prolog (by Ken Been)
Adventure in Prolog (by Amzi)

In Prolog, the expression (constants like pam or bob are called atoms):

parent(pam, bob).

may mean that pam is one of bob’s parents (father or mother). This meaning, however, only exists in the programr’s mind for now. The expression parent(pam,bob) will progressively acquire some of the properties of the concept ‘parent’.

We just saw how to express knowledge in ProLog, but not yet how to write a genuine program. Let’s write a rule:

child(X,Y) :- parent(Y,X).

This rule is meant to express the fact that X is Y’s child if Y is one of the two parents of X. X and Y are not atoms, but variables (as all arguments starting with an upper case letter), and parent and child are predicates. The piece of knowledge that we just expressed relies very much on convention. After all, the two predicates are nothing more than meaningless labels for the machine. Indeed, but let’s consider the following program.

Let’s consider the genealogy of the Simpson family.

parent(marge, lisa).
parent(marge, bart).
parent(marge, maggie).
parent(homer, lisa).
parent(homer, bart).
parent(homer, maggie).
parent(abraham, homer).
parent(abraham, herb).
parent(mona, homer).
parent(jackie, marge).
parent(clancy, marge).
parent(jackie, patty).
parent(clancy, patty).
parent(jackie, selma).
parent(clancy, selma).
parent(selma, ling).

female(mona).
female(jackie).
female(marge).
female(ann).
female(patty).
female(selma).
female(ling).
female(lisa).
female(maggie).
male(abraham).
male(herb).
male(homer).
male(bart).
male(clancy).

child(X,Y) :-
    parent(Y,X).

mother(X,Y) :-
    parent(X,Y),
    female(X).

grandparent(X,Y) :-
    parent(X,Z), % note that the a variable's scope is the clause
    parent(Z,Y). % variable Z keeps its value within the clause

sister(X,Y) :-
    parent(Z,X), % if X gets instantiated, Z gets instantiated as well
    parent(Z,Y),
    female(X),
    X \== Y. % can also be noted: not(X = Y).

ancestor(X,Y) :-
    parent(X,Y).
ancestor(X,Y) :-
    parent(X,Z),
    ancestor(Z,Y). % recursive call

The meaning of this program is straightforward. The comma means ‘and’. The sign :- means ‘if’. The rules in this program are called clauses. Note that the definition of ancestor is recursive. Predicates are still mere labels, but they are linked by various constraints that we attribute to the corresponding concepts. For instance, when a person X is a woman and shares a common parent with anoter person Y, we consider that X is Y’s sister. This is exactly what is expressed in the clause that defines the sister predicate.

Prolog offers a natural way of expressing knowledge. Let’s see how this knowledge can be turned into a program.

You may copy the above clauses into a file with extension .pl, for instance family.pl, and run the following tests by yourself. A Prolog interpreter is a program that reads a knowledge base like the one we just expressed and that can answer questions like the following ones.

> swipl
Welcome to SWI-Prolog
?- [family].
% family compiled 0.00 sec, 108 bytes
?- sister(ann, pat).
    YES
?- sister(bob, liz).
    NO
?- ancestor(pam, jim).
    YES
?- grandparent(X, pat).
    X = pam ;
    X = tom

(in the last example, you should type the semicolon ‘;’ yourself to get a further answer).

To answer this way to questions, the interpreter attempts to match (to "unify") the question with the ‘head’ of a clause. In a clause like A :- B,C., the predicate A constitutes the head and B,C constitutes the queue of the clause. As soon as the interpreter succeeds in unifying the question with the head of the clause it is currently considering, it turns its attention to the predicates present in the queue of the clause, in the order in which they appear, as if they were questions. If it is successful or if the queue is empty (the clause is just a fact like parent(pam,bob).), then the interpreter stops with ‘Success’ and returns True. Otherwise, it stops with a failure and returns False. If successful, the interpreter keeps the values that it assigned to variables when performing unification (for instance X=pam). In case of failure, the interpreter doesn’t give up. It goes back to its last choice point, when several clauses with the same head predicate were available, to try the next clause.

For instance, when unifying ancestor(pam, jim) with the head of a clause, two possibilities are available since two clauses have ancestor(X,Y) as head. If the first clause leads to failure, the interpreter returns to the state in which it was when opting for the first clause (in particular, it forgets all instantiations (assignations of values to variables) that it may have performed since). Then it unifies the question with the second clause ancestor(X,Y):- .... Thanks to this step backwards, or backtracking, the interpreter can explore all possibilities. In case of success, the interpreter provides the first solution it found. You can force it to backtrack, as if it had failed, to find out further solutions if there are any. This is the role of the semicolon ‘;’ typed by the user.

Prolog achieves a good compromise between expression power, which is close to what can we can do with Logic, and efficiency in resolving questions. But any compromise is obtained by abandoning "good" properties. For instance, the Prolog is more limited than Logic in its expression power and it is less efficient than classical programming languages (these negative aspects may prove unacceptable or on the contrary inconsequential, depending on the context). Prolog uses Horn clauses, i.e. clauses that have one single predicate in their head^[Note_1], all predicates in the clause (in the head or in the queue of the clause) being positive.^[Note_2] For instance, the clause :

grandparent(X,Y) :- parent(X,Z), parent(Z,Y).        (1)

expresses the following logical knowledge:

(parent(X,Z) ∧ parent(Z,Y)) ⊃ grandparent(X,Y)    (2)

(∧ means "and"; ⊃ designates the implication). But the clause does not fully express this piece of knowledge. The same knowledge can be expressed in the following way^[Note_3]:

(parent(X,Z) ∧ ¬grandparent(X,Y)) ⊃ ¬parent(Z,Y)    (3)

(¬ designates the negation). Prolog clause (1) does not express knowledge (3). In other words, clause (1) cannot be used by the Prolog interpreter to deduce that Z is not one of the two parents of Y, contrary to what logical mechanisms allow to do using (2). Prolog’s expression power is great, but not as great as what Logic can do.

Prolog represents a great leap forward to the ideal situation in which programming would consist in providing knowledge declaratively to the computer. Instead of writing down series of imperative instructions that the machine will execute in order, we can formulate the problem as pieces of knowledge. Then the machine may produce new knowledge by itself and may answer questions by instantiating variables. Prolog’s declarativity is not absolute, though, if one compares it with Logic. Ideal declarativity presupposes that the knowledge given to Prolog depend neither on the order of clauses nor on the order of predicates within each clause. Prolog achieves a good compromise between expressivity and calculability, at the cost of a few limitations. The first one is the use of Horn clauses, as we saw. Another limitation is due to the presence of est procedural aspects that move us somewhat away from declarativity: the order in which clauses are written may sometimes prove important. To see this, let’s consider a new version of the clause ancestor(X,Y):

ancestor(X,Y) :-
    ancestor(Z,Y),
    parent(X,Z).
ancestor(X,Y) :-
    parent(X,Y).

From a declarative perspective, the knowledge given to the program is the same. Yet, the Prolog interpreter is now unable to answer the question:

?- ancestor(tom,ann).

It enters an endless loop that rapidly fills up the amount of memory allocated to the program (try it).

Prolog programrs easily avoid this kind of trap. The main technique consists in writing the most specific pieces of knowledge first. Otherwise, always attempt to keep declarativity whenever possible. The program correctness is much easier to check when the order of clauses and the order of predicates whithin the clauses have no influence.

Suppose you want a clause descendant(X,Y) expressing the fact that X is a descendant of Y. No need to write it! Just use the clause ancestor(Y,X). With an imperative language such as Java, you would have to rewrite the function entirely. Let’s consider another, more spectacular, example, of Prolog’s reversibility. The following program removes an element from a list. Lists are noted within square brackets.

extract(X, [X|L], L).
extract(X, [Y|L], [Y|L1]) :-
    extract(X, L, L1).

The program can be paraphrased this way:

• If X is at the top of the list (the notation: [X|L] means that the list is formed by X and the elements of L), then the result is just the queue L of the list. Pay attention to the fact that X is an element, whereas L is a list (this is a trap for beginners).
• If X is found in the queue L of the list [Y|L] (this is what the last line says), then remove X from L (this gives L1) and copy the head element Y into the result.

This program is ready to function:

?- extract(3, [3], []).
    YES
?- extract(2, [1,2,3,2,1], L).
    L=[1,3,2,1] ;
    L=[1,2,3,1]
?- extract(X,[1,2,3,4,5],[1,2,4,5]).
    X=3

We can do much more with the same program. We can use it to successively extract all elements from the list:

?- extract(X,[1,2,3,4,5], L).
    X=1, L=[2,3,4,5] ;
    X=2, L=[1,3,4,5] ;
    X=3, L=[1,2,4,5] ;
    X=4, L=[1,2,3,5] ;
    X=5, L=[1,2,3,4]

This program was designed to extract an element from a list. Yet, the same program can perform the converse operation. If the resulting list is instantiated first, the program is able to instantiate the initial list so that the result be correct:

?- extract(3, L, [1,2,4,5]).
L=[3,1,2,4,5] ;
L=[1,3,2,4,5] ;
L=[1,2,3,4,5] ;
L=[1,2,4,3,5] ;
L=[1,2,4,5,3]

We can see that the program achieves an operation which is the converse of what it has been conceived for in the first place. It inserts an element into a list. Prolog programs may have this surprising property of being reversible. Procedural languages lack this property.^[Note_4] With this new behaviour, extract() can be used to define the predicate permute() that finds out all permutations of a list:

permute([], []).
permute([First|Rest], PermutedList) :-
    permute(Rest, PermutedRest),
    extract(First, PermutedList, PermutedRest).

This predicate functions as expected:

?- permute([1,2,3], L).
    L=[1,2,3]
    L=[2,1,3]
    L=[2,3,1]
    L=[1,3,2]
    L=[3,1,2]
    L=[3,2,1]

Reversibility has limits. The call permute(L, [1,2,3]). will return correct results, but will then bring the computer into infinite recursion. The call permute(Rest, PermutedRest) will unify two uninstantiated lists of arbitrary long size. PermutedRest will never be able to match a sub-list of [1,2,3] any more as soon as its size exceeds 2.

Note that a list written as [X|L] has at least one element. We have: [X] = [X|[]].

Prolog relies in part on the unification mechanism. Unification is used to match a question with the head of a clause. The mechanism is quite intuitive. Here is an example (technical aspects of unification will be addressed later). The two following predicates can be unified, which can be shown using the unification operator "=":

?- p(X, b(Z,a), X) = p(Y, Y, b(V,a)).
X = b(V, a),
Z = V,
Y = b(V, a).

(verify using your Prolog interpreter). The result of unification consists in the double instantiation X=Y=b(V,a) and in the constraint Z=V. After unification, the two versions of the predicate p() read similarly:
(p(b(V,a),b(V,a),b(V,a))). During unification, the ‘_’ character is a wild card that unifies to anything. Executing
(p(X,_) = p(Y,b(V,a)).) merely yields X = Y.

Prolog offers a variety of arithmetical and logical operators.

• arithmetical operators : +, -, *, /, div (ou //), mod
  These operators are in fact functors from Prolog’s perspective (3+2 can be written +(3,2)), but these functors have the particular property that they can be evaluated.
• affectation : X is 6 - 2 .
  The variable X takes the value 4. The right-hand term should be fully instantiated at the time of the call. The predicate is triggers the evaluation of -(6,2).
• Arithmetical comparison : <, >, >=, =<, =:=, =\= . Terms in these comparisons must be instantiated at the time of the call. They are evaluated, and then their values are compared.
• Comparison of terms :    X = Y succeeds if X unifies with Y.
          X == Y succeeds if X and Y are syntactically identical.
          X \== Y succeeds if X and Y have different syntactic structures.

Comparison operators are predicates. For instance, 6 > 4+1 can be written >(6,4+1), or >(6,+(4,1)). The resolution mechanism in Prolog consists in exploring a tree "depth-first". Each predicate under evaluation creates a new node in this tree; the branches growing from that node correspond to matching possibilities between the predicate and the head of available clauses.

It is sometimes necessary to control Prolog’s behaviour when exploring the resolution tree. For instance, when a branch is being explored, one may wish to prevent Prolog from considering alternative paths branching from the same node. To do so, we use the cut operator, ), expressed with an exclamation mark "!". Let’s see this with an example. The following predicate adds an element on top of a list while making sure that the element is not already present.

add(X, L, L) :-
    member(X, L),
    !. % nothing to do, and don't visit next clause
add(X, L, [X|L]).

If the value of X by the time of the call can be found in the list, one should not call the second clause. Each time the cut is executed, all alternatives one went through since entering into the predicate (here add) get forgotten. For instance, if the cut is executed in the above example, the presence of the second clause add(X,L,[X|L]) is merely ignored, as well as alternatives that may exist in the execution of member. If the program fails during further execution, add will propagate the failure up to the calling clause, without trying its own alternatives. However, if the failure occurs before executing the cut, backtracking proceeds normally. Here, if member fails, the second clause add(X,L,[X|L]) is executed. We can say metaphorically that backtracking can never cross a cut when moving backwards; it generates a definitive failure for the predicate in which it appears. This failure is propagated up to the calling predicate.

Negation, in Prolog, can be seen as a predicate that acts upon other predicates.
not(p) succeeds if the call to p fails, and fails otherwise. This is called ‘negation as failure’. The same effect can be achieved by associating a cut with the predefinite predicate fail which has the beautiful property of always failing.

q(X,Y) :-
    p(X,Y),
    !,
    fail.
q(X,Y).

q(X,Y) behaves exactly as not(p(X,Y)).

To link negation as failure to logical negation, one has to assume the "closed world hypothesis", which means that everything that can’t be proven is false. This hypothesis is reasonable only if on is certain of having provided all relevant knowledge items to the program for the problem at hand.

Caveat: arithmetical evaluations, negation and the cut move the program away from declarativity by giving to the programer the power of controlling the execution of the program. They should be avoided whenever they are not necessary. The following example can be meditated in this context.

% adapted from I. Bratko - "Prolog - Programming for Artificial Intelligence" Addison Wesley 1990
reasonable(Restaurant) :-
    not(expensive(Restaurant)).
fancy(belle_d_argent).
fancy(maximus).
expensive(belle_d_argent).

?- fancy(X), reasonable(X).
    X=maximus
?- reasonable(X), fancy(X).
    NO

In the second case and contrary to the first one, X is not instantiated when reasonable(X) is called. Prolog executes expensive(Restaurant), succeeds with Restaurant= belle_d_argent, and concludes that not(expensive(Restaurant)) is false. It does not go any further and the question fails.

Some errors are typically made by beginners. When writing [X|L], one supposes that L is a list that represents the queue of the global list. For instance, [a,b] = [a|[b]]. It is possible to write [a,b|L], where L is (or will be) a list.      [a,b|[c,d,e] unifies with [a,b,c,d,e]. However, writing [L|a] does not generate a list, and it cannot be unified with a list like [x,y,z]. a is a constant, an atom, which cannot unify with a list. Don’t attempt to reach the last element of a list by writing L = [StartList|LastElement].

As training exercise (easy):

• Baral, C. (2003). Knowledge representation, reasoning and declarative problem solving. Cambridge, MA: Cambridge university press.
• Bellot, P. (1994). Objectif Prolog. Paris: Masson.
• Blackburn, P., Bos, J. & Striegnitz, K. (2006). Learn prolog now! Londres: College Publications.
• Bratko, I. (1990). PROLOG - Programming for Artificial Intelligence. Addison-Wesley.
• Clocksin, W. F. & Mellish, C. S. (1981). Programming in Prolog. Berlin: Springer Verlag.
• Harrison, J. (2009). Handbook of practical logic and automated reasoning. Cambridge, MA: Cambridge University Press.
• Niederlinski, A. (2014). A Gentle Guide to Constraint Logic Programming via ECLiPSe. Gliwice, PL: Jacek Skalmierski Computer Studio.
• Scott, P. & Nicolson, R. (1991). Cognitive Science Projects in Prolog. Hove: Lawrence Erlbaum Assoc.
• Tau Prolog: A Prolog interpreter in JavaScript

• Fisher, J. R. (2010). prolog :- tutorial.

[Note_1] Headless Horn clauses can be written:    
:- A,B.
Goals A and B will be automatically executed when the program is launched.

[Note_2] Negation is not really part of the language. not is itself a Prolog program and it does not exactly correspond to logical negation, as shown later.

[Note_3] If X is one of the two parents of Z and X is not one of Y’s grandparents, then Z is not one of the two parents of Y.

[Note_4] Some operations, like Prolog’s standard arithmetical operations, are not reversible. The use of the "cut" (see after), by limiting declarativity, limits reversibility as well.

            

Back to the main page