Programmation fonctionnelle, déclarative et impérative [fermé]

Que signifient les termes programmation fonctionnelle, déclarative et impérative?

Au moment d'écrire ces lignes, les réponses les plus votées sur cette page sont imprécises et confuses sur la définition déclarative vs impérative, y compris la réponse qui cite Wikipedia. Certaines réponses confondent les termes de différentes manières.

Reportez-vous également à mon explication de la raison pour laquelle la programmation de feuille de calcul est déclarative, indépendamment du fait que les formules mutent les cellules.

De plus, plusieurs réponses affirment que la programmation fonctionnelle doit être un sous-ensemble de déclaratif. Sur ce point, cela dépend si nous différencions «fonction» de «procédure». Permet d'aborder impératif vs déclaratif en premier.

Définition de l' expression déclarative

Le seul attribut qui puisse éventuellement différencier une expression déclarative d'une expression impérative est la transparence référentielle (RT) de ses sous-expressions. Tous les autres attributs sont soit partagés entre les deux types d'expressions, soit dérivés de la RT.

Un langage 100% déclaratif (c'est-à-dire un langage dans lequel chaque expression possible est RT) ne permet pas (entre autres exigences RT) la mutation des valeurs stockées, par exemple HTML et la plupart de Haskell.

Définition de l' expression RT

La RT est souvent désignée comme n'ayant "aucun effet secondaire". Le terme effets n'a pas de définition précise, donc certaines personnes ne conviennent pas que «pas d'effets secondaires» est le même que RT. RT a une définition précise .

Étant donné que chaque sous-expression est conceptuellement un appel de fonction, RT requiert que l'implémentation d'une fonction (c'est-à-dire les expressions à l'intérieur de la fonction appelée) ne puisse pas accéder à l'état mutable qui est externe à la fonction (accéder à l' état local mutable est permis). En termes simples, la fonction (implémentation) doit être pure .

Définition de la fonction pure

On dit souvent qu'une fonction pure n'a «aucun effet secondaire». Le terme effets n'a pas de définition précise, donc certaines personnes ne sont pas d'accord.

Les fonctions pures ont les attributs suivants.

• la seule sortie observable est la valeur de retour.
• la seule dépendance de sortie est les arguments.
• les arguments sont entièrement déterminés avant la génération d'une sortie.

N'oubliez pas que RT s'applique aux expressions (qui incluent les appels de fonction) et que la pureté s'applique aux (implémentations des) fonctions.

Un exemple obscur de fonctions impures qui font des expressions RT est la concurrence, mais c'est parce que la pureté est rompue au niveau de la couche d'abstraction d'interruption. Vous n'avez pas vraiment besoin de savoir cela. Pour créer des expressions RT, vous appelez des fonctions pures.

Attributs dérivés de RT

Tout autre attribut cité pour la programmation déclarative, par exemple la citation de 1999 utilisée par Wikipedia, dérive de RT, ou est partagé avec la programmation impérative. Prouvant ainsi que ma définition précise est correcte.

Remarque, l'immuabilité des valeurs externes est un sous-ensemble des exigences pour la RT.

• Les langages déclaratifs n'ont pas de structures de contrôle en boucle, par exemple foret while, parce qu'en raison de l'immuabilité , la condition de boucle ne changerait jamais.

• Les langages déclaratifs n'expriment pas le flux de contrôle autre que l'ordre des fonctions imbriquées (ou dépendances logiques), car en raison de l'immuabilité , d'autres choix d'ordre d'évaluation ne modifient pas le résultat (voir ci-dessous).

• Les langages déclaratifs expriment des "étapes" logiques (c'est-à-dire l'ordre d'appel de fonction RT imbriqué), mais la question de savoir si chaque appel de fonction est une sémantique de niveau supérieur (c'est-à-dire "que faire") n'est pas une exigence de la programmation déclarative. La distinction de l'impératif est qu'en raison de l'immuabilité (c'est-à-dire plus généralement RT), ces "étapes" ne peuvent pas dépendre de l'état mutable, plutôt seulement de l'ordre relationnel de la logique exprimée (c'est-à-dire l'ordre d'imbrication des appels de fonction, alias sous-expressions ).

  Par exemple, le paragraphe HTML <p>ne peut pas être affiché tant que les sous-expressions (c'est-à-dire les balises) du paragraphe n'ont pas été évaluées. Il n'y a pas d'état mutable, seulement une dépendance à l'ordre en raison de la relation logique de la hiérarchie des balises (imbrication de sous-expressions, qui sont des appels de fonction imbriqués de façon analogue ).

• Il y a donc l'attribut dérivé de l'immuabilité (plus généralement RT), que les expressions déclaratives n'expriment que les relations logiques des parties constituantes (c'est-à-dire des arguments de la fonction de sous-expression) et non les relations d' état mutables .

Ordonnance d'évaluation

Le choix de l'ordre d'évaluation des sous-expressions ne peut donner un résultat variable que lorsque l'un des appels de fonction n'est pas RT (c'est-à-dire que la fonction n'est pas pure), par exemple, un état mutable externe à une fonction est accessible dans la fonction.

Par exemple, étant donné certaines expressions imbriquées, par exemple f( g(a, b), h(c, d) ), l' évaluation avide et paresseuse des arguments de la fonction donnera les mêmes résultats si les fonctions f, get hsont pures.

Considérant que, si les fonctions f, get hne sont pas purs, le choix de l' ordre d'évaluation peut donner un résultat différent.

Remarque, les expressions imbriquées sont des fonctions imbriquées conceptuellement, car les opérateurs d'expression ne sont que des appels de fonction se faisant passer pour un préfixe unaire, un suffixe unaire ou une notation d'infixe binaire.

Tangentiellement, si tous les identifiants, par exemple a, b, c, d, sont immuables partout, l' état externe au programme ne peut pas être accessible ( par exemple E / S), et il n'y a pas de rupture de la couche d'abstraction, alors les fonctions sont toujours pures.

Soit dit en passant, Haskell a une syntaxe différente, f (g a b) (h c d).

Détails de la commande d'évaluation

Une fonction est une transition d'état (pas une valeur stockée modifiable) de l'entrée à la sortie. Pour les compositions RT d'appels à des fonctions pures , l'ordre d'exécution de ces transitions d'état est indépendant. La transition d'état de chaque appel de fonction est indépendante des autres, en raison du manque d'effets secondaires et du principe qu'une fonction RT peut être remplacée par sa valeur mise en cache . Pour corriger une idée fausse populaire , la composition monadique pure est toujours déclarative et RT , malgré le fait que la IOmonade de Haskell est sans doute impure et donc impérative par rapport à l' Worldétat extérieur au programme (mais dans le sens de la mise en garde ci-dessous, les effets secondaires sont isolés).

Une évaluation désirée signifie que les arguments des fonctions sont évalués avant l'appel de la fonction, et une évaluation paresseuse signifie que les arguments ne sont pas évalués tant que (et si) ils ne sont pas accessibles dans la fonction.

Définition : les paramètres de fonction sont déclarés sur le site de définition de fonction et les arguments de fonction sont fournis sur le site d' appel de fonction . Connaître la différence entre paramètre et argument .

Conceptuellement, toutes les expressions sont (une composition de) des appels de fonction, par exemple , les constantes sont les fonctions sans entrées, les opérateurs unaires sont des fonctions avec une entrée, les opérateurs infixes binaires sont des fonctions à deux entrées, les constructeurs sont des fonctions et des instructions de contrôle même (par exemple if, for, while) peut être modélisé avec des fonctions. L' ordre que ces arguments fonctions (ne pas confondre avec l' ordre d'appel de fonction imbriquée) sont évalués n'est pas déclarée par la syntaxe, par exemple , f( g() )pourrait évaluer avec impatience galors fsur gle résultat de » ou il pourrait évaluer fet d' évaluer que paresseusement glorsque le résultat est nécessaire à l' intérieur f.

Attention, aucun langage complet de Turing (c'est-à-dire qui permet une récursion illimitée) est parfaitement déclaratif, par exemple l'évaluation paresseuse introduit la mémoire et l'indéterminisme du temps. Mais ces effets secondaires dus au choix de l'ordre d'évaluation sont limités à la consommation de mémoire, au temps d'exécution, à la latence, à la non-terminaison, à l'hystérésis externe et donc à la synchronisation externe.

Programmation fonctionnelle

Parce que la programmation déclarative ne peut pas avoir de boucles, la seule façon d'itérer est la récursivité fonctionnelle. C'est en ce sens que la programmation fonctionnelle est liée à la programmation déclarative.

Mais la programmation fonctionnelle ne se limite pas à la programmation déclarative . La composition fonctionnelle peut être contrastée avec le sous - typage , en particulier en ce qui concerne le problème d'expression , où l'extension peut être obtenue en ajoutant des sous-types ou une décomposition fonctionnelle . L'extension peut être un mélange des deux méthodologies.

La programmation fonctionnelle fait généralement de la fonction un objet de première classe, ce qui signifie que le type de fonction peut apparaître dans la grammaire n'importe où. Le résultat est que les fonctions peuvent entrer et fonctionner sur des fonctions, permettant ainsi une séparation des préoccupations en mettant l'accent sur la composition des fonctions, c'est-à-dire en séparant les dépendances entre les sous-calculs d'un calcul déterministe.

Par exemple, au lieu d'écrire une fonction distincte (et d'employer la récursivité au lieu de boucles si la fonction doit également être déclarative) pour chacune d'un nombre infini d'actions spécialisées possibles qui pourraient être appliquées à chaque élément d'une collection, la programmation fonctionnelle utilise une itération réutilisable fonctions, par exemple map, fold, filter. Ces fonctions d'itération introduisent une fonction d'action spécialisée de première classe. Ces fonctions d'itération parcourent la collection et appellent la fonction d'action spécialisée d'entrée pour chaque élément. Ces fonctions d'action sont plus concises car elles n'ont plus besoin de contenir les instructions de bouclage pour itérer la collection.

Cependant, notez que si une fonction n'est pas pure, alors c'est vraiment une procédure. On peut peut-être affirmer que la programmation fonctionnelle qui utilise des fonctions impures, est vraiment une programmation procédurale. Ainsi, si nous convenons que les expressions déclaratives sont RT, alors nous pouvons dire que la programmation procédurale n'est pas une programmation déclarative, et ainsi nous pourrions soutenir que la programmation fonctionnelle est toujours RT et doit être un sous-ensemble de programmation déclarative.

Parallélisme

Cette composition fonctionnelle aux fonctions de premier ordre peut exprimer la profondeur du parallélisme en séparant la fonction indépendante.

Principe de Brent: le calcul avec le travail w et la profondeur d peut être implémenté dans une PRAM à processeur p dans le temps O (max (w / p, d)).

La simultanéité et le parallélisme nécessitent également une programmation déclarative , c'est-à-dire l'immuabilité et la RT.

Alors d'où vient cette hypothèse dangereuse que le parallélisme == concurrence vient? C'est une conséquence naturelle des langues avec des effets secondaires: lorsque votre langue a des effets secondaires partout, alors chaque fois que vous essayez de faire plus d'une chose à la fois, vous avez essentiellement un non-déterminisme causé par l'entrelacement des effets de chaque opération . Donc, dans les langages à effets secondaires, le seul moyen d'obtenir le parallélisme est la concurrence; il n'est donc pas surprenant que nous voyions souvent les deux confondus.

Ordonnance d'évaluation de la PF

Notez que l'ordre d'évaluation a également un impact sur les effets secondaires de terminaison et de performance de la composition fonctionnelle.

Désireux (CBV) et paresseux (CBN) sont des duels catégoriques [ 10 ], car ils ont inversé l'ordre d'évaluation, c'est-à-dire si les fonctions externes ou internes sont respectivement évaluées en premier. Imaginez un arbre à l'envers, puis évaluez avec impatience à partir des conseils de branche d'arbre de fonction jusqu'à la hiérarchie de branche jusqu'au tronc de fonction de niveau supérieur; tandis que, paresseux évalue du tronc jusqu'aux pointes de branche. Désireux n'a pas de produits conjonctifs ("et", a / k / a "produits" catégoriques) et paresseux n'a pas de coproduits disjonctifs ("ou", a / k / a "sommes" catégoriques) [ 11 ].

Performance

• Désireux

  Comme pour la non-terminaison, l'empressement est trop impatient avec la composition fonctionnelle conjonctive, c'est-à-dire que la structure de contrôle de la composition fait un travail inutile qui n'est pas fait avec paresseux. Par exemple , impatient associe ardemment et inutilement toute la liste aux booléens, lorsqu'elle est composée d'un pli qui se termine sur le premier vrai élément.

  Ce travail inutile est à l'origine du prétendu «jusqu'à» un facteur log n supplémentaire dans la complexité temporelle séquentielle de désireux contre paresseux, tous deux avec des fonctions pures. Une solution consiste à utiliser des foncteurs (par exemple des listes) avec des constructeurs paresseux (c'est-à-dire désireux de produits paresseux facultatifs), car avec impatience, l'inexactitude de l'empressement provient de la fonction interne. En effet, les produits sont des types constructifs, c.-à-d. Des types inductifs avec une algèbre initiale sur un point fixe initial [ 11 ]

• Paresseux

  Comme pour la non-terminaison, le paresseux est trop paresseux avec une composition fonctionnelle disjonctive, c'est-à-dire que la finalité coinductive peut se produire plus tard que nécessaire, ce qui entraîne à la fois un travail inutile et un non-déterminisme du retard, ce qui n'est pas le cas avec impatient [ 10 ] [ 11 ] . Des exemples de finalité sont les exceptions d'état, de synchronisation, de non-terminaison et d'exécution. Ce sont des effets secondaires impératifs, mais même dans un langage purement déclaratif (par exemple Haskell), il y a un état dans la monade IO impérative (remarque: toutes les monades ne sont pas impératives!) Implicite dans l'allocation d'espace, et le timing est un état relatif à l'impératif monde réel. L'utilisation de paresseux même avec des coproduits impatients en option entraîne une fuite de la "paresse" dans les coproduits intérieurs, car avec le paresseux, l'inexactitude de la paresse provient de la fonction extérieure(voir l'exemple dans la section Non-terminaison, où == est une fonction d'opérateur binaire externe). En effet, les coproduits sont limités par la finalité, c'est-à-dire les types coinductifs avec une algèbre finale sur un objet final [ 11 ].

  Lazy provoque un indéterminisme dans la conception et le débogage des fonctions de latence et d'espace, dont le débogage dépasse probablement les capacités de la majorité des programmeurs, en raison de la dissonance entre la hiérarchie de fonctions déclarée et l'ordre d'évaluation à l'exécution. Les fonctions pures paresseuses évaluées avec impatience, pourraient potentiellement introduire une non-terminaison inédite lors de l'exécution. Inversement, des fonctions pures avides évaluées avec paresseux pourraient potentiellement introduire un indéterminisme d'espace et de latence inédit au moment de l'exécution.

Non-résiliation

Au moment de la compilation, en raison du problème d'arrêt et de la récurrence mutuelle dans un langage complet de Turing, les fonctions ne peuvent généralement pas être garanties de se terminer.

• Désireux

  Avec impatience mais pas paresseux, pour la conjonction de Head"et" Tail, si l'un Headou l' autre Tailne se termine pas, alors respectivement soit List( Head(), Tail() ).tail == Tail()ou List( Head(), Tail() ).head == Head()n'est pas vrai parce que le côté gauche ne se termine pas, et le droit non.

  Alors que, paresseux, les deux côtés se terminent. Ainsi, impatient est trop impatient avec les produits conjonctifs et ne se termine pas (y compris les exceptions d'exécution) dans les cas où cela n'est pas nécessaire.

• Paresseux

  Avec paresseux mais pas impatient, pour la disjonction de 1"ou" 2, si fne se termine pas, alors ce List( f ? 1 : 2, 3 ).tail == (f ? List( 1, 3 ) : List( 2, 3 )).tailn'est pas vrai parce que le côté gauche se termine, et le côté droit non.

  Alors que, avec impatience aucune des deux parties ne se termine, le test d'égalité n'est jamais atteint. Ainsi, paresseux est trop paresseux avec des coproduits disjonctifs et, dans ces cas, ne se termine pas (y compris les exceptions d'exécution) après avoir fait plus de travail que ne le souhaiterait.

[ 10 ] Continuations déclaratives et dualité catégorique, Filinski, sections 2.5.4 Comparaison de CBV et CBN, et 3.6.1 CBV et CBN dans la LCS.

[ 11 ] Poursuites déclaratives et dualité catégorique, Filinski, sections 2.2.1 Produits et coproduits, 2.2.2 Objets terminaux et initiaux, 2.5.2 CBV avec les produits paresseux et 2.5.3 CBN avec les coproduits désireux.

Il n'y a pas vraiment de définition objective et non ambiguë de ceux-ci. Voici comment je les définirais:

Impératif - L'accent est mis sur les mesures que l'ordinateur doit prendre plutôt que sur ce qu'il fera (par exemple, C, C ++, Java).

Déclaratif - L'accent est mis sur ce que l'ordinateur doit faire plutôt que sur la façon dont il doit le faire (ex. SQL).

Fonctionnel - un sous-ensemble de langages déclaratifs qui met fortement l'accent sur la récursivité

impératif et déclaratif décrivent deux styles de programmation opposés. l'impératif est l'approche traditionnelle "recette étape par étape" tandis que déclarative est plus "c'est ce que je veux, maintenant vous déterminez comment le faire".

ces deux approches se produisent tout au long de la programmation - même avec le même langage et le même programme. généralement l'approche déclarative est considérée comme préférable, car elle libère le programmeur d'avoir à spécifier autant de détails, tout en ayant moins de chance de bugs (si vous décrivez le résultat souhaité, et certains processus automatiques bien testés peuvent fonctionner à rebours de celui-ci à définir les étapes, alors vous pourriez espérer que les choses sont plus fiables que de devoir spécifier chaque étape à la main).

d'autre part, une approche impérative vous donne plus de contrôle de bas niveau - c'est "l'approche microgestionnaire" de la programmation. et cela peut permettre au programmeur d'exploiter les connaissances sur le problème pour donner une réponse plus efficace. il n'est donc pas inhabituel que certaines parties d'un programme soient écrites dans un style plus déclaratif, mais que les parties critiques soient plus impératives.

comme vous pouvez l'imaginer, le langage que vous utilisez pour écrire un programme affecte la façon dont vous pouvez être déclaratif - un langage qui a des "smarts" intégrés pour déterminer ce qu'il faut faire étant donné une description du résultat va permettre une déclaration beaucoup plus déclarative approche que celle où le programmeur doit d'abord ajouter ce genre d'intelligence avec du code impératif avant de pouvoir construire une couche plus déclarative sur le dessus. ainsi, par exemple, un langage comme prolog est considéré comme très déclaratif car il a, en interne, un processus qui recherche des réponses.

jusqu'à présent, vous remarquerez que je n'ai pas mentionné la programmation fonctionnelle . c'est parce que c'est un terme dont le sens n'est pas immédiatement lié aux deux autres. à sa programmation la plus simple et fonctionnelle signifie que vous utilisez des fonctions. en particulier, que vous utilisez un langage qui prend en charge les fonctions en tant que "valeurs de première classe" - cela signifie que non seulement vous pouvez écrire des fonctions, mais vous pouvez écrire des fonctions qui écrivent des fonctions (qui écrivent des fonctions qui ...), et passez des fonctions à les fonctions. en bref - que les fonctions sont aussi flexibles et communes que des choses comme les chaînes et les nombres.

il peut donc sembler étrange que le fonctionnel, l'impératif et le déclaratif soient souvent mentionnés ensemble. la raison en est une conséquence de l'idée de programmation fonctionnelle "à l'extrême". une fonction, dans son sens le plus pur, est quelque chose de mathématique - une sorte de "boîte noire" qui prend une entrée et donne toujours la même sortie. et ce type de comportement ne nécessite pas de stocker des variables changeantes. Donc, si vous concevez un langage de programmation dont le but est de mettre en œuvre une idée très pure et mathématiquement influencée de la programmation fonctionnelle, vous finissez par rejeter, en grande partie, l'idée de valeurs qui peuvent changer (dans un certain sens technique limité).

et si vous faites cela - si vous limitez la façon dont les variables peuvent changer - alors presque par accident, vous finissez par forcer le programmeur à écrire des programmes plus déclaratifs, car une grande partie de la programmation impérative décrit comment les variables changent, et vous ne pouvez plus fais ça! il s'avère donc que la programmation fonctionnelle - en particulier, la programmation dans un langage fonctionnel - tend à donner plus de code déclaratif.

pour résumer, puis:

• impératif et déclaratif sont deux styles de programmation opposés (les mêmes noms sont utilisés pour les langages de programmation qui encouragent ces styles)

• la programmation fonctionnelle est un style de programmation où les fonctions deviennent très importantes et, par conséquent, la modification des valeurs devient moins importante. la capacité limitée à spécifier des changements de valeurs force un style plus déclaratif.

la "programmation fonctionnelle" est donc souvent décrite comme "déclarative".

En un mot:

Un langage impératif spécifie une série d'instructions que l'ordinateur exécute en séquence (faites ceci, puis faites cela).

Un langage déclaratif déclare un ensemble de règles sur les sorties qui devraient résulter de quelles entrées (par exemple, si vous avez A, alors le résultat est B). Un moteur appliquera ces règles aux entrées et donnera une sortie.

Un langage fonctionnel déclare un ensemble de fonctions mathématiques / logiques qui définissent comment l'entrée est traduite en sortie. par exemple. f (y) = y * y. c'est un type de langage déclaratif.

Impératif: comment atteindre notre objectif

   Take the next customer from a list.
   If the customer lives in Spain, show their details.
   If there are more customers in the list, go to the beginning

Déclaratif: ce que nous voulons réaliser

   Show customer details of every customer living in Spain

Programmation impérative désigne tout style de programmation où votre programme est structuré à partir d'instructions décrivant comment les opérations effectuées par un ordinateur se dérouleront .

La programmation déclarative désigne tout style de programmation où votre programme est une description du problème ou de la solution - mais n'indique pas explicitement comment le travail sera effectué .

La programmation fonctionnelle est la programmation en évaluant les fonctions et les fonctions des fonctions ... Comme la programmation fonctionnelle (strictement définie) signifie la programmation en définissant des fonctions mathématiques libres est une forme de programmation déclarative , mais ce n'est pas le seul type de programmation déclarative .

La programmation logique (par exemple dans Prolog) est une autre forme de programmation déclarative. Il s'agit de calculer en décidant si une déclaration logique est vraie (ou si elle peut être satisfaite). Le programme est généralement une série de faits et de règles - c'est-à-dire une description plutôt qu'une série d'instructions.

La réécriture de termes (par exemple CASL) est une autre forme de programmation déclarative. Elle implique une transformation symbolique des termes algébriques. C'est complètement différent de la programmation logique et de la programmation fonctionnelle.

impératif - les expressions décrivent la séquence d'actions à effectuer (associative)

déclarative - les expressions sont des déclarations qui contribuent au comportement du programme (associatif, commutatif, idempotent, monotone)

fonctionnel - les expressions n'ont de valeur que comme effet; la sémantique soutient le raisonnement équationnel

Depuis que j'ai écrit ma réponse précédente, j'ai formulé une nouvelle définition de la propriété déclarative qui est citée ci-dessous. J'ai également défini la programmation impérative comme la double propriété.

Cette définition est supérieure à celle que j'ai fournie dans ma réponse précédente, car elle est succincte et elle est plus générale. Mais il peut être plus difficile à comprendre, car les implications des théorèmes d'incomplétude applicables à la programmation et à la vie en général sont difficiles à comprendre pour les humains.

L'explication citée de la définition discute du rôle que joue la programmation fonctionnelle pure dans la programmation déclarative.

Tous les types de programmation exotiques s'inscrivent dans la taxonomie suivante de déclaratif contre impératif, puisque la définition suivante prétend qu'ils sont doubles.

Déclaratif vs impératif

La propriété déclarative est étrange, obtuse et difficile à saisir dans une définition techniquement précise qui reste générale et non ambiguë, car c'est une notion naïve que nous pouvons déclarer le sens (alias sémantique) du programme sans encourir d'effets secondaires involontaires. Il existe une tension inhérente entre l'expression du sens et l'évitement des effets involontaires, et cette tension dérive en fait des théorèmes d'incomplétude de la programmation et de notre univers.

Il est simpliste, imprécis sur le plan technique et souvent ambigu de définir le déclaratif comme « quoi faire » et l'impératif comme « comment faire » . Un cas ambigu est le « quoi » est le « comment » dans un programme qui produit un programme - un compilateur.

Évidemment, la récursion illimitée qui rend un langage de Turing complet , est également analogue dans la sémantique - pas seulement dans la structure syntaxique de l'évaluation (alias la sémantique opérationnelle). Il s'agit logiquement d'un exemple analogue au théorème de Gödel: « tout système complet d'axiomes est également incohérent ». Méditez sur l'étrangeté contradictoire de cette citation! C'est aussi un exemple qui montre comment l'expression de la sémantique n'a pas de limite prouvable, donc nous ne pouvons pas prouver 2 qu'un programme (et de façon analogue sa sémantique) stoppe alias le théorème de Halting.

Les théorèmes d'incomplétude dérivent de la nature fondamentale de notre univers, qui, comme indiqué dans la deuxième loi de la thermodynamique, est « l'entropie (alias le # de possibilités indépendantes) tend vers un maximum pour toujours ». Le codage et la conception d'un programme ne sont jamais terminés - il est vivant! - car il tente de répondre à un besoin du monde réel, et la sémantique du monde réel est en constante évolution et tend vers plus de possibilités. Les humains ne cessent de découvrir de nouvelles choses (y compris des erreurs dans les programmes ;-).

Pour capturer précisément et techniquement cette notion souhaitée susmentionnée au sein de cet univers étrange qui n'a pas de bord (réfléchissez à cela! Il n'y a pas «à l'extérieur» de notre univers), nécessite une définition laconique mais trompeusement pas simple qui sonnera incorrecte jusqu'à ce qu'elle soit expliquée profondément.

Définition:

---

La propriété déclarative est l'endroit où il ne peut exister qu'un seul ensemble d'instructions possible pouvant exprimer chaque sémantique modulaire spécifique.

La propriété impérative 3 est la dualité, où la sémantique est incohérente dans la composition et / ou peut être exprimée avec des variations d'ensembles d'énoncés.

---

Cette définition du déclaratif est distinctement locale dans sa portée sémantique, ce qui signifie qu'elle nécessite qu'une sémantique modulaire conserve sa signification cohérente, peu importe où et comment elle est instanciée et utilisée dans la portée globale . Ainsi, chaque sémantique modulaire déclarative doit être intrinsèquement orthogonale à toutes les autres possibles - et non un algorithme ou un modèle global impossible (en raison des théorèmes d'incomplétude) pour témoigner de la cohérence, ce qui est également le point de « Plus n'est pas toujours mieux » de Robert Harper, professeur d'informatique à l'Université Carnegie Mellon, l'un des concepteurs de Standard ML.

Des exemples de ces sémantiques déclaratives modulaires comprennent les foncteurs de théorie des catégories, par exemple leApplicative typage nominal, les espaces de noms, les champs nommés et les écritures au niveau opérationnel de la sémantique, puis la programmation fonctionnelle pure.

Ainsi, des langages déclaratifs bien conçus peuvent exprimer plus clairement le sens , quoique avec une certaine perte de généralité dans ce qui peut être exprimé, mais un gain dans ce qui peut être exprimé avec une cohérence intrinsèque.

Un exemple de la définition susmentionnée est l'ensemble des formules dans les cellules d'un tableur - qui ne devraient pas donner la même signification lorsqu'elles sont déplacées vers différentes cellules de colonne et de ligne, c'est-à-dire que les identificateurs de cellule ont été modifiés. Les identifiants de cellule font partie de la signification voulue et n'en sont pas superflus. Ainsi, chaque résultat de feuille de calcul est unique par rapport aux identificateurs de cellule dans un ensemble de formules. La sémantique modulaire cohérente dans ce cas est l'utilisation d'identificateurs de cellules comme entrée et sortie de fonctions pures pour les formules de cellules (voir ci-dessous).

Hyper Text Markup Language aka HTML - le langage pour les pages Web statiques - est un exemple de langage hautement (mais pas parfaitement 3 ) déclaratif qui (au moins avant HTML 5) n'avait pas la capacité d'exprimer un comportement dynamique. Le HTML est peut-être la langue la plus facile à apprendre. Pour un comportement dynamique, un langage de script impératif tel que JavaScript était généralement combiné avec HTML. Le HTML sans JavaScript correspond à la définition déclarative car chaque type nominal (c'est-à-dire les balises) conserve sa signification cohérente sous composition dans les règles de la syntaxe.

Une définition concurrente du déclaratif est les propriétés commutatives et idempotentes des instructions sémantiques, c'est-à-dire que les instructions peuvent être réorganisées et dupliquées sans changer la signification. Par exemple, les instructions affectant des valeurs aux champs nommés peuvent être réorganisées et dupliquées sans changer la signification du programme, si ces noms sont modulaires par rapport à un ordre implicite. Les noms impliquent parfois un ordre, par exemple les identifiants de cellule incluent leur position de colonne et de ligne - déplacer un total sur une feuille de calcul change sa signification. Sinon, ces propriétés nécessitent implicitement une valeur globalecohérence de la sémantique. Il est généralement impossible de concevoir la sémantique des instructions afin qu'elles restent cohérentes si elles sont ordonnées ou dupliquées de manière aléatoire, car l'ordre et la duplication sont intrinsèques à la sémantique. Par exemple, les énoncés «Foo existe» (ou construction) et «Foo n'existe pas» (et destruction). Si l'on considère l'incohérence aléatoire endémique de la sémantique voulue, alors on accepte cette définition comme suffisamment générale pour la propriété déclarative. En substance, cette définition est vide en tant que définition généralisée car elle tente de rendre la cohérence orthogonale à la sémantique, c'est-à-dire de défier le fait que l'univers de la sémantique est dynamiquement illimité et ne peut pas être capturé dans un paradigme de cohérence globale .

Le fait d'exiger les propriétés commutatives et idempotentes pour (l'ordre d'évaluation structurelle de) la sémantique opérationnelle de niveau inférieur convertit la sémantique opérationnelle en une sémantique modulaire localisée déclarative , par exemple la programmation fonctionnelle pure (y compris la récursion au lieu des boucles impératives). Ensuite, l'ordre opérationnel des détails d'implémentation n'affecte pas (c'est-à-dire se propage globalement ) la cohérence de la sémantique de niveau supérieur. Par exemple, l'ordre d'évaluation (et théoriquement également la duplication des) formules de feuille de calcul n'a pas d'importance car les sorties ne sont copiées dans les entrées qu'après que toutes les sorties ont été calculées, c'est-à-dire de manière analogue aux fonctions pures.

C, Java, C ++, C #, PHP et JavaScript ne sont pas particulièrement déclaratifs. La syntaxe de Copute et la syntaxe de Python sont couplées de manière plus déclarative aux résultats escomptés , c'est-à-dire à une sémantique syntaxique cohérente qui élimine les étrangers afin que l'on puisse facilement comprendre le code après l'avoir oublié. Copute et Haskell imposent le déterminisme de la sémantique opérationnelle et encouragent « ne vous répétez pas » (DRY), car ils ne permettent que le paradigme fonctionnel pur.

---

2 Même lorsque nous pouvons prouver la sémantique d'un programme, par exemple avec le langage Coq, cela est limité à la sémantique qui est exprimée dans le typage , et le typage ne peut jamais capturer toute la sémantique d'un programme - pas même pour les langages qui sont pas Turing complet, par exemple avec HTML + CSS, il est possible d'exprimer des combinaisons incohérentes qui ont donc une sémantique non définie.

3 De nombreuses explications prétendent à tort que seule la programmation impérative a des instructions ordonnées syntaxiquement. J'ai clarifié cette confusion entre programmation impérative et programmation fonctionnelle . Par exemple, l'ordre des instructions HTML ne réduit pas la cohérence de leur signification.

Edit: J'ai posté le commentaire suivant sur le blog de Robert Harper:

en programmation fonctionnelle ... la plage de variation d'une variable est un type

Selon la façon dont on distingue la programmation fonctionnelle de la programmation impérative, votre «assignable» dans un programme impératif peut également avoir un type qui limite la variabilité.

La seule définition non confuse que j'apprécie actuellement pour la programmation fonctionnelle est a) les fonctions en tant qu'objets et types de première classe, b) la préférence pour la récursivité sur les boucles, et / ou c) les fonctions pures - c'est-à-dire les fonctions qui n'ont pas d'impact sur la sémantique souhaitée du programme lorsqu'il est mémorisé ( _{^{donc la programmation fonctionnelle parfaitement pure n'existe pas dans une sémantique dénotationnelle à usage général en raison des impacts de la sémantique opérationnelle, par exemple l'allocation de mémoire}} ).

La propriété idempotente d'une fonction pure signifie que l'appel de fonction sur ses variables peut être substitué par sa valeur, ce qui n'est généralement pas le cas pour les arguments d'une procédure impérative. Les fonctions pures semblent être déclaratives par rapport aux transitions d'état non composées entre les types d'entrée et de résultat.

Mais la composition des fonctions pures ne maintient pas une telle cohérence, car il est possible de modéliser un processus impératif d'effets secondaires (état global) dans un langage de programmation fonctionnel pur, par exemple IOMonad de Haskell et de plus il est tout à fait impossible d'empêcher de le faire dans tout langage de programmation fonctionnel pur de Turing.

Comme je l'ai écrit en 2012, ce qui semble au même consensus de commentaires dans votre récent blog , que la programmation déclarative est une tentative de capturer l'idée que la sémantique prévue n'est jamais opaque. Des exemples de sémantique opaque sont la dépendance à l’ordre, la dépendance à l’effacement de la sémantique de niveau supérieur au niveau de la couche sémantique opérationnelle (par exemple, les transtypages ne sont pas des conversions et les génériques réifiés limitent la sémantique de niveau supérieur ), et la dépendance à des valeurs variables qui ne peuvent pas être vérifiées (prouvées correct) par le langage de programmation.

J'ai donc conclu que seules les langues complètes non-Turing peuvent être déclaratives.

Ainsi, un attribut non ambigu et distinct d'un langage déclaratif pourrait être qu'il peut être prouvé que sa sortie obéit à un ensemble énumérable de règles génératives. Par exemple, pour tout programme HTML spécifique (en ignorant les différences de divergence entre les interpréteurs) qui n'est pas scripté (c'est-à-dire n'est pas Turing complet), sa variabilité de sortie peut être énumérable. Ou plus succinctement, un programme HTML est une fonction pure de sa variabilité. Idem un tableur est une fonction pure de ses variables d'entrée.

Il me semble donc que les langages déclaratifs sont l'antithèse de la récursion illimitée , c'est-à-dire que selon le deuxième théorème d'incomplétude de Gödel, les théorèmes autoréférentiels ne peuvent pas être prouvés.

Lesie Lamport a écrit un conte de fées sur la façon dont Euclide aurait pu contourner les théorèmes d'incomplétude de Gödel appliqués aux preuves mathématiques dans le contexte du langage de programmation par la congruence entre les types et la logique (correspondance Curry-Howard, etc.).

Programmation impérative: dire à la «machine» comment faire quelque chose et, par conséquent, ce que vous voulez arriver se produira.

Programmation déclarative: dire à la «machine» ce que vous aimeriez faire et laisser l'ordinateur comprendre comment le faire.

Exemple d'impératif

function makeWidget(options) {
    const element = document.createElement('div');
    element.style.backgroundColor = options.bgColor;
    element.style.width = options.width;
    element.style.height = options.height;
    element.textContent = options.txt;

    return element;
}

Exemple de déclaratif

function makeWidget(type, txt) {
    return new Element(type, txt);
}

Remarque: La différence n'est pas une question de brièveté, de complexité ou d'abstraction. Comme indiqué, la différence est comment et quoi .

De nos jours, nouvelle orientation: nous avons besoin des anciennes classifications?

Les aspects impératifs / déclaratifs / fonctionnels étaient bons dans le passé pour classer les langages génériques, mais de nos jours, tous les "gros langages" (comme Java, Python, Javascript, etc.) ont une option (généralement des cadres ) pour s'exprimer avec "autre concentration" que son principal (impératif habituel), et pour exprimer des processus parallèles, des fonctions déclaratives, des lambdas, etc.

Une bonne variante de cette question est donc "Quel aspect est bon de classer les frameworks aujourd'hui?" ... Un aspect important est quelque chose que nous pouvons étiqueter "style de programmation" ...

Focus sur la fusion des données avec l'algorithme

Un bon exemple à expliquer. Comme vous pouvez le lire sur jQuery sur Wikipedia ,

L'ensemble des fonctionnalités de base de jQuery - sélections d'éléments DOM, traversée et manipulation -, activé par son moteur de sélection (...), a créé un nouveau "style de programmation", fusionnant des algorithmes et des structures de données DOM

Donc jQuery est le meilleur exemple (populaire) de se concentrer sur un "nouveau style de programmation" , qui n'est pas seulement l'orientation des objets, est " Fusionner les algorithmes et les structures de données ". jQuery est quelque peu réactif car les feuilles de calcul, mais pas "orientées cellule", sont " orientées DOM-node " ... Comparaison des principaux styles dans ce contexte:

1. Pas de fusion : dans tous les "grands langages", dans toute expression fonctionnelle / déclarative / impérative, l'habituel est "pas de fusion" des données et des algorithmes, sauf par une certaine orientation d'objet, c'est-à-dire une fusion au strict point de vue de la structure algébrique .

2. Un peu de fusion : toutes les stratégies classiques de fusion, ont de nos jours un cadre l'utilisant comme paradigme ... flux de données , programmation événementielle (ou anciens langages spécifiques au domaine comme awk et XSLT ) ... Comme la programmation avec des feuilles de calcul modernes, elles sont aussi exemples de style de programmation réactive .

3. Big fusion : c'est "le style jQuery" ... jQuery est un langage spécifique au domaine qui se concentre sur "les algorithmes de fusion et les structures de données DOM ".
   PS: d'autres "langages de requête", comme XQuery, SQL (avec PL comme option d'expression impérative) sont également des exemples de fusion d'algorithmes de données, mais ce sont des îles , sans fusion avec d'autres modules système ... Spring , lors de l'utilisation de find()-variants et les clauses de spécification , est un autre bon exemple de fusion.

La programmation déclarative est la programmation en exprimant une logique intemporelle entre l'entrée et la sortie, par exemple, en pseudocode, l'exemple suivant serait déclaratif:

def factorial(n):
  if n < 2:
    return 1
  else:
    return factorial(n-1)

output = factorial(argvec[0])

Nous définissons simplement une relation appelée «factorielle» ici, et définissons la relation entre la sortie et l'entrée comme cette relation. Comme cela devrait être évident ici, à propos de tout langage structuré permet la programmation déclarative dans une certaine mesure. Une idée centrale de la programmation déclarative est les données immuables, si vous les affectez à une variable, vous ne le faites qu'une seule fois, puis plus jamais. D'autres définitions plus strictes impliquent qu'il peut n'y avoir aucun effet secondaire, ces langues sont parfois appelées «purement déclaratives».

Le même résultat dans un style impératif serait:

a = 1
b = argvec[0]
while(b < 2):
  a * b--

output = a

Dans cet exemple, nous n'avons exprimé aucune relation logique statique intemporelle entre l'entrée et la sortie, nous avons modifié les adresses mémoire manuellement jusqu'à ce que l'une d'elles contienne le résultat souhaité. Il devrait être évident que tous les langages autorisent la sémantique déclarative dans une certaine mesure, mais pas tous l'impératif, certains langages déclaratifs «purement» permettent des effets secondaires et des mutations tout à fait.

On dit souvent que les langages déclaratifs spécifient «ce qui doit être fait», par opposition à «comment le faire», je pense que c'est un terme impropre, les programmes déclaratifs spécifient toujours comment on doit passer de l'entrée à la sortie, mais d'une autre manière, le la relation que vous spécifiez doit être effectivement calculable (terme important, recherchez-le si vous ne le connaissez pas). Une autre approche est la programmation non déterministe , qui spécifie vraiment quelles conditions un résultat remplit beaucoup, avant que votre implémentation n'épuise tous les chemins en essais et erreurs jusqu'à ce qu'elle réussisse.

Les langages purement déclaratifs incluent Haskell et Pure Prolog. Une échelle mobile de l'un à l'autre serait: Pure Prolog, Haskell, OCaml, Scheme / Lisp, Python, Javascript, C--, Perl, PHP, C ++, Pascall, C, Fortran, Assembly

Quelques bonnes réponses ici concernant les "types" notés.

Je soumets quelques concepts supplémentaires, plus "exotiques" souvent associés à la foule de programmation fonctionnelle:

• Langage spécifique au domaine ou programmation DSL : création d'un nouveau langage pour traiter le problème en cours.
• Méta-programmation : lorsque votre programme écrit d'autres programmes.
• Programmation évolutive : où vous construisez un système qui s'améliore continuellement ou génère successivement de meilleures générations de sous-programmes.

Je pense que votre taxonomie est incorrecte. Il existe deux types opposés impératif et déclaratif. Fonctionnel n'est qu'un sous-type de déclaratif. BTW, wikipedia déclare le même fait.

En un mot, plus un style de programmation met l'accent sur ce que (faire) en faisant abstraction des détails de comment (le faire), plus ce style est considéré comme déclaratif. L'inverse est vrai pour l'impératif. La programmation fonctionnelle est associée au style déclaratif.