Prolog : "crash course" (1)

Introduction à l'introduction

Tout d'abord, il faut lire ce texte au moins deux fois, afin de comprendre son sens, car on introduit souvent des concepts dont le sens sera dévoilé utérieurement. De toute façon, cette introduction est très superficielle et incomplète.

Nous allons utiliser l'implémentation SWI-Prolog, bien maintenue et efficace. C'est une de plus populaires pour l'enseignement de ce langage.

Le trait caractéristique de Prolog est sa "philosophie de haut niveau", on traite la programmation, la solution des problèmes calculatoires, comme un processus logique, la tentative de prouver la vérité d'une proposition. Le programme est "la preuve", sa formulation. La réponse finale (une structure de données construite comme le résultat), est la "vérité" cherchée.

C'est un de rares langages non-déterministes au sens logique du terme, par design. Cela signifie que Prolog est capable de donner plusieurs réponses à une question, et ceci le rend particulièrement intéressant dans le domaine d'Intelligence Artificielle. "Où aller", ou "quel coup jouer" normalement admettent des réponses multiples. Prolog est un langage "classique" au sens : pas forcément concurrent (même si les implémentations courantes sont typiquement multi-threaded), et ces réponses multiples sont obtenues par le backtracking, le retour en arrière dans l'arbre décisionnel, et la reprise d'une autre branche. (Nous y reviendrons).

Après le lancement de l'exécutable, l'utilisateur se trouve dans un environnement interactif textuel, et il peut écrire des requêtes adressées au système. Par exemple, il peut lancer :

help.
et obtenir l'aide dans une fenêtre séparée. Il peut écrire une "commande logique" triviale, par ex.
true.
% ou :
false.
et obtenir la réponse qui copie la requête (puisque true c'est true, non?). Il ne faut pas oublier de terminer la commande, et toute clause du programme par le point. Le caractère "%" commence un commentaire.

Données

Comme tout langage de programmation, Prolog opère sur des structures de données. Elles peuvent être atomiques, comme des nombres : 2, -2.3, etc, ou symboliques : alpha, x, _symbole, etc.

Les données peuvent être composites, être des termes, des blocs contenant plusieurs données. On met le contenu entre les parenthèses, et on préfixe cette forme par un symbole qui nomme le terme, par ex. struct(1,a,b), rel(2,3,5). Imaginez ceci comme des blocs qui contiennent les éléments mentionnés, et où le symbole préfixe dénote le type du terme. On peut avoir dans le programme plusieurs termes de même type : rel(1,6,7), rel(0,0,0), rel(alpha,beta,quoi), etc. L'usage de ces termes viendra un peu plus tard, pour l'instant sachez qu'ils existent.

Tous les symboles faisant partie des termes – comme mentionné ci-dessus, ont des noms qui commencent par une lettre minuscule.

Variables logiques

Cependant, une catégorie très importante de données doit être introduite : le concept de variable logique, dont le nom commence par majuscule : X, Quoi, Result, etc. Les variables logiques peuvent aussi commecer par l'underscore : _rien, etc.

Il n'est pas facile d'expliquer le sens de ces objets, ils sont un peu similaires, mais quand même très différentes des variables dans d'autres langages. Une variable logique peut être unifiée à une donnée quelconque, le système vérifie si elle "peut être" identique à cette donnée, et si c'est le cas, elle devient synonymique à elle. Elle "ne peut pas" être unifiée, si elle a déjà été unifiée à une autre chose dans le même morceau du programme (la même clause). Alors la clause échoue, la preuve logique donne FAUX.

Dans l'évaluation d'une clause, une variable logique ne peut être "réaffectée", l'unification est à sens unique, et elle est niée, abolie, quand le backtracking, après le renoncement de la continuation de cette branche de la preuve, en essaie une autre. Bien sûr, si on applique la récursivité, on crée chaque fois des nouvelles instances de ces variables, comme avec les variables dans d'autres langages.

L'usage des variables logiques est multiple. Elles servent comme les variables ailleurs, comme les endroits où on stocke les valeurs retournées à l'utilisateur, ou comme des variables temporaires. Elles peuvent aussi servir comme des "trous", pour créer des structures de données incomplètes, par ex. terme(alpha,X), qui dénote un ensemble conceptuel de tous les termes terme(...) à deux champs, dont le premier est alpha.

Programmes.

Nous avons donc les données, les termes atomiques et composites, mais il faut savoir les manipuler, écrire des programmes, avec des structures syntaxiques, et leur sémantique opérationnelle. Contrairement à plusieurs autres langages, en Prolog il n'y a presque rien de nouveau. Les termes sont les éléments du programme, une petite "colle" syntaxique comme des virgules, ou points-virgules, fait le reste. Le texte trm(arg1,arg2,Arg3). est un programme complet (même sans trop de sens). Comment ça marche?

Relations et prédicats

Une structure composite, par ex. trm(A,B,C,D) peut être considérée comme une relation nommée entre les composantes [c'est l'idée même dese bases de données relationnelles]. La structure elle même, peut être considérée comme un prédicat. Les prédicats remplacent en Prolog les fonctions et les conditions logiques. Ce qui dans un langage typique est une fonction, par ex. add(X,Y)R : la somme de X et Y, en Prolog sera codé comme add(X,Y,R). Ici, normalement X et Y sont unifiés avec des données numériques (ou une autre algèbre qui admet l'addition). Si le troisième argument est instancié, par ex. add(3,5,8), le système répond par "vrai" (ou "faux" si on essaie add(2,2,3)).

Si le troisième argument est une variable logique non-instanciée, l'objectif attendu du prédicat add est d'unifier cette variable avec le résultat de l'addition.

Les termes qui sont traités comme les prédicats, sont stockés par Prolog dans une base de données globale, et c'est justement le "programme".

Faits et vérités déduites directement

Voici une petite expérience de programmation. Insérons dans un fichier extérieur, par ex. base.pl, un prédicat, contenant plusieurs clauses (instances d'un prédicat, discernées par les arguments).

pere(adam,abel).
pere(adam,cain).
pere(cain,henoch).
pere(lamech,noe).
pere(noe,sem).
pere(noe,cham).
pere(noe,japhet).
Quand on charge cette base, depuis le menu de l'éditeur du SWI-Prolog, ou en tapant :
[base].
nous disposeons d'un ensemble de vérités, qui peuvent être testées. En tapant :
pere(adam,cain).
% ou
pere(cham,chrostowski).
on obtient des réponses "vrai" ou "faux". En Prolog "faux" signifie que le système est incapable de prouver la vérité d'une proposition.

Si on tape la requête :

pere(lamech,X).
alors puisque le second argument est une variable, elle sera unifiée avec ce que le système est capable de déduire de sa base de données, ici : X = noe.

La requête pere(adam,Qui). en principe admet deux réponses. Le système écrit Qui = abel, mais si l'utilisateur tape ";" (le point-virgule, pas de guillemets), ce qui siqgnifie OU, Prolog cherche d'autres solutions, et fournit également Qui = cain.

On peut aussi lancer les requêtes pere(Lui,abel)., ou pere(X,Y).; le dernier cas fournit toutes les paires père - fils.


Vérités déduites indirectement

Ceci constitue l'essence même de la programmation en Prolog. Les prédicats peuvent être définis par d'autres. L'opérateur :- demande la réduction de la partie gauche, son remplacement par la forme à droite. Sur le plan logique, c'est l'inférence. Pour des conditions composites, la virgule "," signifie ET, et le point-virgule ";" - OU.

Voici les définitions des prédicats fils, et grandpere :

fils(X,Y):-pere(Y,X).
grandpere(X,Y):-pere(X,Z),pere(Z,Y).
Une variable à droite, qui ne figure pas à gauche, peut être considérée comme quantifiée existentiellement. Voici une définition contenant deux clauses, dont une récursive.
ancetre(X,Y):-pere(X,Y).
ancetre(X,Y):-pere(X,Z),ancetre(Z,Y).
Voici une exécution exemplaire (12 est le numéro de commande actuelle, sans signification) :
12 ?- ancetre(adam,X).
X = abel ;
X = cain ;
X = henoch ;
false.
L'expérience suivante contient un piège.
frere(X,Y):-pere(Z,X),pere(Z,Y).

13 ?- frere(abel,X).
X = abel ;
X = cain.
La définition n'empêche pas qu'un item soit considéré comme son propre frère. Voici la correction, avec le prédicat d'inégalité.
frere(X,Y):-pere(Z,X),pere(Z,Y),X\==Y.

Mais le piège continue... Comparons ceci avec :

fr(X,Y):- X\==Y,pere(Z,X),pere(Z,Y).
Le ET logique est commutatif. Intuitivement il n'y a aucune différence entre les deux récentes solutions, cependant la dernière est erronée. Si on vérifie l'inégalité avant de vérifier les prédicats pere, on effectue la comparaison de deux variables logiques non-instanciées, et X\==Y est toujours vrai dans ce cas. La pathologie : X frère de X, – continuera.


Un peu d'interactivité

L'intercface du SWI-Prolog attend de la part de l'utilisateur une requête, une question, un prédicat à vérifier (et éventuellement des variables à instancier). Il n'est pas immédiat la création ou la modification du programme depuis l'interface. Comme il a été dit, on charge le fichier xxxx.pl avec le programme, via l'éditeur du SWI, ou par la commande
[xxxx].
Syntaxiquement les crochets délimitent une liste, et ceci ne peut être un prédicat valide, donc son interprétation est spéciale. Si au lieu d'y mettre un nom de fichier, on tape [user]., le système passe en mode définition, et on peut insérer une clause comme dans un fichier extérieur. Ce mode est terminé par le caractère EOF (Ctrl-D, Ctrl-Z, etc., selon le système).

Quelques commandes spéciales (non-logiques) aident l'utilisateur à manipuler et à diagnostiquer son programme. La commande

trace.
ouvre un mode d'exécution verbose, où le système affiche les appels internes avec les arguments, et les résultats temporaires. On voit les préfixes", comme "call", "exit", qui existeraient dans d'autres langages, mais aussi "redo", la reprise du processus après le backtracking provoqué par un échec intermédiaire. Le caractère espace exécute un pas tracé.

1 ?- trace.
true.

[trace] 1 ?- ancetre(lamech,Z).
   Call: (6) ancetre(lamech, _G5468) ? creep
   Call: (7) pere(lamech, _G5468) ? creep
   Exit: (7) pere(lamech, noe) ? creep
   Exit: (6) ancetre(lamech, noe) ? creep
Z = noe ;
   Redo: (6) ancetre(lamech, _G5468) ? creep
   Call: (7) pere(lamech, _G5541) ? creep
   Exit: (7) pere(lamech, noe) ? creep
   Call: (7) ancetre(noe, _G5468) ? creep
   Call: (8) pere(noe, _G5468) ? creep
   Exit: (8) pere(noe, sem) ? creep
   Exit: (7) ancetre(noe, sem) ? creep
   Exit: (6) ancetre(lamech, sem) ? creep
Z = sem ;
   Redo: (8) pere(noe, _G5468) ? creep
   Exit: (8) pere(noe, cham) ? creep
   Exit: (7) ancetre(noe, cham) ? creep
   Exit: (6) ancetre(lamech, cham) ? creep
Z = cham ;
   Redo: (8) pere(noe, _G5468) ? creep
   Exit: (8) pere(noe, japhet) ? creep
   Exit: (7) ancetre(noe, japhet) ? creep
   Exit: (6) ancetre(lamech, japhet) ? creep
Z = japhet ;
   Redo: (7) ancetre(noe, _G5468) ? creep
   Call: (8) pere(noe, _G5541) ? creep
   Exit: (8) pere(noe, sem) ? creep
   Call: (8) ancetre(sem, _G5468) ? creep
   Call: (9) pere(sem, _G5468) ? creep
   Fail: (9) pere(sem, _G5468) ? creep
   Redo: (8) ancetre(sem, _G5468) ? creep
   Call: (9) pere(sem, _G5541) ? creep
   Fail: (9) pere(sem, _G5541) ? creep
   Fail: (8) ancetre(sem, _G5468) ? creep
   Redo: (8) pere(noe, _G5541) ? creep
   Exit: (8) pere(noe, cham) ? creep
   Call: (8) ancetre(cham, _G5468) ? creep
   Call: (9) pere(cham, _G5468) ? creep
   Fail: (9) pere(cham, _G5468) ? creep
   Redo: (8) ancetre(cham, _G5468) ? creep
   Call: (9) pere(cham, _G5541) ? creep
   Fail: (9) pere(cham, _G5541) ? creep
   Fail: (8) ancetre(cham, _G5468) ? creep
   Redo: (8) pere(noe, _G5541) ? creep
   Exit: (8) pere(noe, japhet) ? creep
   Call: (8) ancetre(japhet, _G5468) ? creep
   Call: (9) pere(japhet, _G5468) ? creep
   Fail: (9) pere(japhet, _G5468) ? creep
   Redo: (8) ancetre(japhet, _G5468) ? creep
   Call: (9) pere(japhet, _G5541) ? creep
   Fail: (9) pere(japhet, _G5541) ? creep
   Fail: (8) ancetre(japhet, _G5468) ? creep
   Fail: (7) ancetre(noe, _G5468) ? creep
   Fail: (6) ancetre(lamech, _G5468) ? creep
false.
La commande notrace. arrête la verbosité. Il existe aussi debug. et nodebug., mais ceci ne sera pas discuté ici.


Suivant
Retour à l'index