Appels de sous-routines dans le monde antique : avant que les ordinateurs n’aient une pile ou un tas
(devblogs.microsoft.com)- Les premiers ordinateurs devaient implémenter les appels de fonction sans pile ni tas, et les compilateurs géraient l’état des appels à l’aide de variables globales cachées correspondant aux paramètres, à l’adresse de retour et aux variables locales
- L’appelant stockait les arguments, plaçait la position de reprise dans une variable d’adresse de retour, puis sautait vers le point d’entrée de la fonction ; une fois le calcul terminé, la fonction sautait de nouveau vers l’adresse stockée
- Même les variables locales logiques utilisaient en réalité un espace de stockage global ; en apparence cela ressemblait à des fonctions, mais en interne le fonctionnement était plus proche d’une mémoire fixe et de
goto - Certaines ABI et certains processeurs optimisaient le passage d’arguments et le traitement de l’adresse de retour au moyen de registres ou de
branch with link, mais la contrainte de base restait la même - Comme l’adresse de retour d’une même fonction était écrasée par un nouvel appel, les appels récursifs étaient impossibles ; les langages de l’époque contournaient cela en interdisant la récursivité ou en ne l’autorisant que de manière explicite
Comment construire des appels de fonction sans pile
- Dans les premiers environnements informatiques, il n’existait pas de pile ni de tas au sens où on l’entend aujourd’hui
- L’allocation dynamique de mémoire sans tas pouvait être remplacée par des tampons de taille fixe
- Même pour traiter des données de taille variable, on réservait à l’avance un tampon fixe suffisamment grand
- Si les données demandées dépassaient la capacité du tampon, le programme se terminait par une erreur fatale
- Une implémentation plus conviviale permettait de définir la capacité maximale à la compilation
- Une implémentation plus sophistiquée plaçait un allocateur personnalisé au-dessus d’un tampon fixe pour l’utiliser comme
allocateetfree
Convention d’appel fondée sur des variables globales cachées
- Pour implémenter les appels de fonction sans pile, le compilateur définissait plusieurs variables globales cachées pour chaque fonction
- une variable globale pour chaque paramètre d’entrée
- une variable globale contenant l’adresse de retour de la fonction
- des variables globales correspondant aux variables locales
- Le code appelant s’exécutait dans l’ordre suivant
- il stockait les valeurs des paramètres dans les variables globales cachées correspondantes
- il écrivait la position de reprise dans la variable d’adresse de retour de la fonction
- il faisait un saut
gotovers l’emplacement de début de la fonction
- La fonction lisait et écrivait à la fois ses paramètres et ses variables locales dans ces variables globales cachées
- Une fois l’exécution terminée, elle plaçait la valeur de retour dans le registre de valeur de retour, puis sautait vers l’adresse stockée dans la variable d’adresse de retour de la fonction
Exemple de transformation d’un code de type C en code fondé sur goto
- La fonction d’exemple
add_two_values(int a, int b)pouvait être transformée sans pile en un schéma de stockage comme celui-cia2v_aeta2v_bsont des variables globales destinées à stocker les argumentsa2v_cest une variable globale correspondant à la variable localeca2v_retaddrest une variable globale destinée à stocker l’adresse de reprise
- L’appelant
sample()stocke31415et2718dans les variables globales d’arguments respectives - Il place ensuite la position
resumedansa2v_retaddr, puis saute versadd_two_values add_two_valuesstocke le résultat du calcul dansreturn_value_register, puis revient viaa2v_retaddr- Une fois revenu à la position
resume, l’appelant stocke la valeur du registre de retour danssample_x
Optimisations avec registres et branch with link
- La même structure pouvait être rendue plus rapide au niveau de l’ABI grâce au passage par registres
- De nombreux processeurs fournissaient un
link registerspécial ainsi que l’instructionbranch with linkbranch with linkenregistre automatiquement dans le link register l’adresse de l’instruction suivant l’instruction de branchement- l’appelant peut placer les deux premiers arguments dans
argument_register_1etargument_register_2 - la fonction appelée peut déplacer les valeurs de ces registres dans ses propres variables globales cachées avant de les utiliser
- L’adresse de retour peut elle aussi être enregistrée depuis
link_registerdans la variable d’adresse de retour de la fonction - Cette optimisation conserve la structure fondamentale qui permet les appels et retours sans pile
Pourquoi la récursivité est bloquée
- La contrainte principale de cette méthode d’appel est l’impossibilité des appels récursifs
- Lors d’un appel récursif, la variable d’adresse de retour de la même fonction est écrasée par l’adresse de retour du nouvel appel
- Quand l’appel extérieur se termine, la position d’origine à laquelle il devait revenir a disparu, ce qui provoque un saut vers un mauvais emplacement
- Les langages de programmation de l’époque évitaient ce problème en ne prenant pas en charge la récursivité
- Au départ, FORTRAN ne prenait même pas en charge les sous-routines, qui n’ont été ajoutées qu’en 1958
- Dans FORTRAN, la prise en charge de la récursivité n’est devenue standard qu’en 1991, et même alors il fallait déclarer explicitement la sous-routine comme
RECURSIVE
Code auto-modifiant et instructions de sous-routine des premiers processeurs
- Certains compilateurs utilisaient de manière plus astucieuse du code auto-modifiant
- le champ d’adresse dans l’instruction de saut à la fin de la fonction jouait en pratique le rôle de variable d’adresse de retour
- Cette méthode n’était pas seulement une astuce, elle pouvait répondre à un besoin pratique
- certains processeurs ne prenaient pas en charge les sauts indirects
- Une fois l’utilité pratique des sous-routines reconnue, plusieurs processeurs ont ajouté des instructions d’appel dédiées
- l’adresse de retour était stockée dans le premier mot de la sous-routine
- l’exécution réelle commençait au deuxième mot
- au retour, un saut indirect était exécuté via le label de début de la sous-routine
- Dans l’exemple assembleur,
bsr add_two_valuesstocke l’adresse de retour dans le premier mot deadd_two_values, puis exécute les vraies instructions à partir de l’instruction qui suit lenopsacrificiel
1 commentaires
Commentaires Hacker News
Sur ce sujet, The Art of Computer Programming était vraiment excellent
En apparence, cela semble ancien, mais il y a énormément d’algorithmes pour gérer des tableaux ou des structures de données à taille dynamique datant d’avant l’ère du heap et de la stack
Le livre progresse pas à pas jusqu’au garbage collection et à l’implémentation des listes Lisp, avec toute la connaissance encyclopédique qu’on attend de Knuth
Un exemple que j’aime particulièrement est la manière dont deux tableaux partagent dynamiquement un même espace. Un tableau croît vers l’avant depuis
location#0, et le second croît à rebours depuislocation#End, ce qui permet de partager efficacement un espace alloué statiquementOn peut étendre cela à un nombre arbitraire de tableaux, mais à ce stade il vaut mieux simplement utiliser
MallocetRealloc, et la technique elle-même se rapproche déjà beaucoup d’une routine de type mallocL’insertion et le collage n’exigeaient pas de déplacer les données, mais la recherche, si. Malgré cela, ça fonctionnait bien
S’il n’y avait pas assez de place, on lui attribuait moins que sa valeur préférée, et si elle n’obtenait même pas son minimum, le lancement échouait
Il me semble que le système plaçait le heap et les bibliothèques en bas de ce segment de RAM physique, et la stack en haut
Vers System 8, l’ajout d’une couche de virtualisation a rendu cette approche moins nécessaire, et à l’époque de MacOS X, avec la mémoire paginée comme sur les autres systèmes, ce genre d’acrobatie n’était plus utile
Cela dit, c’est amusant de penser qu’un de ces « trucs bizarres mais efficaces » de l’Art of Computer Programming a servi à répartir la RAM entre plusieurs applications simultanées
L’une croissait vers le haut et l’autre vers le bas. C’était une architecture fascinante, mais elle n’a finalement pas tenu les performances promises
À l’intérieur d’une page de taille fixe, le tableau des offsets croît vers l’avant, tandis que le tableau des valeurs de lignes à longueur variable croît à rebours depuis la fin. Si l’on supprime une ligne, il me semble que cela peut laisser des trous dans le tableau arrière
Comme la documentation cite TAOCP à propos de la structure B-tree elle-même, il ne serait pas surprenant qu’il y ait eu une inspiration directe
Ajouter les fonctions récursives à ALGOL a été assez controversé, et c’est resté une histoire amusante : https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 - octobre 2022, 8 commentaires
How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 - mai 2020, 47 commentaires
How recursion got into Algol 60: a comedy of errors - https://news.ycombinator.com/item?id=10131664 - août 2015, 124 commentaires
How recursion got into programming: a comedy of errors - https://news.ycombinator.com/item?id=8073361 - juillet 2014, 108 commentaires
J’ai écrit un interpréteur Forth pour une machine SUBLEQ(https://github.com/howerj/subleq) et un interpréteur pour une machine bit-série(https://github.com/howerj/bit-serial), et aucun des deux n’avait la pile d’appels de fonctions nécessaire à Forth
SUBLEQ n’autorise même pas les chargements/stockages indirects, donc dès qu’on veut faire quelque chose d’un peu complexe, il faut du code auto-modifiant
Pour les deux machines, l’approche a consisté à créer une machine virtuelle capable d’assurer ces fonctions, en y ajoutant aussi du multithreading coopératif
S’il faut un heap, on l’écrit en Forth, et l’ensemble de mots en virgule flottante est aussi écrit en Forth. Beaucoup de MCU n’ont toujours pas d’instructions en virgule flottante, et on peut gérer cela via des appels de fonctions logicielles qui l’implémentent
D’autres compilateurs ont probablement utilisé des approches similaires, même si ce n’est pas mentionné. Certains interpréteurs BASIC implémentaient aussi une VM puis la prenaient pour cible, et le P-Code est similaire
L’essentiel de la mémoire système de base était de la mémoire vidéo, à laquelle il fallait accéder via une procédure assez lourde de
poke/peekdes registres de la puce vidéoLa puce vidéo maintenait un pointeur de mémoire courant à auto-incrémentation, de sorte qu’en lecture ou écriture séquentielle le pointeur augmentait de 1, mais le simple fait que l’essentiel de la mémoire système ne soit accessible que de cette manière rendait l’écriture de gros programmes difficile
TI a donc créé une machine abstraite appelée GPL pour rendre cet accès à la RAM vidéo plus naturel. Mais comme elle était interprétée sur le TMS9900, elle était plus lente que du code natif, et le CPU ne pouvait en plus accéder à la RAM de la puce vidéo que lorsque celle-ci n’effectuait pas le balayage de l’écran, par exemple pendant les périodes de retour horizontal/vertical, ce qui la ralentissait encore
Le code BASIC et les variables se trouvaient eux aussi entièrement dans cette mémoire vidéo, donc il est assez évident de quoi était écrit l’interpréteur BASIC du TI-99/4A. Ce n’était pas rapide du tout
Ce qui est intéressant, c’est que le TMS9900 n’avait pas de véritables registres généraux. Les registres d’espace de travail WR0 à WR15 se trouvaient quelque part en mémoire, et le registre pointeur d’espace de travail WP les désignait
Les seuls registres physiques du CPU étaient le PC, le WP et le registre d’état. On pouvait donc faire une forme très primitive de fenêtrage de registres, et un branchement via l’instruction
BLWPactivait un nouvel ensemble de « registres » situé ailleurs en mémoire, tout en stockant l’adresse de retour dans le nouvel espace de travailSi je parle souvent du TI-99/4A en ce moment, c’est parce que je développe un assembleur pour cette machine comme projet perso
Il est vrai que certains processeurs stockaient l’adresse de retour dans le mot situé juste avant la première instruction d’une sous-routine, et le PDP-8 faisait cela
On peut aussi voir l’évolution du PDP-8 comme un parcours vers la prise en charge matérielle de la récursion
Au départ, l’instruction
JMSinscrivait l’adresse de retour dans le premier mot de la fonction. Il était aussi courant que l’appelant place les arguments juste après l’instructionJMS, puis que l’appelé lise les arguments à partir d’un décalage basé sur l’instruction de retour, en incrémentant celle-ci à chaque fois pour que l’adresse de retour pointe de nouveau vers le codePar la suite, il est devenu assez courant d’utiliser l’un des emplacements à auto-incrémentation pour créer une pile simple. Le PDP-8 disposait de 8 emplacements mémoire qui s’incrémentaient à chaque usage comme pointeur, et le prologue/épilogue des fonctions gérait directement cette pile pour permettre une récursion complète
Plus tard encore, des implémentations microprocesseur comme le Harris 6120 ont ajouté une pile matérielle, ce qui a amélioré les performances
R, c’est-à-dire une instruction de sauvegarde de l’adresse de retourCette instruction stockait le
PC+1déjà incrémenté dans la partie adresse de l’instruction à l’emplacement cible, qui était par convention un branchement inconditionnel situé juste avant le début de la sous-routineAprès l’instruction
R, on plaçait une instruction de branchement inconditionnelUvers la sous-routine concernéeLa sous-routine retournait en branchant vers l’adresse située avant elle, où se trouvait un branchement inconditionnel revenant juste après le point d’appel
La récursion était impossible, sauf à utiliser une convention d’appel plus évoluée. Et tous les codes d’instruction du langage assembleur tenaient en une seule lettre
Dans les programmes écrits pour AVR-8, utiliser la convention d’appel C peut parfois sembler complètement absurde
En assembleur, on peut garder les variables de boucle internes dans le gros fichier de registres, ou bien utiliser les méthodes décrites dans l’article
Dans ce genre d’application, la technique de « coloration » des fonctions est aussi bonne. Si l’on sait que les fonctions rouges et vertes ne sont jamais actives en même temps, on peut réutiliser leurs variables locales ou leurs paramètres
Dans un projet de base de code pour microcontrôleur que j’avais rejoint autrefois, plusieurs développeurs ont passé des semaines à traquer des bugs insaisissables dans plusieurs sous-systèmes
Quand on déplaçait le code, les bugs se déplaçaient avec lui. En traçant un peu et en posant des pièges, on a pu identifier des endroits du code où la pile d’appels devenait trop profonde et écrasait d’autres structures de données
C’est exactement comme ça qu’on m’a forcé à programmer quand j’ai appris au début. Non pas dans les années 1970, mais en 2001
parce que ma première expérience de programmation a été le « langage » de script semi-graphique fourni par l’outil de développement de jeux RPG Maker 2000
Si vous n’avez jamais vu le scripting de RM2K, imaginez un mélange de Scratch et du mode Paredit d’Emacs. Exemple : https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...
Ça ressemble à du texte, mais on ne peut pas l’éditer comme du texte ; on ne l’édite qu’au moyen de blocs associés à des boîtes de dialogue de propriétés
Bien sûr, le langage de script de RPG Maker n’avait rien d’aussi chic qu’une pile. Si on voulait des sous-routines réutilisables, il fallait allouer des variables globales secrètes pour les paramètres, et il n’y avait aucune réentrance
Avec le recul, j’ai l’impression qu’en s’obstinant suffisamment, on aurait pu implémenter à la fois des registres et une pile d’exécution dans RPG Maker 2000
Au début, ça paraît facile. On peut créer de faux « registres » comme la zero page du 6502, et même une pile via l’accès indirect aux variables (https://rpgmaker.net/tutorials/523/)
Le problème, c’est que RM2K avait une forme de concurrence avec ses scripts en « parallel process ». Si des processus parallèles utilisent ce genre d’abstraction, différents « threads » écrasent l’état dans tous les sens
Il faut donc plusieurs zero pages et piles par « cœur virtuel », et affecter/lier/ordonnancer un cœur virtuel à chaque script parallèle. Autrement dit, il faut d’une manière ou d’une autre que chaque script dispose de son propre pointeur de pile
Pour rendre ça fiable même en présence de conditions de course, il faut en général quelque chose comme un mutex
Vu l’acharnement des développeurs de jeux RPG Maker, je parierais bien que quelqu’un a trouvé un moyen de détourner une fonctionnalité du runtime pour qu’elle se comporte comme un mutex, mais honnêtement, je préfère ne pas savoir ce qu’ils ont réellement fait tellement c’est effrayant
Je me souviens avoir téléchargé sur rpgmaker.net un jeu qui implémentait un custom battle system. C’était une refonte complète du système de combat intégré, réalisée avec le genre de techniques que vous décrivez
Quand je l’ai ouvert dans l’éditeur pour voir comment ça marchait, j’ai été complètement sidéré. Il y avait des centaines de « variables » et, si je me souviens bien, seules des i64 étaient autorisées, ainsi que des centaines de « switches ». Les switches étaient des booléens
À l’époque, je n’avais absolument aucune notion de pile, de tas ou d’appel de fonction
Je n’arrive même pas à imaginer l’énergie qu’il a fallu pour construire, maintenir, déboguer tout ça
Si je me souviens bien, quand on écrivait des programmes BASIC sur ZX81, on le faisait presque d’une manière « sans pile »
1 GOTO 3010 LET C = A + B20 RETURN30 LET A = 140 LET B = 250 GOSUB 1060 LET A = C70 LET B = 380 GOSUB 1090 PRINT CRUN6En pratique, on faisait soi-même ce que fait le compilateur dans l’article. Les numéros de ligne étaient des adresses mémoire, et les variables cachées ne m’étaient pas cachées. C’est moi qui étais le compilateur
La seule chose que faisait l’interpréteur, c’était stocker l’adresse de retour de
GOSUBCela dit, le code est peut-être syntaxiquement faux, ou ma mémoire me joue des tours. Quarante ans, c’est long, mais l’idée générale est juste
Et le processeur Z80 de la machine, lui, disposait bien de fonctionnalités de gestion de pile. L’interpréteur BASIC était vraiment rudimentaire, mais il avait une excuse : seulement 1 KB de RAM, et 8 KB de ROM pour l’OS, l’interpréteur et tout le reste
GOSUBstocke un numéro de ligne ou une autre référence queRETURNconsultera, et si l’on imbrique des appelsGOSUB, il faut se souvenir de plusieurs points de retour, donc il faut bien une pile sous une forme ou une autreCela dit, certains BASIC n’avaient pas de pile générique, mais seulement un tableau fixe de pointeurs de retour et un index de position courante, avec par exemple une profondeur d’appel figée à 7. Du point de vue du programmeur, ça se comportait comme une pile d’appels
Bien sûr, ce n’est pas une « vraie » pile au sens où on l’entend d’habitude, avec des variables locales et des paramètres
Dans l’environnement par défaut de BBC BASIC, on pouvait faire une démo amusante montrant ce qui se passait lors d’appels imbriqués, y compris récursifs. En plaçant la pile tout en haut de la mémoire d’affichage et en évitant d’y dessiner quoi que ce soit, on pouvait voir la pile grandir au fur et à mesure de l’exécution
Comme la résolution d’écran était faible, les 2 octets d’adresse de retour apparaissaient comme 8 gros pixels dans les modes d’affichage 1 ou 5. En mode 2, c’était 4, mais avec des couleurs clignotantes, donc moins bien ; en modes 0, 3, 4 et 6, c’était 16, mais voir les choses au niveau du bit était plus difficile à interpréter qu’une répétition de 8 couleurs
Avant l’existence de tas extensibles arbitrairement, les programmeurs faisaient au moins preuve d’un minimum de jugement d’ingénierie
parce qu’il fallait tenir compte de la distribution probabiliste des entrées et dimensionner correctement tous les espaces de stockage intermédiaires
C’est de là que venaient les « BUGS AND LIMITATIONS »
Donc on alloue tout statiquement à la compilation, et il faut savoir combien de mémoire les entrées vont consommer
Mais connaître une borne supérieure de consommation mémoire, c’était aussi autrefois normal même pour les développeurs applicatifs. Parce qu’on ne veut absolument pas tomber à court de mémoire
Aujourd’hui, j’ai l’impression qu’on laisse juste l’utilisation mémoire en mode YOLO
Par exemple, c’était une grande amélioration par rapport aux limitations du type longueur maximale de commande finie et courte dans sed
J’ai fait tellement de programmation fonctionnelle qu’il m’est vraiment difficile d’imaginer comment écrire du code sans récursion
Je sais, d’un point de vue technique, comment transformer un algorithme récursif en algorithme itératif, et je l’ai déjà fait dans des environnements aux ressources très limitées, mais je n’aime pas ça
En général, la version récursive est plus élégante et, dans 99 % des cas, suffisamment rapide. Si le compilateur prend en charge la récursion terminale, on est proche de 100 %, mais pour la plupart des tâches plus intéressantes, il faut de toute façon maintenir soi-même la pile
Il m’arrive de faire ce genre de travail exprès, juste pour apprendre comment on faisait avant ma naissance. Je bidouille parfois des jeux Commodore 64, et ça fait fortement ressentir à quel point nous vivons aujourd’hui dans le luxe avec du matériel rapide, peu coûteux et facile à utiliser
Pour faire de la récursion sur ce genre d’anciennes machines, il fallait créer soi-même le mécanisme de pile, et il restait malgré tout des problèmes à gérer parce qu’en dehors du stockage global, il n’y avait fondamentalement rien d’autre à utiliser
J’ai connu cette époque, mais je ne la recommanderais à personne
Dans la fonctionnalité
@letde Enhanced GNU Awk, pour les blocs@lethors fonction, par exemple dans des blocsBEGINouEND, j’ai fait en sorte que le compilateur alloue des variables globales secrètesCes variables sont réutilisées autant que possible entre les blocs
$ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'$ cat awkvars.out$let0001: untyped variable$let0002: untyped variable$let0003: 1ARGC: 1ARGIND: 0ARGV: array, 1 elementsBINMODE: 0[ .. snip many ]https://www.kylheku.com/cgit/egawk/about/
pingne passe pas, etnc -z 104.37.63.7 443non plusMise à jour : l’infrastructure de sécurité semble cassée. Je ne sais même pas de quoi il s’agit, et je n’utilise pas Twitter. Si je vérifie l’AS, c’est Google Fiber
Et j’aimerais qu’on évite de me doxxer s’il vous plaît