Logical programming

This course uses the logic programming language named Prolog.

Logic programming consists of the declaration of a series of facts and rules of deduction. The execution of a program consists in proving a theorem. The program responds whether the theorem can be proved or not from the statements made beforehand.

The logic programming is different from the procedural programming (C, JAVA, etc), the calculations are in the form of logical proofs. We talk about declarative programming: the program describes a situation corresponding to a problem to be solved. Declarative programming is not incompatible with object.

The formulas expressed in Prolog are restricted to Horn clauses and first order logic. A Horn clause is a clause with at most one positive literal.

Rules, facts and goals

If the Horn clause has a positive literal and at least a negative literal, these are rules:
for any x,y,z, ¬child(x,y) ∨ ¬child(y,z) ∨ grand_child(x,z) ce qui équivaut à
child(x,y) ∧ child(y,z) ⇒ grand_child(x,z)

Prolog : grand_child_OF(X,Z) :- child_OF(X,Y), child_OF(Y,Z)

You can write Horn clauses without negative literal (positive Horn clauses), but with only one positive literal. These are facts: child_OF(‘Bernard’,’Bernadette’).
You can write Horn clauses without positive literal (negative Horn clauses), but with only negative literals. These are goals: ?-petit_enfant_de(B,’germaine’), neveu(X,Y).

A program is therefore a set of facts and rules, all in the form of Horn clauses. The Prolog interpreter uses this knowledge base to serve goals.

Prolog

The syntax consists of:

  • Constants: integers or floats, Booleans, identifiers and strings.
  • Variables: identified by strings starting with a capital letter or an underscore (if indefinite, i.e. has no interest for the user). Variable is in the mathematical sense, it always represents the same object and does not change value in the same demo branch.
  • Predicate: identified by strings starting with a lowercase. A predicate has an arity (the number of arguments it requires). Parameters are separated by a comma, equivalent to AND; OR is a semicolon.

Rules and facts:

  • a fact is a predicate with constants as parameters: parent (‘Bernard’, ‘Bernardo’)
  • a rule consists of a head (positive literal) and a tail (conjunction of negative literals terminated by a point: nephew (X, Y): – son (X, Z), brother_or_sister(Y, Z).

Writing in Prolog

A program is a list of facts and rules. We group together the rules that have the same leading predicate and the facts that relate to the same predicate. The order of declaration of the rules can have an impact on the goals.

child_of('roger','gertrude').
child_of('gertrude','germaine').
child_of('marcel','robert').
brother_or_sister('gertrude','robert').
nephew(X,Y) :- child(X,Z), brother_or_sister(Y,Z).
grand_child_of(X,Y) :- child_of(X,Z), child_of(Z,Y).

A constant (‘roger’) covers the whole program while a variable exists only in the clause where it is. So the nephew variable X of nephew(X, Y) is not the same as that one of grand_child_of(X, Y). On the other hand, it is the same as in the conjunction that is associated with it.

Once the programs are loaded and thus the facts and rules base is established, it is possible to ask questions. This is called demonstration or question resolution. A question is asked by replacing, in a rule or fact, a constant or variable by a ‘?’. To know all the rules of a type one writes the name of the rule containing variables followed by a ‘?’ : human (H)? serves to know all the humans of the base.

 

Publicités