La programmation logique est un paradigme de programmation qui regroupe les langages basés sur la logique formelle, tels que Datalog et Prolog . Cet article décrit la syntaxe et...
Worldlex WikiContenu en francaisLecture gratuite
La programmation logique est un paradigme de programmation qui regroupe les langages basés sur la logique formelle, tels que Datalog et Prolog . Cet article décrit la syntaxe et la sémantique du sous-ensemble purement déclaratif de ces langages. Il convient de noter que le terme « programmation logique » désigne également un langage de programmation implication :
ce qui signifie « Si chaquesi c'est vrai, alors« C’est vrai ». Les programmes logiques calculent l’ensemble des faits impliqués par leurs règles.
De nombreuses implémentations de Datalog, Prolog et des langages apparentés ajoutent des fonctionnalités procédurales, comme l'opérateur de coupure de Prolog , ou des fonctionnalités extra-logiques, comme une interface de fonction étrangère . La sémantique formelle de ces extensions dépasse le cadre de cet article.
clauses de Horn ). Si constante et variable sont deux ensembles dénombrables de constantes et de variables respectivement, et relation un ensemble dénombrable de symboles de prédicats , alors la grammaire BNF suivante exprime la structure d'un programme Datalog :
Un atome est dit fondamental si aucun de ses sous-termes n'est une variable. Intuitivement, chaque sémantique définit la signification d'un programme comme l'ensemble de tous les atomes fondamentaux qui peuvent être déduits des règles du programme, à partir des faits.
Il s'agit du modèle minimal de Herbrand. Toutes les interprétations supérieures sont également des modèles, toutes les interprétations inférieures ne le sont pas.
Une règle est dite fondamentale si tous ses atomes (tête et corps) sont fondamentaux. Une règle fondamentale R₂ est une instance fondamentale d' une autre règle R₁ si R₂ est le résultat d'une substitution de constantes pour toutes les variables de R₁ .
La base de Herbrand d'un programme Datalog est l'ensemble de tous les atomes fondamentaux pouvant être construits à partir des constantes présentes dans le programme. Une interprétation (ou instance de base de données ) est un sous-ensemble de la base de Herbrand. Un atome fondamental est vrai dans une interprétation théorique des modèles stipule que la signification d'un programme Datalog est son modèle de Herbrand minimal (ou, de manière équivalente, l'intersection de tous ses modèles de Herbrand) .
Par exemple, ce programme :
d'ensemble des parties . L' monotone par rapport à l' ordre partiel donné par l'inclusion de sous-ensembles sur théorème de Knaster-Tarski , cette application possède un plus petit point fixe ; d'après le théorème du point fixe de Kleene, ce point fixe est le supremum de la chaîne.Le plus petit point fixe de du point fixe suggère un algorithme pour calculer le modèle de Herbrand minimal : partir de l’ensemble des faits initiaux du programme, puis ajouter itérativement les conséquences des règles jusqu’à atteindre un point fixe. Cet algorithme est appelé évaluation naïve .
Théorie de la preuve
Arbre de preuve montrant la dérivation de l'atome fondamental path(x, z)à partir du programme
arbre dont la racine est étiquetée par étiquetés par des atomes fondamentaux de résolution SLD , qui sert de base à l'évaluation de Prolog .
Autres approches
La sémantique de Datalog a également été étudiée dans le contexte des points fixes sur des semi-anneaux plus généraux .
Programmation logique
Bien que le terme « programmation logique » désigne l'ensemble du paradigme des langages de programmation, y compris Datalog et Prolog, lorsqu'on aborde la sémantique formelle, il fait généralement référence à une extension de Datalog utilisant des symboles de fonction . Les programmes logiques sont également appelés à clauses de Horn . La programmation logique présentée dans cet article est étroitement liée au sous-ensemble « pur » ou déclaratif de Prolog .
Syntaxe
La syntaxe de la programmation logique étend celle de Datalog avec des symboles de fonction. La programmation logique supprime la restriction de plage, permettant ainsi aux variables d'apparaître dans les têtes des règles sans figurer dans leur corps.
Sémantique
Du fait de la présence de symboles de fonction, les modèles de Herbrand des programmes logiques peuvent être infinis. Cependant, la sémantique d'un programme logique est toujours définie par son modèle de Herbrand minimal. De même, le point fixe de l'opérateur de conséquence immédiate peut ne pas converger en un nombre fini d'étapes (ou vers un ensemble fini). Néanmoins, tout atome fondamental du modèle de Herbrand minimal possède un arbre de preuve fini. C'est pourquoi Prolog est évalué de haut en bas. Tout comme en Datalog, l'équivalence des trois sémantiques peut être démontrée.
Négation
La programmation logique présente l'avantage que les trois principales définitions de sa sémantique concordent. En revanche, il existe de nombreuses propositions contradictoires concernant la sémantique des programmes logiques avec négation. Cette divergence provient du fait que les programmes logiques possèdent un modèle de Herbrand minimal unique, contrairement aux programmes de programmation logique (et même aux programmes Datalog) avec négation.
Syntaxe
La négation s'écrit not, et peut apparaître devant n'importe quel atome dans le corps d'une règle.
Worldlex Wiki 
