Les compilateurs peuvent-ils convertir la logique récursive en logique non récursive équivalente?

15

J'ai appris le F # et ça commence à influencer ma façon de penser quand je programme C #. À cette fin, j'ai utilisé la récursivité lorsque je pense que le résultat améliore la lisibilité et je ne peux pas imaginer qu'il se termine par un débordement de pile.

Cela m'amène à me demander si les compilateurs pourraient convertir automatiquement les fonctions récursives en une forme non récursive équivalente?

Aaron Anodide
la source
L'optimisation des appels de queue est un bon exemple si basique, mais cela ne fonctionne que si vous avez return recursecall(args);pour la récursivité, les choses plus complexes sont possibles en créant une pile explicite et en la réduisant, mais je doute qu'elles le
fassent
@ratchet freak: récursivité ne signifie pas "calcul utilisant une pile".
Giorgio
1
@Giorgio Je sais mais une pile est le moyen le plus simple de convertir la récursivité en boucle
ratchet freak

Réponses:

21

Oui, certains langages et compilateurs convertissent la logique récursive en logique non récursive. Ceci est connu comme l' optimisation des appels de queue - notez que tous les appels récursifs ne sont pas optimisés pour les appels de queue. Dans cette situation, le compilateur reconnaît une fonction du formulaire:

int foo(n) {
  ...
  return bar(n);
}

Ici, le langage est capable de reconnaître que le résultat renvoyé est le résultat d'une autre fonction et de changer un appel de fonction avec une nouvelle trame de pile en saut.

Sachez que la méthode factorielle classique:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

n'est pas un appel de queue optimisable en raison de l'inspection nécessaire au retour.

Pour rendre cet appel de queue optimisable,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compiler ce code avec gcc -O2 -S fact.c(le -O2 est nécessaire pour activer l'optimisation dans le compilateur, mais avec plus d'optimisations de -O3, il devient difficile pour un humain de lire ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

On peut voir en segment .L4, le jneplutôt qu'un call(qui fait un appel de sous-programme avec un nouveau cadre de pile).

Veuillez noter que cela a été fait avec C. L'optimisation des appels de queue en java est difficile et dépend de l'implémentation de la JVM - tail-recursion + java et tail-recursion + optimisation sont de bons ensembles de balises à parcourir. Vous pouvez trouver d' autres langues JVM sont capables de récursion mieux optimiser la queue (essai de Clojure (qui nécessite l' RECUR d'optimiser la queue d'appel), ou scala).

Communauté
la source
1
Je ne suis pas sûr que ce soit ce que le PO demande. Ce n'est pas parce que le runtime consomme ou non l'espace de pile d'une certaine manière que la fonction n'est pas récursive.
1
@MattFenwick Comment voulez-vous dire? "Cela m'amène à me demander si les compilateurs pourraient convertir automatiquement les fonctions récursives en une forme non récursive équivalente" - la réponse est "oui sous certaines conditions". Les conditions sont démontrées, et il y a des pièges dans certains autres langages populaires avec des optimisations d'appel de queue que j'ai mentionnées.
9

Faites preuve de prudence.

La réponse est oui, mais pas toujours, et pas tous. C'est une technique qui porte plusieurs noms différents, mais vous pouvez trouver des informations assez définitives ici et sur wikipedia .

Je préfère le nom "Tail Call Optimization" mais il y en a d'autres et certaines personnes confondront le terme.

Cela dit, il y a quelques choses importantes à réaliser:

  • Pour optimiser un appel de queue, l'appel de queue nécessite des paramètres qui sont connus au moment de l'appel. Cela signifie que si l'un des paramètres est un appel à la fonction elle-même, il ne peut pas être converti en boucle, car cela nécessiterait une imbrication arbitraire de ladite boucle qui ne peut pas être développée au moment de la compilation.

  • C # n'optimise pas de manière fiable les appels de queue. L'IL a pour instruction de le faire que le compilateur F # émettra, mais le compilateur C # l'émettra de manière incohérente, et selon la situation JIT, le JIT peut ou non le faire du tout. Toutes les indications sont que vous ne devez pas compter sur l'optimisation de vos appels de queue en C #, le risque de débordement en le faisant est important et réel

Jimmy Hoffa
la source
1
Etes-vous sûr que c'est ce que le PO demande? Comme je l'ai signalé sous l'autre réponse, ce n'est pas parce que le runtime consomme ou non l'espace de pile d'une certaine manière que la fonction n'est pas récursive.
1
@MattFenwick qui est en fait un excellent point, en termes réels, cela dépend, Le compilateur F # émettant des instructions d'appel de queue maintient complètement la logique récursive, il demande simplement au JIT de l'exécuter de manière à remplacer l'espace de pile plutôt que l'espace de pile - en croissance, cependant d'autres compilateurs peuvent littéralement compiler en une boucle. (Techniquement, le JIT se compile en boucle ou peut-être même sans boucle si la boucle est totale à l'avant)
Jimmy Hoffa