L’idée d’un sous-programme a été élaborée après que les machines informatiques existaient déjà depuis un certain temps.Les instructions arithmétiques et de saut conditionnel ont été planifiées à l’avance et ont relativement peu changé, mais les instructions spéciales utilisées pour les appels de procédure ont beaucoup changé au fil des ans.Les premiers ordinateurs et microprocesseurs, tels que le Manchester Baby et le RCA 1802, n’avaient pas une seule instruction d’appel de sous-programme.Des sous-programmes pouvaient être implémentés, mais ils obligeaient les programmeurs à utiliser la séquence d’appels — une série d’instructions — sur chaque site d’appel.

Des sous-programmes ont été implémentés dans le Z4 de Konrad Zuse en 1945.

En 1945, Alan M. Turing a utilisé les termes « bury » et « unbury » comme moyen d’appeler et de revenir des sous-programmes.

En janvier 1947, John Mauchly a présenté des notes générales lors d’un Symposium sur les Machines à Calculer Numériques à grande échelle sous le parrainage conjoint de l’Université Harvard et du Bureau of Ordnance de la Marine américaine. Ici, il discute du fonctionnement série et parallèle suggérant

…la structure de la machine n’a pas besoin d’être compliquée un peu. Il est possible, toutes les caractéristiques logiques essentielles à cette procédure étant disponibles, de faire évoluer une instruction de codage pour placer les sous-programmes en mémoire à des endroits connus de la machine, et de telle sorte qu’ils puissent facilement être mis en service.

En d’autres termes, on peut désigner le sous-programme A comme division et le sous-programme B comme multiplication complexe et le sous-programme C comme évaluation d’une erreur-type d’une séquence de nombres, et ainsi de suite à travers la liste des sous-programmes nécessaires pour un problème particulier. … Tous ces sous-programmes seront alors stockés dans la machine, et il suffit d’y faire une brève référence par numéro, comme ils sont indiqués dans le codage.

Kay McNulty avait travaillé en étroite collaboration avec John Mauchly au sein de l’équipe ENIAC et avait développé une idée de sous-programmes pour l’ordinateur ENIAC qu’elle programmait pendant la Seconde Guerre mondiale. Elle et les autres programmeurs ENIAC utilisaient les sous-programmes pour aider à calculer les trajectoires de missiles.

Goldstine et von Neumann ont écrit un article daté du 16 août 1948 sur l’utilisation des sous-programmes.

Certains ordinateurs et microprocesseurs très anciens, tels que IBM 1620, Intel 4004 et Intel 8008, et les microcontrôleurs PIC, ont un appel de sous-programmes à instruction unique qui utilise une pile matérielle dédiée pour stocker les adresses de retour — ce matériel ne prend en charge que quelques niveaux d’imbrication de sous-programmes, mais peut prendre en charge des sous-programmes récursifs. Les machines antérieures au milieu des années 1960 – telles que l’UNIVAC I, le PDP—1 et l’IBM 1130 – utilisent généralement une convention d’appel qui enregistre le compteur d’instructions dans le premier emplacement mémoire du sous—programme appelé. Cela permet des niveaux arbitrairement profonds d’imbrication de sous-programmes, mais ne prend pas en charge les sous-programmes récursifs. Le PDP-11 (1970) est l’un des premiers ordinateurs avec une instruction d’appel de sous-programmes de poussée de pile; cette fonctionnalité prend en charge à la fois l’imbrication de sous-programmes arbitrairement profonds et prend également en charge les sous-programmes récursifs.

Support du language

Dans les tout premiers assembleurs, le support des sous-programmes était limité. Les sous-programmes n’étaient pas explicitement séparés les uns des autres ou du programme principal, et en effet le code source d’un sous-programme pouvait être entrecoupé de celui d’autres sous-programmes. Certains assembleurs proposeraient des macros prédéfinies pour générer les séquences d’appel et de retour. Dans les années 1960, les assembleurs avaient généralement un support beaucoup plus sophistiqué pour les sous-programmes en ligne et assemblés séparément qui pouvaient être reliés entre eux.

Bibliothèques de sous-routinesedit

Même avec cette approche lourde, les sous-programmes se sont révélés très utiles. D’une part, ils permettaient l’utilisation du même code dans de nombreux programmes différents. De plus, la mémoire était une ressource très rare sur les premiers ordinateurs, et les sous-programmes permettaient des économies importantes dans la taille des programmes.

De nombreux premiers ordinateurs chargeaient les instructions du programme en mémoire à partir d’une bande de papier perforée. Chaque sous-programme pourrait alors être fourni par un morceau de bande séparé, chargé ou épissé avant ou après le programme principal (ou « ligne principale »); et la même bande de sous-programme pourrait alors être utilisée par de nombreux programmes différents. Une approche similaire s’appliquait aux ordinateurs qui utilisaient des cartes perforées pour leur entrée principale. Le nom bibliothèque de sous-programmes signifiait à l’origine une bibliothèque, au sens littéral, qui conservait des collections indexées de bandes ou de jeux de cartes à usage collectif.

Return by indirect jumpEdit

Pour supprimer le besoin de code auto-modifiant, les concepteurs informatiques ont finalement fourni une instruction de saut indirect, dont l’opérande, au lieu d’être l’adresse de retour elle-même, était l’emplacement d’une variable ou d’un registre de processeur contenant l’adresse de retour.

Sur ces ordinateurs, au lieu de modifier le saut de retour du sous-programme, le programme appelant stockerait l’adresse de retour dans une variable de sorte que lorsque le sous-programme était terminé, il exécuterait un saut indirect qui dirigerait l’exécution vers l’emplacement donné par la variable prédéfinie.

Jump to subroutineEdit

Une autre avancée était l’instruction jump to subroutine, qui combinait l’enregistrement de l’adresse de retour avec le jump appelant, réduisant ainsi considérablement les frais généraux.

Dans le système IBM/360, par example, les instructions de branche BAL ou BALR, conçues pour l’appel de procédure, enregistreraient l’adresse de retour dans un registre de processeur spécifié dans l’instruction, par le registre de convention 14. Pour revenir, le sous-programme n’avait qu’à exécuter une instruction de branche indirecte (BR) via ce registre. Si le sous-programme avait besoin de ce registre à d’autres fins (comme appeler un autre sous-programme), il enregistrerait le contenu du registre dans un emplacement de mémoire privée ou une pile de registres.

Dans des systèmes tels que le HP 2100, l’instruction JSB effectuerait une tâche similaire, sauf que l’adresse de retour était stockée dans l’emplacement mémoire qui était la cible de la branche. L’exécution de la procédure commencerait en fait à l’emplacement de mémoire suivant. Dans le langage d’assemblage HP 2100, on écrirait, par exemple

 ... JSB MYSUB (Calls subroutine MYSUB.) BB ... (Will return here after MYSUB is done.)

pour appeler un sous-programme appelé MYSUB à partir du programme principal. Le sous-programme serait codé comme

 MYSUB NOP (Storage for MYSUB's return address.) AA ... (Start of MYSUB's body.) ... JMP MYSUB,I (Returns to the calling program.)

L’instruction JSB plaçait l’adresse de l’instruction SUIVANTE (à savoir BB) à l’emplacement spécifié comme son opérande (à savoir MYSUB), puis se ramifiait à l’emplacement SUIVANT après cela (à savoir AA =MYSUB +1). Le sous-programme pourrait ensuite revenir au programme principal en exécutant le saut indirect JMP MYSUB, I qui s’est ramifié à l’emplacement stocké à l’emplacement MYSUB.

Les compilateurs pour Fortran et d’autres langages pourraient facilement utiliser ces instructions lorsqu’elles sont disponibles. Cette approche prenait en charge plusieurs niveaux d’appels ; cependant, étant donné que l’adresse de retour, les paramètres et les valeurs de retour d’un sous-programme se voyaient attribuer des emplacements de mémoire fixes, elle ne permettait pas les appels récursifs.

Incidemment, une méthode similaire a été utilisée par Lotus 1-2-3, au début des années 1980, pour découvrir les dépendances de recalcul dans une feuille de calcul. A savoir, un emplacement était réservé dans chaque cellule pour stocker l’adresse de retour. Comme les références circulaires ne sont pas autorisées pour l’ordre de recalcul naturel, cela permet une promenade dans l’arbre sans réserver d’espace pour une pile en mémoire, ce qui était très limité sur les petits ordinateurs tels que l’IBM PC.

Call stackEdit

La plupart des implémentations modernes d’un appel de sous-programme utilisent une pile d’appels, un cas particulier de la structure de données de la pile, pour implémenter des appels et des retours de sous-programme. Chaque appel de procédure crée une nouvelle entrée, appelée cadre de pile, en haut de la pile; lorsque la procédure revient, son cadre de pile est supprimé de la pile et son espace peut être utilisé pour d’autres appels de procédure. Chaque trame de pile contient les données privées de l’appel correspondant, qui incluent généralement les paramètres et les variables internes de la procédure, ainsi que l’adresse de retour.

La séquence d’appels peut être implémentée par une séquence d’instructions ordinaires (une approche encore utilisée dans les architectures RISC (reduced instruction set computing) et VLIW (very long instruction word)), mais de nombreuses machines traditionnelles conçues depuis la fin des années 1960 ont inclus des instructions spéciales à cet effet.

La pile d’appels est généralement implémentée comme une zone de mémoire contiguë. C’est un choix arbitraire de conception que le bas de la pile soit l’adresse la plus basse ou la plus élevée dans cette zone, de sorte que la pile puisse croître en avant ou en arrière en mémoire; cependant, de nombreuses architectures ont choisi ce dernier.

Certaines conceptions, notamment certaines implémentations de Forth, utilisaient deux piles distinctes, l’une principalement pour les informations de contrôle (comme les adresses de retour et les compteurs de boucles) et l’autre pour les données. Le premier était, ou fonctionnait comme une pile d’appels et n’était accessible qu’indirectement au programmeur via d’autres constructions de langage tandis que le second était plus directement accessible.

Lorsque les appels de procédure basés sur la pile ont été introduits pour la première fois, une motivation importante était d’économiser une mémoire précieuse. Avec ce schéma, le compilateur n’a pas à réserver d’espace séparé en mémoire pour les données privées (paramètres, adresse de retour et variables locales) de chaque procédure. À tout moment, la pile ne contient que les données privées des appels actuellement actifs (à savoir, qui ont été appelés mais ne sont pas encore retournés). En raison de la manière dont les programmes étaient généralement assemblés à partir de bibliothèques, il n’était (et n’est toujours) pas rare de trouver des programmes qui incluent des milliers de sous-programmes, dont seulement une poignée sont actifs à un moment donné. Pour de tels programmes, le mécanisme de pile d’appels pourrait économiser des quantités importantes de mémoire. En effet, le mécanisme de pile d’appels peut être considéré comme la méthode la plus ancienne et la plus simple de gestion automatique de la mémoire.

Cependant, un autre avantage de la méthode de pile d’appels est qu’elle permet des appels récursifs de sous-programmes, car chaque appel imbriqué à la même procédure obtient une instance distincte de ses données privées.

Modification de l’empilement différé

Un inconvénient du mécanisme de pile d’appels est le coût accru d’un appel de procédure et de son retour correspondant. Le coût supplémentaire comprend l’incrémentation et la décrémentation du pointeur de pile (et, dans certaines architectures, la vérification du débordement de pile), et l’accès aux variables et paramètres locaux par des adresses relatives à la trame, au lieu d’adresses absolues. Le coût peut être réalisé en augmentant le temps d’exécution, ou en augmentant la complexité du processeur, ou les deux.

Cette surcharge est la plus évidente et la plus répréhensible dans les procédures feuille ou les fonctions feuille, qui reviennent sans faire d’appels de procédure eux-mêmes.Pour réduire cette surcharge, de nombreux compilateurs modernes essaient de retarder l’utilisation d’une pile d’appels jusqu’à ce qu’elle soit vraiment nécessaire. Par example, l’appel d’une procédure P peut stocker l’adresse de retour et les paramètres de la procédure appelée dans certains registres de processeur, et transférer le contrôle au corps de la procédure par un simple saut. Si la procédure P retourne sans faire d’autre appel, la pile d’appels n’est pas utilisée du tout. Si P doit appeler une autre procédure Q, il utilisera alors la pile d’appels pour enregistrer le contenu de tous les registres (tels que l’adresse de retour) qui seront nécessaires après le retour de Q.