Logique et programmation déclarative
La programmation logique et déclarative exprime les problèmes sous forme de relations, de faits et de règles, confiant la recherche de solutions à un moteur d'inférence plutôt qu'à des instructions explicites étape par étape.
Definition
La programmation logique est un paradigme déclaratif dans lequel un programme est un ensemble de clauses logiques (faits et règles), et le calcul procède par déduction automatisée, généralement la résolution avec unification, pour répondre aux requêtes formulées sur cette base de connaissances.
Scope
Ce domaine couvre la programmation logique basée sur les clauses de Horn et la résolution (comme dans Prolog), la programmation logique avec contraintes, et l'idée déclarative plus large de spécifier ce qui doit être vrai plutôt que la manière de le calculer. Il inclut l'unification, la recherche par retour arrière (backtracking), la sémantique des programmes logiques basée sur la théorie des modèles et la théorie de la preuve, ainsi que la séparation de la spécification logique du contrôle.
Core questions
- Que signifie calculer en prouvant un objectif à partir de clauses logiques ?
- Comment l'unification et le retour arrière (backtracking) réalisent-ils la recherche sur un programme relationnel ?
- Comment la séparation de la logique et du contrôle est-elle précisée ?
- Comment les contraintes étendent-elles la programmation logique pure ?
Key theories
- Principe de résolution
- La résolution de Robinson fournit une règle d'inférence unique, orientée machine, pour la logique du premier ordre, offrant le moteur déductif qui rend la programmation logique réalisable sur le plan computationnel.
- Logique plus contrôle
- L'analyse de Kowalski distingue le contenu logique d'un programme (ce qui est vrai) de sa composante de contrôle (comment la preuve est recherchée), présentant la programmation logique comme un moyen de faire varier le contrôle tout en maintenant la logique fixe.
- Sémantique déclarative et procédurale des programmes logiques
- Lloyd formalise les sémantiques basées sur la théorie des modèles, les points fixes et opérationnelles des programmes logiques définis et prouve leur correspondance, fondant ainsi la signification des programmes logiques.
Clinical relevance
Les techniques déclaratives et basées sur la logique sous-tendent les langages de requête de bases de données, les solveurs de contraintes, la représentation des connaissances et les moteurs de règles. Leur accent sur la spécification des problèmes plutôt que sur les algorithmes les rend bien adaptées aux tâches de recherche combinatoire, de configuration et de raisonnement.
History
Le principe de résolution de Robinson en 1965 a posé les bases déductives. Au début des années 1970, Colmerauer et Roussel ont créé Prolog, et Kowalski a formulé l'interprétation procédurale des clauses de Horn. Le paradigme a prospéré tout au long des années 1980, influençant le projet japonais de la Cinquième Génération, et s'est ensuite étendu à la programmation logique avec contraintes et à la programmation par ensembles de réponses (answer-set programming).
Debates
- Pureté versus contrôle pratique
- Les langages de programmation logique équilibrent l'idéal d'une logique déclarative pure avec les besoins pratiques de contrôle explicite, tels que le 'cut' (coupe) et l'ordonnancement, qui améliorent l'efficacité mais compromettent la séparation nette entre logique et contrôle.
Key figures
- Robert Kowalski
- Alain Colmerauer
- J. Alan Robinson
- John Lloyd
- Philippe Roussel
Related topics
Seminal works
- kowalski1979
- robinson1965
- lloyd1987
- colmerauer1993
Frequently asked questions
- En quoi la programmation logique diffère-t-elle de la programmation impérative ?
- Au lieu de spécifier une séquence d'opérations, un programme logique déclare des faits et des règles, et un moteur d'inférence recherche des preuves qui répondent aux requêtes ; ainsi, le programmeur se concentre sur ce qui est vrai plutôt que sur la manière de le calculer.
- Qu'est-ce que l'unification ?
- L'unification est le processus qui consiste à trouver une substitution rendant deux termes logiques identiques ; c'est le mécanisme central par lequel les programmes logiques font correspondre les objectifs aux têtes de clauses.