Appels de sous-routines dans le monde antique : avant que les ordinateurs n’aient une pile ou un tas

Appel de sous-routines à l’époque ancienne, quand les ordinateurs n’avaient ni pile ni tas

• En informatique moderne, on considère la pile et le tas comme allant de soi, mais aux débuts de l’informatique, les ordinateurs fonctionnaient sans pile ni tas.
• Il n’est pas difficile d’imaginer l’informatique sans allocation dynamique de mémoire. Il faut utiliser des tampons mémoire de taille fixe pour tout.
• Lorsqu’il faut traiter des données de taille variable, on réserve un tampon de taille fixe suffisamment grand pour contenir les données prévisibles.
• On peut fournir des réglages à la compilation pour permettre au client d’ajuster la capacité maximale, ou écrire un allocateur personnalisé capable d’« allouer » et de « libérer » de la mémoire dans un tampon de taille fixe.

Appeler des fonctions sans pile

• Le compilateur définit des variables globales secrètes pour les paramètres d’entrée, l’adresse de retour et les variables locales de chaque fonction.
• Pour générer un appel de fonction, le compilateur assigne les valeurs des paramètres à ces variables globales secrètes, assigne l’adresse de retour à la « variable d’adresse de retour » secrète de la fonction, puis saute au début de la fonction.
• La fonction lit ses paramètres depuis les variables globales secrètes et utilise des variables globales secrètes prédéfinies correspondant logiquement aux variables locales.
• À la fin de la fonction, elle saute à l’adresse contenue dans sa « variable d’adresse de retour » secrète.

Optimisation de l’ABI

• Pour optimiser l’ABI, certaines valeurs sont transmises dans des registres plutôt que dans des variables globales.
• La plupart des processeurs disposent d’un registre de « lien » et d’une instruction de « branchement avec lien », qui règle automatiquement le registre de lien à l’adresse suivant l’instruction de « branchement avec lien ».
• On optimise la convention d’appel pour transmettre les deux premiers paramètres dans des registres.

L’impossibilité des appels récursifs

• Les appels récursifs ne fonctionnent pas. Un appel récursif écrase la variable d’adresse de retour avec l’adresse de retour de l’appel récursif, si bien que l’appel extérieur saute au mauvais endroit une fois terminé.
• Les langages de programmation de l’époque résolvaient ce problème en déclarant qu’ils ne prenaient pas en charge la récursivité.

Bonus

• Certains compilateurs étaient encore plus astucieux en utilisant du code auto-modifiant : la variable spéciale d’adresse de retour est en réalité le champ d’adresse de l’instruction de saut située à la fin de la fonction.
• Lorsque le processeur ne prend pas en charge les sauts indirects, cette méthode devient une nécessité pratique.
• Une fois la valeur pratique des sous-routines reconnue, de nombreux processeurs ont ajouté des instructions d’appel de sous-routine qui stockent l’adresse de retour dans le premier mot de la sous-routine et commencent l’exécution au deuxième mot de celle-ci.
• Pour revenir depuis la sous-routine, on exécute un saut indirect via le label de début de la sous-routine.

L’avis de GN⁺

• Cet article aide à comprendre l’évolution des techniques de gestion mémoire utilisées dans le développement logiciel moderne en expliquant comment on programmait aux débuts de l’informatique, quand il n’y avait ni pile ni tas.
• La manière de programmer de cette époque, sans pile ni tas, peut sembler très étrangère et inefficace aux développeurs d’aujourd’hui, mais elle fournit des connaissances de fond essentielles pour comprendre comment la technologie a évolué au fil de l’histoire de l’informatique.
• Les contraintes de programmation d’une époque où les appels récursifs étaient impossibles offrent un fait historique intéressant aux développeurs qui utilisent aujourd’hui des algorithmes récursifs.
• D’un point de vue critique, ces méthodes de programmation initiales montrent aussi à quel point elles étaient limitées face aux exigences complexes et variées du monde moderne.

[GN⁺]

Avis Hacker News

• Évaluation positive du livre The Art of Computer Programming

  • Ce livre peut sembler ancien, mais il traite de divers algorithmes modifiant des tableaux dynamiques et des structures de données d’avant les heap et les stack.
  • Il explique aussi le garbage collection et l’implémentation des listes Lisp, et offre un savoir de type encyclopédique qui donne envie de lire Knuth.

• Explication d’une méthode permettant à deux tableaux de partager dynamiquement un même espace

  • Un tableau grandit normalement à partir de la position #0, tandis que l’autre grandit en sens inverse à partir de la position #End, ce qui permet aux deux tableaux de partager efficacement un espace alloué statiquement.
  • Cette méthode peut être étendue à plusieurs tableaux, mais à ce stade il peut être préférable d’utiliser Malloc et Realloc.

• Partage d’un lien vers une histoire amusante sur le fait que l’introduction des fonctions récursives dans le langage ALGOL a été controversée

  • Un lien est partagé vers un récit intéressant sur l’histoire de l’introduction de la récursion dans les langages de programmation.

• Partage d’une expérience d’écriture d’un interpréteur Forth pour une machine SUBLEQ et une machine bit-série

  • Ces deux machines ne disposent pas de stack d’appels de fonctions, pourtant essentielle à Forth.
  • SUBLEQ n’autorise ni chargement ni stockage indirects, et nécessite du code auto-modifiant pour effectuer des tâches inhabituelles.
  • Une machine virtuelle a été construite pour fournir ces fonctionnalités et prendre en charge le multithreading coopératif.
  • Si nécessaire, le heap est écrit en Forth, avec aussi des opérations en virgule flottante implémentées sous forme de fonctions logicielles.

• Explication de l’évolution technique liée aux appels de sous-routine sur le processeur PDP-8

  • Au départ, l’instruction JMS stockait l’adresse de retour dans le premier mot de la fonction.
  • Plus tard, des emplacements à auto-incrémentation ont été utilisés pour créer une stack simple, et le prologue/l’épilogue de la fonction gérait manuellement cette stack, rendant possible une récursion complète.
  • Ensuite, une stack matérielle a été ajoutée dans l’implémentation microprocesseur pour améliorer les performances.

• Partage de la préférence pour la récursion d’un utilisateur ayant longtemps pratiqué la programmation fonctionnelle

  • Cette personne sait comment transformer des algorithmes récursifs en algorithmes itératifs, mais préfère la récursion.
  • Dans la plupart des cas, la récursion est suffisamment rapide, surtout quand le compilateur prend en charge la tail recursion.
  • En bidouillant des jeux Commodore 64, cette personne cherche aussi à comprendre comment on programmait autrefois.

• Partage d’une expérience de conception d’un multiplexeur série RS232 vers 1991

  • Conception matérielle utilisant un processeur Z80, une EPROM et un périphérique série Z80-SIO.
  • En l’absence de stack, la méthode consistait à précharger l’adresse de retour dans une paire de registres pour effectuer les appels de fonctions.

• Mention de la situation passée où, avant que le heap puisse être extensible, les programmeurs devaient réfléchir à la distribution probable des entrées et dimensionner correctement les tampons intermédiaires

  • Cela entraînait des « bugs et limites ».

• Explication du fait qu’à l’époque où l’on ne pouvait pas utiliser la récursion, la tail recursion restait possible

  • Il fallait utiliser des branchements ordinaires sauf pour l’appel initial effectué avec branch_with_link.

• Explication de la manière dont le compilateur d’Enhanced GNU Awk alloue des variables globales secrètes pour les blocs @let situés hors des fonctions

  • Ces variables sont réutilisées autant que possible.

• Mention d’un post décrivant le monde visé par l’article Goto considered harmful

  • La plupart des gens ne connaissent que le titre, alors que l’article défend l’idée de fournir un point d’entrée unique aux sous-routines.
  • Il arrive d’écrire du code assembleur qui saute vers une autre sous-routine, mais on ne souhaite pas que tout le code assembleur fonctionne ainsi.