Prologue - Prolog

Prolog est un langage de programmation logique associé à l' intelligence artificielle et à la linguistique informatique .

Prolog a ses racines dans la logique du premier ordre , une logique formelle , et contrairement à de nombreux autres langages de programmation , Prolog se veut principalement un langage de programmation déclaratif : la logique du programme est exprimée en termes de relations , représentées sous forme de faits et de règles . Un calcul est lancé en exécutant une requête sur ces relations.

Le langage a été développé et mis en œuvre à Marseille, en France, en 1972 par Alain Colmerauer avec Philippe Roussel, sur la base de l' interprétation procédurale de Robert Kowalski des clauses de Horn .

Prolog a été l'un des premiers langages de programmation logique et reste le langage le plus populaire aujourd'hui, avec plusieurs implémentations gratuites et commerciales disponibles. Le langage a été utilisé pour la démonstration de théorèmes , les systèmes experts , la réécriture de termes , les systèmes de types et la planification automatisée , ainsi que son domaine d'utilisation initial, le traitement du langage naturel . Les environnements Prolog modernes prennent en charge la création d' interfaces utilisateur graphiques , ainsi que d'applications administratives et en réseau.

Prolog est bien adapté aux tâches spécifiques qui bénéficient de requêtes logiques basées sur des règles telles que la recherche dans les bases de données , les systèmes de commande vocale et les modèles de remplissage.

Syntaxe et sémantique

Dans Prolog, la logique du programme est exprimée en termes de relations, et un calcul est lancé en exécutant une requête sur ces relations. Les relations et les requêtes sont construites en utilisant le type de données unique de Prolog, le terme . Les relations sont définies par des clauses . Étant donné une requête, le moteur Prolog tente de trouver une réfutation de résolution de la requête niée. Si la requête niée peut être réfutée, c'est-à-dire qu'une instanciation pour toutes les variables libres est trouvée qui rend fausse l'union des clauses et l'ensemble singleton constitué de la requête niée, il s'ensuit que la requête d'origine, avec l'instanciation trouvée appliquée, est un conséquence logique du programme. Cela rend Prolog (et d'autres langages de programmation logique) particulièrement utile pour les applications de bases de données, de mathématiques symboliques et d'analyse de langage. Étant donné que Prolog autorise les prédicats impurs , la vérification de la valeur de vérité de certains prédicats spéciaux peut avoir des effets secondaires délibérés , tels que l'impression d'une valeur à l'écran. Pour cette raison, le programmeur est autorisé à utiliser une certaine quantité de programmation impérative conventionnelle lorsque le paradigme logique n'est pas pratique. Il possède un sous-ensemble purement logique, appelé "pur Prolog", ainsi qu'un certain nombre de fonctionnalités extralogiques.

Types de données

Le type de données unique de Prolog est le terme . Les termes sont soit des atomes , des nombres , des variables ou des termes composés .

• Un atome est un nom à usage général sans signification inhérente. Des exemples d'atomes comprennent x, red, 'Taco', et 'some atom'.
• Les nombres peuvent être des flottants ou des entiers . Les systèmes Prolog compatibles avec la norme ISO peuvent vérifier le drapeau Prolog "limité". La plupart des principaux systèmes Prolog prennent en charge les nombres entiers de longueur arbitraire.
• Les variables sont désignées par une chaîne composée de lettres, de chiffres et de caractères de soulignement, et commençant par une lettre majuscule ou un trait de soulignement. Les variables ressemblent étroitement aux variables en logique en ce qu'elles sont des espaces réservés pour des termes arbitraires.
• Un terme composé est composé d'un atome appelé « foncteur » et d'un certain nombre d' « arguments », qui sont à nouveau des termes. Les termes composés sont généralement écrits sous la forme d'un foncteur suivi d'une liste de termes d'argument séparés par des virgules, qui est contenue entre parenthèses. Le nombre d'arguments est appelé l' arité du terme . Un atome peut être considéré comme un terme composé d' arité zéro. Un exemple de terme composé est person_friends(zelda,[tom,jim]).

Cas particuliers de termes composés :

• Une liste est une collection ordonnée de termes. Il est indiqué par des crochets avec les termes séparés par des virgules, ou dans le cas de la liste vide, par []. Par exemple, [1,2,3]ou [red,green,blue].
• Chaînes : Une séquence de caractères entourée de guillemets équivaut soit à une liste de codes de caractères (numériques), soit à une liste de caractères (atomes de longueur 1), soit à un atome selon la valeur du drapeau Prolog double_quotes. Par exemple, "to be, or not to be".

ISO Prolog fournit les atom/1, number/1, integer/1et float/1prédicats pour vérification de type .

Règles et faits

Les programmes Prolog décrivent des relations, définies au moyen de clauses. Pure Prolog est limité aux clauses de Horn . Il existe deux types de clauses : les faits et les règles. Une règle est de la forme

Head :- Body.

et est lu comme "La tête est vraie si le corps est vrai". Le corps d'une règle se compose d'appels à des prédicats, appelés objectifs de la règle . L' opérateur logique intégré (c'est-à- ,/2dire un opérateur d' arité 2 avec le nom ,) dénote une conjonction d'objectifs et ;/2dénote une disjonction . Les conjonctions et disjonctions ne peuvent apparaître que dans le corps, pas dans la tête d'une règle.

Les clauses avec des corps vides sont appelées faits . Un exemple de fait est :

cat(crookshanks).

ce qui équivaut à la règle :

cat(crookshanks) :- true.

Le prédicat intégré true/0est toujours vrai.

Compte tenu du fait ci-dessus, on peut demander :

Est-ce que crookshanks est un chat ?

 ?- cat(crookshanks).
 Yes

que sont les chats ?

 ?- cat(X).
 X = crookshanks

Les clauses avec des corps sont appelées règles . Voici un exemple de règle :

animal(X) :- cat(X).

Si nous ajoutons cette règle et demandons quelles choses sont des animaux ?

 ?- animal(X).
 X = crookshanks

En raison de la nature relationnelle de nombreux prédicats intégrés, ils peuvent généralement être utilisés dans plusieurs directions. Par exemple, length/2peut être utilisé pour déterminer la longueur d'une liste ( length(List, L), étant donné une liste List) ainsi que pour générer un squelette de liste d'une longueur donnée ( length(X, 5)), et aussi pour générer à la fois des squelettes de liste et leurs longueurs ensemble ( length(X, L)). De même, append/3peut être utilisé à la fois pour ajouter deux listes (listes append(ListA, ListB, X)données ListAet ListB) ainsi que pour diviser une liste donnée en parties ( append(X, Y, List), étant donné une liste List). Pour cette raison, un ensemble relativement petit de prédicats de bibliothèque suffit pour de nombreux programmes Prolog.

En tant que langage à usage général, Prolog fournit également divers prédicats intégrés pour effectuer des activités de routine telles que l' entrée/sortie , en utilisant des graphiques et en communiquant autrement avec le système d'exploitation. Ces prédicats n'ont pas de sens relationnel et ne sont utiles que pour les effets secondaires qu'ils présentent sur le système. Par exemple, le prédicat write/1affiche un terme à l'écran.

Exécution

L'exécution d'un programme Prolog est initiée par l'affichage par l'utilisateur d'un objectif unique, appelé la requête. Logiquement, le moteur Prolog essaie de trouver une réfutation de résolution de la requête niée. La méthode de résolution utilisée par Prolog est appelée résolution SLD . Si la requête niée peut être réfutée, il s'ensuit que la requête, avec les liaisons de variables appropriées en place, est une conséquence logique du programme. Dans ce cas, toutes les liaisons de variables générées sont signalées à l'utilisateur et la requête est censée avoir réussi. Sur le plan opérationnel, la stratégie d'exécution de Prolog peut être considérée comme une généralisation des appels de fonction dans d'autres langages, une différence étant que plusieurs têtes de clause peuvent correspondre à un appel donné. Dans ce cas, le système crée un point de choix, unifie le but avec la tête de clause de la première alternative et continue avec les buts de cette première alternative. Si un objectif échoue au cours de l'exécution du programme, toutes les liaisons de variables effectuées depuis la création du point de choix le plus récent sont annulées et l'exécution se poursuit avec l'alternative suivante de ce point de choix. Cette stratégie d'exécution est appelée retour en arrière chronologique . Par exemple:

mother_child(trude, sally).
 
father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).
 
sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).
 
parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

Cela a pour résultat que la requête suivante est évaluée comme vraie :

 ?- sibling(sally, erica).
 Yes

Ceci est obtenu comme suit : Initialement, la seule tête de clause correspondante pour la requête sibling(sally, erica)est la première, donc prouver la requête équivaut à prouver le corps de cette clause avec les liaisons de variables appropriées en place, c'est-à-dire la conjonction (parent_child(Z,sally), parent_child(Z,erica)). Le prochain but à prouver est celui le plus à gauche de cette conjonction, c'est-à-dire parent_child(Z, sally). Deux têtes de clause correspondent à cet objectif. Le système crée un point de choix et essaie la première alternative, dont le corps est father_child(Z, sally). Ce but peut être prouvé en utilisant le fait father_child(tom, sally), donc la liaison Z = tomest générée, et le prochain but à prouver est la deuxième partie de la conjonction ci-dessus : parent_child(tom, erica). Encore une fois, cela peut être prouvé par le fait correspondant. Comme tous les objectifs peuvent être prouvés, la requête réussit. Étant donné que la requête ne contenait aucune variable, aucune liaison n'est signalée à l'utilisateur. Une requête avec des variables, comme :

?- father_child(Father, Child).

énumère toutes les réponses valides lors du retour en arrière.

Notez qu'avec le code comme indiqué ci-dessus, la requête ?- sibling(sally, sally).réussit également. On insérerait des objectifs supplémentaires pour décrire les restrictions pertinentes, si désiré.

Boucles et récursivité

Des algorithmes itératifs peuvent être implémentés au moyen de prédicats récursifs.

Négation

Le prédicat Prolog intégré \+/1fournit la négation en tant qu'échec , ce qui permet un raisonnement non monotone . Le but \+ illegal(X)dans la règle

legal(X) :- \+ illegal(X).

est évalué comme suit : Prolog tente de prouver illegal(X). Si une preuve de cet objectif peut être trouvée, l'objectif initial (c'est-à-dire \+ illegal(X)) échoue. Si aucune preuve ne peut être trouvée, l'objectif initial réussit. Par conséquent, l' \+/1opérateur de préfixe est appelé opérateur "non prouvable", car la requête ?- \+ Goal.réussit si Goal n'est pas prouvable. Ce type de négation est valable si son argument est "ground" (c'est-à-dire qu'il ne contient aucune variable). La solidité est perdue si l'argument contient des variables et que la procédure de preuve est terminée. En particulier, la requête ?- legal(X).ne peut plus être utilisée pour énumérer toutes les choses qui sont légales.

Programmation en Prolog

Dans Prolog, le chargement du code est appelé consultation . Prolog peut être utilisé de manière interactive en entrant des requêtes à l'invite Prolog ?-. S'il n'y a pas de solution, Prolog écrit no. Si une solution existe, elle est imprimée. S'il existe plusieurs solutions à la requête, celles-ci peuvent être demandées en entrant un point-virgule ;. Il existe des directives sur les bonnes pratiques de programmation pour améliorer l'efficacité, la lisibilité et la maintenabilité du code.

Voici quelques exemples de programmes écrits en Prolog.

Bonjour le monde

Un exemple de requête :

?- write('Hello World!'), nl.
Hello World!
true.

?-

Optimisation du compilateur

Tout calcul peut être exprimé de manière déclarative comme une séquence de transitions d'état. À titre d'exemple, un compilateur d'optimisation avec trois passes d'optimisation pourrait être implémenté en tant que relation entre un programme initial et sa forme optimisée :

program_optimized(Prog0, Prog) :-
    optimization_pass_1(Prog0, Prog1),
    optimization_pass_2(Prog1, Prog2),
    optimization_pass_3(Prog2, Prog).

ou de manière équivalente en utilisant la notation DCG :

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

Tri rapide

Le quicksort algorithme de tri, concernant une liste à sa version triée:

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> [].
quicksort([X|Xs]) -->
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

Modèles de conception de Prolog

Un modèle de conception est une solution générale réutilisable à un problème courant dans la conception de logiciels . Certains modèles de conception dans Prolog sont des squelettes, des techniques, des clichés, des schémas de programme, des schémas de description logique et une programmation d'ordre supérieur .

Programmation d'ordre supérieur

Un prédicat d'ordre supérieur est un prédicat qui prend un ou plusieurs autres prédicats comme arguments. Bien que la prise en charge de la programmation d'ordre supérieur fasse sortir Prolog du domaine de la logique du premier ordre, ce qui ne permet pas la quantification sur des prédicats, ISO Prolog possède désormais des prédicats d'ordre supérieur intégrés tels que call/1, call/2, call/3, findall/3, setof/3, et bagof/3. De plus, étant donné que des objectifs Prolog arbitraires peuvent être construits et évalués au moment de l'exécution, il est facile d'écrire des prédicats d'ordre supérieur comme maplist/2, qui applique un prédicat arbitraire à chaque membre d'une liste donnée, et sublist/3, qui filtre les éléments qui satisfont un prédicat donné , permettant également le curry .

Pour convertir les solutions de la représentation temporelle (substitutions de réponses lors du retour en arrière) en représentation spatiale (termes), Prolog dispose de divers prédicats toutes solutions qui collectent toutes les substitutions de réponses d'une requête donnée dans une liste. Cela peut être utilisé pour la compréhension de la liste . Par exemple, les nombres parfaits sont égaux à la somme de leurs diviseurs propres :

 perfect(N) :-
     between(1, inf, N), U is N // 2,
     findall(D, (between(1,U,D), N mod D =:= 0), Ds),
     sumlist(Ds, N).

Cela peut être utilisé pour énumérer des nombres parfaits, et aussi pour vérifier si un nombre est parfait.

Autre exemple, le prédicat maplistapplique un prédicat Pà toutes les positions correspondantes dans une paire de listes :

maplist(_, [], []).
maplist(P, [X|Xs], [Y|Ys]) :-
   call(P, X, Y),
   maplist(P, Xs, Ys).

Quand Pest un prédicat qui, pour tout X, P(X,Y)s'unifie Yavec une seule valeur unique, maplist(P, Xs, Ys)équivaut à appliquer la fonction map dans la programmation fonctionnelle en tant que Ys = map(Function, Xs).

Le style de programmation d'ordre supérieur dans Prolog a été mis au point dans HiLog et λProlog .

Modules

Pour la programmation dans les grands , Prolog propose un système de modules . Le système de modules est normalisé par l'ISO. Cependant, tous les compilateurs Prolog ne prennent pas en charge les modules et il existe des problèmes de compatibilité entre les systèmes de modules des principaux compilateurs Prolog. Par conséquent, les modules écrits sur un compilateur Prolog ne fonctionneront pas nécessairement sur les autres.

Analyse

Il existe une notation spéciale appelée grammaires à clauses définies (DCG). Une règle définie via -->/2au lieu de :-/2est développée par le préprocesseur ( expand_term/2, une fonction analogue aux macros dans d'autres langages) selon quelques règles de réécriture simples, résultant en des clauses Prolog ordinaires. Plus particulièrement, la réécriture dote le prédicat de deux arguments supplémentaires, qui peuvent être utilisés pour enchaîner implicitement l'état, de manière analogue aux monades dans d'autres langues. Les DCG sont souvent utilisés pour écrire des analyseurs syntaxiques ou des générateurs de listes, car ils fournissent également une interface pratique pour les listes de différences.

Méta-interprètes et réflexion

Prolog est un langage homoiconique et offre de nombreuses facilités de réflexion . Sa stratégie d'exécution implicite permet d'écrire un évaluateur méta-circulaire concis (appelé aussi méta-interprète ) pour du code Prolog pur :

solve(true).
solve((Subgoal1,Subgoal2)) :- 
    solve(Subgoal1),
    solve(Subgoal2).
solve(Head) :- 
    clause(Head, Body),
    solve(Body).

où truereprésente une conjonction vide et clause(Head, Body)s'unifie avec les clauses de la base de données de la forme Head :- Body.

Étant donné que les programmes Prolog sont eux-mêmes des séquences de termes Prolog ( :-/2est un opérateur infixe ) qui sont facilement lus et inspectés à l'aide de mécanismes intégrés (comme read/1), il est possible d'écrire des interpréteurs personnalisés qui augmentent Prolog avec des fonctionnalités spécifiques au domaine. Par exemple, Sterling et Shapiro présentent un méta-interprète qui effectue un raisonnement avec incertitude, reproduit ici avec de légères modifications :

solve(true, 1) :- !.
solve((Subgoal1,Subgoal2), Certainty) :-
    !,
    solve(Subgoal1, Certainty1),
    solve(Subgoal2, Certainty2),
    Certainty is min(Certainty1, Certainty2).
solve(Goal, 1) :-
    builtin(Goal), !, 
    Goal.
solve(Head, Certainty) :-
    clause_cf(Head, Body, Certainty1),
    solve(Body, Certainty2),
    Certainty is Certainty1 * Certainty2.

Cet interpréteur utilise une table de prédicats Prolog intégrés de la forme

builtin(A is B).
builtin(read(X)).
% etc.

et les clauses représentées par clause_cf(Head, Body, Certainty). Compte tenu de ceux-ci, il peut être appelé solve(Goal, Certainty)à exécuter Goalet à obtenir une mesure de certitude quant au résultat.

Complétude de Turing

Pure Prolog est basé sur un sous-ensemble de la logique des prédicats du premier ordre , les clauses de Horn , qui est Turing-complet . L'exhaustivité de Turing de Prolog peut être montrée en l'utilisant pour simuler une machine de Turing :

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).
 
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).
 
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
 
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
 
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

Un exemple simple de machine de Turing est spécifié par les faits :

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

Cette machine effectue une incrémentation par l'un d'un nombre en codage unaire : elle boucle sur un nombre quelconque de cellules "1" et ajoute un "1" supplémentaire à la fin. Exemple de requête et de résultat :

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

Cela illustre comment tout calcul peut être exprimé de manière déclarative comme une séquence de transitions d'état, implémentée dans Prolog comme une relation entre des états d'intérêt successifs.

Mise en œuvre

Prologue ISO

La norme ISO Prolog se compose de deux parties. ISO/IEC 13211-1, publiée en 1995, vise à normaliser les pratiques existantes des nombreuses implémentations des éléments de base de Prolog. Il a clarifié des aspects du langage qui étaient auparavant ambigus et conduit à des programmes portables. Il existe trois corrigenda : Cor.1:2007, Cor.2:2012 et Cor.3:2017. ISO/IEC 13211-2, publiée en 2000, ajoute la prise en charge des modules à la norme. La norme est maintenue par le groupe de travail ISO/IEC JTC1 / SC22 /WG17. ANSI X3J17 est le groupe consultatif technique américain pour la norme.

Compilation

Pour plus d'efficacité, le code Prolog est généralement compilé en code machine abstrait, souvent influencé par le jeu d'instructions Warren Abstract Machine (WAM) basé sur les registres . Certaines implémentations utilisent une interprétation abstraite pour dériver les informations de type et de mode des prédicats au moment de la compilation, ou compiler en code machine réel pour des performances élevées. Concevoir des méthodes d'implémentation efficaces pour le code Prolog est un domaine de recherche active dans la communauté de programmation logique, et diverses autres méthodes d'exécution sont utilisées dans certaines implémentations. Il s'agit notamment de la binarisation des clauses et des machines virtuelles basées sur la pile .

Récursivité de la queue

Les systèmes Prolog implémentent généralement une méthode d'optimisation bien connue appelée optimisation des appels de queue (TCO) pour les prédicats déterministes présentant une récursivité de queue ou, plus généralement, des appels de queue : la trame de pile d'une clause est supprimée avant d'effectuer un appel dans une position de queue. Par conséquent, les prédicats récursifs de queue déterministes sont exécutés avec un espace de pile constant, comme les boucles dans d'autres langages.

Indexation des termes

La recherche de clauses unifiables avec un terme dans une requête est linéaire en nombre de clauses. L'indexation des termes utilise une structure de données qui permet des recherches en temps sous-linéaire . L'indexation n'affecte que les performances du programme, elle n'affecte pas la sémantique. La plupart des prologues n'utilisent l'indexation que sur le premier terme, car l'indexation sur tous les termes est coûteuse, mais les techniques basées sur des mots codés par champ ou des mots de code superposés permettent une indexation rapide sur l'ensemble de la requête et de l'en-tête.

Hachage

Certains systèmes Prolog, tels que WIN-PROLOG et SWI-Prolog, implémentent désormais le hachage pour aider à gérer plus efficacement les grands ensembles de données. Cela a tendance à générer des gains de performances très importants lorsque vous travaillez avec de grands corpus tels que WordNet .

Dépôt

Certains systèmes Prolog, ( B-Prolog , XSB , SWI-Prolog , YAP , et Ciao ), mettre en œuvre une memoization méthode appelée dépôt , ce qui libère l'utilisateur de stocker manuellement des résultats intermédiaires. Le dépôt est un compromis espace-temps ; le temps d'exécution peut être réduit en utilisant plus de mémoire pour stocker les résultats intermédiaires :

Les sous-objectifs rencontrés dans une évaluation de requête sont conservés dans un tableau, avec les réponses à ces sous-objectifs. Si un sous-objectif est rencontré à nouveau, l'évaluation réutilise les informations de la table plutôt que de réexécuter la résolution par rapport aux clauses du programme.

Le dépôt peut être étendu dans différentes directions. Il peut prendre en charge les prédicats récursifs via la résolution SLG ou le tableau linéaire. Dans un système Prolog multi-thread, les résultats de la table peuvent être gardés privés pour un thread ou partagés entre tous les threads. Et dans le dépôt incrémentiel, le dépôt peut réagir aux changements.

Implémentation dans le matériel

Au cours du projet Systèmes informatiques de cinquième génération , il y a eu des tentatives pour implémenter Prolog dans le matériel dans le but d'obtenir une exécution plus rapide avec des architectures dédiées. De plus, Prolog possède un certain nombre de propriétés qui peuvent permettre une accélération grâce à une exécution parallèle. Une approche plus récente a consisté à compiler des programmes Prolog restreints en un réseau de portes programmable sur site . Cependant, les progrès rapides du matériel à usage général ont systématiquement dépassé les architectures plus spécialisées.

Limites

Bien que Prolog soit largement utilisé dans la recherche et l'éducation, Prolog et d'autres langages de programmation logique n'ont pas eu d'impact significatif sur l'industrie informatique en général. La plupart des applications sont petites par rapport aux normes industrielles, avec quelques-unes dépassant les 100 000 lignes de code. La programmation au sens large est considérée comme compliquée car tous les compilateurs Prolog ne prennent pas en charge les modules et il existe des problèmes de compatibilité entre les systèmes de modules des principaux compilateurs Prolog. La portabilité du code Prolog entre les implémentations a également été un problème, mais les développements depuis 2007 ont signifié : « la portabilité au sein de la famille des implémentations Prolog dérivées d'Édimbourg/Quintus est suffisamment bonne pour permettre le maintien d'applications portables dans le monde réel. »

Le logiciel développé en Prolog a été critiqué pour avoir une pénalité de haute performance par rapport aux langages de programmation conventionnels. En particulier, la stratégie d'évaluation non déterministe de Prolog peut être problématique lors de la programmation de calculs déterministes, ou même lors de l'utilisation de « ne se soucie pas du non-déterminisme » (où un seul choix est fait au lieu de revenir en arrière sur toutes les possibilités). Des coupures et d'autres constructions de langage peuvent devoir être utilisées pour obtenir des performances souhaitables, détruisant l'une des principales attractions de Prolog, la capacité d'exécuter des programmes "en avant et en arrière".

Prolog n'est pas purement déclaratif : en raison de constructions comme l' opérateur cut , une lecture procédurale d'un programme Prolog est nécessaire pour le comprendre. L'ordre des clauses dans un programme Prolog est important, car la stratégie d'exécution du langage en dépend. D'autres langages de programmation logique, tels que Datalog , sont vraiment déclaratifs mais restreignent le langage. En conséquence, de nombreux programmes Prolog pratiques sont écrits pour se conformer à l' ordre de recherche en profondeur d'abord de Prolog , plutôt que comme des programmes logiques purement déclaratifs.

Rallonges

Diverses implémentations ont été développées à partir de Prolog pour étendre les capacités de programmation logique dans de nombreuses directions. Ceux-ci incluent les types , les modes, la programmation logique par contraintes (CLP), la programmation logique orientée objet (OOLP), la concurrence, la logique linéaire (LLP), les capacités de programmation logique fonctionnelle et d'ordre supérieur, ainsi que l'interopérabilité avec les bases de connaissances :

Les types

Prolog est un langage non typé. Les tentatives d'introduction de types remontent aux années 1980, et à partir de 2008, il y a toujours des tentatives d'étendre Prolog avec des types. Les informations sur les types sont utiles non seulement pour la sécurité des types, mais aussi pour raisonner sur les programmes Prolog.

Modes

La syntaxe de Prolog ne précise pas quels arguments d'un prédicat sont des entrées et lesquels sont des sorties. Cependant, cette information est importante et il est recommandé de l'inclure dans les commentaires. Les modes fournissent des informations précieuses lors du raisonnement sur les programmes Prolog et peuvent également être utilisés pour accélérer l'exécution.

Contraintes

La programmation en logique de contraintes étend Prolog pour inclure des concepts issus de la satisfaction de contraintes . Un programme de logique de contraintes autorise des contraintes dans le corps des clauses, telles que : A(X,Y) :- X+Y>0. Il est adapté aux problèmes d' optimisation combinatoire à grande échelle et est donc utile pour des applications en milieu industriel, telles que l' ordonnancement automatisé du temps et la planification de la production . La plupart des systèmes Prolog sont livrés avec au moins un solveur de contraintes pour les domaines finis, et souvent aussi avec des solveurs pour d'autres domaines comme les nombres rationnels.

Orientation objet

Flora-2 est un système de représentation des connaissances et de raisonnement orienté objet basé sur la logique F et intègre HiLog , la logique de transaction et le raisonnement défaisable .

Logtalk est un langage de programmation logique orienté objet qui peut utiliser la plupart des implémentations de Prolog en tant que compilateur back-end. En tant que langage multi-paradigme, il prend en charge à la fois les prototypes et les classes.

Oblog est une petite extension portable et orientée objet de Prolog par Margaret McDougall de EdCAAD, Université d'Édimbourg.

Objlog était un langage basé sur des cadres combinant des objets et Prolog II du CNRS, Marseille, France.

Prolog++ a été développé par Logic Programming Associates et publié pour la première fois en 1989 pour les PC MS-DOS. La prise en charge d'autres plates-formes a été ajoutée et une deuxième version a été publiée en 1995. Un livre sur Prolog++ de Chris Moss a été publié par Addison-Wesley en 1994.

Visual Prolog est un langage multi-paradigme avec des interfaces, des classes, des implémentations et des expressions d'objets.

Graphique

Les systèmes Prolog qui fournissent une bibliothèque graphique sont SWI-Prolog , Visual Prolog , WIN-PROLOG et B-Prolog .

Concurrence

Prolog-MPI est une extension SWI-Prolog open source pour le calcul distribué sur l' interface de passage de messages . Il existe également divers langages de programmation Prolog concurrents.

programmation web

Certaines implémentations de Prolog, notamment Visual Prolog , SWI-Prolog et Ciao , prennent en charge la programmation Web côté serveur avec prise en charge des protocoles Web, HTML et XML . Il existe également des extensions pour prendre en charge les formats Web sémantiques tels que RDF et OWL . Prolog a également été suggéré comme langage côté client . De plus, Visual Prolog prend en charge JSON-RPC et Websockets .

Adobe Flash

Cedar est un interpréteur Prolog gratuit et basique. À partir de la version 4 et au-dessus, Cedar prend en charge FCA (Flash Cedar App). Cela fournit une nouvelle plate-forme pour la programmation en Prolog via ActionScript .

Autre

• F-logic étend Prolog avec des cadres/objets pour la représentation des connaissances .
• La logique de transaction étend Prolog avec une théorie logique des opérateurs de mise à jour à changement d'état. Il a à la fois une sémantique théorique et procédurale.
• OW Prolog a été créé afin de répondre au manque de graphisme et d'interface de Prolog.

Interfaces vers d'autres langues

Des frameworks existent qui peuvent faire le pont entre Prolog et d'autres langages :

• Le LPA Intelligence Server permet l'intégration de LPA Prolog pour Windows dans C, C#, C++, Java, VB, Delphi, .Net, Lua, Python et d'autres langages. Il exploite le type de données string dédié fourni par LPA Prolog
• L'API Logic Server permet à la fois l'extension et l'intégration de Prolog en C, C++, Java, VB, Delphi, .NET et tout langage/environnement pouvant appeler un .dll ou un .so. Il est implémenté pour Amzi ! Prolog Amzi! Prolog + Logic Server mais la spécification de l'API peut être mise à disposition pour toute implémentation.
• JPL est un pont Java Prolog bidirectionnel qui est livré avec SWI-Prolog par défaut, permettant à Java et Prolog de s'appeler (récursivement). Il est connu pour avoir une bonne prise en charge de la concurrence et est en cours de développement actif.
• InterProlog , un pont de bibliothèque de programmation entre Java et Prolog, implémentant des appels de prédicat/méthode bidirectionnels entre les deux langages. Les objets Java peuvent être mappés en termes Prolog et vice versa. Permet le développement d' interfaces graphiques et d'autres fonctionnalités en Java tout en laissant le traitement logique dans la couche Prolog. Prend en charge XSB , avec prise en charge de SWI-Prolog et YAP prévue pour 2013.
• Prova fournit une intégration de la syntaxe native avec Java, la messagerie d'agent et les règles de réaction. Prova se positionne comme un système de script basé sur des règles (RBS) pour middleware. Le langage innove en combinant la programmation impérative et déclarative .
• PROL Un moteur Prolog intégrable pour Java. Il comprend un petit IDE et quelques bibliothèques.
• GNU Prolog for Java est une implémentation d'ISO Prolog en tant que bibliothèque Java (gnu.prolog)
• Ciao fournit des interfaces aux bases de données C, C++, Java et relationnelles.
• C#-Prolog est un interpréteur Prolog écrit en C# (géré). Peut être facilement intégré dans les programmes C#. Caractéristiques : interpréteur fiable et assez rapide, interface en ligne de commande, interface Windows, DCG intégré, prédicats XML, prédicats SQL, extensible. Le code source complet est disponible, y compris un générateur d'analyseur syntaxique qui peut être utilisé pour ajouter des extensions à des fins spéciales.
• Une Warren Abstract Machine pour PHP Un compilateur et interpréteur Prolog en PHP 5.3. Une bibliothèque qui peut être utilisée de manière autonome ou dans le cadre Symfony2.1 qui a été traduite du travail de Stephan Buettcher en Java qui peut être trouvée [ici stefan .buettcher .org /cs /wam /index .html ]
• tuProlog est un système Prolog léger pour les applications et infrastructures distribuées, intentionnellement conçu autour d'un noyau minimal, pour être configuré de manière statique ou dynamique en chargeant/déchargeant des bibliothèques de prédicats. tuProlog prend en charge nativement la programmation multi-paradigme, fournissant un modèle d'intégration propre et transparent entre Prolog et les langages orientés objet traditionnels, à savoir Java, pour la version Java de tuProlog, et tout langage basé sur .NET (C#, F#..), pour tuProlog . version NET.

Histoire

Le nom Prolog a été choisi par Philippe Roussel comme une abréviation de programmation en logique ( français pour la programmation en logique ). Elle a été créée vers 1972 par Alain Colmerauer avec Philippe Roussel, sur la base de l' interprétation procédurale de Robert Kowalski des clauses de Horn . Il était motivé en partie par le désir de concilier l'utilisation de la logique comme langage déclaratif de représentation des connaissances avec la représentation procédurale des connaissances qui était populaire en Amérique du Nord à la fin des années 1960 et au début des années 1970. Selon Robert Kowalski , le premier système Prolog a été développé en 1972 par Colmerauer et Philippe Roussel. La première implémentation de Prolog était un interpréteur écrit en Fortran par Gérard Battani et Henri Meloni. David HD Warren a emmené cet interpréteur à Édimbourg et y a implémenté un front-end alternatif, qui est venu définir la syntaxe « Edinburgh Prolog » utilisée par la plupart des implémentations modernes. Warren a également implémenté le premier compilateur pour Prolog, créant l'influent DEC-10 Prolog en collaboration avec Fernando Pereira. Warren a ensuite généralisé les idées derrière DEC-10 Prolog, pour créer la Warren Abstract Machine .

Les chercheurs européens en IA préféraient Prolog tandis que les Américains préféraient Lisp , ce qui aurait provoqué de nombreux débats nationalistes sur les mérites des langues. Une grande partie du développement moderne de Prolog est venue de l'impulsion du projet de systèmes informatiques de cinquième génération (FGCS), qui a développé une variante de Prolog nommée Kernel Language pour son premier système d'exploitation .

Pure Prolog était à l'origine limité à l'utilisation d'un prouveur de théorème de résolution avec des clauses de Horn de la forme :

H :- B1, ..., Bn.

L'application du théorème-démonstrateur traite ces clauses comme des procédures :

to show/solve H, show/solve B1 and ... and Bn.

Cependant, le Prolog pur fut bientôt étendu pour inclure la négation comme échec , dans laquelle les conditions négatives de la forme not(B _i ) sont montrées en essayant et en échouant de résoudre les conditions positives correspondantes B _i .

Les extensions ultérieures de Prolog par l'équipe d'origine ont introduit des capacités de programmation de logique de contrainte dans les implémentations.

Utilisation dans l'industrie

Prolog a été utilisé dans Watson . Watson utilise le logiciel DeepQA d'IBM et le cadre Apache UIMA (Unstructured Information Management Architecture). Le système a été écrit dans divers langages, dont Java, C++ et Prolog, et s'exécute sur le système d'exploitation SUSE Linux Enterprise Server 11 à l'aide du framework Apache Hadoop pour fournir une informatique distribuée. Prolog est utilisé pour la correspondance de motifs sur des arbres d'analyse en langage naturel. Les développeurs ont déclaré : « Nous avions besoin d'un langage dans lequel nous pourrions exprimer facilement des règles de correspondance de modèles sur les arbres d'analyse et d'autres annotations (telles que les résultats de la reconnaissance d'entités nommées), et une technologie qui pourrait exécuter ces règles de manière très efficace. Nous avons constaté que Prolog était le choix idéal pour la langue en raison de sa simplicité et de son expressivité." Prolog est utilisé dans la plate-forme de développement Low-Code GeneXus , qui se concentre sur l'IA. La base de données graphique open source TerminusDB est implémentée dans prolog. TerminusDB est conçu pour la création et la conservation collaboratives de graphes de connaissances .

Voir également

• Comparaison des implémentations Prolog
• Modélisation logico-linguistique . Une méthode pour construire un système basé sur les connaissances qui utilise Prolog.
• Programmation du poste de réponse . Une approche entièrement déclarative de la programmation logique.
• Association pour la programmation logique

Langues associées

• Le langage Gödel est une implémentation fortement typée de la programmation logique à contraintes concurrentes . Il est construit sur SICStus Prolog.
• Visual Prolog , anciennement connu sous le nom de PDC Prolog et Turbo Prolog, est un dialecte orienté objet fortement typé de Prolog, qui est très différent du Prolog standard. Sous le nom de Turbo Prolog, il était commercialisé par Borland, mais il est maintenant développé et commercialisé par la firme danoise PDC (Prolog Development Center) qui l'a initialement produit.
• Datalog est un sous-ensemble de Prolog. Elle est limitée aux relations qui peuvent être stratifiées et n'autorise pas les termes composés. Contrairement à Prolog, Datalog n'est pas Turing-complet .
• Mercury est une émanation de Prolog orientée vers le génie logiciel au sens large avec un système de type statique et polymorphe, ainsi qu'un système de mode et de déterminisme.
• GraphTalk est une implémentation propriétaire de la machine abstraite de Warren, avec des propriétés orientées objet supplémentaires.
• À certains égards, Prolog est un sous-ensemble de Planner . Les idées de Planner ont ensuite été développées dans la métaphore de la communauté scientifique .
• AgentSpeak est une variante de Prolog pour la programmation du comportement des agents dans les systèmes multi-agents .
• Erlang a commencé avec une implémentation basée sur Prolog et maintient une grande partie de la syntaxe basée sur l'unification de Prolog.
• Pilog est un langage déclaratif construit sur PicoLisp , qui a la sémantique de Prolog, mais utilise la syntaxe de Lisp.

Les références

Lectures complémentaires