Die Idee einer Subroutine wurde ausgearbeitet, nachdem Rechenmaschinen bereits seit einiger Zeit existierten.Die arithmetischen und bedingten Sprunganweisungen wurden im Voraus geplant und haben sich relativ wenig geändert, aber die speziellen Anweisungen für Prozeduraufrufe haben sich im Laufe der Jahre stark geändert.Die frühesten Computer und Mikroprozessoren, wie der Manchester Baby und der RCA 1802, hatten keinen einzigen Unterprogrammaufrufbefehl.Unterprogramme könnten implementiert werden, aber Programmierer mussten die Aufrufsequenz — eine Reihe von Anweisungen — an jeder Aufrufstelle verwenden.

Unterprogramme wurden 1945 in Konrad Zuses Z4 implementiert.Im Jahr 1945 verwendete Alan M. Turing die Begriffe „bury“ und „unbury“ als Mittel zum Aufrufen und Zurückkehren von Unterprogrammen.Im Januar 1947 präsentierte John Mauchly allgemeine Anmerkungen auf einem Symposium über digitale Rechenmaschinen in großem Maßstab unter der gemeinsamen Schirmherrschaft der Harvard University und des Bureau of Ordnance der United States Navy. Hier diskutiert er den seriellen und parallelen Betrieb.

…der Aufbau der Maschine muss kein bisschen kompliziert sein. Da alle für diese Vorgehensweise wesentlichen logischen Merkmale zur Verfügung stehen, ist es möglich, einen Codierbefehl zur Platzierung der Unterprogramme im Speicher an der Maschine bekannten Stellen so weiterzuentwickeln, daß sie leicht in Gebrauch genommen werden können.

Mit anderen Worten, man kann das Unterprogramm A als Division und das Unterprogramm B als komplexe Multiplikation und das Unterprogramm C als Auswertung eines Standardfehlers einer Zahlenfolge usw. durch die Liste der Unterprogramme bezeichnen, die für ein bestimmtes Problem benötigt werden. … Alle diese Unterprogramme werden dann in der Maschine gespeichert, und alles, was man tun muss, ist einen kurzen Verweis auf sie nach Nummer zu machen, wie sie in der Codierung angegeben sind.

Kay McNulty hatte eng mit John Mauchly im ENIAC-Team zusammengearbeitet und eine Idee für Subroutinen für den ENIAC-Computer entwickelt, den sie während des Zweiten Weltkriegs programmierte. Sie und die anderen ENIAC-Programmierer verwendeten die Subroutinen, um die Flugbahn von Raketen zu berechnen.Goldstine und von Neumann schrieben ein Papier vom 16.August 1948 über die Verwendung von Subroutinen.Einige sehr frühe Computer und Mikroprozessoren, wie der IBM 1620, der Intel 4004 und der Intel 8008 sowie die PIC-Mikrocontroller, verfügen über einen Unterprogrammaufruf mit einer Anweisung, der einen dedizierten Hardwarestapel zum Speichern von Absenderadressen verwendet — solche Hardware unterstützt nur wenige Ebenen der Unterprogrammverschachtelung, kann jedoch rekursive Unterprogramme unterstützen. Maschinen vor Mitte der 1960er Jahre – wie der UNIVAC I, der PDP—1 und der IBM 1130 – verwenden typischerweise eine Aufrufkonvention, die den Anweisungszähler im ersten Speicherort des aufgerufenen Unterprogramms speichert. Dies ermöglicht beliebig tiefe Ebenen der Unterprogrammverschachtelung, unterstützt jedoch keine rekursiven Unterprogramme. Der PDP-11 (1970) ist einer der ersten Computer mit einer Stack-Pushing-Unterprogrammaufrufanweisung; Diese Funktion unterstützt sowohl eine beliebig tiefe Unterprogrammverschachtelung als auch rekursive Unterprogramme.

Sprachunterstützungedit

In den sehr frühen Assemblern war die Unterstützung von Unterprogrammen begrenzt. Unterprogramme wurden nicht explizit voneinander oder vom Hauptprogramm getrennt, und tatsächlich konnte der Quellcode eines Unterprogramms mit dem anderer Unterprogramme durchsetzt werden. Einige Assembler würden vordefinierte Makros anbieten, um die Aufruf- und Rückgabesequenzen zu generieren. In den 1960er Jahren hatten Assembler normalerweise eine viel ausgefeiltere Unterstützung für Inline- und separat montierte Unterprogramme, die miteinander verknüpft werden konnten.

Subroutine librariesEdit

Selbst mit diesem umständlichen Ansatz erwiesen sich Subroutinen als sehr nützlich. Zum einen erlaubten sie die Verwendung desselben Codes in vielen verschiedenen Programmen. Darüber hinaus war Speicher auf frühen Computern eine sehr knappe Ressource, und Unterprogramme ermöglichten erhebliche Einsparungen bei der Größe von Programmen.

Viele frühe Computer luden die Programmanweisungen von einem gestanzten Papierband in den Speicher. Jedes Unterprogramm könnte dann durch ein separates Stück Band bereitgestellt werden, das vor oder nach dem Hauptprogramm (oder „Mainline“) geladen oder gespleißt wird; und dasselbe Unterprogrammband könnte dann von vielen verschiedenen Programmen verwendet werden. Ein ähnlicher Ansatz wurde in Computern angewendet, die Lochkarten für ihre Haupteingabe verwendeten. Der Name Subroutine Library bedeutete ursprünglich eine Bibliothek, im wörtlichen Sinne, die indizierte Sammlungen von Bändern oder Kartendecks für den kollektiven Gebrauch aufbewahrte.

Return by indirect jumpEdit

Um selbstmodifizierenden Code überflüssig zu machen, stellten Computerdesigner schließlich einen indirekten Sprungbefehl bereit, dessen Operand nicht die Rücksprungadresse selbst war, sondern der Speicherort einer Variablen oder eines Prozessorregisters, das die Rücksprungadresse enthielt.

Auf diesen Computern würde das aufrufende Programm, anstatt den Rücksprung des Unterprogramms zu ändern, die Rücksprungadresse in einer Variablen speichern, so dass es nach Abschluss des Unterprogramms einen indirekten Sprung ausführen würde, der die Ausführung an den von der vordefinierten Variablen angegebenen Ort leitet.

Jump to subroutineEdit

Ein weiterer Fortschritt war der Befehl jump to subroutine, der das Speichern der Rücksprungadresse mit dem aufrufenden Sprung kombinierte, wodurch der Overhead erheblich minimiert wurde.In dem IBM System/360 würden beispielsweise die Verzweigungsanweisungen BAL oder BALR, die für den Prozeduraufruf ausgelegt sind, die Rücksprungadresse in einem in der Anweisung angegebenen Prozessorregister durch das Konventionsregister 14 speichern. Um zurückzukehren, musste das Unterprogramm nur einen indirekten Verzweigungsbefehl (BR) über dieses Register ausführen. Wenn das Unterprogramm dieses Register für einen anderen Zweck benötigt (z. B. zum Aufrufen eines anderen Unterprogramms), wird der Inhalt des Registers an einem privaten Speicherort oder in einem Registerstapel gespeichert.

In Systemen wie dem HP 2100 würde der JSB-Befehl eine ähnliche Aufgabe ausführen, außer dass die Rücksprungadresse in dem Speicherort gespeichert wurde, der das Ziel des Zweigs war. Die Ausführung der Prozedur würde tatsächlich am nächsten Speicherort beginnen. In der Assemblersprache HP 2100 würde man zum Beispiel

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

schreiben, um eine Unterroutine namens MYSUB aus dem Hauptprogramm aufzurufen. Die Subroutine würde codiert werden als

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

Die JSB-Anweisung platzierte die Adresse der NÄCHSTEN Anweisung (nämlich BB) an dem als Operand angegebenen Ort (nämlich MYSUB) und verzweigte sich dann zum NÄCHSTEN Ort danach (nämlich AA = MYSUB + 1). Die Unterroutine könnte dann zum Hauptprogramm zurückkehren, indem sie den indirekten Sprung JMP MYSUB ausführt, der zu dem unter location MYSUB gespeicherten Speicherort verzweigt.

Compiler für Fortran und andere Sprachen könnten diese Anweisungen leicht verwenden, wenn sie verfügbar sind. Dieser Ansatz unterstützte mehrere Ebenen von Aufrufen; Da jedoch der Rücksprungadresse, den Parametern und den Rückgabewerten eines Unterprogramms feste Speicherorte zugewiesen wurden, waren rekursive Aufrufe nicht zulässig.Übrigens wurde eine ähnliche Methode von Lotus 1-2-3 in den frühen 1980er Jahren verwendet, um die Neuberechnungsabhängigkeiten in einer Tabelle zu ermitteln. In jeder Zelle wurde nämlich ein Speicherort reserviert, um die Absenderadresse zu speichern. Da Zirkelverweise für die natürliche Neuberechnungsreihenfolge nicht zulässig sind, ermöglicht dies einen Baumspaziergang, ohne Speicherplatz für einen Stapel im Speicher zu reservieren, der auf kleinen Computern wie dem IBM-PC sehr begrenzt war.

Call stackEdit

Die meisten modernen Implementierungen eines Unterprogrammaufrufs verwenden einen Aufrufstapel, einen Sonderfall der Stapeldatenstruktur, um Unterprogrammaufrufe und -rückgaben zu implementieren. Jeder Prozeduraufruf erstellt oben im Stapel einen neuen Eintrag, der als Stapelrahmen bezeichnet wird; wenn die Prozedur zurückkehrt, wird ihr Stapelrahmen aus dem Stapel gelöscht, und ihr Speicherplatz kann für andere Prozeduraufrufe verwendet werden. Jeder Stapelrahmen enthält die privaten Daten des entsprechenden Aufrufs, der normalerweise die Parameter und internen Variablen der Prozedur sowie die Rücksprungadresse enthält.Die Aufrufsequenz kann durch eine Folge gewöhnlicher Anweisungen implementiert werden (ein Ansatz, der immer noch in RISC-Architekturen (Reduced Instruction Set Computing) und VLIW-Architekturen (Very Long Instruction Word) verwendet wird), aber viele traditionelle Maschinen, die seit den späten 1960 entwickelt wurden, haben spezielle Anweisungen für diesen Zweck enthalten.

Der Aufrufstapel wird normalerweise als zusammenhängender Speicherbereich implementiert. Es ist eine willkürliche Designwahl, ob der Boden des Stapels die niedrigste oder höchste Adresse in diesem Bereich ist, so dass der Stapel im Speicher vorwärts oder rückwärts wachsen kann; viele Architekturen entschieden sich jedoch für letzteres.Einige Entwürfe, insbesondere einige Forth-Implementierungen, verwendeten zwei separate Stapel, einen hauptsächlich für Steuerinformationen (wie Absenderadressen und Schleifenzähler) und den anderen für Daten. Ersteres war oder funktionierte wie ein Aufrufstapel und war für den Programmierer nur indirekt über andere Sprachkonstrukte zugänglich, während letzteres direkter zugänglich war.

Als stapelbasierte Prozeduraufrufe eingeführt wurden, war eine wichtige Motivation, wertvollen Speicher zu sparen. Bei diesem Schema muss der Compiler keinen separaten Speicherplatz für die privaten Daten (Parameter, Absenderadresse und lokale Variablen) jeder Prozedur reservieren. Der Stack enthält zu jedem Zeitpunkt nur die privaten Daten der Anrufe, die derzeit aktiv sind (dh die aufgerufen wurden, aber noch nicht zurückgegeben wurden). Aufgrund der Art und Weise, wie Programme normalerweise aus Bibliotheken zusammengestellt wurden, war (und ist) es nicht ungewöhnlich, Programme zu finden, die Tausende von Unterprogrammen enthalten, von denen zu einem bestimmten Zeitpunkt nur eine Handvoll aktiv sind. Für solche Programme könnte der Aufrufstapelmechanismus erhebliche Speichermengen einsparen. Tatsächlich kann der Aufrufstapelmechanismus als die früheste und einfachste Methode zur automatischen Speicherverwaltung angesehen werden.Ein weiterer Vorteil der Call-Stack-Methode besteht jedoch darin, dass sie rekursive Unterprogrammaufrufe ermöglicht, da jeder verschachtelte Aufruf derselben Prozedur eine separate Instanz seiner privaten Daten erhält.

Delayed stacking Edit

Ein Nachteil des Aufrufstapelmechanismus sind die erhöhten Kosten eines Prozeduraufrufs und dessen übereinstimmende Rückgabe. Die zusätzlichen Kosten umfassen das Inkrementieren und Dekrementieren des Stapelzeigers (und in einigen Architekturen das Überprüfen auf Stapelüberlauf) und den Zugriff auf die lokalen Variablen und Parameter über frame-relative Adressen anstelle von absoluten Adressen. Die Kosten können in einer erhöhten Ausführungszeit oder einer erhöhten Prozessorkomplexität oder in beidem realisiert werden.

Dieser Overhead ist am offensichtlichsten und zu beanstanden in Blattprozeduren oder Blattfunktionen, die zurückkehren, ohne selbst Prozeduraufrufe zu tätigen.Um diesen Overhead zu reduzieren, versuchen viele moderne Compiler, die Verwendung eines Aufrufstapels zu verzögern, bis er wirklich benötigt wird. Beispielsweise kann der Aufruf einer Prozedur P die Rücksprungadresse und Parameter der aufgerufenen Prozedur in bestimmten Prozessorregistern speichern und die Steuerung durch einen einfachen Sprung an den Körper der Prozedur übertragen. Wenn die Prozedur P ohne einen anderen Aufruf zurückkehrt, wird der Aufrufstapel überhaupt nicht verwendet. Wenn P eine andere Prozedur Q aufrufen muss, verwendet es den Aufrufstapel, um den Inhalt aller Register (z. B. die Rücksprungadresse) zu speichern, die nach der Rückkehr von Q benötigt werden.