Programmation fonctionnelle – Beaucoup d’insistance sur la récursivité, pourquoi?

Je suis initié à la functional programming [FP] (en utilisant Scala). Une des choses qui ressort de mes premiers apprentissages est que les MF comptent beaucoup sur la récursivité. Et il semble aussi que, dans les FP purs, la seule façon de faire des choses itératives est d’écrire des fonctions récursives.

Et à cause de la forte utilisation de la récursivité, la prochaine chose que les partenaires de projet devaient s’inquiéter, ce sont les StackoverflowExceptions généralement dues à des appels récursifs de longue durée. Cela a été abordé en introduisant des optimisations (optimisations liées à la récursion de la queue dans la maintenance des stackframes et annotation @tailrec partir de Scala v2.8).

Quelqu’un peut-il s’il vous plaît m’éclairer pourquoi la récursivité est si importante pour le paradigme de functional programming? Y a-t-il quelque chose dans les spécifications des langages de programmation fonctionnels qui soit “violé” si nous faisons des choses de manière itérative? Si oui, alors je tiens à le savoir également.

PS: Notez que je suis novice en functional programming, alors n’hésitez pas à me signaler les ressources existantes si elles expliquent / répondent à ma question. Aussi, je comprends que Scala en particulier fournit également un support pour faire des choses itératives.

La thèse de Church Turing souligne l’équivalence entre différents modèles de calculabilité.

En utilisant la récursion, nous n’avons pas besoin d’un état mutable pour résoudre certains problèmes, ce qui permet de spécifier une sémantique en termes plus simples. Ainsi, les solutions peuvent être plus simples, dans un sens formel.

Je pense que Prolog montre mieux que les langages fonctionnels l’efficacité de la récursivité (elle n’a pas d’itération) et les limites pratiques que nous rencontrons lors de son utilisation.

La functional programming pure signifie une programmation sans effets secondaires. Ce qui signifie que si vous écrivez une boucle, par exemple, le corps de votre boucle ne peut pas produire d’effets secondaires. Ainsi, si vous voulez que votre boucle fasse quelque chose, elle doit réutiliser le résultat de l’itération précédente et produire quelque chose pour la prochaine itération. Ainsi, le corps de votre boucle est une fonction, prenant comme paramètre le résultat de l’exécution précédente et s’appelant pour la prochaine itération avec son propre résultat. Cela n’a pas un énorme avantage sur l’écriture directe d’une fonction récursive pour la boucle.

Un programme qui ne fait pas quelque chose de sortingvial devra parcourir quelque chose à un moment donné. Pour la functional programming, cela signifie que le programme doit utiliser des fonctions récursives.

La caractéristique qui oblige à faire les choses récursivement est les variables immuables.

Considérons une fonction simple pour calculer la sum d’une liste (en pseudocode):

 fun calculateSum(list): sum = 0 for each element in list: # dubious sum = sum + element # impossible! return sum 

Maintenant, l’ element dans chaque itération de la liste est différent, mais nous pouvons réécrire ceci pour utiliser une fonction foreach avec un argument lambda pour se débarrasser de ce problème:

 fun calculateSum(list): sum = 0 foreach(list, lambda element: sum = sum + element # impossible! ) return sum 

Cependant, la valeur de la variable de sum doit être modifiée à chaque exécution du lambda. Ceci est illégal dans un langage avec des variables immuables, vous devez donc le réécrire d’une manière qui ne modifie pas l’état:

 fun calculateSum([H|T]): return H + calculateSum(T) fun calculateSum([]): return 0 

Désormais, cette implémentation nécessitera une poussée et une extraction de la stack d’appels, et un programme dans lequel toutes les petites opérations feraient cela ne fonctionnerait pas très rapidement. Par conséquent, nous le réécrivons pour être récursif, de sorte que le compilateur peut faire l’optimisation des appels de queue:

 fun calculateSum([H|T], partialSum): return calculateSum(T, H + partialSum) fun calculateSum([], partialSum): return partialSum fun calculateSum(list): return calculateSum(list, 0) 

Bien sûr, si vous voulez effectuer une boucle indéfinie, vous avez absolument besoin d’un appel récursif de queue, sinon il y aurait un dépassement de capacité.

L’annotation @tailrec dans Scala est un outil pour vous aider à parsingr quelles fonctions sont récursives en queue. Vous prétendez que “cette fonction est récursive” et le compilateur peut vous dire si vous vous êtes trompé. Ceci est particulièrement important dans Scala par rapport aux autres langages fonctionnels, car la machine sur laquelle il est exécuté, la JVM, ne prend pas bien en charge l’optimisation des appels, il n’est donc pas possible d’optimiser dans d’autres langages fonctionnels.

TL; DR : la récursion est utilisée pour gérer les données définies par induction, qui sont omniprésentes.

La récursivité est naturelle lorsque vous opérez à des niveaux d’abstraction plus élevés. La functional programming ne consiste pas seulement à coder avec des fonctions; il s’agit d’opérer sur des niveaux d’abstraction plus élevés, où vous utilisez naturellement des fonctions. En utilisant des fonctions, il est naturel de réutiliser la même fonction (pour la rappeler), quel que soit le contexte dans lequel elle a du sens.

Le monde est construit par la répétition de blocs de construction similaires / identiques. Si vous coupez un morceau de tissu en deux, vous avez deux morceaux de tissu. L’induction mathématique est au cœur des mathématiques. Nous, humains, comptons (comme dans 1,2,3 … ). Toute chose définie par induction (comme {nombre de 1} est {1 et les nombres de 2} ) est naturelle à gérer / parsingr par une fonction récursive, selon les mêmes cas où cette chose est définie / construite.

La récursivité est partout. Toute boucle itérative est de toute façon une récursivité déguisée, car lorsque vous entrez à nouveau dans cette boucle, vous entrez à nouveau dans la même boucle (avec peut-être des variables de boucle différentes). Donc, ce n’est pas comme inventer de nouveaux concepts sur l’informatique, c’est plus comme découvrir les fondements et les rendre explicites .


La récursivité est donc naturelle. Nous écrivons simplement des lois sur notre problème, des équations impliquant la fonction que nous définissons qui préservent certains invariants (en supposant que la fonction est définie de manière cohérente), en re-spécifiant le problème en termes simplifiés, et le tour est joué! Nous avons la solution.

Un exemple, une fonction pour calculer la longueur de la liste (un type de données récursif défini par induction). Supposons qu’il soit défini et renvoie la longueur de la liste, sans surprise. Quelles sont les lois auxquelles il doit obéir? Quel invariant est préservé sous quelle simplification d’un problème?

Le plus immédiat est de séparer la liste de son élément principal, et le rest – c’est-à-dire la queue de la liste (selon la façon dont une liste est définie / construite). La loi est,

 length (x:xs) = 1 + length xs 

D’uh! Mais qu’en est-il de la liste vide? ça doit être ça

 length [] = 0 

Alors, comment écrivons-nous une telle fonction? … Attendez … Nous l’avons déjà écrite! (Dans Haskell, si vous vous demandez si l’application de la fonction est exprimée par juxtaposition, les parenthèses ne sont utilisées que pour le regroupement et (x:xs) est une liste avec x son premier élément et xs le rest).

Tout ce dont nous avons besoin d’un langage pour permettre un tel style de programmation, c’est qu’il a un coût total de possession (et peut-être un peu luxueux, TRMCO ), donc il n’y a pas d’explosion de stack et nous sums prêts.


Une autre chose est la pureté – immuabilité des variables de code et / ou de la structure des données (champs des enregistrements, etc.).

Qu’est-ce que cela fait, en plus de libérer nos esprits d’avoir à suivre ce qui change quand, est-ce que cela rend le temps explicitement apparent dans notre code, au lieu de se cacher dans nos variables / données mutables “changeantes”. Nous ne pouvons que “changer” dans le code impératif la valeur d’une variable à partir de maintenant – nous ne pouvons pas très bien changer sa valeur dans le passé, pouvons-nous?

Et donc nous nous retrouvons avec des listes de l’historique des modifications enregistrées, avec un changement apparaissant explicitement dans le code: au lieu de x := x + 2 nous écrivons let x2 = x1 + 2 . Cela facilite le raisonnement sur le code.


Pour traiter l’immuabilité dans le contexte de la récursion de queue avec le TCO , considérez cette réécriture récursive de la length fonction ci-dessus sous le paradigme d’argument de l’accumulateur:

 length xs = length2 0 xs -- the invariant: length2 a [] = a -- 1st arg plus length2 a (x:xs) = length2 (a+1) xs -- length of 2nd arg 

Ici, TCO signifie réutilisation des trames d’appel, en plus du saut direct, de sorte que la chaîne d’appel de length [1,2,3] peut être considérée comme une mutation des entrées de la trame de la stack d’appel correspondant aux parameters de la fonction:

 length [1,2,3] length2 0 [1,2,3] -- a=0 (x:xs)=[1,2,3] length2 1 [2,3] -- a=1 (x:xs)=[2,3] length2 2 [3] -- a=2 (x:xs)=[3] length2 3 [] -- a=3 (x:xs)=[] 3 

Dans un langage pur, sans aucune primitive de mutation de valeur, la seule manière d’exprimer un changement consiste à transmettre des valeurs mises à jour en tant qu’arguments à une fonction , pour qu’elles soient traitées ultérieurement. Si le traitement ultérieur est le même que précédemment, nous devons naturellement appeler la même fonction pour cela, en lui passant les valeurs mises à jour en argument. Et c’est la récursivité.


Et ce qui suit rend explicite l’historique du calcul de la longueur d’une liste d’arguments (et peut être réutilisé, le cas échéant):

 length xs = last results where results = length3 0 xs length3 a [] = [a] length3 a (x:xs) = a : length3 (a+1) xs 

Dans Haskell, on parle de récursion gardée ou de corecursion (du moins je le pense).

Il n’y a rien de «spécial» en récursivité. C’est un outil répandu en programmation et en mathématiques et rien de plus. Cependant, les langages fonctionnels sont généralement minimalistes. Ils introduisent beaucoup de concepts fantaisistes tels que la correspondance de modèles, le système de types, la compréhension de listes, etc., mais ce n’est rien de plus que du sucre syntaxique pour des outils très généraux et très puissants, mais simples et primitifs. Ces outils sont les suivants: abstraction de fonction et application de fonction. C’est un choix conscient, car la simplicité du langage de base rend le raisonnement beaucoup plus facile. Cela facilite également l’écriture de compilateurs. La seule façon de décrire une boucle en termes d’outils consiste à utiliser la récursivité, de sorte que les programmeurs impératifs peuvent penser que la functional programming concerne la récursivité. Ce n’est pas le cas, il est simplement nécessaire d’imiter ces boucles fantaisistes pour les pauvres qui ne peuvent pas abandonner ce sucre syntaxique plutôt que de le dire, et c’est donc l’une des premières choses dans laquelle ils sont restés.

Un autre point où (peut être indirect) la récursivité requirejse est le traitement des structures de données définies récursivement. L’exemple le plus courant est la list ADT. Dans FP, il est généralement défini comme cette data List a = Nil | Branch a (List a) data List a = Nil | Branch a (List a) . Étant donné que la définition de l’ADT est récursive, la fonction de traitement doit également être récursive. Là encore, la récursivité n’est pas particulière: le traitement de ces ADT de manière récursive se présente naturellement dans les langages impératifs et fonctionnels. Eh bien, en cas de liste de type ADT, des boucles impératives peuvent encore être adoptées, mais dans le cas de structures arborescentes différentes, elles ne le peuvent pas.

Il n’y a donc rien de spécial dans la récursivité. C’est simplement un autre type d’application de fonction. Cependant, en raison des limitations des systèmes informatiques modernes (qui proviennent de décisions de conception mal faites en langage C, qui est un assembleur multi-plateforme de facto standard), les appels de fonctions ne peuvent pas être nesteds indéfiniment même s’ils sont des appels de queue. Pour cette raison, les concepteurs de langages de programmation fonctionnels doivent soit limiter les appels de queue autorisés à la récursion de queue (scala), soit utiliser des techniques compliquées comme le trampoline (ancien code ghc) ou comstackr directement dans asm (ghc codegen).

TL; DR: Il n’y a rien de spécial dans la récursivité dans FP, pas plus que dans IP, cependant, la récursion de la queue est le seul type d’appels de queue autorisés dans Scala en raison des limitations de la JVM.

Éviter les effets secondaires est l’un des piliers de la functional programming (l’autre utilise des fonctions d’ordre supérieur).

Imaginez comment vous pourriez utiliser le contrôle de stream impératif sans compter sur la mutation. C’est possible?

Bien sûr, for (var i = 0; i < 10; i++) ... dépend de la mutation ( i++ ). En fait, toute construction de boucle conditionnelle le fait. Dans while (something) ... le something dépendra d'un état mutable. Bien sûr, while (true) ... n'utilise pas de mutation. Mais si vous voulez sortir de cette boucle, vous aurez besoin d'une if (something) break . Vraiment, essayez de penser à un mécanisme de bouclage (non infini) autre que la récursivité qui ne repose pas sur la mutation.

Et for (var x in someCollection) ... ? Nous nous rapprochons maintenant de la functional programming. Le x peut être considéré comme un paramètre du corps de la boucle. La réutilisation du nom n'est pas la même chose que la réatsortingbution d'une valeur. Peut-être que dans le corps de la boucle, vous obtenez yield return valeurs de yield return en tant qu'expression en termes de x (pas de mutation).

Exactement équivalent, vous pouvez déplacer le corps de la boucle for dans le corps d'une fonction foo (x) ... et ensuite le mapper sur someCollection utilisant une fonction d'ordre supérieur - en remplaçant votre construction de boucle par quelque chose comme Map(foo, someCollection) .

Mais alors, comment la fonction de bibliothèque Map implémentée sans mutation? Eh bien, en utilisant la récursivité bien sûr! C'est fait pour toi. Il devient moins courant de devoir implémenter les fonctions récursives une fois que vous commencez à utiliser le second pilier des fonctions d'ordre supérieur pour remplacer vos constructions en boucle.

De plus, avec l’optimisation des appels de fin, une définition récursive équivaut à un processus itératif. Vous pouvez également profiter de cet article de blog: http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

Il y a deux propriétés que je considère essentielles à la functional programming:

  1. Les fonctions sont des membres de première classe (seulement pertinents, car pour rendre utile la deuxième propriété est nécessaire)

  2. Les fonctions sont pures, c’est-à-dire qu’une fonction appelée avec les mêmes arguments renvoie la même valeur.

Maintenant, si vous programmez dans un style impératif, vous devez utiliser l’affectation.

Considérez une boucle for. Il a un index et à chaque itération, l’index a une valeur différente. Vous pouvez donc définir une fonction qui renvoie cet index. Si vous appelez cette fonction deux fois, vous obtiendrez des résultats différents. Casser ainsi le principe n ° 2.

Si vous ne respectez pas le principe n ° 2, le fait de contourner des fonctions (principe n ° 1) devient extrêmement dangereux, car le résultat de la fonction dépend désormais du moment et de la fréquence d’appel d’une fonction.

La dernière fois que j’ai utilisé un langage fonctionnel (Clojure), je n’ai jamais été tenté d’utiliser la récursivité. Tout pourrait être traité comme un ensemble de choses auxquelles une fonction était appliquée pour obtenir des produits partiels, auxquels une autre fonction était appliquée, jusqu’à ce que le résultat final soit atteint.

La récursivité n’est qu’un moyen, et pas nécessairement le plus clair, pour gérer les nombreux éléments que vous devez généralement gérer

Dans l’intérêt des nouveaux apprenants en PF, je voudrais append mes 2 centimes. Comme mentionné dans certaines réponses, la récursivité est leur usage des variables immuables, mais pourquoi devons-nous le faire? C’est parce que cela facilite l’exécution du programme sur plusieurs cœurs en parallèle, mais pourquoi nous le voulons? Ne pouvons-nous pas l’exécuter en single core et être heureux comme toujours? Non, car le contenu à traiter augmente de jour en jour et le cycle de l’horloge du processeur ne peut pas être augmenté de manière aussi significative que l’ajout de cœurs. Au cours de la dernière décennie, la vitesse d’horloge a été de l’ordre de 2,7 GHz à 3,0 GHz pour les ordinateurs grand public et les concepteurs de puces ont du mal à installer de plus en plus de transistors. comme elle utilisait la récursivité et que la mémoire était très chère à cette époque, les vitesses d’horloge montaient d’année en année, alors la communauté a décidé de continuer avec OOP Edit: c’était assez rapide, je n’avais que quelques minutes