Comment fonctionnent les langages de programmation fonctionnels?

Si les langages de programmation fonctionnels ne peuvent enregistrer aucun état, comment font-ils des opérations simples, comme la lecture de données d’un utilisateur? Comment peuvent-ils “stocker” l’entrée (ou stocker des données à ce sujet?)

Par exemple: comment cette simple chose en C se traduirait-elle par un langage de programmation fonctionnel tel que Haskell?

#include int main() { int no; scanf("%d",&no); return 0; } 

(Ma question a été inspirée par cet excellent post: “Execution in the Kingdom of Nouns” . Sa lecture m’a permis de mieux comprendre ce qu’est exactement la programmation orientée object, comment Java l’implémente d’une manière extrême et comment les langages de programmation fonctionnels sont contraste.)

Si les langages de programmation fonctionnels ne peuvent sauver aucun état, comment font-ils des choses simples, comme lire les entrées d’un utilisateur (je veux dire, comment les “stockent”) ou stockent-ils des données?

Comme vous l’avez compris, la functional programming n’a pas d’état, mais cela ne signifie pas qu’elle ne peut pas stocker de données. La différence est que si j’écris une déclaration (Haskell) dans le sens de

 let x = func value 3.14 20 "random" in ... 

Je suis certain que la valeur de x est toujours la même dans le ... : rien ne peut le changer. De même, si j’ai une fonction f :: Ssortingng -> Integer (une fonction prenant une chaîne et renvoyant un entier), je peux être sûr que f ne modifiera pas son argument, ni ne changera aucune variable globale, ni n’écrira de données dans un fichier. , etc. Comme dit Sepp2k dans un commentaire ci-dessus, cette non-mutabilité est vraiment utile pour raisonner sur les programmes: vous écrivez des fonctions qui plient, broient et mutilent vos données, renvoyant de nouvelles copies pour pouvoir les enchaîner. de ces appels de fonctions peuvent faire n’importe quoi “nuisible”. Vous savez que x est toujours x , et vous n’avez pas à vous inquiéter que quelqu’un ait écrit x := foo bar quelque part entre la déclaration de x et son utilisation, car c’est impossible.

Maintenant, que faire si je veux lire l’entrée d’un utilisateur? Comme KennyTM l’a dit, l’idée est qu’une fonction impure est une fonction pure qui passe le monde entier en argument et renvoie à la fois son résultat et le monde. Bien sûr, vous ne voulez pas réellement faire ceci: d’une part, c’est horriblement maladroit, et d’autre part, que se passe-t-il si je réutilise le même object du monde? Donc, cela devient en quelque sorte abstrait. Haskell le gère avec le type IO:

 main :: IO () main = do str < - getLine let no = fst . head $ reads str :: Integer ... 

Cela nous dit que main est une action IO qui ne retourne rien; exécuter cette action est ce que cela signifie d’exécuter un programme Haskell. La règle est que les types d'E / S ne peuvent jamais échapper à une action d'E / S; dans ce contexte, nous introduisons cette action en utilisant do . Ainsi, getLine renvoie une IO Ssortingng , qui peut être pensée de deux manières: premièrement, comme une action qui, lorsqu'elle est exécutée, produit une chaîne; deuxièmement, comme une chaîne "entachée" par IO car elle a été obtenue impeccablement. Le premier est plus correct, mais le second peut être plus utile. Le < - prend la Ssortingng de la IO Ssortingng et la stocke dans str - mais comme nous sums dans une action IO, nous devrons la boucler afin qu'elle ne puisse pas "s'échapper". La ligne suivante tente de lire un nombre entier ( reads ) et saisit la première correspondance réussie ( fst . head ); tout est pur (pas de IO), nous lui donnons donc un nom avec let no = ... . On peut alors utiliser à la fois no et str dans le ... Nous avons donc stocké des données impures (de getLine dans str ) et des données pures ( let no = ... ).

Ce mécanisme de travail avec IO est très puissant: il vous permet de séparer la partie algorithmique pure de votre programme du côté de l'interaction utilisateur impure, et de l'appliquer au niveau du type. Votre fonction minimumSpanningTree ne peut pas changer quelque chose ailleurs dans votre code, ni écrire un message à votre utilisateur, etc. C'est sur.

C'est tout ce que vous devez savoir pour utiliser IO dans Haskell; Si c'est tout ce que vous voulez, vous pouvez vous arrêter ici. Mais si vous voulez comprendre pourquoi cela fonctionne, continuez à lire. (Et notez que ces éléments seront spécifiques à Haskell - les autres langages peuvent choisir une implémentation différente.)

Donc, cela semblait sans doute être un truc, ajoutant en quelque sorte de l'impureté au pur Haskell. Mais ce n'est pas le cas - il se trouve que nous pouvons implémenter le type IO entièrement dans Haskell pur (du moment que nous recevons le RealWorld ). L'idée est la suivante: un type IO d'action IO type est identique à une fonction RealWorld -> (type, RealWorld) , qui prend le monde réel et renvoie à la fois un object de type type et le RealWorld modifié. On définit alors un couple de fonctions pour pouvoir utiliser ce type sans devenir fou:

 return :: a -> IO a return a = \rw -> (a,rw) (>>=) :: IO a -> (a -> IO b) -> IO b ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw' 

Le premier nous permet de parler d'actions IO qui ne font rien: return 3 est une action IO qui n'interroge pas le monde réel et renvoie simplement 3 . L'opérateur >>= , prononcé "bind", nous permet d'exécuter des actions IO. Il extrait la valeur de l'action IO, la transmet au monde réel via la fonction et renvoie l'action IO résultante. Notez que >>= applique notre règle selon laquelle les résultats des actions IO ne peuvent jamais s'échapper.

Nous pouvons alors transformer le main ci main dessus en un ensemble d'applications de fonction:

 main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ... 

Le runtime de Haskell fait un main avec le RealWorld initial, et nous sums prêts! Tout est pur, il a juste une syntaxe de fantaisie.

[ Edit: Comme le souligne @Conal , ce n'est pas vraiment ce que Haskell utilise pour faire des IO. Ce modèle casse si vous ajoutez la simultanéité, ou de toute autre manière pour que le monde change au milieu d'une action IO, il serait donc impossible pour Haskell d'utiliser ce modèle. Il est précis uniquement pour le calcul séquentiel. Ainsi, il se peut que l'IO de Haskell soit un peu une esquive; même si ce n'est pas le cas, ce n'est certainement pas aussi élégant. Selon l'observation de @Calal, voir ce que Simon Peyton-Jones dit dans Tackling the Awkward Squad [pdf] , section 3.1; il présente ce qui pourrait constituer un modèle alternatif dans ce sens, mais le laisse tomber pour sa complexité et adopte une approche différente.]

Encore une fois, cela explique (à peu près) comment IO et la mutabilité en général fonctionnent dans Haskell; Si c'est tout ce que vous voulez savoir, vous pouvez arrêter de lire ici. Si vous voulez une dernière dose de théorie, continuez à lire - mais souvenez-vous, à ce stade, nous sums allés très loin de votre question!

Donc, la dernière chose: il s'avère que cette structure - un type paramésortingque avec return et >>= - est très générale; c'est ce qu'on appelle une monade, et la notation do , return et >>= fonctionnent avec n'importe lequel d'entre eux. Comme vous l'avez vu ici, les monades ne sont pas magiques; tout ce qui est magique, c'est que do blocs deviennent des appels de fonction. Le type RealWorld est le seul endroit où nous voyons de la magie. Les types comme [] , le constructeur de liste, sont également des monades, et ils n'ont rien à voir avec du code impur.

Vous connaissez maintenant (presque) tout ce qui concerne le concept de monade (à l'exception de quelques lois qui doivent être satisfaites et de la définition mathématique formelle), mais vous n'avez pas l'intuition. Il existe un nombre dérisoire de tutoriels monad en ligne; J'aime celle-ci , mais vous avez des options. Cependant, cela ne vous aidera probablement pas ; La seule façon de comprendre l'intuition consiste à les utiliser et à lire quelques tutoriels au bon moment.

Cependant, vous n'avez pas besoin de cette intuition pour comprendre IO . Comprendre les monades en général est la cerise sur le gâteau, mais vous pouvez utiliser IO dès maintenant. Vous pourriez l'utiliser après que je vous ai montré la première fonction main . Vous pouvez même traiter le code IO comme s'il était dans un langage impur! Mais rappelez-vous qu'il y a une représentation fonctionnelle sous-jacente: personne ne sortingche.

(PS: Désolé pour la longueur. Je suis allé un peu loin.)

Beaucoup de bonnes réponses ici, mais elles sont longues. Je vais essayer de donner une courte réponse utile:

  • Les langages fonctionnels mettent l’état aux mêmes endroits que C: dans les variables nommées et dans les objects alloués sur le tas. Les différences sont que:

    • Dans un langage fonctionnel, une “variable” obtient sa valeur initiale quand elle entre dans la scope (via un appel de fonction ou let-binding), et cette valeur ne change pas par la suite . De même, un object alloué sur le tas est immédiatement initialisé avec les valeurs de tous ses champs, qui ne changent pas par la suite.

    • Les “changements d’état” ne sont pas liés à la mutation de variables ou d’objects existants, mais à la liaison de nouvelles variables ou à l’allocation de nouveaux objects.

  • IO fonctionne par un tour. Un calcul à effet secondaire qui produit une chaîne est décrit par une fonction qui prend un argument World et renvoie une paire contenant la chaîne et un nouveau monde. The World inclut le contenu de tous les lecteurs de disque, l’historique de chaque paquet réseau envoyé ou reçu, la couleur de chaque pixel à l’écran, etc. L’essentiel est que l’access au monde est soigneusement restreint afin que

    • Aucun programme ne peut faire une copie du monde (où voulez-vous le mettre?)

    • Aucun programme ne peut jeter le monde

    L’utilisation de cette astuce permet qu’il y ait un monde unique, dont l’état évolue avec le temps. Le système d’exécution du langage, qui n’est pas écrit dans un langage fonctionnel, implémente un calcul à effets secondaires en mettant à jour le monde unique en place au lieu d’en renvoyer un nouveau.

    Cette astuce est magnifiquement expliquée par Simon Peyton Jones et Phil Wadler dans leur article phare “Imperative Functional Programming” .

J’interromps un commentaire en réponse à une nouvelle réponse, pour donner plus d’espace:

J’ai écrit:

Pour autant que je sache, cette histoire IO ( World -> (a,World) ) est un mythe lorsqu’elle est appliquée à Haskell, car ce modèle n’explique que le calcul purement séquentiel, tandis que le type IO de Haskell inclut la concurrence. Par “purement séquentiel”, je veux dire que même le monde (univers) n’est pas autorisé à changer entre le début et la fin d’un calcul impératif, sauf en raison de ce calcul. Par exemple, lorsque votre ordinateur est en train de se défaire, votre cerveau, etc., ne le peut pas. La concurrence peut être gérée par quelque chose de plus semblable à World -> PowerSet [(a,World)] , qui permet de déterminer et de séparer les éléments.

Norman a écrit:

@Conal: Je pense que l’histoire d’IO se généralise assez bien au non-déterminisme et à l’entrelacement; Si je me souviens bien, il y a une assez bonne explication dans le document “Awkward Squad”. Mais je ne connais pas un bon article qui explique clairement le vrai parallélisme.

@Norman: Généraliser dans quel sens? Je suggère que le modèle dénomination / explication généralement donné, World -> (a,World) , ne correspond pas à Haskell IO car il ne tient pas compte du non-déterminisme et de la concurrence. Il pourrait y avoir un modèle plus complexe qui convient, comme World -> PowerSet [(a,World)] , mais je ne sais pas si un tel modèle a été élaboré et montré adéquat et cohérent. Je doute personnellement qu’une telle bête puisse être trouvée, étant donné IO est peuplé de milliers d’appels d’API impératifs importés par FFI. Et en tant que tel, IO remplit son objective:

Problème ouvert: la monade IO est devenue la poubelle d’Haskell. (Chaque fois que nous ne comprenons pas quelque chose, nous le jetons dans la monade IO.)

(Extrait de la conférence POPL de Simon PJ. Porter la chemise de coiffure Porter la chemise de cheveux: une rétrospective sur Haskell .)

Dans la section 3.1 de Tackling the Awkward Squad , Simon pointe ce qui ne fonctionne pas sur le type IO a = World -> (a, World) , y compris “L’approche ne s’adapte pas bien lorsque nous ajoutons la concurrence”. Il suggère ensuite un modèle alternatif possible, puis abandonne la tentative d’explication dénotationnelle en disant:

Cependant, nous adopterons plutôt une sémantique opérationnelle, basée sur des approches standard de la sémantique des calculs de processus.

Cette impossibilité de trouver un modèle dénotationnel précis et utile explique pourquoi je considère Haskell IO comme une rupture par rapport à l’esprit et aux avantages profonds de ce que nous appelons la «functional programming», ou ce que Peter Landin a plus spécifiquement appelé «programmation dénotative». . Voir les commentaires ici.

La functional programming dérive du lambda calcul. Si vous voulez vraiment comprendre la functional programming, consultez http://worrydream.com/AlligatorEggs/

C’est une façon “amusante” d’apprendre le lambda calcul et de vous plonger dans le monde passionnant de la functional programming!

Comment connaître Lambda Calculus est utile dans la functional programming.

Donc, Lambda Calculus est la base de nombreux langages de programmation réels tels que Lisp, Scheme, ML, Haskell, ….

Supposons que nous voulions décrire une fonction qui ajoute trois à n’importe quelle entrée pour que nous écrivions:

 plus3 x = succ(succ(succ x)) 

Read “plus3 est une fonction qui, appliquée à un nombre x quelconque, donne le successeur du successeur du successeur de x”

Notez que la fonction qui ajoute 3 à un nombre quelconque ne doit pas être nommée plus3; le nom «plus3» est juste un raccourci pratique pour nommer cette fonction

( plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

Notez que nous utilisons le symbole lambda pour une fonction (je pense que cela ressemble à un Alligator, je suppose que c’est là que vient l’idée des œufs d’Alligator)

Le symbole lambda est l’ alligator (une fonction) et le x est sa couleur. Vous pouvez également considérer x comme un argument (les fonctions Lambda Calculus ne sont supposées avoir qu’un seul argument), le rest vous pouvez le considérer comme le corps de la fonction.

Considérons maintenant l’abstraction:

 g ≡ λ f. (f (f (succ 0))) 

L’argument f est utilisé dans une position de fonction (dans un appel). Nous appelons ga une fonction d’ordre supérieur car elle prend une autre fonction en entrée. Vous pouvez penser aux autres fonctions appelées f comme ” oeufs “. Maintenant, en prenant les deux fonctions ou ” Alligators ” que nous avons créées, nous pouvons faire quelque chose comme ceci:

 (g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) = ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0))) = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0))))) = (succ (succ (succ (succ (succ (succ (succ 0))))))) 

Si vous remarquez que vous pouvez voir que notre Alligator λ f mange notre Alligator λ x, puis l’Alligator λ x et meurt. Ensuite, notre Alligator λ x renaît dans les œufs d’Alligator de λ f. Ensuite, le processus se répète et l’Alligator λ x à gauche mange maintenant l’autre Alligator λ x à droite.

Ensuite, vous pouvez utiliser cet ensemble simple de règles de ” Alligators ” mangeant des ” Alligators ” pour concevoir une grammaire et ainsi les langages de programmation fonctionnels sont nés!

Donc, vous pouvez voir si vous connaissez Lambda Calculus, vous comprendrez comment fonctionnent les langages fonctionnels.

La technique de manipulation de l’état dans Haskell est très simple. Et vous n’avez pas besoin de comprendre les monades pour vous en occuper.

Dans un langage de programmation avec état, vous avez généralement une valeur stockée quelque part, un code s’exécute, puis vous avez une nouvelle valeur stockée. Dans les langages impératifs, cet état est quelque part “en arrière-plan”. Dans un langage fonctionnel (pur), vous rendez cela explicite, vous écrivez donc explicitement la fonction qui transforme l’état.

Donc, au lieu d’avoir un état de type X, vous écrivez des fonctions qui associent X à X. Ça y est! Vous passez de la reflection sur l’état à la reflection sur les opérations que vous souhaitez effectuer sur l’état. Vous pouvez ensuite enchaîner ces fonctions et les combiner de différentes manières pour créer des programmes complets. Bien sûr, vous n’êtes pas limité à mapper X à X. Vous pouvez écrire des fonctions pour prendre différentes combinaisons de données en entrée et renvoyer diverses combinaisons à la fin.

Les monades sont un outil parmi d’autres pour aider à organiser cela. Mais les monades ne sont pas la solution au problème. La solution consiste à penser aux transformations d’état plutôt qu’à l’état.

Cela fonctionne également avec I / O. En fait, ce qui se passe est la suivante: au lieu d’obtenir des entrées de l’utilisateur avec un équivalent direct de scanf et de les stocker quelque part, vous écrivez plutôt une fonction pour dire ce que vous feriez avec scanf transmettre cette fonction à l’API d’E / S. C’est exactement ce que fait >>= lorsque vous utilisez la monade IO dans Haskell. Vous n’avez donc jamais besoin de stocker le résultat d’une E / S, vous n’avez qu’à écrire du code indiquant comment vous souhaitez le transformer.

(Certaines langues fonctionnelles autorisent les fonctions impures.)

Pour les langages purement fonctionnels , l’interaction du monde réel est généralement incluse comme l’un des arguments de la fonction, comme ceci:

 RealWorld pureScanf(RealWorld world, const char* format, ...); 

Différentes langues ont des stratégies différentes pour séparer le monde du programmeur. Haskell, par exemple, utilise des monades pour cacher l’argument du world .


Mais la partie pure du langage fonctionnel lui-même est déjà complète à Turing, ce qui signifie que tout ce qui est réalisable dans C est également réalisable dans Haskell. La principale différence avec le langage impératif est de ne pas modifier les états en place:

 int compute_sum_of_squares (int min, int max) { int result = 0; for (int i = min; i < max; ++ i) result += i * i; // modify "result" in place return result; } 

Vous intégrez la partie modification dans un appel de fonction, transformant généralement les boucles en récurrences:

 int compute_sum_of_squares (int min, int max) { if (min >= max) return 0; else return min * min + compute_sum_of_squares(min + 1, max); } 

Le langage fonctionnel peut sauver l’état! Ils ne font généralement qu’encourager ou vous forcer à être explicite à cet égard.

Par exemple, vérifiez l’ état de Haskell’s Monad .

pourrait être utile, la programmation de la fonction pour le rest de nous

haskell:

 main = do no < - readLn print (no + 1) 

Vous pouvez bien sûr atsortingbuer des choses aux variables dans les langages fonctionnels. Vous ne pouvez tout simplement pas les modifier (toutes les variables sont donc des constantes dans les langages fonctionnels).