Prolog - Définition

Réversibilité

Une particularité de Prolog est de ne pas donner de statut aux paramètres d'un prédicat, ce ne sont pas des paramètres 'donnés' ou 'résultats', ou même 'donnés/résultats', leur statut est indifférent et sera définis en fonction des requêtes utilisées.

Ceci permet, parfois, la définition de prédicats réversibles, c'est-à-dire dont les appels standards, permettant d'obtenir des résultats à partir de données, peuvent être inversés pour chercher les données initiales menant à certains résultats (alors ce qui est donné, ce sont les résultats, et ce qui est obtenu (les résultats) ce sont les données initiales recherchées).

Exemples

Symétrique d'un arbre binaire

Prenons des arbres binaires avec comme nœud f et comme feuille 0 ou 1.

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

L'utilisation standard de ce prédicat est du type :

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

Mais l'on peut aussi avoir :

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

Grammaire générative

Lorsqu'on fait de la grammaire générative avec Prolog, le but est de ne pouvoir générer que des phrases grammaticalement correctes ; on peut aussi rajouter des foncteurs pour que Prolog nous donne des arbres représentant la structure des phrases.

      domains        liste=string*            predicates        s(liste,liste)        sn(liste,liste)        sv(liste,liste)            clauses /*grammaire*/        s(L0,L):-sn(L0,L1),sv(L1,L).            /*lexique*/      sn([je|U],U).      sv([mange|U],U).      sv([viens|U],U).      

        Goal:s([je,viens],[])        Yes              Goal:s([je,mange],[])        Yes              Goal:s([viens,mange],[])        No      

      domains        liste=string*        expr= fs(string,string)      predicates        s(liste,liste,expr)        sn(liste,liste,string)        sv(liste,liste,string)            clauses /*grammaire*/        s(L0,L,fs(A,B)):-sn(L0,L1,A),sv(L1,L,B).            /*lexique*/      sn([je|U],U,je).      sv([mange|U],U,mange).      sv([viens|U],U,viens).      

        Goal:s([je,viens],[],R)        R=fs("je","viens")        1 Solution              Goal:s([je,mange],[],R)        R=fs("je","mange")        1 Solution              Goal:s([viens,mange],[],R)        No Solution      

Et après ?

Prolog et la programmation logique a donné naissance à un courant de programmation reprenant la plupart des spécificités de Prolog et les apports de la programmation par contrainte pour aboutir à la programmation logique par contrainte (PLC).

Autres pistes :

• vers les bases de données (?).
• avec du parallélisme (?).

Particularités de Prolog

Comme langage de programmation, Prolog se distingue par :

• le non-déterminisme, pour la résolution de problèmes ouverts : le 'ou' utilisé en Prolog est un vrai 'ou' logique qui permet l'exploration de l'ensemble des possibles.
• la réversibilité (cf. plus haut)
• la gestion des requêtes sous-contraintes/sur-contraintes : l'absence de statut pour les paramètres d'un prédicat (cf. réversibilité) et le modèle d'exécution employé permet, d'un coté, l'emploi de requêtes sous-contraintes exposant l'ensemble des possibles, et de l'autre coté, l'emploi de requêtes sur-contraintes permettant la vérification de propriétés particulières sur les solutions exhibées ou le filtrage de ces solutions.

Bibliographie

• Jean-Paul Delahaye, Cours de Prolog avec Turbo Prolog, Eyrolles, 1988 - id : 9782212081916.
• Jacky Legrand, Le langage Prolog - Exemples en Turbo Prolog, Technip, 1992 - .
• Patrick Blackburn, Johan Bos, Kristina Streignitz, PROLOG tout de suite, College Publications, 7 août 2007.