Les programmes en langages fonctionnels plus susceptibles d'avoir débordements de pile?

Question

Je commence à apprendre OCaml, et je suis vraiment apprécier la puissance de récursion dans la langue. Cependant, une chose que je suis inquiet est empilez déversoirs.

Si OCaml utilise la pile pour les appels de fonction, ne sera pas déborder il a fini par la pile? Par exemple, si j'ai la fonction suivante:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

il doit éventuellement provoquer une pile débordement. Si je devais faire la chose équivalente en c ++ (en utilisant récursion), je sais que ce serait déborder.

Alors ma question est, est-il construit des garde-fous pour éviter les langages fonctionnels de déborder la pile? Sinon, sont-ils pas moins utiles comme celui-ci, puisque l'algorithme de sommation ci-dessus, écrit dans un style procédural avec une boucle, peut gérer un nombre quelconque (dis-en ce qui concerne le débordement d'entier)?

Answer 1

Toutes les implémentations (décent de langages fonctionnels ;-) optimiser la récursivité de queue, mais ce n'est pas ce que vous faites ici, puisque l'appel récursif est pas la dernière opération (il doit être suivi par l'addition).

Ainsi, on apprend rapidement à utiliser une fonction auxiliaire qui est récursif queue (et prend le courant total étant accumulé comme un argument), de sorte que l'optimiseur peut faire son travail, à savoir, déduction faite de la syntaxe possible de O'Caml dans laquelle I » m rouillé:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

Ici, la somme arrive en tant qu'argument à l'appel récursif, à savoir, avant que la récursion lui-même, et donc l'optimisation queue peut donner un coup de (parce que la récursivité est la dernière chose qui doit arriver!).

Answer 2

Les langages fonctionnels ont généralement une pile beaucoup plus grande. Par exemple, j'ai écrit une fonction spécifiquement pour tester les limites de la pile dans OCaml, et il a obtenu plus de 10.000 appels avant d'barfed. Cependant, votre point est valide. Stack-déversoirs sont toujours quelque chose que vous devez faire attention dans les langages fonctionnels.

L'une des stratégies que les langages fonctionnels afin d'atténuer leur dépendance à l'égard récursion est l'utilisation de l'optimisation queue d'appel . Si l'appel à la prochaine récursion de la fonction en cours est la dernière instruction de la fonction, l'appel en cours peut être mis au rebut de la pile et le nouvel appel instancié à sa place. Les instructions de montage qui sont générés sont fondamentalement les mêmes que ceux pour tout en boucles dans le style impératif.

Votre fonction n'est pas la queue d'appel optimisable parce que la récursion est pas la dernière étape. Il doit revenir d'abord, puis il peut ajouter x au résultat. Habituellement, cela est facile de se déplacer, vous créez simplement une fonction d'aide qui passe un accumulateur ainsi que les autres paramètres

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;

Answer 3

Quelques langages fonctionnels tels que le schéma précisent que récursion doit être optimisé pour être équivalent à l'itération; Par conséquent, une fonction récursive dans le schéma ne sera jamais entraîner un débordement de pile, peu importe combien de fois il récursif (en supposant, bien sûr, qu'il ne récursion pas aussi ou se livrer à récursion mutuelle dans d'autres endroits en dehors de la fin).

La plupart des autres langages fonctionnels ne nécessitent pas récursion queue pour être mis en œuvre efficacement; certains choisissent de le faire, d'autres ne le font pas, mais il est relativement facile à mettre en œuvre, donc j'attendre à ce que la plupart des implémentations font.

Answer 4

Il est certainement facile pour les novices d'écrire récurrences profondes qui soufflent la pile. Objective Caml est inhabituel en ce les fonctions List de la bibliothèque ne sont pas pile sans danger pour les longues listes . Des applications comme Unison ont effectivement remplacé la bibliothèque standard List Caml avec une pile de sécurité version. La plupart des autres implémentations font un meilleur travail avec la pile. (Avertissement:. Mes informations décrit OCaml 3.08, la version actuelle, 3.11, peut-être mieux)

Standard ML de New Jersey est inhabituel en ce qu'il n'utilise une pile, de sorte que votre profonde récurrences continuer jusqu'à ce que vous manquez de tas. Il est décrit dans l'excellent livre de Andrew Appel avec continuations Compiler.

Je ne pense pas qu'il y ait un problème grave; il est plus un « point de conscience » que si vous allez écrire beaucoup de code récursif, que vous êtes plus susceptible de le faire dans une langue fonctionnelle, vous devez être au courant des appels non-queue et de la taille de la pile comme par rapport à la taille des données que vous allez traiter.

Answer 5

Ceci est difficile - en principe oui, mais les compilateurs et les runtimes pour les langages fonctionnels représentent le degré accru de récursivité dans les langages fonctionnels. Le plus fondamental est que la plupart des runtimes linguistiques fonctionnelles demandent une pile beaucoup plus grande que les programmes itératifs normaux utiliseraient. Mais en plus qu'un compilateur de langage fonctionnel est beaucoup plus capable de transformer le code récursif en un non récurrent en raison des contraintes plus strictes de la langue.