Skip to content

Texte : langages logiques

Parallèlement au renouveau des langages fonctionnels est née une approche fondamentalement différente de la programmation déclarative. Plutôt que de décrire une « formule » exprimant le calcul à effectuer, i.e. une fonction au sens fonctionnel, l’idée est de laisser encore plus de travail implicite à l’interpréteur ou au runtime. Ceci a conduit à ce qu’on a appelé la « programmation logique ». Dans ce contexte, un programme est une simple question, à laquelle, conformément à la logique aristotélicienne, on attend une réponse « oui » ou « non ». On ne donne plus la formule qui y répond, ni le raisonnement qui y conduit, ni évidemment la séquence d’opérations qui permettrait de le trouver, puis d’évaluer la réponse.

Bien sûr, cette « question » est contextualisée : on doit fournir préalablement (dans le programme même, où cela joue le rôle de « déclarations », ou bien dans sa « bibliothèque ») une « base de connaissances » constituée de faits connus et acceptés pour « vrais » (des prédicats (facts), ce qu’on appelle les axiomes en logique formelle) et des règles de déduction (rules), de combinaison de ces prédicats pour établir de nouvelles vérités (c’est le « système formel » dans lequel on travaille). L’interpréteur utilise alors ces données pour essayer de construire au moins une séquence de règles menant des prédicats à la question posée ou à sa négation.

Un tel programme définit ainsi ce qu’on appelle un «système logique» (deductive system), ou simplement « une logique », au sens de la logique mathématique. Son interpréteur s’appelle un « moteur d’inférence ».

Pour que ce moteur puisse être conçu, pour qu’il existe un algorithme capable de déduire une réponse à la question à partir de la base de connaissances, il faut imposer une forme particulière aux règles permises. En plus, il est préférable de se limiter à des situations où ce moteur peut être efficace ! Voilà pourquoi les langages logiques imposent une logique du premier ordre (first-order logic) — cette logique admet des prédicats écrits avec des variables simples, des opérateurs booléens (∧,∨,¬) et des quantificateurs (∀,∃) sur ces variables, mais pas de variables quantifiées représentant d’autres prédicats ou fonctions — et même souvent exclusivement des « clauses de Horn ».

Une clause de Horn est une clause, c’est-à-dire une expression booléenne disjonctive (i.e. formée de disjonctions (∨) de littéraux) qui contient au plus un littéral positif, les autres littéraux étant des négations.

La motivation provient de ce qu’une telle clause « q∨¬p1∨⋯∨¬pn » peut s’écrire « q ⫤ p1∧⋯∧pn », ce qui signifie « si p1 ... et pn, alors q », condition sous une forme bien comprise de tout programmeur !

On peut montrer que la combinaison de deux clauses de Horn est encore une clause de Horn (c’est un système stable) et que vérifier si une telle clause est vraie est un problème polynomial, même linéaire, par rapport au nombre de littéraux. De plus, un système logique défini à l’aide de clauses de Horn est équivalent à une machine de Turing universelle ; c’est donc un modèle parfait pour définir un langage de programmation.

Un langage logique est un langage pour lequel un programme est décrit par des clauses de Horn.

Parmi elles, les clauses positives (celles formées du seul littéral positif) énoncent les faits (facts), les axiomes ; les clauses strictes (definite clauses) (celles avec un seul littéral positif et au moins un négatif) définissent les règles de déduction (deduction rules) et les clauses négatives (sans littéral positif) représentent les questions posées (query) ou le but à atteindre (goal clauses).

Cette dernière catégorie se justifie du fait que « ¬q∨¬p1∨⋯∨¬pn » peut s’écrire « ∅ ⫤ q∧p1∧⋯∧pn », une preuve par l’absurde, puisqu’une clause vide « ∅ » est fausse. C’est le principe de la négation par l’échec (NAF ou Negation As Failure) : dans un langage logique, pour prouver « q » (i.e. affirmer qu’il est vrai), on montre qu’on ne peut déduire « ¬q » à partir des faits « p1...pn » selon les règles définies.

Il existe plusieurs exemples de langages logiques, mais celui qui est de loin le plus utilisé et qui constitue véritablement l’archétype de cette famille de langages, c’est Prolog.

Ce langage est une création française. Il a été imaginé vers 1971–72 par Alain Colmerauer et Philippe Roussel, chercheurs dans le domaine de l’intelligence artificielle, plus précisément en traductique, à l’université d’Aix-Marseille (à Luminy). Pour sa définition et sa mise en œuvre, ils se fondaient directement sur les travaux préalables du logicien et informaticien Robert Kowalski, à l’époque de l’université d’Édimbourg (Edinburgh), sur l’interprétation procédurale (et automatique) des clauses de Horn. Pour le décrire correctement, ils ont également utilisé les grammaires de van Wijngaarden, celles qui avaient si bien servi à la définition d’ALGOL68.

Durant l’été 1972, ils ont implanté un premier système Prolog en FORTRAN (ce qu’on appelle le Prolog I) qui eut rapidement du succès, malgré sa syntaxe complètement francophone et son efficacité très limitée... S’en suivirent de longs travaux intensifs en collaboration entre les deux équipes qui conduisirent à la conception d’un tout nouveau modèle de moteur d’inférence. En 1977, David Warren développa ce qu’on a appelé « le Prolog d’Édimbourg », mais ce n’est qu’en 1983 qu’il dévoila son modèle de machine abstraite, la WAM (Warren Abstract Machine), correspondant au Prolog II, qui le rendait aussi performant que les meilleurs LISP de l’époque. Il y eut ensuite le Prolog III en 1987, puis le Prolog IV en 1995–96, qui correspond à l’adoption de la norme ISO (revue en 2000) qui est le Prolog couramment utilisé aujourd’hui et qui accepte la programmation par contraintes et quelques autres extensions.

Comme Java, Prolog est en effet un langage compilé dont le bytecode produit est ensuite exécuté par une machine virtuelle, mais un programme peut aussi être compilé directement en code binaire natif. Ainsi, un système Prolog fonctionne normalement en deux temps : il compile les clauses qui vont constituer sa base de connaissances, puis il passe en mode « réponse aux questions » par le moteur d’inférence, a priori en mode interactif (il affiche le prompt « :- », puisqu’une question est une règle sans membre de gauche).

La syntaxe de Prolog est très simple. Ses termes sont des atomes, variables foncteurs ou structures :

  • Un atome est un nom (un identificateur alphanumérique commençant par une lettre minuscule), un nombre (en notation littérale), une chaîne de caractères (entre apostrophes) une structure vide (« {} » ou « [] ») ou, dans certaines circonstances, un opérateur, (graphic token).
  • Une variable (un identificateur commençant par une lettre capitale ou par « _ »).
  • Un foncteur (functor) ou terme composé (compound terms). Il s’agit d’une construction syntaxique, semblable à celle d’une fonction, composée d’un atome (le nom du foncteur) suivi immédiatement (i.e. sans espace), entre parenthèses, d’une suite d’autres termes séparés par une virgule (les paramètres du foncteur). Parmi eux peuvent figurer d’autres foncteurs, ce qui permet la récursivité fonctionnelle. L’arité d’un foncteur est évidemment significative.
  • Une structure, une liste : entre crochets, une suite de premiers atomes, puis une liste de suite précédée de «|» («[a,b|L]»), la suite pouvant être omise si elle est vide («[a,b]» est synonyme de « [a, b | []] ») ; elle peut aussi être écrite en « dotted notation » à l’aide du foncteur «.» («.(a,b)» est synonyme de «[a|b]»).

Bien sûr, une « variable » de Prolog n’a rien à voir avec le sens donné en programmation impérative. Il s’agit ici d’une variable au sens de la logique mathématique, d’une inconnue. Dans une règle (voir ci-dessous), une variable correspond à une quantification universelle « ∀ », c’est une variable libre du λ-calcul ; dans une question, elle permettra de rechercher une valeur conduisant à une vérité, si elle existe « ∃? ».

Un programme en Prolog est une suite de clauses : prédicat, règle ou question. Chaque clause se termine par un point « . ». Un fait ou prédicat s’énonce en Prolog par un foncteur, suivi directement du point : « vert(herbe). », ce qui veut vraisemblablement dire que «l’herbe est verte», mais c’est une interprétation purement humaine : il n’y a aucun sens inné dans les atomes (c’est comme en physique).

Un prédicat peut contenir des variables, ce qui énonce une « vérité générale ». Par exemple, la propriété « est le second élément d’une liste » peut s’énoncer comme le fait « sec([_, X | _], X). ». Ce foncteur a deux paramètres : une liste et une simple variable. On note l’usage de la variable « _ » indiquant une valeur quelconque ; le premier argument est une liste dont le premier élément est quelconque, le deuxième « X » et la suite est une liste quelconque (elle peut être vide).

Une règle s’écrit à l’aide du symbole « :- », également terminée par un point. Son membre de gauche est un foncteur qui sera vrai si tous les termes figurant dans membre de droite le sont ; ils sont séparés par une virgule « , » signifiant « et ». L’usage de variables permet d’écrire des règles générales : «mortel(X):-humain(X).», ce qui veut vraisemblablement dire que «tout humain est mortel», toujours en lecture anthropocentrique. De même,

'Ferrari'(X) :- rouge(X), voiture(X).

pourrait signifier que toutes les voitures rouges sont des Ferrari (on peut rêver en programmant).

Tant le membre de gauche que le membre de droite peuvent être vides. Ce second cas revient à un fait et on omet le « :- » ; le premier cas est une question.

Pour aider le programmeur, de nombreuses règles sont prédéfinies par le langage et, parmi elles, quelques prédicats : «true», «fail», «is», «+», etc.

Ainsi le célèbre programme « Hello, World! » s’écrit, de manière interactive, à l’aide des prédicats prédéfinis «write» et «nl» :

write('Hello, World!'), nl.

Et « halt. » permet de quitter l’interpréteur ; c’est plus propre que « CTRL-D ».

Ainsi, en combinant intelligemment les faits et les règles, on peut tout programmer (Prolog est Turing complet). Par exemple, tester si « y est la valeur absolue de x » pourrait s’écrire, en première tentative :

abs(X, Y) :- X < 0, Y is -X.
abs(X, X) :- X >= 0.

Ce n’est qu’une première version, incomplète (voir ci-dessous) et incorrecte, car elle ne s’assure pas que « X » est numérique, ce qui est imposé par tous les termes du membre de droite. Le foncteur prédéfini « is » impose l’égalité de ses deux paramètres, mais il évalue le second avant l’unification avec le premier.

Le nom des variables n’a pour portée que la règle courante ; elle ne s’étend donc pas d’une règle à l’autre. Ainsi, à la seconde ligne ci-dessus, on aurait pu utiliser un autre nom que « X » sans changer le sens du programme.

Ensuite, si l’on interroge par exemple par «abs(-1,1).» ou «abs(5,5).», il répond «yes», mais il répond «no» si l’on demande «abs(2,3).» ou «abs(-1,-1).» ou même «abs(1,a).» (puisque «a» est un atome quelconque différent de «1»). Par contre, «abs(a,1).» produit une erreur (voir correction ci-dessous).

Mais l’intérêt est qu’on peut faire « calculer » une bonne réponse en utilisant le moteur d’inférence et son mécanisme d’unification des variables au sein d’une clause : Prolog cherche à résoudre le problème,

donc à attribuer des valeurs aux variables qui conduisent à une vérité, y compris sur base d’autres variables. Ainsi, à la question

abs(-5, A).

il répond «A = 5», puis par un prompt «?». Si l’on répond par « ↵ », il s’arrête là, puis affiche «yes», car il est content de lui et très fier d’avoir trouvé une solution à votre problème ; mais si l’on répond « ; », il en recherche une autre et répondra « no » s’il n’en trouve plus, ce qui est le cas ici. En Prolog, « , » signifie « et », tandis que « ; » signifie « ou » inclusif.

Une telle recherche impose au moteur d’inférence d’effectuer de nombreux backtrackings pour attribuer des valeurs aux variables. Voilà pourquoi il existe un prédicat prédéfini très important : « ! » baptisé « cut » dont le sens est « n’allez pas plus loin, il n’y a plus d’autre voie utile ». Il permet non seulement d’éviter la recherche d’une autre réponse si elle n’existe pas, mais aussi d’éviter des erreurs parasites qui apparaîtraient dans des voies nécessairement fausses (cela rappelle le principe du SFINAE).

Tenant compte de cela, on peut définir un foncteur « abs(X, Y) » représentant « y = |x| », qui - si les deux variables sont numériques, teste simplement la relation ; - si X est numérique et Y une variable, calcule la seule valeur possible en utilisant le foncteur unaire prédéfini « abs » ; un « cut » est nécessaire ; - si Y est numérique et X une variable, trouve les deux solutions, sauf si Y est nul ; - est faux, mais sans erreur, dans toute autre situation.

abs(X, Y) :- number(X), Y is abs(X), !.
abs(X, Y) :- number(Y), Y > 0, X is -Y.
abs(X, Y) :- number(Y), Y >= 0, X is Y.

On voit que les choses se conçoivent et s’écrivent de façon relativement différente que dans un langage impératif. Pour programmer en Prolog, il faut penser comme un mathématicien, à l’aide de théorèmes (i.e. de propriétés vraies), plutôt que comme un informaticien qui raisonne sur des algorithmes.

Toutefois, si l’on veut que le programme soit efficace, c’est comme dans tout langage : il faut réfléchir aux structures internes, aux codages binaires et finalement, aux instructions qui seront effectivement exécutées par le processeur (ouf ! on redevient informaticien).

Si l’on tient compte de cet aspect — qui est loin d’être un détail ou une option ! — il faut bien connaître l’algorithme suivi par le moteur d’inférence et programmer en conséquence. De ce point de vue, Prolog n’est pas un langage logique pur, puisque l’ordre d’écriture des règles, ainsi que celui des termes dans le membre de droite ont un impact sur l’exécution du programme : il produira les réponses dans un ordre différent ou mettra beaucoup beaucoup beaucoup plus de temps pour répondre.

Par définition du langage, le moteur d’inférence de Prolog parcourt les règles dans leur ordre de définition et, au sein de chaque règle, il évalue les termes de gauche à droite. Cela correspond à un parcours de recherche descendante, appelé « SLD-resolution », au départ de la question posée, pour trouver d’abord les règles dont le membre de gauche correspond (même nom de foncteur et même arité) et tenter d’y attribuer une valeur aux variables éventuelles par unification en parcourant les autres règles pour chacune d’elles, et ainsi de suite. En cas d’échec, il entre en backtracking et tente une autre valeur pour la dernière substitution effectuée.

Ainsi, pour être efficace, il faut veiller à ce que les chemins menant à un échec soient les plus courts possibles (i.e. les moins profonds dans l’arbre de recherche) ou apparaissent après les bons (si l’on recherche une seule réponse). Par exemple, dans le programme ci-dessus, la première règle et son « cut » permet de capturer immédiatement les simples tests, comme « abs(-42,42). », sans explorer les deux autres règles. De même, placer la ligne 3 en dernière position fait qu’il ne recherche pas inutilement une deuxième solution à la question « abs(A,0). ».

Les exemples précédents correspondent à une exécution interactive : les questions sont encodées à l’exécution comme une donnée d’un programme. On peut également concevoir des programmes complets en utilisant le prédicat unaire prédéfini «initialization». Voici, en guise d’exemple, la résolution du problème des tours de Hanoï.

hanoi(Disques) :- integer(Disques), Disques > 0, hanoi_(Disques, 1, 2).
hanoi_(0, _, _) :- !.
hanoi_(Disques, Debut, Fin) :-
  Dm1 is Disques-1, Autre is 6-(Debut+Fin),
  hanoi_(Dm1, Debut, Autre),
  write([Debut, Fin]),
  hanoi_(Dm1, Autre, Fin).

:- initialization(hanoi(4)).

Ce n’est pas vraiment différent des autres langages, impératifs ou déclaratifs. Il faut toutefois utiliser des variables intermédiaires (« Dm1 », « Autre ») pour représenter des « sous-expressions » auxquelles elles sont unifiées (voir ligne 4). En fait, ce concept n’existe pas vraiment en Prolog, mais il existe plutôt quelques « evaluable functors » prédéfinis, comme l’est « abs » utilisé plus haut. Ainsi, « + » et « - » sont des noms de foncteurs évaluables binaires qui, de plus, peuvent s’écrire en notation infixe habituelle.

Autres langages déclaratifs

La programmation par contraintes (constraint programming) est un autre paradigme déclaratif important. On exprime le problème sous forme de variables (ou inconnues) et on décrit les relations entre elles qui doivent être respectées, ce qui réduit l’ensemble de leurs valeurs admissibles. Ces relations sont ce qu’on appelle les contraintes. Un programme est un ensemble de contraintes qui est soumis à un compilateur ou interpréteur qu’on appelle un « résolveur » (solver).

Il existe quelques exemples de résolveurs, généralement conçus pour un domaine de variables particulier (pour des valeurs binaires, on parle de SAT-solver), mais le plus souvent, il s’agit d’extensions ou de bibliothèques particulières de langages traditionnels. Il existe de telles bibliothèques en C++, en Java, etc. Mais Prolog, depuis sa version III, contient un ensemble de foncteurs prédéfinis permettant de réaliser réellement une programmation par contraintes.

Par ailleurs, les langages de balisage (markup language) sont une autre forme de programmation déclarative. Parmi eux, HTML ou XML sont certainement les exemples les plus connus. Un programme y est constitué de balises qui guident le comportement d’un interpréteur dont le rôle est de structurer, de produire ou d’afficher un document, de le mettre en page.

De manière générale, les langages déclaratifs connaissent une évolution — certains diraient une dénaturation — vers « plus d’impératif ». Parfois, cela se fait au sein du langage même (LISP a ainsi une fonction prédéfinie « progn » qui correspond à une évaluation séquentielle de ses paramètres), mais aussi par la création d’un nouveau langage dérivé : ainsi, XSLT est une extension impérative Turing complète de XML. Un autre exemple très connu dans le monde des sciences formelles est le langage « LaTeX », dont le moteur sous-jacent, celui du langage TeX originel, est purement impératif (c’est le langage d’assemblage d’une machine à pile virtuelle). Les langages de présentation (appelés « d’impression » à l’origine), tels PostScript ou PDF (Portable Document Format), appartiennent également à cette dernière catégorie.