Prolog


Prolog is a language of logic programming . The name Prolog is an acronym for Programming in LOGIC. It was created by Alain Colmerauer and Philippe Roussel around 1972 . The goal was to create a programming language where the expected logical rules of a solution would be defined and let the compiler transform it into a sequence of instructions. One of the expected gains was increased ease of application maintenance, the addition or deletion of rules over time not requiring re-examination of all others.

Prolog is used in artificial intelligence and in the treatment linguistic computer (mainly natural languages ). Its rules of syntax and its semantics are simple and considered as clear (one of the objectives was to provide a tool for linguists who are ignorant of computing). Initial results with Prolog resulted in some research in the 1980s on a fifth generation of computers (known as Fifth Generation Japan due to MITI ‘s strong commitment to the project). The effort involved was significant, the spin-offs more modest,

Prolog is based on the computation of the first order predicates ; However, it is restricted in its initial version to accept only the Horn clauses (modern versions of Prolog accept more complex predicates, especially with the treatment of negation by failure ). The execution of a Prolog program is indeed an application of the theorem proving by resolution of the first order. The basic concepts are the unification , the recursion and backtracking . The Prolog resolution algorithm is based on an extension of the SLD-resolution .

Prolog can build a knowledge base in an indeterminate order, since only the relations in the presence and not their writing sequence count. Prolog can then solve a series of logical problems related to such a knowledge base (notion deductive database), a problem similar to the search for an issue (or several) in a labyrinth of established constraints.

Types of terms

Prolog does not use data typing in the usual sense of programming languages . Indeed, it makes no real distinction between the data of the program and the program itself (the principle of declarative programming ). Its lexical elements, termed terms , encompass the following types.

Atomes

Constant texts constitute atoms . An atom usually consists of a string of letters, numbers, and _underscores ( ), beginning with a lowercase letter . To introduce a non-alphanumeric atom, it is surrounded by apostrophes: thus ‘+’ is an atom, + an operator).

Numbers

Common implementations of Prolog typically do not differentiate integers from floats.

Variables

Variables are indicated by using a set of letters, numbers, and underscores beginning with an uppercase letter .

Thus, X3 as Unit_Price are variable name names.

Prolog is not an imperative programming language ; A variable is therefore not a container to which a value is assigned, but represents (as in mathematics in X> 0 ) the set of admissible values ​​for it under the constraints.

The initially indefinite field of the variable is defined by the unification around the constraints. Once the variable is unified, its value can no longer be modified within the same evaluation branch. The backtracking , however, allows to return to this unification in the context of the continuing research of allowable values (or new allowable values), as part of a comprehensive exploration.

The anonymous variable is written with a dash (_). Any variable whose name begins with a dash is also an anonymous variable. It is, like the x or the y of the algebra, a dummy variable serving as intermediary of calculation.

Compound terms

Prolog can represent complex data only in compound terms . A compound term consists of a head (also called a functor ), which must be an atom, and unrestricted parameters. The number of parameters, named arity of the term, is significant. A compound term is identified by its head and its arity, and usually written as a functor / arity.

Examples of compound terms:

  • Likes (romeo, juliette)
The functor is loved and the arity 2, the compound term is written aime/2.
  • F (g (X), h (Y))
The functor is f and the arity 2, the compound term is written f/2.
  • Initialization
The functor is initialization and the arity 0, the compound term is written initialisation/0. An atom is therefore a term composed of arity 0.

Lists

A list is not an isolated data type but is defined by a recursive construct (using the .arity functor 2, so it is at the level of the internal representation a compound term):

  1. The atom [] is an empty list;
  2. If T is a list and H is an element, then the term ‘.’ ( H , T ) is a list.

The first element, called the head, is H , followed by the contents of the rest of the list, indicated as T or tail. The list [1, 2, 3] would be internally represented as ‘.’ ( 1 , ‘.’ ( 2 , ‘.’ ( 3 , []))) A syntax shortcut is [ H | T ], which is mainly used to construct rules. The whole of a list can be treated by acting on the first element, and then on the rest of the list, by recursion , as in LISP .

For the convenience of the programmer, the lists can be constructed and deconstructed in various ways.

  • Enumeration of elements: [abc, 1, f (x), Y , g ( A , rst)]
  • Extraction of the head element: [abc | L1 ]
  • Extraction of several head elements: [abc, 1, f (x) | L2 ]
  • Expansion of the term ‘.’ (ABC, (1 (f (x), ( ‘.’. ‘.’ ” Y , (g ( ‘.’ A , rst), [])))))

Character strings

Strings are usually written as a sequence of characters surrounded by apostrophes. They are often represented internally by an ASCII code list.

Predicates

The programming in Prolog is very different from programming in an imperative language . In Prolog, we feed a knowledge base of facts and rules; It is then possible to make queries to the knowledge base.

The base unit of Prolog is the predicate , which is defined as being true. A predicate consists of a head and a number of arguments. For example :

Cat (tom).

Here ‘cat’ is the head, and ‘tom’ is the argument. Here are some simple queries you can ask a Prolog interpreter based on this fact:

- chat (tom).
 Yes.
- chat (X).
 X = tom;
 Fail.

In this second example, to the question ‘chat (X)’ the interpreter proposes the response ‘X = tom’ unifying the variable ‘X’ to the atom ‘tom’. In Prolog it is a success . After this first response, the user can ask if there are other answers using the “; (Symbol of the disjunction), here the interpreter answers that he does not find any. This search for other solutions is based on a model of non-deterministic execution (in the sense of the non-determinism of non-deterministic automata) with a return to the various points of choice and exploration of unexplored alternatives.

- chat (vim).
 Fail.

In this last example, to the question ‘chat (vim)’ the interpreter answers that it can not prove this fact, in Prolog it is a failure. By making the assumption that all the facts are known ( hypothesis of the closed world ), this means that ‘vim’ is not a cat.

Predicates are generally defined to express the facts that the program knows about the world. In most cases, the use of predicates requires a certain convention. For example, the semantics of the following two predicates is not immediate:

Father (marie, pierre).
Pere (stone, marie).

In both cases, ‘father’ is the head while ‘marie’ and ‘pierre’ are the arguments. However, in the first case, Mary comes first in the list of arguments, and in the second it is Pierre (the order in the list of arguments matters). The first case is an example of a definition in the verb-subject-subject order and could be read with the auxiliary ‘avoir’: Marie is for Pierre, and the second for verb-subject-object and could be read With the auxiliary ‘to be’: Peter is the father of Mary. Since Prolog does not understand natural language, both versions are correct as far as it is concerned; However, it is important to adopt coherent programming standards for the same program. In general, it is the auxiliary ‘being’ that is used.

It will be

Family (stone, marie, [arthur, bruno, charlotte]).

Means that pierre and marie are respectively the father and the mother of 3 children: arthur, bruno and charlotte; “Family” is then a 3-term predicate, the last being a list of any number (possibly zero) of children.

Predefined

Some predicates are built into the language and allow a Prolog program to perform routine activities (such as digital evaluation, input / output , GUI functionality and generally communicate with the computer system). For example, the write predicate can be used for on-screen display. So

Write ('Hello').

Will display the word ‘Bonjour’ on the monitor. Such predicates do not properly belong to logical programming, their functionality relying exclusively on their edge effects.

Other predicates built in language are logical in nature, and included in libraries . They serve to simplify the development by encapsulating generic treatments, such as lists processing algorithms, for example.

Finally, other predicates are of a higher order and are used to control the execution of Prolog interpreters (for example, dynamic addition / deletion of rules and facts, dropping selection points, harvesting query results). .)

NB – Without the predefined predicates, Prolog is sometimes called Pure Prolog (according to the iso standard in English : definite Prolog).

Rules

The second type of instructions in Prolog is the rule. An example of a rule is:

Light (on): - switch (on).

The “: -” means “if”; This rule indicates light (on) is true if switch (on) is true. Rules can also use variables such as:

Father (X, Y): parent (X, Y), male (X).

To signify that X is the father of a Y if X is a parent of Y and X is male, where “,” indicates a conjunction.

We could also have:

Parent (X, Y): father (X, Y); Mother (X, Y).

To signify that X is a parent of Y if X is the father of Y or X is the mother of Y, where “;” denotes an alternative.

A fact is a special case of rule. In fact, the following two lines are equivalent:

at.
A: - true.

Evaluation

When the interpreter receives a query, it searches for the rules (included facts) whose left part can be unified with the query, and performs this unification with the first rule found. For example, having this Prolog code:

(X, Y): parent (Z, X), parent (Z, Y), X \ = Y.
Parent (X, Y): father (X, Y).
Parent (X, Y): - mother (X, Y).
Mother (trude, sally).
Father (tom, sally).
Father (tom, erica).
(Mike, tom).

As a result, the following request is evaluated as true:

? - brother_or_sister (sally, erica).
 Yes.

The interpreter arrives at this result by matching the brother_or_sister (X, Y) rule by unifying X with sally and Y with erica . This means that the request can be extended to parent (Z, sally) , parent (Z, erica) . Matching this conjunction is obtained by looking at all possible parents of sally . However, parent (trude, sally) does not lead to a viable solution, because if trude is substituted for Z , parent (trude, erica) must be true, and no such fact (or some rule that can satisfy that) is present. Also in place,

Negation by failure

The pure logical negation does not exist in Prolog, we rely on the negation by the failure , which is noted differently according to the implementations of Prolog (we will adopt the notation by the key word not(prédicat)). In negation by failure, the negation of a predicate is considered true if the evaluation of the predicate leads to failure (can not be verified).

In Prolog, negation by failure is based on the hypothesis of the closed world: everything that is true is known or demonstrable from what is known in a finite time.

See example below:

Parent ( jorge , andres ).
Parent ( andres , Felipe ).
Grandparent ( X , Y ) : parent ( X , Z ), parent ( Z , Y ).
? Grandparent ( jorge , _ ).
% True
% there is enough information to say that jorge has a known grandparent.
% Hypothesis of the closed world → there is not enough information to reach a conclusion -> false
? Grandparent ( andres , _ ).
% False
% Negation by failure based on the hypothesis of the closed world
? Not ( grandparent ( andres , _ )).
% True

Execution

Prolog is a logical language, so in theory, one does not have to worry about how it runs. However, it is sometimes prudent to consider how the inference algorithm works, so that a Prolog program does not last too long.

For example, we can write code to count the number of items in a list.

Elems ([], 0).
Elems ([H | T], X): elems (T, Y), X is Y + 1.

This simply means:

  • If the list is empty, the number of elements is zero
  • If a list is not empty, then X is increased by one with respect to Y, the number of elements in the rest of the list (without the first element).

In this case, there is a clear distinction between cases in the antecedent in the rules. But consider the case where you need to decide if you continue playing in a casino;

Miser (X): - money (X).
Miser (X): - have credited (X), NOT have money (X).

If you have money, you keep betting. If you have lost everything you need to borrow, or else … more bet. Money (X) can be a very expensive function, for example, if it can access your bank account via the internet. But it is the same thing for having credited .

In theory, Prolog implementations can evaluate these rules in any order, so you might have written;

Miser (X): - have credited (X), NOT have money (X).
Miser (X): - money (X).

This is good, because the two options are mutually exclusive. However checking out if you can get a loan is not necessary if you know you have money. So in practice, Prolog implementations will first test the rule you wrote first . You can use the cut operator to tell the interpreter to skip the second option if the first option is sufficient. For example:

Miser (X): - money (X),!.
Miser (X): - have credited (X), NOT have money (X).

This is called a green shutdown operator . The ! Simply told the interpreter not to seek any alternative. But you notice that if you need money it needs to evaluate the second rule, and it will. Evaluate avoirargent in the second rule is pretty useless because you know you do not have, for good reason, otherwise, the second rule is not evaluated. Also you can change the code to:

Miser (X): - money (X),!.
Miser (X): - have credited (X).

This is called a red stop operator , because it is dangerous to do this. You are now dependent on the correct placement of the stop operator and the order of the rules to determine their logical sense. If the rules are mixed, you can now use your credit card before spending your money available.

You will write instead:

Miser (X): - have money (X),! ; Have credit (X).

Which reads: to bet X, or I have this money right away, or else I have the necessary credit.

Reversibility

In general, Prolog does not impose a status on the parameters of a predicate: they are not parameters ‘given’ or ‘results’, or even ‘given / results’, their status is indifferent a priori and will be defined in function Queries, and sometimes predefined ones used.

This often allows the definition of reversible predicates: closed queries, providing results from the data, can be inverted into open queries, looking for data leading to a positive result.

Age (captain, 45) is true or false; Age (captain, X) asks what is the age X of the captain, age (X, 45) asks what X is 45 years old.

This possibility is used in the generator / acceptor above.

Examples

Let us take binary trees with node f and as sheet 0 or 1.

 Symmetric (0,0).
 Symmetric (1,1).
 (A, B), f (Y, X)): - symmetric (A, X), symmetric (B, Y).

The standard use of this predicate is of the type:

 ? - symmetric (f (f (0,1), 1), R).
 R = f (1, f (1,0))

But we can also have:

 ? - symmetric (A, f (f (0,1), 1)).
 A = f (1, f (1,0))

Special features

As a programming language, Prolog distinguishes itself by:

  • The non-determinism, for the solving of open problems: the ‘or’ used in Prolog is a true ‘or’ logic that allows the exploration of all possible.
  • The reversibility (see above)
  • The management of the under-constrained / over-constrained queries: the absence of status for the parameters of a predicate (see reversibility) and the execution model used allows, on one side, Constraints exposing the set of possibilities and, on the other hand, the use of over-constrained queries allowing the verification of particular properties on the solutions exhibited or the filtering of these solutions.

Jobs

Aspect databases

From the outset, Prolog has approached the domain of relational databases , to which it provides a great deal of flexibility in terms of queries, since they are deductible from the facts: they thus become deductive databases . Thus, a basis of facts of the family style (Father, Mother, List of Children) can, by means of a few rules, answer various questions of genealogy.

Beyond that, Prolog can also propose a query system common to a set of interdependent data bases; By combining the available basic relations, one obtains the services of a virtual base combining these bases, resulting in a considerable enrichment of the possible queries.

Linguistic aspect

Language processing is possible in Prolog based on formal grammars .

  • A generator will generate sentences conforming to a grammar and a given lexicon, an acceptor will verify the conformity of a sentence;
  • An analyzer that has recognized a sentence (or text), will construct a “decorated tree” that will be its abstraction; For example, the nominal group the beautiful cat will become
Gn (le, beau, chat) or better
Gn (art (le), adj (beau), noun (chat)) , or even according to the objective
Gn (art (le, def, masc, sing), adj (beau, masc, sing), name (chat, masc, sing, animé)) .
  • Beyond that, a translator will assume the transformation of the tree abstraction-of-entry into an abstraction-of-output tree, which will drive the final text generator.
[display]

Examples

The linguistic applications of Prolog have been simplified and amplified by the use of DCGs ( Definite Clause Grammar  (en) ) (Pereira & Warren, 1980).

Prolog can be used for automatic or semi-automatic translation.

More frequently, a simple parser will allow the use of pseudo-natural queries for the querying of relational databases.

Combinatory Aspect

Prolog applications that are interesting a priori could have excessive execution times due to the underlying combinatorics. Prolog and logic programming gave rise to a programming current combining most of Prolog’s specificities and the contributions of Constraint Programming to Prolog IV (1996) to Constraint Logic Programming (PLC). Effective in combinatorial problems, particularly in CAD , operational research and games.

Indeed, one can for example impose that n variables sharing a domain with n values ​​are mutually exclusive, reducing the number of cases from n ^ n to n !. For example, for n = 10, from 10 billion to 3.6 million.

In 1980, the Japanese project 5 th generation  (in) had put great hopes in the parallelization of Prolog, which have faced the fact that Prolog is grammatical inspiration, its logical connectors are not commutative. However, the exploitation of the rules can accommodate a pipeline mode, interruptible if necessary. Either the rule:

MusicianGrec (X): - musician (X), Greek (X).

As soon as Prolog finds a musician, he can check if it is Greek, in which case it is a first answer. As a result, verification of the nationality of a musician can be done while the search of other musicians known to the system continues. This procedure is all the more effective in that research begins with the most selective predicate: this is the case if the system knows fewer musicians than Greeks.

Mathematical Aspect

Prolog allows reasoning by induction, and thus provides the ability to verify conjectures. Its ability to process trees that can represent formulas allows it to be used in formal calculation .

Intelligent Modules

Beyond purely Prolog applications, the ability to combine Prolog with traditional languages ​​has enabled the many applications of intelligent modules such as expert modules since the ‘ 85s . With comparable performance, these modules increase the flexibility and relevance of applications.

Evolutions

  • Prolog works within the framework of logic of order 1 and the good end of programs Prolog is guaranteed in a framework of monotonic logic, which supposes that there is not update of the knowledge base during a reasoning. However, reusable intermediate results can be stored using the assert () predicate, corresponding to an irreversible form of learning, for example in memoization .
Beyond that, the use of predicates retract () allows the modification of the knowledge base, required by the processing of dynamic systems, as well as some necessary unlearning, but Prolog then works in non- monotonic logic , losing the guarantee of good end.
These questions have led to a distinction between static, unmodifiable, and dynamic facts .
  • Extensions have been proposed, notably in the Prolog ISO, to promote constraint programming , reification allowing limited access to the order 2 .
  • PROLOG is also the support of extensions in the field of non-classical logic , and in particular of modal logic , with the MOLOG language developed by the team of Luis Fariñas Del Cerro at IRIT .

Implementations

  • Amzi! Prolog  [ archive ] , paying except version without server nor redistributables
  • B-Prolog  [ archive ] , except Academic license
  • Borland Turbo Prolog 1 , implementation for MS-DOS marketed in 1987, subsequently taken over by a Danish company under the name Visual Prolog
  • Ciao Prolog  [ archive ] , free (GPL)
  • GNU Prolog  [ archive ] , developed by the Paris-1 Panthéon-Sorbonne University , free (GPL and LGPL)
  • Open Prolog  [ archive ] , free (postcardware), for Mac
  • Prolog.NET  [ archive ] , developed at the Oregon Institute of Technology  (en) , free, arrested in 2006 for .NET 2.0
  • Qu-Prolog  [ archive ] , a multithreaded prolog developed by the University of Queensland , free, Unix and Linux only
  • Quintus Prolog  [ archive ] , developed by the Swedish Institute of Computer Science  (sv) , multiplatform,
  • Rebol Prolog  [ archive ] , implementation in Rebol, to be interpreted in Rebol
  • SICStus Prolog  [ archive ] , developed by the Swedish Institute of Computer Science , paying
  • Strawberry Prolog  [ archive ] , free light version
  • SWI Prolog  [ archive ] , developed by the University of Amsterdam , free (GPL) 2 .
  • TuProlog  [ archive ] , free, two versions, Java or .NET
  • Visual Prolog  [ archive ] , Free Personal Edition
  • Http://xsb.sourceforge.net/ XSB  [ archive ] , free, based on InterProlog like SWI and Yap
  • YAP Prolog  [ archive ] , developed by the University of Porto , free, multiplatform, fast
  • Squeak Prolog  [ archive ] A Prolog integrated with Smalltalk in the Squeak environment , resulting from Prolog integrated in Smalltalk / V. Syntax nonstandard but allows to mix programming imperative object (Smalltalk) and logic (Prolog). Smalltalk can ask questions to Prolog and Prolog can execute Smalltalk orders. Free.
  • Prolog II (1982) III & IV (1996)  [ archive ] , freeware, PC and DOS or Windows, Prologs of Alain Colmerauer and his team of Marseille
  • Jekejeke Prolog  [ archive ] , version and free debugger, 100% Java, also for Android

Bibliography

  • F. Giannesini, H. Kanoui, R. Pasero, M. Van Caneghem, Prolog , Interéditions, 1985: definition of the Prolog “de Marseille”, with a preface by A. Colmerauer
  • WF Clocksin, CS Mellish, CS, Programming in Prolog . Springer-Verlag 1981. ( ISBN 3-540-11046-1 ): definition of the “Edinburgh Prolog”; Several reissues.
  • Jean-Paul Delahaye , Prolog Course with Turbo Prolog , Eyrolles, 1988 – id: 9782212081916.
  • Jacky Legrand, The Prolog Language – Examples in Turbo Prolog , Technip, 1992 – ( ISBN  2-7108-0627-4 ) .
  • Patrick Blackburn, Johan Bos, Kristina Streignitz, PROLOG right away , College Publications, August 7, 2007.
  • L. Sterling, E. Shapiro, The Art of Prolog , Masson, 1990: Translated from English by M. Eytan.
  • H. Coelho, JC Cotta, LM Pereira, How to solve it with PROLOG , National Laboratory of Engenharia Civil (Portugal), 1985.

Notes and references

  1. ↑ ( en ) Turbo Prolog manuals  [ archive ] .
  2. ↑ ( in ) Manual SWI-Prolog  [ archive ] .