Je connais la récursivité, mais je ne sais pas comment c'est possible. Je vais utiliser l'exemple suivant pour expliquer ma question plus en détail.
(def (pow (x, y))
(cond ((y = 0) 1))
(x * (pow (x , y-1))))
Le programme ci-dessus est en langage Lisp. Je ne sais pas si la syntaxe est correcte depuis que je l'ai inventée dans ma tête, mais ça ira. Dans le programme, je définis la fonction pow, et dans pow, elle s'appelle elle-même. Je ne comprends pas comment il peut faire ça. D'après ce que je sais, l'ordinateur doit analyser complètement une fonction avant de pouvoir la définir. Si tel est le cas, l'ordinateur doit donner un message non défini lorsque j'utilise pow car je l'ai utilisé avant qu'il ne soit défini. Le principe que je décris est celui en jeu lorsque vous utilisez un x dans x = x + 1, alors que x n'était pas défini précédemment.
4 Réponses :
Les compilateurs sont beaucoup plus intelligents que vous ne le pensez. Un compilateur peut transformer l'appel récursif dans cette définition:
Disassembly of function POW (CONST 0) = 1 2 required arguments 0 optional arguments No rest parameter No keyword parameters 12 byte-code instructions: 0 L0 0 (LOAD&PUSH 1) 1 (CALLS2&JMPIF 172 L15) ; ZEROP 4 (LOAD&PUSH 2) 5 (LOAD&PUSH 3) 6 (LOAD&DEC&PUSH 3) 8 (JSR&PUSH L0) 10 (CALLSR 2 57) ; * 13 (SKIP&RET 3) 15 L15 15 (CONST 0) ; 1 16 (SKIP&RET 3)
en une intruction goto pour redémarrer la fonction à partir de zéro:
(defun pow (x y)
(cond ((zerop y) 1)
(t (* x (pow x (1- y))))))
S'il s'agissait d'une fonction récursive plus compliquée qu'un compilateur ne peut pas dérouler dans une boucle, il appellerait simplement la fonction à nouveau.
D'après ce que je sais, l'ordinateur doit analyser complètement une fonction avant de pouvoir la définir.
Quand le compilateur voit que l'on définit une fonction POW, alors il se dit: maintenant nous définissons la fonction POW. Si la définition voit alors un appel à POW, alors le compilateur se dit: oh, cela semble être un appel à la fonction que je compile actuellement et il peut alors créer du code pour faire un appel récursif.
Une fonction n'est qu'un bloc de code. Son nom est juste une aide pour que vous n'ayez pas à calculer l'adresse exacte à laquelle il aboutira. Le langage de programmation transformera les noms en l'endroit où le programme doit aller pour s'exécuter.
Comment une fonction en appelle une autre en stockant l'adresse de la commande suivante dans cette fonction sur la pile, peut-être ajouter des arguments à la pile, puis sauter à l'emplacement d'adresse de la fonction. La fonction elle-même saute à l'adresse de retour qu'elle trouve afin que le contrôle revienne à l'appelé. Il existe plusieurs conventions d'appel implémentées par le langage de quel côté faire quoi. Les processeurs n'ont pas vraiment de support de fonction, donc tout comme il n'y a rien qui s'appelle une boucle while dans les processeurs, les fonctions sont émulées.
Tout comme les fonctions ont des noms, les arguments ont aussi des noms, mais ce ne sont que de simples pointeurs, tout comme l'adresse de retour. Lorsqu'il s'appelle lui-même, il ajoute simplement une nouvelle adresse de retour et des arguments sur la pile et saute sur lui-même. Le haut de la pile sera différent et donc les mêmes noms de variables sont des adresses uniques à l'appel, donc x et y dans l'appel précédent sont ailleurs que le x et y . En fait, il n'y a pas de traitement spécial nécessaire pour appeler lui-même que pour appeler autre chose.
Historiquement, le premier langage de haut niveau, Fortran, ne supportait pas la récursivité. Il s'appellerait mais quand il revenait, il retournait à l'appelé d'origine sans faire le reste de la fonction après l'appel de soi. Fortran lui-même aurait été impossible à écrire sans récursivité, alors bien que lui-même utilisait la récursivité, il ne l'offrait pas au programmeur qui l'utilisait. Cette limitation est la raison pour laquelle John McCarthy a découvert Lisp.
Je pense que pour voir comment cela peut fonctionner en général , et en particulier dans les cas où les appels récursifs ne peuvent être transformés en boucles, il vaut la peine de réfléchir à la façon dont un le langage compilé général pourrait fonctionner, car les problèmes ne sont pas différents.
Imaginons comment un compilateur pourrait transformer cette fonction en code machine:
(defun foo (x) (+ x (bar x)))
Et supposons que c'est le cas je ne sais rien de bar au moment de la compilation. Eh bien, il a deux options.
foo de telle manière que l'appel à bar soit traduit par un ensemble d'instructions qui disent: 'recherchez la définition de fonction stockée sous le nom bar , quel qu'il soit, et arrangez-vous pour appeler cette fonction avec les bons arguments '. foo de telle manière qu'il y ait un appel de fonction au niveau de la machine à une fonction, mais l'adresse de cette fonction est laissée comme un espace réservé d'une sorte. Et il peut ensuite attacher des métadonnées à foo qui dit: 'avant que cette fonction ne soit appelée, vous devez trouver la fonction nommée bar , trouver son adresse, la coller dans le code au bon endroit, et supprimez ces métadonnées . Ces deux mécanismes permettent de définir foo avant de savoir ce qu'est bar . Et notez qu'au lieu de bar j'aurais pu écrire foo : ces mécanismes traitent aussi les appels récursifs. Cependant, ils diffèrent en dehors de cela.
foo est appelé, il doit effectuer une sorte de recherche dynamique pour bar qui impliquera une surcharge (mais cette surcharge peut être assez petit):
bar est redéfini, alors la nouvelle définition sera reprise, ce qui est très souhaitable pour un langage interactif, ce que sont généralement les implémentations Lisp. foo a toutes ses références à d'autres fonctions qui lui sont liées, alors les appels se produisent au niveau de la machine:
La seconde de ces implémentations est proche de la façon dont les compilateurs traditionnels compilent le code: ils compilent le code en laissant un tas d'espaces réservés avec des métadonnées associées indiquant à quels noms correspondent ces espaces réservés. Un linker (parfois appelé link-loader, ou loader) parcourt alors tous les fichiers produits par le compilateur ainsi que d'autres bibliothèques de code et résout toutes ces références, ce qui entraîne un peu de code qui peut réellement être exécuté.
Un système Lisp très simple pourrait fonctionner entièrement par le premier mécanisme (je suis presque sûr que c'est ainsi que fonctionne Python, par exemple). Un compilateur plus avancé fonctionnera probablement par une combinaison du premier et du deuxième mécanisme. À titre d'exemple, CL permet au compilateur de faire des hypothèses selon lesquelles les auto-appels apparents dans les fonctions sont auto-appels, et ainsi le compilateur peut bien les compiler comme des appels directs (essentiellement, il compilera les fonction puis liez-le à la volée). Mais lors de la compilation du code en général, il peut appeler «par le nom» de la fonction.
Il existe aussi des stratégies plus ou moins héroïques que les choses pourraient faire: par exemple au premier appel d'une fonction liez-le, à la volée, à toutes les choses auxquelles il fait référence, et notez dans leurs définitions que si elles changent, alors cette chose doit également être dissociée pour que tout se reproduise. Ce genre d'astuces semblait autrefois invraisemblable, mais les compilateurs pour des langages comme JavaScript font des choses au moins aussi épineuses que ça tout le temps maintenant.
Notez que les compilateurs et les éditeurs de liens pour les systèmes modernes font en fait quelque chose de plus compliqué que j'ai décrit, à cause des bibliothèques partagées & c: ce que j'ai décrit est plus ou moins ce qui s'est passé avant la bibliothèque partagée.
il ne suffit pas d'ajouter plus de parenthèses au code python / ruby, pour obtenir du code lisp. désolé, ce n'est même pas proche de lisp. la prochaine fois, donnez un exemple dans la langue que vous connaissez, la récursivité ne se limite pas à lisp. sur la façon dont il est mis en œuvre - cela dépend et c'est un sujet énorme. vous pouvez en apprendre davantage sur les méthodes à partir de «Une introduction à la programmation fonctionnelle par le biais de Lambda Calculus» de Greg Michaelson.