- Prolog construit les programmes autour d’une seule clause et d’un modèle de données centré sur les termes, ce qui permet d’exprimer des relations calculables avec une petite grammaire
- L’approche déclarative consiste à décrire ce qui est vrai plutôt qu’une procédure d’exécution, si bien qu’une même relation peut servir au calcul, à la génération et à l’interrogation
- Le Prolog pur repose sur les clauses de Horn et la résolution, et l’effet de l’ajout de contraintes ou de clauses sur l’ensemble des solutions peut être prédit logiquement
- Le programme lui-même étant un term Prolog, il est facile de lire, analyser et transformer d’autres programmes, et aussi de créer des langages spécifiques à un domaine via des réécritures à la compilation
- Grâce à sa dynamique à l’exécution et à des mécanismes implicites comme la recherche, l’unification et la propagation de contraintes, il s’emploie dans des domaines très variés, du traitement du langage aux bases de données, à la vérification et à l’optimisation
Un petit langage fait de clauses et de termes
- Toutes les données de Prolog sont représentées sous forme de term Prolog
- L’élément central du langage est une clause, dont la forme de base est
Head :- Body.
- Cela signifie que si Body est vrai, alors Head est vrai
- L’opérateur infixe
(:-)/2 représente une flèche ← orientée de droite à gauche
- Si Head est toujours vrai,
:- Body peut être omis
- Cette seule structure suffit pour écrire un premier programme Prolog utile
- Tout calcul connu peut être décrit avec de telles clauses, ce qui fait de Prolog un langage Turing-complet
- Une machine de Turing peut être implémentée en décrivant par clauses la relation entre l’état courant, le symbole sous la tête de lecture du ruban, etc., et l’état suivant
- Un exemple d’implémentation est disponible dans turing.pl
Programmation déclarative et pensée centrée sur les relations
- Prolog est un langage déclaratif qui exprime ce qui est vrai au sujet des solutions recherchées, plutôt que la manière de les trouver
- Cette nature permet des spécifications concises, claires et générales
- La relation entre une liste et sa longueur peut être décrite ainsi
list_length([], 0).
list_length([_|Ls], N) :-
N #> 0,
N #= N0 + 1,
list_length(Ls, N0).
- Dans certains systèmes Prolog, il faut inclure une bibliothèque distincte pour utiliser l’arithmétique entière déclarative
- Cette définition peut se lire déclarativement ainsi
- la longueur de la liste vide
[] est 0
- si la longueur de
Ls est N0 et que N vaut N0 + 1, alors la longueur de [_|Ls] est N, et cette relation n’est vraie que si N est supérieur à 0
- Une même relation peut être utilisée dans plusieurs modes
list_length("abc", L) renvoie L = 3list_length(Ls, 3) trouve une liste Ls = [_A,_B,_C] de longueur 3list_length(Ls, L) énumère des réponses générales, de la liste vide aux listes de longueur croissante
- Prolog signale en général toutes les réponses par backtracking
length/2 figure dans l’ébauche de Prologue for Prolog et est fourni comme prédicat intégré de même sens dans presque toutes les implémentations Prolog
Prolog comme langage de programmation logique
- La catégorie des langages déclaratifs comprend les langages de programmation fonctionnelle et les langages de programmation logique
- Une fonction est un cas particulier de relation, et la programmation fonctionnelle peut être vue comme une forme restreinte de programmation logique
- Prolog est enraciné dans la logique
- Un programme Prolog pur est constitué d’un ensemble de clauses de Horn
- Son exécution peut être considérée comme un cas particulier de résolution
- Grâce à ce lien avec la logique formelle, on peut appliquer un débogage déclaratif fondé sur les propriétés logiques du programme
- lorsqu’on ajoute des contraintes, l’ensemble des solutions ne peut que se réduire
- lorsqu’on ajoute des clauses, l’ensemble des solutions ne peut que s’étendre
- cette propriété des programmes Prolog purs s’appelle la monotonie
- Le système GUPU d’Ulrich Neumerkel est un exemple d’application de ces idées
Une propriété homoiconique qui traite les programmes comme des données
- Un programme Prolog est aussi un term Prolog valide
- Grâce à cette propriété, un programme Prolog peut facilement analyser, transformer et interpréter d’autres programmes Prolog
- Le prédicat intégré
read/1 permet de lire des termes Prolog, et donc aussi des clauses Prolog
- Prolog dispose d’un puissant mécanisme de macros qui réécrit les programmes à la compilation
- cela permet d’implémenter des langages spécifiques à un domaine qui expriment le travail de manière plus naturelle
list_length(Ls,N) et N#>0 ont une apparence notationnelle différente, mais ne sont que des formes plus lisibles rendues possibles par les opérateurs préfixés, infixés et postfixés de Prolog
- par exemple, le term Prolog
+(a,b) peut s’écrire a+b en notation opératoire
- comme la syntaxe abstraite est uniforme, tous les termes Prolog peuvent être lus et traités quelle que soit leur forme d’écriture
- Il est possible de définir dynamiquement des opérateurs personnalisés adaptés à un usage spécifique
Dynamique à l’exécution et extensibilité
- Un programme Prolog peut facilement être généré, appelé et modifié à l’exécution
- Cette propriété renforce son expressivité et permet d’implémenter des prédicats d’ordre supérieur prenant d’autres prédicats en argument
- Il est aussi possible d’implémenter des techniques très dynamiques comme l’adaptive parsing
- Prolog est bien adapté à l’écriture de programmes extensibles par des règles personnalisées fournies par d’autres programmeurs ou par les utilisateurs eux-mêmes
- Proloxy et Gerrit Code Review illustrent cette approche, avec des exigences décrites sous forme de règles Prolog lisibles et flexibles
- Un interpréteur pour Prolog pur peut être défini en deux lignes de code Prolog
- Le sujet est traité dans A Couple of Meta-interpreters in Prolog
Une large palette d’usages et des mécanismes implicites
- Le caractère relationnel de Prolog rend les programmes souples et généraux
- Cette nature joue un rôle important dans la représentation des connaissances pour le traitement du langage et les bases de données
- Les systèmes Prolog modernes fournissent les capacités nécessaires, des simples logic puzzles jusqu’aux applications à grande échelle
- La polyvalence et la puissance de Prolog reposent sur des mécanismes implicites comme la recherche, l’unification, l’indexation des arguments et la propagation de contraintes
- Les développeurs peuvent s’appuyer sur ces mécanismes pour déléguer une grande partie du travail au moteur Prolog
1 commentaires
Avis sur Hacker News
Je partage presque entièrement ce sentiment. J’ai utilisé Prolog dans trois cours d’IA à l’université, et nous avons couvert quasiment tout « AI: A Modern Approach » ainsi que la programmation en Prolog : c’était vraiment une expérience qui tordait la façon de penser.
Il me fallait toujours un échauffement pour me remettre à penser à la Prolog, et pendant ce semestre, j’écrivais même dans d’autres langages un code spaghetti horriblement prologuesque. À l’époque, le plus gros inconvénient était la difficulté d’interopérabilité avec le reste : il fallait embarquer Prolog dans la JVM, utiliser des implémentations peu fournies, ou s’appuyer sur des bindings C. C’est excellent pour certaines tâches, notamment les problèmes de satisfaction de contraintes, mais dès qu’on y mêle des choses comme une interface utilisateur ou l’accès au système de fichiers, ça ne me semblait pas adapté. À ce moment-là, SWI était aussi à la traîne et on utilisait des solutions propriétaires comme Sicstus ; la dernière fois que j’ai vérifié, SWI avait rattrapé les implémentations propriétaires, donc aujourd’hui je choisirais probablement SWI. L’examen de Prolog était le plus terrifiant que j’aie connu à l’université : 60 minutes de live coding sur 3 exercices, suivies d’un oral. Mais je m’en suis bien sorti : j’ai passé 40 minutes sur l’exercice facile, puis résolu les deux autres en quelques minutes. Dans le cours suivant, le devoir qui consistait à implémenter un agent joueur pour le faire s’affronter dans un tournoi était amusant, et « The Art of Prolog » ainsi que « The Craft of Prolog » comptent parmi les meilleurs livres de programmation que j’aie lus.
The Craft of Prolog est aussi excellent, mais il est très spécialisé dans la programmation système avec d’anciens systèmes Prolog, et certains chapitres sont aujourd’hui datés. Beaucoup d’idées de Prolog survivent dans la programmation par ensembles de réponses et dans Datalog, et Datalog est excellent pour construire des analyseurs statiques modernes : https://arxiv.org/abs/2012.10086
Je me demande soudain comment les chatbots s’en sortent avec Prolog. En ont-ils vu suffisamment ? Peuvent-ils raisonner de cette façon ?
Prolog est génial, et il vaut la peine d’être appris ne serait-ce que pour le plaisir de découvrir un paradigme de programmation inhabituel. Beaucoup de concepts s’y expriment d’une manière complètement différente, et une fois que le paradigme fait tilt, les choses deviennent au contraire bien plus simples.
Par exemple, en Prolog, on ne manipule généralement pas directement les collections : on fournit des informations sur ce que sont les éléments de la collection, puis on laisse l’implémentation trouver le reste. Dessiner un arbre de dépendances peut se faire avec seulement trois règles : ce que sont les entités, comment déterminer la relation entre les entités X et Y, et comment la représenter. Cela dit, comme c’est difficile, il est compliqué de convaincre les gens de l’apprendre ou de l’utiliser, et je n’ai pas encore trouvé de façon de l’intégrer proprement dans d’autres applis. Je sais que la FFI est une option, mais je ne suis pas convaincu que ce soit prêt pour la production. Ces derniers mois, j’ai cherché des alternatives à Prolog plus proches de la « production », mais LispWorks ou Franz Allegro CL sont trop chers et pas assez faciles à intégrer. Si quelqu’un connaît des exemples d’intégration réussie de Prolog dans des logiciels modernes, ça m’intéresse vraiment. XPCE ne fonctionne pas sur Mac, donc je cherche aussi une solution GUI. Swish vaut aussi le détour comme notebook en ligne : https://swish.swi-prolog.org
J’ai entendu dire que cela a désormais été retiré, donc ce n’est pas un exemple « moderne », mais c’est un très bel exemple d’application de Prolog. Le fil part de https://news.ycombinator.com/item?id=36821871 vers https://web.archive.org/web/20030218034509/http://www.resear..., et vaut vraiment la lecture. Lien associé : https://news.ycombinator.com/item?id=14046420
Les deux fonctionnaient plutôt bien, mais les cas d’usage étaient limités. Mon expérience de Prolog à l’université était amusante, mais je ne voudrais pas l’utiliser pour autre chose qu’un problème intrinsèquement de forme Prolog. Dès qu’on commence à implémenter quelque chose d’un peu complexe, les abstractions fuient de partout, et on a davantage l’impression de se battre contre l’algorithme de backtracking que de profiter des forces du langage.
Racklog est une intégration de la programmation logique à la Prolog dans Racket, et « intégration » signifie ici qu’on ne perd pas Racket. On peut écrire des fragments de code de style Prolog côte à côte avec du code Racket normal. Il contient la plupart des fonctionnalités de Prolog, y compris la métalogique et les prédicats de « collections » de second ordre, en n’excluant que ce qui peut être fait plus facilement et plus efficacement avec des sous-expressions Racket. https://docs.racket-lang.org/racklog/index.html Racket a aussi une GUI, et en pratique presque tout ce dont on peut avoir besoin.
CUE s’intègre beaucoup plus facilement dans les workflows existants, ce qui permet de transformer les avantages de la programmation logique en quelque chose de pratique. https://cuelang.org | https://cuetorials.com
Pendant plusieurs années, en développant en C++ un logiciel d’optimisation de chaîne d’approvisionnement, j’ai utilisé le logiciel de propagation de contraintes d’ILOG, Solver, aujourd’hui propriété d’IBM. À l’époque, j’avais aussi évalué BinProlog : il intégrait la propagation d’intervalles, se compilait en x86 natif et son interopérabilité FFI était correcte
Malgré tout, il semble qu’il ait fini par être éclipsé par SWI Prolog et la toolchain GNU. Pour l’interface graphique, il faut sans doute voir ça comme un tout autre domaine de spécialisation ; nous utilisions notre propre moteur de rendu de canvas en C++ et un horrible outil de développement 4GL intégré appelé « 4D » ou « Fourth Dimension ». https://www.tomshw.it/data/images/2/0/4/3/infor-advanced-sch...
Le langage Shen de Mark Tarver contient une implémentation complète de Prolog : https://shenlanguage.org/SD/Prolog.html
Le chapitre correspondant de The Book of Shen existe aussi : https://shenlanguage.org/TBoS/tbos_359.html Tarver a également écrit deux livres accompagnés de logiciels sur la programmation logique. Logic, Proof and Computation : https://shenlanguage.org/lpc.html Programming the Logic Lab : https://shenlanguage.org/logiclab.html
Le pattern matching, la vérification de types optionnelle et le Prolog intégré sont impressionnants. Son créateur a été en partie mis à l’écart de la communauté plus large à cause de son manque de diplomatie, mais il est brillant, et l’adoption est restée de niche et à la pointe. Si une organisation comme Mozilla avait été derrière, le langage aurait sans doute eu un attrait beaucoup plus grand public. Les présentations de @deech datent maintenant, mais elles restent excellentes et pertinentes : https://www.youtube.com/watch?v=lMcRBdSdO_U, https://www.youtube.com/watch?v=BUJNyHAeAc8 Cela dit, je suis un fan fervent d’APL/J/BQN, donc à prendre avec ce biais en tête
Je me souviens avoir appris Prolog il y a environ 25 ans, dans un cursus IA + informatique. On l’utilisait beaucoup dans le module de traitement automatique du langage naturel
Au début, c’était frustrant et agaçant, mais une fois qu’on s’y habituait, c’était étonnamment amusant ; comme il n’y avait que la récursion pour faire des itérations, c’était aussi une excellente introduction à la récursion
À l’université, nous apprenions Prolog surtout avec des mathématiciens qui n’utilisaient pratiquement que ce type de langage, et pour eux Prolog était une manière de penser tout à fait naturelle. À l’inverse, pour des étudiants qui avaient surtout utilisé des langages procéduraux, c’était déroutant et frustrant, et tout le monde essayait d’utiliser Prolog comme un autre langage, ce qui finissait mal. Ce n’est qu’au troisième ou quatrième cours utilisant Prolog, après avoir étudié les algorithmes sous-jacents, que la bonne manière de s’en servir m’est entrée dans la tête. Plus tard, j’ai aidé un étudiant de licence qui galérait avec Prolog : l’essentiel n’était pas d’essayer de faire se comporter Prolog comme les langages qu’il connaissait déjà, mais de changer sa manière de raisonner sur la résolution de problèmes pour l’adapter au monde de Prolog. Après une assez longue discussion, il a vraiment eu le déclic, et il a brillamment terminé son devoir
Mais une fois que le nouveau paradigme s’est emboîté dans ma tête, j’ai vraiment fini par l’adorer. Rien que pour ce moment de déclic, le cours en valait largement la peine
Les autres commentaires parlent de Prolog en général, mais je veux dire que The Power of Prolog est une très bonne série de tutoriels
Les vidéos valent aussi le détour, et Markus sait bien retenir l’intérêt des spectateurs et des lecteurs
Grâce à cette vidéo, j’ai commencé à voir Prolog comme un mouvement actuel et progressiste de la programmation
Prolog est un beau langage. J’ai écrit des dizaines de milliers de lignes pour du raisonnement mathématique, du raisonnement à base de règles, etc. ; dans ces domaines, il convient parfaitement et le travail est énormément plaisant
Pour d’autres types d’applications, il y a deux problèmes. D’abord, le paradigme est tellement différent qu’il s’intègre mal avec les bibliothèques et les autres langages. Ensuite, créer une vraie interface graphique est presque impossible, là encore parce que cela ne colle pas au paradigme
En général, côté Prolog, l’interface externe ressemble à un prédicat dont tous les arguments sont instanciés, et côté externe, on interagit avec Prolog comme avec une base de données SQL. On envoie une requête, on la décompose, on demande davantage de solutions ou on pilote le backtracking. On peut dire que ce type d’interaction n’est pas « intéressant », mais c’est parce que les bibliothèques n’exploitent pas vraiment les fonctionnalités utiles de Prolog qu’elles fonctionnent ainsi. Si on le souhaite, on peut créer une couche d’interopérabilité plus épaisse, regrouper plusieurs fonctions de bibliothèque derrière une interface de prédicat unique côté Prolog, puis appeler telle ou telle sous-routine selon le mode d’instanciation des arguments. Mais ce n’est pas très différent du fait d’exposer une bibliothèque C à un langage orienté objet comme Python en regroupant plusieurs fonctions C comme accesseurs de propriétés ou méthodes d’une structure de données
J’utilise beaucoup Prolog pour l’analyse de données. Au début, il faut passer par une phase où l’on se force à tout faire autant que possible en Prolog pour comprendre comment transformer les questions en problèmes symboliques
C’est parce que Prolog prend très mal en charge le calcul scientifique et la manipulation de chaînes. Une fois passé ce cap, les solutions en Prolog sont souvent plus élégantes que la meilleure alternative suivante. Et comme c’est un paradigme logique, cela vaut la peine de prendre le temps de comprendre comment preuve par négation + unification = programmation logique. C’est de loin le langage de programmation qui m’a le plus ouvert l’esprit parmi ceux que j’ai appris.
Le Prolog standard n’intègre pas les expressions régulières par défaut, mais les implémentations populaires fournissent généralement une bibliothèque pour cela. Si je devais faire beaucoup de traitement de chaînes et choisir entre C et Prolog, je choisirais clairement Prolog. Entre Python et Prolog, cela dépendrait de la tâche.
Quoi qu’il en soit, c’est un excellent site, et je suis content que ce sujet revienne.
Comme j’avais déjà écrit un solveur en Java, j’ai essayé de porter ce code en Prolog, mais ça ne marchait pas du tout. J’ai fini par repartir de zéro et écrire un simple code Prolog qui vérifiait si un Sudoku était valide, puis je me suis rendu compte qu’en exécutant ces prédicats, on pouvait aussi résoudre le Sudoku. J’ai ainsi terminé le solveur en moins de 10 lignes. C’était un vrai moment Eurêka, et Prolog est très puissant, mais injustement sous-utilisé dans le monde professionnel. Heureusement, j’ai eu l’occasion de travailler un peu avec Datalog et OWL.