Skip to content

MOOC NSI - fondamentaux.

Transcription de la vidéo

2.2.6.4 : Programmation logique

Parallèlement au renouveau des langages fonctionnels est née une approche fondamentalement différente de programmation déclarative avec la programmation logique.

Plutôt que de décrire une « formule » exprimant le calcul à effectuer, c'est-à-dire 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.

Pour répondre à cette « question », on doit fournir préalablement une « base de connaissances » constituée de faits connus et acceptés pour « vrais » (des prédicats) et des règles de déduction, de combinaison de ces prédicats pour établir de nouvelles vérités.

Un tel programme définit ainsi ce qu’on appelle un «système logique».

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), et même souvent exclusivement des « clauses de Horn » qui impose un format particulier.

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 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.

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, sur l’interprétation procédurale (et automatique) des clauses de Horn.

Un programme en Prolog est une suite de clauses : prédicat, règle ou question.

Pour plus d'explication sur Prolog et quelques exemples, je vous renvois à nouveau au support écrit.

Dans la classe des langages déclaratifs, citons également la programmation par contraintes.

On exprime le problème sous forme d'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 » (ou solver en anglais).

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 Python, C++, Java, etc.

Mais Prolog, depuis sa version III, intègre réellement la programmation par contraintes dans le langage.