Programmation logique

Ce cours sera basé sur le langage de programmation logique Prolog.

La programmation logique consiste en la déclaration d’une série de faits et de règles de déduction. L’exécution d’un programme consiste à prouver un théorème. Le programme répond si le théorème peut être prouvé ou non à partir des déclarations faites au préalable.

La programmation logique est différente de la programmation procédurale (C, JAVA, etc), les calculs se font sous forme de preuves logiques. On parle de programmation déclarative : le programme décrit une situation correspondant à un problème à résoudre. La programmation déclarative n’est pas incompatible avec la structuration objet.

Les formules exprimées en Prolog sont restreintes aux clauses de Horn et la logique de premier ordre. Une clause de Horn est une clause comportant au plus un littéral positif. Ces dernières ne seront pas explicités mais implicites dans les explications du langage Prolog.

Règles, faits et buts

Si la clause de Horn a un littéral positif et au moins un littéral négatif, ce sont des règles :
qqsoit x,y,z, ¬enfant(x,y) ∨ ¬enfant(y,z) ∨ petit_enfant(x,z) ce qui équivaut à
enfant(x,y) ∧ enfant(y,z) ⇒ petit_enfant(x,z)

s’écrit en Prolog : petit_enfant_de(X,Z) :- enfant_de(X,Y), enfant_de(Y,Z)

On peut écrire des clauses de Horn sans littéral négatif (clauses de Horn positives), mais avec seulement un littéral positif. Ce sont des faits : enfant_de(‘Bernard’,’Bernadette’).
On peut écrire des clauses de Horn sans littéral positif, (clauses de Horn négatives), mais avec seulement des littéraux négatifs. Ce sont des buts : ?-petit_enfant_de(B,’germaine’),neveu(X,Y).

Un programme est donc un ensemble de faits et de règles, le tout sous forme de clauses de Horn. L’interpréteur Prolog se sert de cette base de connaissances pour répondre à des buts.

Syntaxe Prolog

La syntaxe est constituée de :

  • Constantes : nombres entiers ou flottants, booléens, identificateurs et chaines de caractères.
  • Variables : identifiées par des chaines de caractères débutant par une majuscule ou un underscore (si indéterminée, i.e. n’a pas d’intérêt pour l’utilisateur). Variable est au sens mathématique, elle représente toujours le même objet et ne change pas de valeur dans la même branche de démonstration.
  • Prédicat : identifiés par des chaines de caractères débutant par une minuscule. Un prédicat possède une arité (le nombre d’arguments qu’il requiert). Les paramètres sont séparés par une virgule, équivalant du ET; le OU est un point-virgule.

Règles et faits  :

  • un fait est un prédicat avec des constantes comme paramètres : parent(‘Bernard’, ‘Bernardo’)
  • une règles est constituée d’une tête (littéral positif) et d’une queue (conjonction des littéraux négatifs terminée par un point : neveu(X,Y) :- fils(X,Z), frère_ou_soeur(Y,Z).

Écrire un programme Prolog

Un programme est une liste de faits et de règles. On regroupe les règles qui ont le même prédicat de tête et les faits qui portent sur le même prédicat. L’ordre de déclaration des règles peut avoir un impact sur les buts.

enfant_de('roger','gertrude').
enfant_de('gertrude','germaine').
enfant_de('marcel','robert').
frère_ou_soeur('gertrude','robert').
neveu(X,Y) :- fils(X,Z), frère_ou_soeur(Y,Z).
petit_enfant_de(X,Y) :- enfant_de(X,Z),enfant_de(Z,Y).

Une constante (‘roger’) porte sur tout le programme tandis qu’une variable n’existe que dans la clause où elle se trouve. Donc la variable X de neveu (X,Y) n’est pas le même que celui de petit_enfant_de(X,Y). Par contre, il est le même que dans la conjonction qui lui est associé.

Une fois les programmes chargés et donc la base de faits et de règles constituée, il est possible de poser des questions. On parle alors de démonstration ou de résolution de question. Une question se pose en remplacer dans une règle ou fait une constante ou variable par un ‘?’. Pour connaitre toutes les règles d’un type on écrit le nom de la règle contenant des variables suivi d’un ‘?’ : humain(H)? sert à connaitre tous les humains de la base.

Publicités