Prolog - SpeedyLook encyclopedia

Various types of terms

Prolog does not employ types of data according to the usual manner of the computer programming languages. This is mainly due to the fact that in Prolog, there is no real distinction between the data of the program and the program itself (principle of the declaratory Programmation). We must on this subject speak about the lexical elements, called terms, and which include the following types.

Atoms

The boilerplates are input in the form of atoms. An atom is a sequence consisting of letters, numbers and under-indents, which starts with a small letter. Usually, if a nonalphanumeric atom is necessary, it is surrounded by apostrophes (for example “+” is an atom, + is an operator).

Numbers

The majority of the Prolog implementations do not make a difference between integers and with floating decimal point.

Variables

The variables are indicated by using a whole of letters, numbers and characters of underlining and starting with a capital letter.

For example " X3" and " Prix_Unitaire" are names of variables. In the Prolog environment, unlike the procedural computer programming languages, a variable is not a container to which one can affect a value. Its behavior is closer to a form, initially indefinite, than one specifies more and more by Unification. Once the variable is unified, its value cannot be any more modified within the same branch of evaluation (the Retour on trace makes it possible however to reconsider this unification).

The variable anonymity is written with a low Tiret (_). Any variable whose name starts with a low indent is also an anonymous variable.

Made up terms

The made up terms are the only ways in which Prolog can represent complex data. A made up term consists of head, such a called Foncteur (which must be an atom), and parameters (without restriction of the type). The number of parameters, also called Arite of the term, is significant. A made up term is identified by its head and its arite, it is usually written like functor/arite.

Examples of made up terms:

likes (Romeo, Juliette)

the functor is likes and arite 2, the made up term is written aime/2.

F (G (X), H (Y))

the functor is F and arite 2, the made up term is written f/2.

initialization

the functor is initialization and arite 0, the made up term is written initialization/0. An atom is thus a term made up of arite 0.

Lists

A list is not an isolated type of data, because it is defined by a recursive construction (using the functor . arite 2, it is thus on the level of the representation interns a made up term):

the atom is an empty list;
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 remainder of the list, indicated like T or tail. The list 2,3 would be represented in-house like “. ” ( 1 , “. ” ( 2 , “. ” ( 3 ,))) A short cut of syntax is | '' T '', which is especially used to build rules. The totality of a list can be treated while acting on the first element, and then on the remainder of the list, by Récursivité.

For the facility of the programmer, the lists can be built and déconstruites in various ways.

Enumeration of elements: 1, F (X), '' Y '', G ('' has '', rst)
Extraction of the element of head: | '' L1 ''
Extraction of several elements of head: 1, F (X) | '' L2 ''
Expansion of the term: “. ” (ABC, “. ” (1, “. ” (F (X), “. ” ( Y , “. ” (G ( has , rst),)))))

Character strings

The character strings are in general written like a sequence of natures surrounded by apostrophes. They are often represented in-house by a list of ASCII codes.

Predicates

The Programmation in Prolog is very different from the programming in imperative language. In Prolog, one feeds a Base of knowledge facts and rules; it is then possible to make requests at the base of knowledge. The basic unit of Prolog is the Prédicat, 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 some simple requests that you can ask a Prolog interpreter based on this fact:

? - cat (Tom). yes.

? - cat (X). X = Tom; fail.

In this second example, with the question “cat (X)” the interpreter proposes the answer “X = Tom” unifying the variable “X” with the atom “Tom”. The user asks for another answer by " ; " (symbol of disjunction), the interpreter answers that it does not find any.

The predicates are in general defined to express the facts that the program knows in connection with the world. In the majority of the cases, the use of predicates requires a certain convention. For example, the semantics of the two following predicates is not immediate:

father (sally, stalemate). father (stalemate, sally).

In both cases, “father” is the head while “sally” and “stalemate” are the arguments. However, in the first case, Sally comes in first in the list of the arguments, and in the second it is Pat (the order in the list of the arguments imports). The first case is an example of a definition in the order verb-subject-object, and the second of verb-object-subject. As Prolog does not include/understand the natural language, the two versions are correct in what relates to it; however it is important to adopt coherent standards of programming for the same program.

Some predicates are built in the language and make it possible a Prolog program to make activities of routine (like the Entrée/sortie, the functionalities of the Graphical interface and to generally communicate with the system of the computer). For example, the predicate write can be used for the screen display. Thus

Write (“Hello”).

the word will present “Hello” on the monitor. Such predicates do not concern the logical programming strictly speaking, their functionality resting exclusively on their effects edges.

Other predicates built in the languages are of nature logical, and included in libraries. They are used to simplify the development by encapsulating generic treatments, like algorithms of list processing for example.

Rules

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

light (one): - switch (one).

“: -” means “if”; this rule indicates light (one) is true so interruptory (one) is true. The rules can also use variables like:

father (X, Y): - relative (X, Y), male (X).

What means “if somebody is the relative of someone else and that it is a male, he is thus the father”. The antecedent and consequent is in the inverse order of what one normally finds in logic. It is possible to place multiple predicates and consequently, grouped with a conjunction “and”, for example:

has, B, C: - D.

who is simply the equivalent of three separated rules, however the three separate rules are not the equivalent of (has and B and c) if D, since it is about one “or” inclusive:

has: - D. B: - D. C: - D.

The rules of this type are on the other hand not authorized:

has; B: - C.

who means “if C then has or B”. It is indeed not a clause of Horn.

It will be noted that a fact is a particular case of rule. Indeed the two following lines are equivalent:

a. has: - true.

Evaluation

When interpreter receives request, it seeks rules (made included) the left part can be unified with the request, and this unification with the first found rule carries out. For example having this Prolog code:

frère_ou_sœur (X, Y): - relative (Z, X), relative (Z, Y), X \ = Y. father (X, Y): - relative (X, Y), male (X). mother (X, Y): - relative (X, Y), female (X). relative (X, Y): - father (X, Y). relative (X, Y): - mother (X, Y). mother (trude, sally). father (Tom, sally). father (Tom, erica). father (mike, Tom). male (Tom). female (trude). male (mike).

He results from it that the following request is evaluated like true:

? - frère_ou_sœur (sally, erica) yes.

The interpreter arrives at this result while making correspond the rule frère_ou_sœur (X, Y) by unifying X with sally and Y with erica . That means that the request can be wide with parent (Z, sally) , parent (Z, erica) . To make correspond this conjunction is obtained by looking at all the 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) will have to be true, and no fact such (or some rule which can satisfy that) is present. Also for the place, Tom is substituted for Z , and erica and sally appears being frère_ou_sœur nevertheless.

The code

mother (X, Y): - relative (X, Y), female (X). relative (X, Y): - father (X, Y).

can seem suspect. After all each relative is not a father. But it is true that each father is a relative. On another side, somebody is the mother of the one only if it is at the same time her relative and female.

To indicate that all the fathers are male, you need the code

male (X): - father (X, _).

what simply is indifferent to which is the child (the soustiret is an anonymous variable).

Negation by the failure

The pure logical negation does not exist in Prolog, one rests on the Négation by the failure, which is noted differently according to the implementations of Prolog (we will adopt the notation by the key word not). In negation by the failure, a predicate is regarded as forgery if, in a finished time, one fails to show that it is true (by the algorithm of resolution of Prolog). That is called the assumption of the closed world (opposite with the assumption of the open world): it is considered that all that must be known is included in the database, it does not have there an outside world which could contain unknown pieces of evidence of the program. In other words, as long as a fact is not known as being true, he is regarded as forgery.

A rule like this one: mangeable (X): - not indigestible (X).

can only be evaluated while initially seeking to show that “indigestible (X)” is true. If this research fails, then " mangeable (X) " is true. It is what is called the Négation by failure.

Execution

Prolog is a logical language, also in theory you should not worry you of how it is carried out. However it is sometimes advisable to take into account how the algorithm of inference acts, to prevent that a Prolog program does not last too a long time.

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

elems (, 0). elems (, X): - elems (T, Y), X is Y + 1.

That means simply; if the list is empty, the number of elements is zero. If a list is not empty, then X is increased by one compared to Y, which is the number of elements in the remainder of the list without the first element.

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

miser (X): - avoirargent (X). miser (X): - avoircrédit (X), NOT avoirargent (X). If you have money, you continue with miser. If you very lost you need to borrow, or if not… more bet. avoirargent (X) can be a very expensive function, for example, if it can reach on your bank account by the Internet. But it is the same thing for avoircrédit .

In theory, the implementations of Prolog can evaluate these rules in any order, also you could as well have written;

miser (X): - avoircrédit (X), NOT avoirargent (X). miser (X): - avoirargent (X).

What is well, because the two options are excluded one the other. However to check if you can obtain a loan is not necessary if you know that you have money. Also in practice, the implementations of Prolog will test initially the rule which you wrote in first . You can use the operator cut to tell the interpreter to jump the second option if the first is enough. For example:

miser (X): - avoirargent (X)!. miser (X): - avoircrédit (X), NOT avoirargent (X).

That is called an operator of green stop . The ! simply tells the interpreter not to more seek of alternative. But you note that if you need money it needs to evaluate the second rule, and it will do it. To evaluate avoirargent in the second rule is rather useless because you know that you do not have any, for the good reason that, if not, the second rule would not be evaluated. Also you can change the code into:

miser (X): - avoirargent (X)!. miser (X): - avoircrédit (X).

That is called a red operator of stop , because it is dangerous to do that. You are now depend on the correct placement on the operator on stop and the order on the rules to determine their logical direction. The accidents Cut-and-to stick watch for in the dark corners. If the rules are mixed, you can now use your credit card before spending your money available.

Generative grammar

When one makes generative grammar with Prolog, the goal is to be able to generate only grammatically correct sentences; one can also add functors so that Prolog gives us trees representing the structure of the sentences.

Implementations

Open Prolog
Ciao Prolog
GNU Prolog, developed by INRIA
YAP Prolog
SWI Prolog, developed by the University of Amsterdam
Strawberry Prolog
Visual Prolog
SICStus Prolog, developed by the Swedish Institute for Computer Science
Amzi! Prolog
B-Prolog
TuProlog
http://xsb.sourceforge.net/ XSB
Rebol Prolog
Prolog.NET
qu-Prolog, a prolog multithread developed by the University of Queensland

See too

Warren' S Abstract Machine

External bonds

Course and Tutoriel Prolog
the forum of French-speaking Prolog mutual aid
Learn Prolog Now!
Banner page of Alain Colmerauer

Beats-smg: Prolog

Random links:

Solecism | Bellano | Andrea Soncin | Ceti alpha | Nerik