Prolog

Prolog est un OVNI. C’est un langage de programmation, phare du paradigme de la programmation logique. C’est un mélange programmation impérative et raisonnement logique pour trouver une ou des solutions. Chaque ligne du programme est une clause :

papaGentil(X) :- homme(X), gentil(X), enfantDe(X, Y).

• :- : sépare ce que l’on définit (à gauche) de la définition (à droite). La définition est une conjunction.
• , : sépare les formules atomiques. La virgule peut se lire et.
• X : variable

Motivations

C’est beau

Ecrire un algorithme de backtracking c’est fastidieux. Avec Prolog, on ne le fait jamais : le backtracking est un mécanisme clef du langage. Ce qui est génial, c’est la notion de variable :

• soit elle a une valeur et on continue le calcul avec cette valeur (comme en C, Java, Javascript, etc.)
• soit il faut lui trouver une valeur !

Sur https://www.swi-prolog.org/pldoc/man?section=clpfd-sudoku, on trouve l’exemple d’un programme Prolog qui résout le jeu du Sudoku. Voici une reproduction de ce programme. Il utilise les mécanismes de Prolog et de la programmation par contraintes. Admirez la concision du programme.

:- use_module(library(clpfd)).

% la liste de listes Rows
% représente une grille de Suduku
sudoku(Rows) :-
        length(Rows, 9),
        maplist(same_length(Rows), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
        blocks(As, Bs, Cs),
        blocks(Ds, Es, Fs),
        blocks(Gs, Hs, Is).

% blocks(Row1, Row2, Row3) signifie que
% les carrés 3x3 respectent la règle du carré
blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
        all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
        blocks(Ns1, Ns2, Ns3).

• use_module(library(clpfd)) : veut dire que l’on utilise une librairie. Ici, clpfd pour “Constraint Logic Programming over Finite Domains”.
• length : length(Liste, Longueur) signifie la liste Liste est de longueur Longueur
• maplist : c’est comme map. Il applique un prédicat à chaque élément de la liste.
• same_length : same_length(Liste, Liste2) dit que les deux listes sont de la même longueur. C’est utilisé sous une forme curryfié.
• append : append(Rows, Vs) dit que Vs est la liste applatie de Rows par exemple append([[1, 3], [2, 4]], [1, 3, 2, 4]).
• all_distinct : all_distinct(L) renvoie vrai quand tous les éléments de L sont distincts.
• ins : ins vient de la librarie clpfd et permet de dire que les éléments de Vs sont dans 1..9 (si X était une valeur, on écrit X in 1..9)
• transpose : transpose(Rows, Columns) dit que Columns est la transposée de Rows.
• = : ça fait une unification !
• | : [N1,N2,N3|Ns1] veut dire que N1, N2, N3 sont les trois premiers éléments de la liste, alors que Ns1 est la liste des nombres qui suivent.

Pour résoudre un Sudoku, après l’invite de commande Prolog ?-, on écrit la grille partielle en mettant des variables anonymes _ pour les valeurs inconnues que l’on donne à manger au prédicat sudoku :

?- Grille = [
    [5,3,_, _,7,_, _,_,_],
    [6,_,_, 1,9,5, _,_,_],
    [_,9,8, _,_,_, _,6,_],

    [8,_,_, _,6,_, _,_,3],
    [4,_,_, 8,_,3, _,_,1],
    [7,_,_, _,2,_, _,_,6],

    [_,6,_, _,_,_, 2,8,_],
    [_,_,_, 4,1,9, _,_,5],
    [_,_,_, _,8,_, _,7,9]
   ],
   sudoku(Grille).

Utile en IA

• Les LLMs ont parfois du mal à raisonner. Raisonner avec des règles est parfois prometteur, notamment pour résoudre ARC.
• Mélange ML et Prolog : Problog

Mise en place

On installe l’interpréteur Prolog comme suit :

    sudo apt install swi-prolog

On peut aussi appeler Prolog depuis Python (des applications entièrement réalisés en Prolog c’est rare !).

from pyswip import Prolog

prolog = Prolog()

def printOutput(queryString: str, variables: list[str]):
    for result in prolog.query(queryString):
        for variable in variables:
            print(f"{variable} = {result[variable]}")

prolog.consult("sudoku.pl")
printOutput("""Grille = [
    [5,3,_, _,7,_, _,_,_],
    [6,_,_, 1,9,5, _,_,_],
    [_,9,8, _,_,_, _,6,_],

    [8,_,_, _,6,_, _,_,3],
    [4,_,_, 8,_,3, _,_,1],
    [7,_,_, _,2,_, _,_,6],

    [_,6,_, _,_,_, 2,8,_],
    [_,_,_, 4,1,9, _,_,5],
    [_,_,_, _,8,_, _,7,9]
   ],
   sudoku(Grille).""", ["Grille"])

Exemple de la famiglia

Programme

Voici un programme Prolog :

ancetre(X, Y) :- parent(X, Z), ancetre(Z, Y).
ancetre(X, Y) :- parent(X, Y).
parent(jean, marie).
parent(marie, bob).

Requête

On peut obtenir un ancêtre de Jean avec :

?- ancetre(jean, X).

Programme complet

On peut aussi écrire un programme complet avec un main :

ancetre(X, Y) :- parent(X, Z), ancetre(Z, Y).
ancetre(X, Y) :- parent(X, Y).
parent(jean, marie).
parent(marie, bob).

% c'est comme ça qu'on dit qu'il faut initialiser le programme avec main
:- initialization(main). 

main :- 
    ancetre(jean, X),    % trouve moi X qui est un ancêtre de jean
    format("Un ancêtre de jean est ~w ", [X]).  % affiche un ancêtre

Obtenir toutes les solutions

On peut appuyer sur , pour obtenir d’autres solutions. Sinon, le mot clé fail permet de continuer le backtracking.

ancetre(X, Y) :- parent(X, Z), ancetre(Z, Y).
ancetre(X, Y) :- parent(X, Y).
parent(jean, marie).
parent(marie, bob).

:- initialization(main). % c'est comme qu'on donne la fonction main
main :- 
    ancetre(jean, X),
    format("~w ", [X]),
    fail.

Analyse syntaxique

Toujours avec cet esprit vérification/génération, on peut utiliser Prolog pour des grammaires. La vérification d’appartenance à un langage et la génération d’un élément du langage se fait avec le même programme. Autrement dit, analyse syntaxique et génération se font avec le même programme Prolog.

Grammaire

Prolog offre une syntaxe élégante pour écrire des grammaires. On parle de Definite clause grammar. Cela signifie que les règles de la grammaire sont, comme, on le vérifie des clauses avec un litéral positif (definite clause).

sentence --> groupe_nominal, groupe_verbal.
groupe_nominal --> det, nom.
groupe_verbal --> verbe, groupe_nominal.

det --> [le] ; [la].
nom --> [chat] ; [souris].
verbe --> [mange] ; [poursuit].

Sucre syntaxique

En fait,

phrase --> groupe_nominal, groupe_verbal.

Hé oui, le --> est du sucre syntaxique. En fait,

sentence --> groupe_nominal, groupe_verbal.

se réécrit en fait en la clause :

sentence(In, Out) :- groupe_nominal(In, Rest), groupe_verbal(Rest, Out).

Dans la règle ci-dessus, In, Out et Rest sont des listes de mots. La formule sentence(In, Out) signifie que dans le début de la liste In correspond à une phrase et que le reste qui n’a pas été parsé est Out. La logique est la même pour groupe_nominal(In, Rest).

Requête

Pour obtenir toutes les phrases on écrit :

?- sentence(S, []).

Négation par échec

\+ est la négation par échec. \+ frere(X, Y) est considéré comme vrai quand, avec le programme actuel, on n’arrive pas à prouver que frere(X, Y).

Attention, l’ordre est important.

homme(jean).
homme(paul).
femme(marie).

marie_avec(jean, marie).

celibataire(X) :-
    homme(X),
    \+ marie_avec(X, _).

celibataire2(X) :-
    \+ marie_avec(X, _),
    homme(X).

Règle d’or (souvent) : toujours instancier les variables avant de nier des faits qui en parlent.

Coupe (cut)

Le symbole ! est une coupe, elle permet d’arrêter l’exploration. Plus précisément :

• il fixe/gèle le choix de la règle pour le prédicat courant
• il fixe les valeurs variables qui ont été fixés à gauche du !

Au lieu d’écrire

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

on écrit

max(X, Y, X) :- X >= Y, !.  % Si X >= Y, c'est BON, on coupe ! Ne va pas voir la règle du dessous.
max(X, Y, Y).

mention(Note, 'Tres Bien') :- Note >= 16, !.
mention(Note, 'Admis')     :- Note >= 10, !.
mention(_, 'Recale').

Quiz

double(X, Y) :- Y is X * 2.

Que se passe-t-il si on exécute la requête inverse : ?- double(X, 10). ?

• X = 5 (Prolog est intelligent et résout l’équation à l’envers).
• Une erreur d’instanciation (Arguments are not sufficiently instantiated).
• X = 20

Explication : l’opérateur arithmétique is en Prolog est unidirectionnel et requiert que le côté droit soit entièrement calculable. Pour rendre ce prédicat réversible, il faudrait utiliser la bibliothèque de contraintes clpfd (Y #= X * 2).

ancetre(X, Y) :- ancetre(Z, Y), parent(X, Z).
ancetre(X, Y) :- parent(X, Y).
parent(jean, marie).

Si on lance la requête ?- ancetre(jean, marie)., que se passe-t-il ?

• Prolog répond true. instantanément.
• Prolog boucle à l’infini (Stack Overflow / Out of local stack).
• Prolog répond false.

C’est le piège de la récursion à gauche. En voulant évaluer la première règle, Prolog essaie de résoudre ancetre(Z, marie) avant même de regarder si Jean est parent de Marie. Il replonge immédiatement dans la même règle avec une variable libre, créant une branche infinie. La règle de base (parent(X, Y)) doit toujours être placée avant le cas récursif en Prolog !

autorise(age_requis) :- age(A), A >= 18.

Si la base de connaissances ne contient aucun fait concernant l’âge, que renvoie la requête ?- \+ autorise(age_requis). ?

• true (parce qu’on ne trouve aucun âge valide).
• false (parce que l’âge n’est pas vérifié).
• Une erreur de syntaxe.

C’est la nature profonde de l’Hypothèse du Monde Clos. Le but interne autorise(age_requis) échoue (puisqu’il n’y a aucun fait age(A) pour prouver que $A \geq 18$). Le + prend cet échec, l’inverse, et renvoie donc true (il est vrai qu’on ne peut pas prouver l’autorisation). C’est souvent contre-intuitif pour un développeur qui s’attendrait à ce qu’une absence de donnée renvoie “inconnu” ou “faux”.

note(X, 'Mention') :- X >= 14, !.
note(_, 'Passable').

Que renvoie ?- note(10, Y). ?

• “Mention”
• “Passable”
• false

note(X, 'Mention') :- !, X >= 14.
note(_, 'Passable').

Que renvoie ?- note(10, Y). ?

• “Mention”
• “Passable”
• false

Déplacer le ! au début verrouille le choix de la première règle avant d’avoir testé X >= 14. Pour la note 10 : Prolog choisit la règle 1, exécute le ! (interdit d’aller voir la règle du dessous ‘Passable’), puis teste 10 >= 14 qui échoue. Comme on a coupé les ponts avec la deuxième règle, le prédicat entier échoue (false) au lieu de chuter vers ‘Passable’. C’est la définition parfaite d’une coupe rouge destructrice !