Comment fonctionnent les langages de programmation fonctionnelle?

Si les langages de programmation fonctionnelle ne peuvent enregistrer aucun état, comment font-ils des choses simples comme lire l'entrée d'un utilisateur? Comment «stockent-ils» l'entrée (ou stockent-ils des données d'ailleurs?)

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

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

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

Si les langages de programmation fonctionnels ne peuvent enregistrer aucun état, comment font-ils des trucs simples comme lire les entrées d'un utilisateur (je veux dire comment les «stockent»), ou stocker des données d'ailleurs?

Comme vous l'avez compris, la programmation fonctionnelle 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 assuré que la valeur de xest toujours la même dans le ...: rien ne peut la changer. De même, si j'ai une fonction f :: String -> Integer(une fonction prenant une chaîne et renvoyant un entier), je peux être sûr que fcela ne modifiera pas son argument, ni ne changera aucune variable globale, ni n'écrira de données dans un fichier, etc. Comme sepp2k l'a dit dans un commentaire ci-dessus, cette non-mutabilité est vraiment utile pour raisonner sur les programmes: vous écrivez des fonctions qui plient, fusionnent et mutilent vos données, renvoyant de nouvelles copies afin de pouvoir les enchaîner, et vous pouvez être sûr qu'aucune de ces appels de fonction peuvent faire quelque chose de «nuisible». Vous savez que xc'est toujours le cas xet vous n'avez pas à vous inquiéter que quelqu'un ait écrit x := foo barquelque part entre la déclaration dex et son utilisation, car c'est impossible.

Maintenant, que faire si je veux lire l'entrée d'un utilisateur? Comme l'a dit KennyTM, 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 faire ça: d'une part, c'est horriblement maladroit, et d'autre part, que se passe-t-il si je réutilise le même objet du monde? Donc, cela est abstrait d'une manière ou d'une autre. Haskell le gère avec le type IO:

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

Cela nous indique qu'il mains'agit d'une action IO qui ne renvoie rien; exécuter cette action est ce que signifie 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, getLinerenvoie un IO String, qui peut être considéré de deux manières: d'abord, comme une action qui, lorsqu'elle est exécutée, produit une chaîne; deuxièmement, comme une chaîne "entachée" par IO puisqu'elle a été obtenue impur. Le premier est plus correct, mais le second peut être plus utile. Le <-prend le Stringhors du IO Stringet le stocke dans str- mais puisque nous sommes dans une action IO, nous devrons l'envelopper de nouveau, donc il ne peut pas «s'échapper». La ligne suivante tente de lire un entier ( reads) et saisit la première correspondance réussie (fst . head); tout cela est pur (pas d'IO), nous lui donnons donc un nom avec let no = .... Nous pouvons alors utiliser à la fois noet strdans le .... Nous avons ainsi stocké des données impures (de getLinededans str) et des données pures ( let no = ...).

Ce mécanisme pour travailler avec IO est très puissant: il vous permet de séparer la partie pure et algorithmique de votre programme du côté impur, de l'interaction utilisateur, et de l'appliquer au niveau du type. Votre minimumSpanningTreefonction ne peut pas changer quelque chose ailleurs dans votre code, ou é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 ce truc sera spécifique à Haskell - d'autres langages peuvent choisir une implémentation différente.)

Donc, cela semblait probablement être un peu une triche, ajoutant en quelque sorte de l'impureté à Haskell pur. Mais ce n'est pas le cas - il s'avère que nous pouvons implémenter le type IO entièrement dans Haskell pur (tant qu'on nous donne le RealWorld). L'idée est la suivante: une action IO IO typeest la même qu'une fonction RealWorld -> (type, RealWorld), qui prend le monde réel et renvoie à la fois un objet de type typeet le modifié RealWorld. Nous définissons ensuite quelques fonctions afin de 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'

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

Nous pouvons ensuite transformer ce qui précède mainen l'ensemble d'applications de fonction ordinaire suivant:

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

Le démarrage mainde l' exécution Haskell avec l'initiale RealWorld, et nous sommes prêts! Tout est pur, il a juste une syntaxe sophistiquée.

[ Edit: Comme le souligne @Conal , ce n'est pas vraiment ce que Haskell utilise pour faire des E / S. Ce modèle casse si vous ajoutez la concurrence, ou en fait une manière quelconque pour que le monde change au milieu d'une action IO, il serait donc impossible pour Haskell d'utiliser ce modèle. Il n'est précis que 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 @ Conal, voyez ce que dit Simon Peyton-Jones 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, fonctionne 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 rappelez-vous, à ce stade, nous sommes allés très loin de votre question!

Donc une dernière chose: il s'avère que cette structure - un type paramétrique avec returnet >>=- est très générale; cela s'appelle une monade, et la donotation return, et >>=fonctionne 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 les doblocs se transforment en appels de fonction. Le RealWorldtype est le seul endroit où nous voyons de la magie. Des types comme [], le constructeur de liste, sont également des monades, et ils n'ont rien à voir avec du code impur.

Vous savez maintenant (presque) tout sur le concept de monade (sauf quelques lois qui doivent être satisfaites et la définition mathématique formelle), mais vous manquez d'intuition. Il existe un nombre ridicule de tutoriels monades en ligne; J'aime celui-ci , mais vous avez des options. Cependant, cela ne vous aidera probablement pas ; le seul véritable moyen d'obtenir l'intuition consiste à combiner leur utilisation et la lecture de 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 pouvez l'utiliser après que je vous ai montré la première mainfonction. Vous pouvez même traiter le code IO comme s'il était dans un langage impur! Mais rappelez-vous qu'il existe une représentation fonctionnelle sous-jacente: personne ne triche.

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

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

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

  • Dans un langage fonctionnel, une «variable» obtient sa valeur initiale lorsqu'elle entre dans la portée (via un appel de fonction ou une liaison let), et cette valeur ne change pas par la suite . De même, un objet 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" sont gérés non pas en mutant des variables ou des objets existants mais en liant de nouvelles variables ou en allouant de nouveaux objets.

• IO fonctionne par un truc. Un calcul à effet secondaire qui produit une chaîne est décrit par une fonction qui prend un World comme argument et renvoie une paire contenant la chaîne et un nouveau World. Le monde comprend le contenu de tous les lecteurs de disque, l'historique de chaque paquet réseau jamais envoyé ou reçu, la couleur de chaque pixel à l'écran, et des trucs comme ça. La clé de l'astuce est que l'accès au monde est soigneusement restreint afin que

  • Aucun programme ne peut faire une copie du Monde (où le mettriez-vous?)

  • Aucun programme ne peut jeter le monde

  En utilisant cette astuce, il est possible 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 à effet secondaire en mettant à jour l'unique Monde 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 de référence "Imperative Functional Programming" .

Je coupe une réponse de commentaire à une nouvelle réponse, pour donner plus d'espace:

J'ai écrit:

Pour autant que je sache, cette IOhistoire ( 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 IOtype de Haskell inclut la concurrence. Par "purement séquentiel", je veux dire que même le monde (l'univers) n'est pas autorisé à changer entre le début et la fin d'un calcul impératif, autrement qu'en raison de ce calcul. Par exemple, pendant que votre ordinateur s'éloigne, votre cerveau, etc. La concurrence peut être gérée par quelque chose de plus semblable World -> PowerSet [(a,World)], qui permet le non-déterminisme et l'entrelacement.

Norman a écrit:

@Conal: Je pense que l'histoire de l'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 l'article "Awkward Squad". Mais je ne connais pas de bon article qui explique clairement le vrai parallélisme.

@Norman: généralise dans quel sens? Je suggère que le modèle / explication dénotationnel généralement donné World -> (a,World)ne correspond pas à Haskell IOcar il ne tient pas compte du non-déterminisme et de la concurrence. Il peut 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 démontré adéquat et cohérent. Personnellement, je doute qu'une telle bête puisse être trouvée, étant donné qu'elle IOest peuplée de milliers d'appels d'API impératifs importés par FFI. Et en tant que tel, IOremplit son objectif:

Problème ouvert: la IOmonade est devenue la bête de Haskell. (Chaque fois que nous ne comprenons pas quelque chose, nous le jetons dans la monade IO.)

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

Dans la section 3.1 de Tackling the Awkward Squad , Simon indique ce qui ne fonctionne pas type IO a = World -> (a, World), notamment "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'explications dénotationnelles, 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 incapacité à trouver un modèle de dénotation précis et utile est à l'origine de la raison pour laquelle je vois Haskell IO comme un départ de l'esprit et des avantages profonds de ce que nous appelons la «programmation fonctionnelle», ou ce que Peter Landin a plus spécifiquement appelé «programmation dénotative» . Voir les commentaires ici.

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

C'est une façon «amusante» d'apprendre le calcul lambda et de vous amener dans le monde passionnant de la programmation fonctionnelle!

Comment connaître Lambda Calculus est utile dans la programmation fonctionnelle.

Ainsi, Lambda Calculus est la base de nombreux langages de programmation du monde réel tels que Lisp, Scheme, ML, Haskell, ....

Supposons que nous voulions décrire une fonction qui ajoute trois à n'importe quelle entrée pour ce faire, nous écririons:

plus3 x = succ(succ(succ x)) 

Lire "plus3 est une fonction qui, lorsqu'elle est appliquée à n'importe quel nombre x, donne le successeur du successeur du successeur de x"

Notez que la fonction qui ajoute 3 à n'importe quel nombre n'a pas besoin d'ê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 peu à un alligator, je suppose que c'est de 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 de calcul Lambda ne sont en réalité supposées avoir qu'un seul argument) le reste, 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 fonction d'ordre supérieur car elle prend une autre fonction comme entrée. Vous pouvez considérer les autres appels de fonction f comme des " œufs ". En prenant maintenant 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, vous pouvez voir que notre λ f Alligator mange notre λ x Alligator puis le λ x Alligator et meurt. Ensuite, notre λ x Alligator renaît dans les œufs d'Alligator de λ f. Ensuite, le processus se répète et le λ x Alligator sur la gauche mange maintenant l'autre λ x Alligator sur la droite.

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

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

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

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

Donc, au lieu d'avoir un état de type X, vous écrivez des fonctions qui mappent X à X. C'est tout! Vous passez de la réflexion sur l'état à la réflexion 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 entiers. Bien sûr, vous n'êtes pas limité à simplement mapper X à X. Vous pouvez écrire des fonctions pour prendre diverses combinaisons de données en entrée et renvoyer diverses combinaisons à la fin.

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

Cela fonctionne également avec les E / S. En effet, ce qui se passe est le suivant: au lieu d'obtenir des entrées de l'utilisateur avec un équivalent direct de scanf, et de les stocker quelque part, vous écrivez à la place une fonction pour dire ce que vous feriez avec le résultat de scanfsi vous l'aviez, puis passez cela fonction à l'API d'E / S. C'est exactement ce que >>=fait lorsque vous utilisez la IOmonade dans Haskell. Ainsi, vous n'avez jamais besoin de stocker le résultat d'une E / S n'importe où - il vous suffit d'écrire du code qui indique comment vous souhaitez le transformer.

(Certains langages fonctionnels permettent des fonctions impures.)

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

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

Différents langages ont des stratégies différentes pour abstraire le monde du programmeur. Haskell, par exemple, utilise des monades pour masquer l' worldargument.

Mais la partie pure du langage fonctionnel lui-même est déjà Turing complet, ce qui signifie que tout ce qui est faisable en C est également faisable en Haskell. La principale différence avec le langage impératif est au lieu de 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 incorporez la partie de modification dans un appel de fonction, transformant généralement les boucles en récursions:

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 enregistrer l'état! Ils vous encouragent ou vous forcent généralement à être explicite à ce sujet.

Par exemple, consultez la Monade d'État de Haskell .

pourrait être utile, la programmation de fonctions pour le reste d'entre nous

haskell:

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

Vous pouvez bien sûr affecter des choses à des variables dans des langages fonctionnels. Vous ne pouvez tout simplement pas les changer (donc fondamentalement toutes les variables sont des constantes dans les langages fonctionnels).