Programmation déclarative

En informatique , la programmation déclarative est un paradigme de programmation qui exprime la logique d'un calcul sans décrire entièrement son flux de contrôle .

Les langages qui autorisent ce style permettent au développeur de minimiser ou d'éliminer les effets de bord en décrivant ce que le programme doit accomplir en fonction du domaine du problème , plutôt que de décrire entièrement comment y parvenir sous forme d'une séquence de primitives du langage de programmation (le « comment » étant laissé à l' implémentation du langage ). Ceci contraste avec la programmation impérative , qui implémente les algorithmes par étapes explicites.

La programmation déclarative peut considérer les programmes comme des théories d'une logique formelle , et les calculs comme des déductions dans cette théorie logique. La programmation déclarative simplifie parfois l'écriture de programmes parallèles .

Les paradigmes de langages déclaratifs courants incluent la programmation logique (par exemple, Prolog , Datalog , la programmation par ensembles de réponses ) et les systèmes de modélisation algébrique .

La programmation déclarative est souvent définie comme tout style de programmation non impératif. D'autres définitions courantes tentent de la définir simplement par opposition à la programmation impérative. Par exemple :

• Un programme de haut niveau qui décrit ce qu'un calcul doit effectuer.
• Tout langage de programmation qui ne présente pas d’effets secondaires , ou plus précisément, qui possède une transparence référentielle .
• Un langage ayant une correspondance claire avec la logique mathématique .

Ces définitions se recoupent largement.

La programmation déclarative est un style de programmation non impératif où les programmes décrivent les résultats souhaités sans lister explicitement les commandes ou les étapes à exécuter. Les langages de programmation logique se caractérisent par un style majoritairement déclaratif. En programmation logique, les programmes sont constitués d'instructions exprimées sous forme logique , et le calcul utilise ces instructions pour résoudre des problèmes, eux aussi exprimés sous forme logique.

Dans un langage purement fonctionnel , comme Haskell , toutes les fonctions sont sans effet de bord , et les changements d'état sont uniquement représentés par des fonctions qui transforment l'état, lequel est explicitement représenté comme un objet de première classe dans le programme. Bien que les langages purement fonctionnels ne soient pas impératifs, ils offrent souvent la possibilité de décrire l'effet d'une fonction comme une série d'étapes. D'autres langages fonctionnels, tels que Lisp , OCaml et Erlang , prennent en charge une approche hybride, combinant programmation procédurale et fonctionnelle.

Certains langages de programmation logique, tels que Prolog , et les langages de requêtes de bases de données , tels que SQL , bien que déclaratifs par principe, prennent également en charge un style de programmation procédural.

La programmation déclarative est un terme générique qui englobe un certain nombre de paradigmes de programmation plus connus .

La programmation par contraintes formalise les relations entre les variables sous forme de contraintes qui définissent les propriétés de la solution cible. L'ensemble des contraintes est résolu en attribuant une valeur à chaque variable de manière à ce que la solution soit compatible avec le plus grand nombre possible de contraintes. La programmation par contraintes complète souvent d'autres paradigmes : la programmation fonctionnelle, logique, voire impérative.

Les Makefiles, par exemple, spécifient les dépendances de manière déclarative , mais incluent également une liste impérative d'actions à effectuer. De même, yacc spécifie une grammaire hors contexte de manière déclarative, mais inclut des extraits de code provenant d'un langage hôte, généralement impératif (comme le C ).

Les langages de programmation logique, tels que Prolog , Datalog et la programmation par ensembles de réponses , calculent en prouvant qu'un but est une conséquence logique du programme, ou en démontrant que le but est vrai dans un modèle défini par le programme. Prolog calcule en décomposant les buts en sous-buts, selon une approche descendante utilisant le raisonnement à rebours , tandis que la plupart des systèmes Datalog calculent de bas en haut en utilisant le raisonnement direct . Les programmes par ensembles de réponses utilisent généralement des solveurs SAT pour générer un modèle du programme.

Les modèles, ou représentations mathématiques, des systèmes physiques peuvent être implémentés dans un code informatique déclaratif. Ce code contient un certain nombre d'équations, et non des affectations impératives, qui décrivent (« déclarent ») les relations comportementales. Lorsqu'un modèle est exprimé dans ce formalisme, un ordinateur est capable d'effectuer des manipulations algébriques afin de formuler au mieux l'algorithme de résolution. La causalité mathématique est généralement imposée aux limites du système physique, tandis que la description comportementale du système lui-même est déclarative ou acausale. Parmi les langages et environnements de modélisation déclaratifs, on peut citer Analytica , Modelica et Simile .

Prolog (1972) signifie « PROgramming in LOGic ». Il a été développé pour répondre aux questions en langage naturel , en utilisant la résolution SL à la fois pour déduire les réponses aux requêtes et pour analyser et générer des phrases en langage naturel.

Les éléments constitutifs d'un programme Prolog sont les faits et les règles . Voici un exemple simple :

chat ( tom ). % tom est un chat souris ( jerry ). % jerry est une sourisanimal ( X ) :- chat ( X ). % chaque chat est un animal animal ( X ) : - souris ( X ). % chaque souris est un animalgrand ( X ) :- chat ( X ). % chaque chat est grand petit ( X ) :- souris ( X ). % chaque souris est petitemanger ( X , Y ) :- souris ( X ), fromage ( Y ). % chaque souris mange chaque fromage manger ( X , Y ) :- gros ( X ), petit ( Y ). % chaque gros être mange chaque petit être

Avec ce programme, la requête réussit, tandis que échoue. De plus, la requête réussit avec la substitution de réponse . eat(tom,jerry)eat(jerry,tom)eat(X,jerry)X=tom

Prolog exécute les programmes de manière descendante, en utilisant la résolution SLD pour raisonner à rebours et réduire les buts à des sous-buts. Dans cet exemple, il utilise la dernière règle du programme pour réduire le but de répondre à la requête aux sous-buts suivants : trouver d’abord un X tel que la condition soit vraie, puis montrer que la condition est vraie. Il utilise des règles de manière itérative pour réduire encore les sous-buts à d’autres sous-buts, jusqu’à parvenir à unifier tous les sous-buts avec des faits du programme. Cette stratégie de raisonnement à rebours et de réduction des buts traite les règles des programmes logiques comme des procédures, faisant de Prolog un langage de programmation à la fois déclaratif et procédural . eat(X,jerry)big(X)small(jerry)

La vaste gamme d'applications de Prolog est mise en évidence dans le livre Year of Prolog, célébrant le 50e anniversaire de Prolog.

Datalog trouve ses origines dans les débuts de la programmation logique, mais il a été identifié comme un domaine distinct vers 1977. Du point de vue syntaxique et sémantique , il s'agit d'un sous-ensemble de Prolog. Cependant, en raison de l'absence de termes composés , il n'est pas Turing-complet .

La plupart des systèmes Datalog exécutent les programmes de bas en haut, en utilisant des règles pour raisonner en avant , en déduisant de nouveaux faits à partir de faits existants, et en s'arrêtant lorsqu'il n'y a plus de nouveaux faits qui peuvent être déduits, ou lorsque les faits dérivés s'unifient avec la requête.

Datalog a été appliqué à des problèmes tels que l'intégration de données , l'extraction d'informations , la mise en réseau , la sécurité , le cloud computing et l'apprentissage automatique .

La programmation par ensembles de réponses (ASP) a émergé à la fin des années 1990, s'appuyant sur la sémantique des modèles stables (ensembles de réponses) de la programmation logique. À l'instar de Datalog, elle constitue un sous-ensemble de Prolog ; et, du fait de l'absence de termes composés, elle n'est pas Turing-complète.

La plupart des implémentations d'ASP exécutent un programme en commençant par l' ancrer , en remplaçant toutes les variables des règles par des constantes de toutes les manières possibles, puis en utilisant un solveur SAT propositionnel, tel que l' algorithme DPLL , pour générer un ou plusieurs modèles du programme.

Ses applications sont orientées vers la résolution de problèmes de recherche difficiles et la représentation des connaissances .