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


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


445
2018-03-02 14:03


origine


Réponses:


Au moment d'écrire ceci, les réponses les mieux 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 Wikipédia. Certaines réponses confondent les termes de différentes manières.

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

En outre, plusieurs réponses affirment que la programmation fonctionnelle doit être un sous-ensemble de déclaration. Sur ce point, cela dépend si nous distinguons "fonction" de "procédure". Permet de gérer impérativement vs déclaratif en premier.

Définition de expression déclarative

le seulement attribut qui peut éventuellement différencier un déclaratif expression d'un impératif expression 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 déclaratif à 100% (c'est-à-dire un langage dans lequel chaque expression possible est RT) ne permet pas (parmi d'autres exigences RT) la mutation de valeurs stockées, par ex. HTML et la plupart des Haskell.

Définition de 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, de sorte que certaines personnes ne sont pas d'accord pour dire que «aucun effet secondaire» n'est identique à RT. RT a un définition précise.

Puisque chaque sous-expression est conceptuellement un appel de fonction, RT exige que l'implémentation d'une fonction (c'est-à-dire la ou les expressions à l'intérieur de la fonction appelée) ne puisse pas accéder à l'état mutable qui est externe à la fonction (accès à mutable local Etat est autorisée). En termes simples, la fonction (implémentation) devrait être pur.

Définition de fonction pure

Une fonction pure est souvent dite "sans effets secondaires". 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 toute sortie.

N'oubliez pas que RT s'applique aux expressions (qui incluent les appels de fonctions) et que la pureté s'applique aux fonctions (mises en œuvre de).

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

Attributs dérivés de RT

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

Notez, l'immutabilité de valeurs externes est un sous-ensemble des exigences pour RT.

  • Les langages déclaratifs n'ont pas de structures de contrôle en boucle, par ex. for et while, car en raison de l'immuabilité, la condition de boucle ne changera jamais.

  • Les langages déclaratifs n'expriment pas de flux de contrôle autre que l'ordre de fonction imbriqué (a.k.a dépendances logiques), car en raison de l'immuabilité, les 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 la fonction RT imbriquée), mais le fait que chaque appel de fonction soit une sémantique de niveau supérieur (c'est-à-dire "quoi faire") n'est pas exigé. La distinction de l'impératif est que en raison de l'immuabilité (plus généralement RT), ces "étapes" ne peuvent pas dépendre de l'état mutable, mais seulement de l'ordre relationnel de la logique exprimée (c'est-à-dire l'ordre d'imbrication des appels de fonction, a.k.a sous-expressions).

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

  • Ainsi, il y a l'attribut dérivé de l'immutabilité (plus généralement RT), que les expressions déclaratives, expriment seulement la logique relations des parties constituantes (c'est-à-dire des arguments de la fonction de sous-expression) et non état mutable des relations.

Ordre d'évaluation

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

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

Considérant que, si les fonctions f, g, et h ne sont pas pures, alors le choix de l'ordre d'évaluation peut donner un résultat différent.

Notez que les expressions imbriquées sont des fonctions imbriquées conceptuellement, puisque 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 infixe binaire.

Tangentiellement, si tous les identificateurs, par ex. a, b, c, d, sont immuable partout, on ne peut accéder à l'état externe au programme (c'est-à-dire aux E / S), et il n'y a pas de rupture de couche d'abstraction, alors les fonctions sont toujours pures.

Par ailleurs, 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 mutable) de l'entrée à la sortie. Pour les compositions RT d'appels à pur fonctions, 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 de l'absence d'effets secondaires et du principe qu'un La fonction RT peut être remplacée par sa valeur en cache. À corriger une idée fausse populaire, la composition monadique pure est toujours déclaratif et RT, malgré le fait que Haskell IO monade est sans doute impur et donc impératif w.r.t. la World état externe au programme (mais dans le sens de la mise en garde ci-dessous, les effets secondaires sont isolés).

L'évaluation Eager signifie que les arguments des fonctions sont évalués avant l'appel de la fonction, et que l'évaluation paresseuse les arguments ne sont pas évalués jusqu'à (et si) ils sont accédés dans la fonction.

Définition: fonction paramètres sont déclarés à la fonction définition site, et fonction arguments sont fournis à la fonction appel site. Connaître la différence entre paramètre et argument.

Conceptuellement, toutes les expressions sont (une composition de) appels de fonction, par ex. les constantes sont des fonctions sans entrées, les opérateurs unaires sont des fonctions avec une entrée, les opérateurs infixes binaires sont des fonctions avec deux entrées, les constructeurs sont des fonctions et même des instructions de contrôle (par ex. if, for, while) peut être modélisé avec des fonctions. le ordonner que ces  argument les fonctions (ne pas confondre avec l'ordre d'appel de la fonction imbriquée) sont évaluées et ne sont pas déclarées par la syntaxe, par ex. f( g() ) pourrait évaluer avec impatience g puis f sur gle résultat ou il pourrait évaluer f et seulement évaluer paresseusement g quand son résultat est nécessaire dans f.

Avertissement, non Turing complet le langage (c'est-à-dire qui permet une récursivité illimitée) est parfaitement déclaratif, par ex. L'évaluation paresseuse introduit l'indéterminisme de la mémoire et 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-fin, et hystérésis externe donc synchronisation externe.

Programmation fonctionnelle

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

Mais la programmation fonctionnelle n'est pas limitée à la programmation déclarative. La composition fonctionnelle peut être contrasté avec le sous-typage, en particulier en ce qui concerne Problème d'expression, où l'extension peut être réalisée par soit 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ù n'importe quel autre type. Le résultat est que les fonctions peuvent entrer et opérer sur des fonctions, permettant ainsi la 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 séparée (et utilisant 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 emploie des fonctions d'itération réutilisables, par ex. 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 en boucle pour itérer la collection.

Cependant, notez que si une fonction n'est pas pure, alors c'est vraiment une procédure. Nous pouvons peut-être soutenir que la programmation fonctionnelle qui utilise des fonctions impures est vraiment une programmation procédurale. Ainsi, si nous sommes d'accord que les expressions déclaratives sont RT, alors nous pouvons dire que la programmation procédurale n'est pas une programmation déclarative, et donc nous pourrions argumenter 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 la profondeur dans le parallélisme en séparant la fonction indépendante.

Le principe de Brent: calcul avec travail w et profondeur d peut être   implémenté dans un PRAM p-processeur en temps O (max (w / p, d)).

La simultanéité et le parallélisme aussi nécessite une programmation déclarative, c’est-à-dire immuabilité et RT.

Alors d'où vient cette supposition dangereuse que le parallélisme == Concurrence   viens de? C'est une conséquence naturelle des langues avec des effets secondaires:   quand votre langue a des effets secondaires partout, alors chaque fois que vous essayez   faire plus d'une chose à la fois, vous avez essentiellement   non-déterminisme causé par l'entrelacement des effets de chaque   opération. Donc, dans les langues secondaires, la seule façon d'obtenir   le parallélisme est la simultanéité; il n'est donc pas surprenant que nous   souvent voir les deux confondus.

Ordre d'évaluation de la PF

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

Eager (CBV) et paresseux (CBN) sont des duels catégoriques [dix], car ils ont inversé l'ordre d'évaluation, c'est-à-dire si les fonctions externes ou internes sont évaluées en premier. Imaginez un arbre à l'envers, puis avide évalue à partir de la branche de l'arbre de fonction remonte la hiérarchie de la branche vers le tronc de fonction de niveau supérieur; tandis que, paresseux évalue du tronc vers le bas aux conseils de branche. Eager 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 avec la non-résiliation, impatient est trop désireux 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. Pour Exemple, désireux d'attacher avec empressement et inutilement la liste entière aux booléens, lorsqu'elle est composée d'un pli qui se termine sur le premier élément vrai.

    Ce travail inutile est la cause du prétendu "jusqu'à" un supplément log n facteur dans le temps séquentiel complexité de désireux paresseux, à la fois avec des fonctions pures. Une solution consiste à utiliser des foncteurs (par exemple, des listes) avec des constructeurs paresseux (c’est-à-dire avides de produits paresseux facultatifs), car avec une impatience, l’inconvénient provient de la fonction interne. C’est parce que les produits sont des types constructifs, c’est-à-dire des types inductifs avec une algèbre initiale sur un point de repère initial [11]

  • Paresseux

    Comme avec la non-résiliation, la paresse est trop paresseuse avec la composition fonctionnelle disjonctive, c’est-à-dire que la finalité coinductive peut se produire plus tard que nécessaire, entraînant à la fois un travail inutile et un déterminisme tardif.dix] [11] Des exemples de finalité sont les exceptions d'état, de temporisation, 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 existe un état dans la monade IO impérative (note: toutes les monades ne sont pas impératives!) Implicite dans l'allocation d'espace et le monde réel. Utiliser la paresse même avec des coproduits avides facultatifs fuit la "paresse" dans les coproduits intérieurs, car provient de la fonction externe (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 coinducteurs avec une algèbre finale sur un objet final [11]

    Lazy provoque l’indéterminisme dans la conception et le débogage des fonctions pour la latence et l’espace, dont le débogage dépasse probablement les capacités de la majorité des programmeurs, à cause de la dissonance entre la hiérarchie des fonctions déclarées et l'ordre d'évaluation de l'exécution. Les fonctions pures paresseuses évaluées avec impatience pourraient potentiellement introduire une non-résiliation inédite au moment de l'exécution. Inversement, des fonctions pures désirées évaluées avec paresse pourraient potentiellement introduire un indéterminisme de latence et de latence inaperçu au moment de l'exécution.

Non résiliation

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

  • Désireux

    Avec impatient mais pas paresseux, pour la conjonction de Head "et" Tail, si soit Head ou Tail ne se termine pas, puis 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 côté droit le fait.

    Considérant que, avec paresseux les deux côtés se terminent. Ainsi, impatient est trop avide de produits conjonctifs, et non-aboutit (y compris les exceptions d'exécution) dans les cas où cela n'est pas nécessaire.

  • Paresseux

    Avec paresseux mais pas désireux, pour la disjonction de 1 "ou" 2, si f ne se termine pas, alors 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 que le côté droit ne le fait pas.

    Alors qu'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 parvient pas à se terminer (y compris les exceptions d'exécution) après avoir fait plus de travail que désireux.

[dix] Continuation déclarative et dualité catégorique, Filinski, sections 2.5.4 Une comparaison de CBV et CBN, et 3.6.1 CBV et CBN dans le SCL.

[11] Continuation déclarative et dualité catégorique, Filinski, sections 2.2.1 Produits et coproduits, 2.2.2 Objets terminaux et initiaux, 2.5.2 CBV avec produits paresseux, et 2.5.3 CBN avec coproduits enthousiastes.


242
2017-12-02 14:11



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

Impératif - L’accent est mis sur les mesures à prendre par l’ordinateur plutôt que sur ce que l’ordinateur va faire (ex. C, C ++, Java).

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

Fonctionnel - un sous-ensemble de langages déclaratifs fortement centrés sur la récursivité


98
2018-03-02 14:11



impératif et déclaratif décrire deux styles de programmation opposés. impératif est l'approche traditionnelle "recette par étape" tandis que déclaratif est plus "c'est ce que je veux, maintenant vous travaillez sur la façon de 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. En général, l'approche déclarative est préférable, car elle libère le programmeur d'avoir à spécifier autant de détails, tout en réduisant les risques de bogues (si vous décrivez le résultat que vous voulez, et qu'un processus automatique bien testé peut revenir en arrière). définissez les étapes, vous pouvez alors espérer que les choses sont plus fiables que d'avoir à spécifier chaque étape à la main).

D'un autre côté, une approche impérative vous donne un contrôle plus bas - c'est l'approche "micromanager" 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 rare que certaines parties d'un programme soient écrites dans un style plus déclaratif, mais pour 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 intégré "l'intelligence" pour savoir quoi faire étant donné qu'une description du résultat va permettre une déclaration beaucoup plus déclarative approche que le programmeur doit d'abord ajouter ce type d'intelligence avec le 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 comporte un processus intégré qui recherche les réponses.

jusqu'à présent, vous remarquerez que je n'ai pas mentionné fonctionnel la programmation. c'est parce que c'est un terme dont le sens n'est pas immédiatement lié aux deux autres. à sa plus simple, la programmation fonctionnelle signifie que vous utilisez des fonctions. en particulier, que vous utilisez un langage qui supporte les fonctions comme "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 (écrire des fonctions ...), et passer des fonctions à les fonctions. en bref, les fonctions sont aussi flexibles et communes que les chaînes et les nombres.

il peut donc sembler étrange que les termes fonctionnel, impératif et déclaratif soient souvent mentionnés ensemble. la raison en est que l’idée de la programmation fonctionnelle est poussée à 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 certaine entrée et donne toujours la même sortie. et ce genre de comportement ne nécessite pas de stocker des variables changeantes. 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, parce qu'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 un code plus déclaratif.

pour résumer, alors:

  • 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, les changements de valeurs deviennent moins importants. la capacité limitée à spécifier des changements de valeurs force un style plus déclaratif.

la "programmation fonctionnelle" est donc souvent qualifiée de "déclarative".


50
2017-09-05 02:36



En un mot:

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

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

UNE Langage fonctionnel déclare un ensemble de fonctions mathématiques / logiques qui définissent comment les entrées sont traduites en sortie. par exemple. f (y) = y * y. c'est un type de langage déclaratif.


50
2018-03-02 17:18



Impératif: Comment pour 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: quelle nous voulons atteindre

   Show customer details of every customer living in Spain

23
2017-10-23 18:45



Programmation impérative signifie tout style de programmation où votre programme est structuré hors des instructions décrivant comment les opérations effectuées par un ordinateur se produira.

Programmation déclarative signifie n'importe quel 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 fait.

Programmation fonctionnelle est la programmation en évaluant les fonctions et les fonctions des fonctions ... En tant que programmation fonctionnelle (strictement définie), on programme en définissant des fonctions mathématiques libres d'effet est une forme de programmation déclarative mais ce n'est pas le seul type de programmation déclarative.

Programmation logique (par exemple dans Prolog) est une autre forme de programmation déclarative. Cela implique le calcul en décidant si une déclaration logique est vraie (ou si elle peut être satisfaite). Le programme est typiquement une série de faits et de règles - c'est-à-dire une description plutôt qu'une série d'instructions.

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


19
2018-05-03 11:07



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

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

fonctionnel - les expressions ont valeur comme seul effet; la sémantique supporte le raisonnement équationnel


12
2017-08-07 01:27



Depuis que j'ai écrit ma réponse précédente, j'ai formulé 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 propriété duale.

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

L’explication citée de la définition traite du rôle pur la programmation fonctionnelle joue dans la programmation déclarative.

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

Déclaratif vs. Impératif

La propriété déclarative est bizarre, obtuse et difficile à capturer dans une définition techniquement précise qui reste générale et non ambiguë, parce que c'est une notion naïve que nous pouvons déclarer la signification (a.k.a sémantique) du programme sans encourir des effets secondaires inattendus. Il y a une tension inhérente entre l'expression de la signification et l'évitement des effets non intentionnels, et cette tension provient en fait de la théorèmes d'incomplétude de la programmation et de notre univers.

C'est trop simplifié, techniquement imprécis, et souvent ambigu pour définir déclaratif comme "Que faire" et impératif comme "comment faire". Un cas ambigu est le "quelle" est le "Comment"Dans un programme qui produit un programme - un compilateur.

Evidemment le récursivité illimitée qui rend une langue complète Turing, est également analogue dans la sémantique - pas seulement dans la structure syntaxique de l'évaluation (a.k.a sémantique opérationnelle). C'est logiquement un exemple analogue au théorème de Gödel- "tout système complet d'axiomes est également incohérent". Réfléchis à l'étrangeté contradictoire de cette citation! C'est aussi un exemple qui montre comment l'expression de la sémantique n'a pas de lien prouvable, donc nous ne pouvons pas prouver2 qu'un programme (et, par analogie, sa sémantique) arrête 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 (a.k.a. le nombre de possibilités indépendantes) est tendance au maximum pour toujours". Le codage et la conception d'un programme n'est jamais fini - il est vivant! - parce qu'il essaie de répondre à un besoin du monde réel, et la sémantique du monde réel change et tend toujours vers plus de possibilités. Les humains ne cessent jamais de découvrir de nouvelles choses (y compris des erreurs dans les programmes ;-).

Pour capturer précisément et techniquement cette notion désirée ci-dessus dans cet univers bizarre qui n'a pas de bord (réfléchissez qu'il n'y a pas "extérieur" de notre univers), exige une définition succincte mais faussement-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 possible d'instructions pouvant exprimer chaque sémantique modulaire spécifique.

La propriété impérative3 est le dual, 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 local dans la portée sémantique, ce qui signifie qu'il exige qu'une sémantique modulaire conserve sa signification cohérente, peu importe où et comment elle est instanciée et utilisée dans global portée. Ainsi, chaque sémantique modulaire déclarative devrait être intrinsèquement orthogonale à tous les autres possibles - et non pas impossible (en raison de théorèmes d'incomplétude) global algorithme ou modèle pour témoigner de la cohérence, ce qui est aussi le but de "Plus n'est pas toujours meilleur»Par 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 des foncteurs de théorie de catégories, p. Ex. la Applicative, typage nominal, espaces de noms, champs nommés et w.r.t. au niveau opérationnel de la sémantique puis de la programmation fonctionnelle pure.

Ainsi, des langages déclaratifs bien conçus peuvent exprimer plus clairement le sens, quoiqu'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 mentionnée ci-dessus est l'ensemble des formules dans les cellules d'un tableur - qui ne devraient pas avoir le même sens lorsqu'il est déplacé vers des cellules de colonnes et de lignes différentes, c'est-à-dire des identifiants de cellule changés. Les identifiants de cellule font partie de la signification voulue et ne sont pas superflus. Chaque résultat de feuille de calcul est donc unique. aux identificateurs de cellule dans un ensemble de formules. La sémantique modulaire cohérente dans ce cas est l'utilisation d'identifiants de cellules comme entrée et sortie de pur fonctions pour les formules de cellules (voir ci-dessous).

Hyper Text Markup Language a.k.a. HTML - le langage pour les pages Web statiques - est un exemple d'un haut (mais pas parfaitement3) langage déclaratif qui (au moins avant HTML 5) n'avait pas la capacité d'exprimer un comportement dynamique. 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. HTML sans JavaScript correspond à la définition déclarative car chaque type nominal (c'est-à-dire les balises) conserve sa signification cohérente sous la composition dans les règles de la syntaxe.

Une définition concurrente pour déclarative est la commutatif et idempotent propriétés des déclarations sémantiques, c'est-à-dire que les instructions peuvent être réorganisées et dupliquées sans changer le sens. Par exemple, les instructions affectant des valeurs à des champs nommés peuvent être réorganisées et dupliquées sans changer la signification du programme, si ces noms sont modulaires w.r.t. à toute commande implicite. Les noms impliquent parfois un ordre, par ex. les identifiants de cellule incluent leur position de colonne et de ligne - le déplacement d'un total sur une feuille de calcul change sa signification. Sinon, ces propriétés nécessitent implicitement global cohérence de la sémantique. Il est généralement impossible de concevoir la sémantique des instructions pour 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 expressions "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 assez générale pour la propriété déclarative. Essentiellement, 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 ne soit pas lié de manière dynamique global paradigme de cohérence.

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 déclaration localisé sémantique modulaire, par ex. pur programmation fonctionnelle (y compris récursivité au lieu de boucles impératives). Ensuite, l’ordre opérationnel des détails de la mise en œuvre n’a pas d’impact (c’est-à-dire globalement dans) la cohérence de la sémantique de niveau supérieur. Par exemple, l'ordre d'évaluation (et théoriquement aussi la duplication) des formules de tableur n'a pas d'importance car les sorties ne sont pas copiées sur les entrées avant que toutes les sorties aient été calculées, c'est-à-dire analogues 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 plus déclaratives couple a   résultats attendus, c’est-à-dire une sémantique syntaxique cohérente qui élimine les parasites afin que l’on puisse facilement   comprendre le code après l'avoir oublié. Copute et Haskell appliquent   déterminisme de la sémantique opérationnelle et encourager "ne répète pas   toi même"(DRY), parce qu'ils permettent seulement le paradigme fonctionnel pur.


2Même là où nous pouvons prouver la sémantique d'un programme, par ex. avec le langage Coq, cela se limite à la sémantique exprimée dans la dactylographieet la saisie ne peut jamais capturer toute la sémantique d'un programme, même pour les langues qui ne sont pas complètes, par ex. 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 comporte des instructions ordonnées de manière syntaxique. J'ai clarifié cela confusion entre programmation impérative et 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 comment on distingue fonctionnel d'impératif   la programmation, votre «assignable» dans un programme impératif peut aussi avoir   un type plaçant une limite sur sa variabilité.

La seule définition non confuse que j'apprécie actuellement pour le fonctionnel   la programmation est a) fonctionne comme des objets et des types de première classe, b)   préférence pour la récursivité sur les boucles, et / ou c) les fonctions pures - c.-à-d.   les fonctions qui n'affectent pas la sémantique souhaitée de   programme lorsqu'il est mémorisé (donc parfaitement pur fonctionnel   la programmation n'existe pas dans une sémantique dénotationnelle d'usage général   en raison des impacts de la sémantique opérationnelle, par ex. Mémoire   allocation).

La propriété idempotent d’une fonction pure signifie l’appel de fonction sur   ses variables peuvent être substituées par sa valeur, qui n'est généralement pas   le cas pour les arguments d'une procédure impérative. Fonctions pures   semble être déclarative w.r.t. aux transitions d'état sans décomposition   entre les types d'entrée et de résultat.

Mais la composition des fonctions pures n’en maintient pas   cohérence, car il est possible de modéliser un effet secondaire (global   état) processus impératif dans un langage de programmation purement fonctionnel,   par exemple. IOMonad de Haskell et d'ailleurs il est tout à fait impossible de   empêcher de le faire dans toute programmation fonctionnelle pure complète de Turing   la langue.

Comme je a écrit en 2012, ce qui semble être le même consensus   commentaires dans votre blog récent, cette programmation déclarative est un   tenter de capturer la notion que la sémantique prévue ne sont jamais   opaque. Les exemples de sémantique opaque sont la dépendance à l'ordre,   dépendance à l'effacement de la sémantique de niveau supérieur au niveau opérationnel   couche de sémantique (par ex. les moulages ne sont pas des conversions et des génériques réifiés   limiter la sémantique de niveau supérieur), et la dépendance aux valeurs variables   qui ne peut pas être vérifié (prouvé correct) par le langage de programmation.

J'ai donc conclu que seuls les langages complets non Turing peuvent être   déclaratif.

Ainsi un attribut non ambigu et distinct d'un langage déclaratif   pourrait être que sa production peut être prouvée à obéir à un ensemble énumérable de   règles génératives. Par exemple, pour tout programme HTML spécifique (en ignorant   différences dans les manières dont les interprètes divergent) qui n'est pas scripté   (c'est-à-dire que Turing n'est pas complète) alors sa variabilité de sortie peut être   énumérable. Ou plus succinctement un programme HTML est une fonction pure de   sa variabilité. Ditto un tableur est une fonction pure de son   variables d'entrée.

Il me semble donc que les langues déclaratives sont l'antithèse de    récursivité illimitée, c'est-à-dire par la deuxième incomplétude de Gödel   Les théorèmes théoriques auto-référentiels ne peuvent être prouvés.

Lesie Lamport a écrit un conte de fées sur la façon dont Euclide pourrait avoir   travaillé autour des 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   logique (correspondance de Curry-Howard, etc.)


7
2018-03-13 10:06



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

Programmation déclarative: dire à la "machine" ce que vous souhaitez faire et laisser l’ordinateur trouver le moyen de 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 contre quelle.


5
2017-12-19 18:21