Prolog

TD n°1

Historique de prolog

Présentation du langage

Le langage prolog (programmation en logique) fut introduit en 1972 par Alain Colmerauer. Ce langage permet d'écrire des programmes sous une forme très proche de la logique des prédicats du premier ordre.

C'est un langage :

déclaratif (contrairement aux langages impératifs comme Java, C++, Python, etc.) : il permet de déclarer des connaissances, sans expliciter leur traitement ;
indéterministe : il permet le traitement de problèmes comportant plusieurs solutions.

Dans un programme prolog, on retrouve toujours :

Des connaissances, décrivant des faits, regroupés dans une base de faits (BF),
Des règles applicables aux faits, regroupés dans une base de règles (BR).
BF + BR = BC (Base de connaissances)
Un moteur d'inference (M.I.) intégré dans le langage, qui permet d'"appliquer" les règles aux faits

La programmation logique en quelques dates

1930 : Jaques Herbrand achève sa théorie sur le calcul des prédicats.
1970 : R. Kowalski et A. Colmerauer utilisent la logique comme language de programmation.
1972 : Le premier interprète prolog voit le jour à L'Université de Marseille, grâce à P. Roussel et A. Colmerauer.
1977 : Le premier compilateur prolog apparaît à l'Université d'Edimburg, fruit du travail de D.H.D. Warren.

Revenons sur la naissance de prolog. En France, en 1970, A. Colmerauer se prend d'intérêt pour la façon de faire des déductions sur des textes. Étudiant alors le travail de R. Kowalski sur les méthodes de résolution, il s'en servit de base comme premier modèle théorique de prolog. Mais son but n'était pas de créer un nouveau langage de programmation. Il voulait pouvoir décrire, en français, un univers à l'ordinateur afin que celui-ci puisse répondre à des questions sur cet univers. Ils firent alors, avec R. Kowalski, un embryon d'un tel système, et c'est ainsi que fut développé l'outil prolog.

P. Roussel, de son côté, se servit du modèle de A. Colmerauer et avec l'aide de confrères d'Edimburg, il conçut le premier interprète, qui fut codé, par la suite, en fortran.

Le prolog est un langage de programmation logique basé sur deux grands mécanismes: le chaînage arrière et l'unification.

Le chaînage arrière est le fait de partir du but recherché, de rechercher les règles dont le but est la conclusion, puis, en prenant les conditions de ces règles comme nouveaux sous buts, recommencer la recherche récursivement, contruisant ainsi une base de faits. Ensuite, il ne reste plus qu'à unifier les faits trouvés avec le but recherché.

L'unification est le fait d'essayer de rendre deux assertions identiques (un fait et une règle en général) en donnant des valeurs aux variables qu'elles contiennent.

C'est un langage clair et lisible pour tout utilisateur, et l'écriture d'un programme en est aisée. Il est surtout utilisé pour faire des systèmes sur les langages naturels et les systèmes experts.

Premier exercice

But : définir un arbre généalogique, et pouvoir lui poser des questions...

Ébauche papier

Réaliser un arbre généalogique quelconque, mais en respectant certaines contraintes pour pouvoir l'exploiter facilement :

Pour s'y retrouver à la main, prendre A comme initiale des ancètres de plus haut niveau, B comme initiale des ancètres du niveau suivant, etc.

Au moins 4 niveaux (5 si on code arrière grand-père). Cela donnera par exemple :

andre+augustine              
      |__ bernard+becassine      
      |     |__ clement+chantal  
      |     |     |__ dudulle    
      |     |     |__ damien     
      |     |     |__ daniela    
      |__ babar                  
      |     |__ celestine        
      |__ brigitte+baptiste      
            |__ cedric+charlotte 
            |     |__ didier     
            |     |__ dagobert   
            |     |__ dominique  
            |__ caroline

Codage des faits

Pour décrire un arbre généalogique, il y a les faits (ce qui est particulier à chaque famille, par exemple que « Bécassine est une femme » ou que « Dudulle est le fils de Chantal ») et les règles (ce qui est vrai pour toutes les familles, par exemple que « le frère du père est l'oncle »). Il y a plusieurs tactiques pour décrire les faits, certaines plus intelligentes que d'autres. Chaque choix influera sur les règles qui seront à définir.
Réflexions à avoir avant et pendant la création :

Avec quel ensemble minimal de prédicats peut-on décrire complétement les faits d'un arbre généalogique ? Autrement dit, quels prédicats sont « basiques », indispensables, et lesquels peuvent être définis par des règles à partir des autres ? Les faits seront déclarés avec ces prédicats, les autres seront définis dans des règles.
Les commentaires en prolog : ils sont encadrés par /* .... */
Faire en sorte de ne pas mettre d'informations redondantes.

Attention :

tout ce qui commence par une majuscule est une variable (attention avec les prénoms et les noms de fichiers !) ;
dans les prédicats à 2 arguments, l'ordre n'est pas imposé par Prolog, c'est une convention ; on prendra toujours la convention « lien_parente(X,Y) » signifie « X est lien_parente Y » ; mais l'ordre utilisé dans la définition doit être le même que celui utilisé pour les questions, bien sûr (pas de commutativité des arguments) ;
toutes les variantes de Prolog font la distinction majuscule/minuscule, mais toutes ne traitent pas correctement les caractères spéciaux ou accentués du français : éviter d'en mettre dans vos prénoms et dans vos prédicats ;
en principe, le tiret haut est utilisable dans les noms de prédicats (grand-pere, etc.), mais ça pose parfois des problèmes par-ci par-là (confusion avec la soustraction sans doute) : préférer le tiret bas (« _ »).

Utilisation...

Écrire le fichier avec un éditeur, avec une extension ".pl".
En vous positionnant dans le dossier contenant votre fichier, lancer la ligne de commande "gprolog" : l'interpréteur GNUProlog se lance et affiche : |?
Charger le fichier en tapant
```
|? [nom du fichier sans l'extension .pl].
```
Si votre fichier contient des erreurs syntaxiques, elles vous seront signalées.
Poser quelques questions fermées (à réponses Yes/No) : par exemple "Andre est-il un homme/une femme ?", "Bernard est-il un enfant de Caroline ?" , etc. Après chaque modification du fichier, sauvegarder et recharger.
Quelques questions ouvertes avec une seule variable : par exemple "Qui sont les enfants de Babar ?", etc.
Quelques questions ouvertes avec plusieurs variables : par exemple "Qui est parent de qui ?", "Quels couples homme/femme ont eu un enfant ensemble ?", etc.

Règles

La formule « ∀x ∀y [enfant(x,y) ⇒ parent(y,x)] » se traduira « parent(Y,X) :- enfant(X,Y). ».

Expliciter sous forme de règles la définition des relations suivantes :

parent (ou enfant, suivant le choix fait initialement)
fils, fille, père, mère
grand_parent, petit_enfant, grand_père, grand_mère, petit_fils, petite_fille
frere_ou_soeur, frère, soeur
oncle_ou_tante, oncle, tante
cousin_ou_cousine, cousin, cousine

Règle récursive

Donner la définition de la relation de parenté "être un ancêtre de"

Traduire en interrogations prolog des questions formuléees en français

Qui est le père de Dagobert ?
Qui est la sœur du père de Dagobert ?
Qui est la mère du cousin du père de Dagobert ?
etc.

Dernière modification : 9/9/2011