Subroutinenaufrufe in der Antike: bevor Computer Stack oder Heap hatten

Subroutinenaufrufe in der Frühzeit ohne Stack und Heap

• In der modernen Datenverarbeitung gelten Stack und Heap als selbstverständlich, doch in den Anfangstagen funktionierten Computer auch ohne sie.
• Sich Computing ohne dynamische Speicherzuweisung vorzustellen, ist nicht schwer. Für alles mussten Speicherpuffer fester Größe verwendet werden.
• Mussten Daten variabler Größe verarbeitet werden, reservierte man einen ausreichend großen Puffer fester Größe, der die zu erwartenden Daten aufnehmen konnte.
• Man bot Einstellungen zur Compile-Zeit an, damit Clients die maximale Kapazität anpassen konnten, oder schrieb einen benutzerdefinierten Allokator, der Speicher aus Puffern fester Größe "zuweisen" und "freigeben" konnte.

Funktionsaufrufe ohne Stack

• Der Compiler definiert geheime globale Variablen für die eingehenden Parameter, die Rücksprungadresse und die lokalen Variablen jeder Funktion.
• Um einen Funktionsaufruf zu erzeugen, weist der Compiler die Parameterwerte diesen geheimen globalen Variablen zu, schreibt die Rücksprungadresse in die geheime "Rücksprungadress-Variable" der Funktion und springt dann an den Anfang der Funktion.
• Die Funktion liest ihre Parameter aus den geheimen globalen Variablen und verwendet vordefinierte geheime globale Variablen, die logisch den lokalen Variablen entsprechen.
• Wenn die Funktion endet, springt sie zu der Adresse, die in ihrer geheimen "Rücksprungadress-Variable" steht.

ABI-Optimierung

• Zur Optimierung des ABI werden einige Werte statt über globale Variablen in Registern übergeben.
• Die meisten Prozessoren besitzen ein "Link"-Register und einen "Branch with Link"-Befehl, der das Link-Register automatisch auf die Adresse nach dem "Branch with Link"-Befehl setzt.
• Die Calling Convention wird so optimiert, dass die ersten beiden Parameter in Registern übergeben werden.

Warum Rekursion unmöglich war

• Rekursive Aufrufe funktionieren nicht. Ein rekursiver Aufruf überschreibt die Rücksprungadress-Variable mit der Rücksprungadresse des rekursiven Aufrufs, sodass der äußere Aufruf nach Abschluss an die falsche Stelle springt.
• Programmiersprachen jener Zeit lösten dieses Problem, indem sie erklärten, dass Rekursion nicht unterstützt wird.

Bonusgespräch

• Einige Compiler arbeiteten raffinierter mit selbstmodifizierendem Code: Die spezielle Rücksprungadress-Variable ist in Wirklichkeit das Adressfeld des Sprungbefehls am Ende der Funktion.
• Falls der Prozessor keine indirekten Sprünge unterstützt, wurde diese Methode aus praktischer Notwendigkeit eingesetzt.
• Nachdem der praktische Wert von Subroutinen erkannt worden war, ergänzten viele Prozessoren Subroutinenaufrufe als Befehl, indem sie die Rücksprungadresse im ersten Wort der Subroutine speicherten und die Ausführung beim zweiten Wort der Subroutine begannen.
• Um aus der Subroutine zurückzukehren, führte man einen indirekten Sprung über das Startlabel der Subroutine aus.

Meinung von GN⁺

• Dieser Artikel hilft dabei, die Entwicklung moderner Speicherverwaltungstechniken zu verstehen, indem er erklärt, wie in der frühen Computerzeit ohne Stack und Heap programmiert wurde.
• Die Programmierweise aus der Zeit ohne Stack und Heap mag heutigen Entwicklerinnen und Entwicklern sehr fremd und ineffizient erscheinen, liefert aber wichtiges Hintergrundwissen, um zu verstehen, wie sich Technik im Lauf der Computergeschichte entwickelt hat.
• Die Einschränkungen einer Zeit, in der rekursive Aufrufe unmöglich waren, bieten Entwicklerinnen und Entwicklern, die heute rekursive Algorithmen verwenden, einen interessanten historischen Einblick.
• Aus kritischer Sicht zeigen diese frühen Programmiermethoden auch, wie stark sie darin begrenzt waren, die komplexen und vielfältigen Anforderungen der Gegenwart zu erfüllen.

[GN⁺]

Hacker-News-Kommentare

• Positive Bewertung des Buchs "The Art of Computer Programming"

  • Das Buch wirkt alt, behandelt aber verschiedene Algorithmen zum Verändern dynamischer Arrays und Datenstrukturen aus der Zeit vor Heap und Stack.
  • Das Buch erklärt auch Garbage Collection und die Implementierung von Lisp-Listen und liefert enzyklopädisches Wissen, das typisch für Knuth ist.

• Erklärung, wie zwei Arrays sich dynamisch einen Speicherbereich teilen können

  • Ein Array wächst normal ab Position #0, das andere rückwärts ab Position #End, sodass beide sich einen statisch zugewiesenen Speicher effizient teilen.
  • Diese Methode lässt sich auf mehrere Arrays erweitern, aber ab einem gewissen Punkt ist es möglicherweise besser, Malloc und Realloc zu verwenden.

• Link zu einer unterhaltsamen Geschichte darüber, dass die Einführung rekursiver Funktionen in die Sprache ALGOL umstritten war

  • Über den Link wird eine interessante Geschichte darüber geteilt, wie Rekursion in Programmiersprachen eingeführt wurde.

• Geteilte Erfahrung beim Schreiben eines Forth-Interpreters für SUBLEQ-Maschinen und bit-serielle Maschinen

  • Diese beiden Maschinen besitzen keinen Funktionsaufruf-Stack, der für Forth wesentlich ist.
  • SUBLEQ erlaubt kein indirektes Laden und Speichern und benötigt selbstmodifizierenden Code, um ungewöhnliche Aufgaben auszuführen.
  • Es wird eine virtuelle Maschine aufgebaut, um diese Funktionen bereitzustellen und kooperatives Multithreading zu unterstützen.
  • Falls nötig, wird der Heap in Forth geschrieben; außerdem sind Gleitkommaoperationen enthalten, die als Softwarefunktionen implementiert sind.

• Erklärung zur technischen Evolution von Subroutine-Aufrufen beim PDP-8-Prozessor

  • Anfangs speicherte der JMS-Befehl die Rücksprungadresse im ersten Wort der Funktion.
  • Später wurde mit Auto-Increment-Positionen ein einfacher Stack erzeugt, und Funktionsprolog/Epilog verwalteten diesen Stack manuell, wodurch vollständige Rekursion möglich wurde.
  • Noch später wurde den Mikroprozessor-Implementierungen ein Hardware-Stack hinzugefügt, um die Leistung zu verbessern.

• Ein Nutzer mit langer Erfahrung in funktionaler Programmierung teilt seine Vorliebe für Rekursion

  • Er weiß, wie sich rekursive Algorithmen in iterative Algorithmen umwandeln lassen, bevorzugt aber Rekursion.
  • In den meisten Fällen ist Rekursion schnell genug, besonders wenn der Compiler Tail Recursion unterstützt.
  • Beim Hacken von Commodore-64-Spielen versucht er zu lernen, wie früher programmiert wurde.

• Geteilte Erfahrung mit dem Entwurf eines RS232-Seriell-Multiplexers um 1991

  • Hardware-Design mit einem Z80-Prozessor, EPROM und einem Z80-SIO-Seriellgerät.
  • Da kein Stack vorhanden war, wurden Rücksprungadressen für Funktionsaufrufe vorab in Registerpaare geladen.

• Hinweis auf die frühere Situation, in der Programmierer die mögliche Verteilung der Eingaben berücksichtigen und die Größe von Zwischenspeichern passend festlegen mussten, bevor der Heap erweiterbar war

  • Dadurch entstanden "Bugs und Grenzen".

• Erklärung, dass Tail Recursion in einer Zeit möglich war, in der allgemeine Rekursion nicht verwendet werden konnte

  • Abgesehen von dem für den ersten Aufruf verwendeten branch_with_link mussten normale Sprünge verwendet werden.

• Erklärung, wie der Compiler in Enhanced GNU Awk für @let-Blöcke außerhalb von Funktionen geheime globale Variablen zuweist

  • Diese Variablen werden so weit wie möglich wiederverwendet.

• Erwähnung eines Posts, der die Welt des Papers "Goto considered harmful" beschreibt

  • Die meisten Menschen kennen nur den Titel, dabei argumentiert das Paper für einen einzelnen Eintrittspunkt bei Subroutinen.
  • Manchmal schreibt man Assembler-Code so, dass er in eine andere Subroutine hineinspringt, aber man möchte nicht, dass sämtlicher Assembler-Code so aussieht.