Was sind die Alternativen zur Verwendung eines Stacks zur Darstellung der Funktionsaufrufsemantik?

19

Wir alle wissen und lieben, dass Funktionsaufrufe normalerweise über den Stack implementiert werden. Es gibt Frames, Absenderadressen, Parameter, das ganze Los.

Der Stack ist jedoch ein Implementierungsdetail: Aufrufkonventionen können verschiedene Aufgaben ausführen (dh x86-Fastcall verwendet (einige) Register, MIPS und Follower verwenden Registerfenster usw.) und Optimierungen können sogar andere Aufgaben ausführen (Inlining, Auslassen von Frame-Zeigern, Tail-Call-Optimierung ..).

Sicher, das Vorhandensein von praktischen Stapelanweisungen auf vielen Maschinen (VMs wie JVM und CLR, aber auch echte Maschinen wie x86 mit PUSH / POP usw.) macht es bequem, sie für Funktionsaufrufe zu verwenden, aber in einigen Fällen ist es möglich auf eine Art und Weise zu programmieren, in der ein Call-Stack nicht benötigt wird (ich denke hier an Continuation Passing Style oder Akteure in einem Message-Passing-System)

Also begann ich mich zu fragen: Ist es möglich, Funktionsaufrufsemantik ohne Stapel oder besser mit einer anderen Datenstruktur (vielleicht einer Warteschlange oder einer assoziativen Karte?) Zu implementieren?
Natürlich verstehe ich, dass ein Stapel sehr wichtig ist Praktisch (es gibt einen Grund, warum es allgegenwärtig ist), aber ich bin kürzlich auf eine Implementierung gestoßen, die mich zum Staunen gebracht hat.

Weiß jemand von euch, ob es jemals in einer Sprache / Maschine / virtuellen Maschine gemacht wurde, und wenn ja, was sind die auffälligen Unterschiede und Mängel?

EDIT: Mein Bauchgefühl ist, dass verschiedene Teilberechnungsansätze unterschiedliche Datenstrukturen verwenden können. Zum Beispiel ist die Lambda-Berechnung nicht stapelbasiert (die Idee der Funktionsanwendung wird durch Reduzierungen erfasst), aber ich habe mir eine reale Sprache / Maschine / ein reales Beispiel angesehen. Deshalb frage ich ...

Lorenzo Dematté
quelle
Clean verwendet einen Graph und einen Graph-Rewrite-Rechner, der wiederum mit einem Drei-Stapel-Rechner implementiert wird, jedoch mit einem anderen Inhalt als gewöhnlich.
Für virtuelle Maschinen kann eine verknüpfte Liste verwendet werden. Jeder Knoten der Liste ist ein Rahmen. Da der Hardware-Stack von der VM verwendet wird, können Frames auf dem Heap ohne den Overhead von vorhanden sein realloc().
Shawnhcorey

Antworten:

19

Je nach Sprache ist es möglicherweise nicht erforderlich, einen Aufrufstapel zu verwenden. Aufrufstapel sind nur in Sprachen erforderlich, die eine Rekursion oder eine gegenseitige Rekursion ermöglichen. Wenn die Sprache keine Rekursion zulässt, kann zu jedem Zeitpunkt nur ein Aufruf einer Prozedur aktiv sein, und lokale Variablen für diese Prozedur können statisch zugeordnet werden. Solche Sprachen müssen zwar für Kontextänderungen, für die Interrupt-Behandlung sorgen, benötigen aber noch keinen Stack.

In FORTRAN IV (und früheren Versionen) und früheren Versionen von COBOL finden Sie Beispiele für Sprachen, für die keine Aufrufstapel erforderlich sind.

In Control Data 6600 (und früheren Control Data-Computern) finden Sie ein Beispiel für einen sehr erfolgreichen frühen Supercomputer, der keine direkte Hardwareunterstützung für Aufrufstapel bot. Auf dem PDP-8 finden Sie ein Beispiel für einen sehr erfolgreichen frühen Minicomputer, der keine Rufstapel unterstützt.

Soweit ich weiß, waren die Burroughs B5000-Stapelmaschinen die ersten Maschinen mit Hardware-Aufrufstapeln. Die B5000-Maschinen wurden von Grund auf für die Ausführung von ALGOL entwickelt, für die eine Rekursion erforderlich war. Sie verfügten auch über eine der ersten deskriptorbasierten Architekturen, die die Grundlage für Fähigkeitsarchitekturen bildeten.

Soweit ich weiß, war es der PDP-6 (der in den DEC-10 überging), der Call-Stack-Hardware populär machte, als die Hacker-Community am MIT einen davon entgegennahm und feststellte, dass der PUSHJ-Vorgang (Push Return Address and Jump) durchgeführt wurde erlaubte es, die Dezimal-Druckroutine von 50 Anweisungen auf 10 zu reduzieren.

Die grundlegendste Funktionsaufrufsemantik in einer Sprache, die eine Rekursion ermöglicht, erfordert Funktionen, die gut zu einem Stapel passen. Wenn das alles ist, was Sie brauchen, dann ist ein Basisstapel eine gute, einfache Übereinstimmung. Wenn Sie mehr benötigen, muss Ihre Datenstruktur mehr leisten.

Das beste Beispiel dafür, dass ich mehr brauche, als ich je erlebt habe, ist die "Fortsetzung", die Fähigkeit, eine Berechnung in der Mitte auszusetzen, sie als gefrorene Staatsblase zu speichern und sie später, möglicherweise mehrmals, wieder abzufeuern. Fortsetzungen wurden im Scheme-Dialekt von LISP populär, um unter anderem Fehler-Exits zu implementieren. Fortsetzungen erfordern die Fähigkeit, die aktuelle Ausführungsumgebung zu erfassen und später zu reproduzieren, und ein Stapel ist dafür etwas unpraktisch.

Abelson & Sussmans "Struktur und Interpretation von Computerprogrammen" geht auf Fortsetzungen ein.

John R. Strohm
quelle
2
Das war eine großartige historische Einsicht, danke! Als ich meine Frage stellte, dachte ich tatsächlich an Fortsetzungen, insbesondere an den Continuation-Passing-Style (CPS). In diesem Fall ist ein Stack nicht nur unpraktisch, sondern wahrscheinlich auch nicht erforderlich: Sie müssen sich nicht merken, wohin Sie zurückkehren möchten, sondern einen Punkt angeben, an dem Sie mit der Ausführung fortfahren können. Ich fragte mich, ob andere stapellose Ansätze üblich waren, und Sie gaben einige sehr gute, die mir nicht bekannt waren.
Lorenzo Dematté
Ein wenig verwandt: Sie haben richtig darauf hingewiesen, "wenn die Sprache keine Rekursion zulässt". Was ist mit Sprache mit Rekursion, insbesondere Funktionen, die nicht rekursiv sind? Brauchen sie einen Stack "by Design"?
Lorenzo Dematté
"Aufrufstapel sind nur in Sprachen erforderlich, die eine Rekursion oder eine gegenseitige Rekursion ermöglichen" - Nr. Wenn eine Funktion von mehr als einer Stelle aus aufgerufen werden kann (z. B. von beiden foound barkann aufgerufen werden baz), muss die Funktion wissen, wohin sie zurückkehren soll. Wenn Sie diese Informationen verschachteln, erhalten Sie einen Stapel. Es spielt keine Rolle, wie Sie es nennen, oder ob es von der CPU-Hardware oder von etwas unterstützt wird, das Sie in der Software emulieren (oder auch wenn es sich um eine verknüpfte Liste statisch zugewiesener Einträge handelt), es ist immer noch ein Stapel.
Brendan
@Brendan nicht unbedingt (zumindest ist das der ganze Zweck meiner Frage). "Wohin zurück" oder besser "wohin als nächstes" muss es ein Stack sein, dh eine LIFO-Struktur? Könnte es ein Baum, eine Karte, eine Schlange oder etwas anderes sein?
Lorenzo Dematté
Mein Bauchgefühl ist zum Beispiel, dass CPS nur einen Baum braucht, aber ich bin mir nicht sicher und weiß auch nicht, wohin ich schauen soll. Deshalb
frage
6

Es ist nicht möglich, eine Funktionsaufrufsemantik zu implementieren, ohne einen Stapel zu verwenden. Es können nur Wortspiele gespielt werden (z. B. mit einem anderen Namen wie "FILO return buffer").

Es ist möglich, etwas zu verwenden, das keine Funktionsaufrufsemantik implementiert (z. B. Continuation-Passing-Stil, Akteure), und dann darüber Funktionsaufrufsemantik zu erstellen. Dies bedeutet jedoch, dass eine Art Datenstruktur hinzugefügt wird, um zu verfolgen, an welche Stelle die Steuerung übergeben wird, wenn die Funktion zurückkehrt, und dass diese Datenstruktur eine Art Stapel (oder ein Stapel mit einem anderen Namen / einer anderen Beschreibung) ist.

Stellen Sie sich vor, Sie haben viele Funktionen, die sich alle gegenseitig aufrufen können. Zur Laufzeit muss jede Funktion wissen, wohin sie beim Beenden der Funktion zurückkehren muss. Bei firstAnrufen secondhaben Sie:

second returns to somewhere in first

Wenn Sie dann secondAnrufe thirdhaben:

third returns to somewhere in second
second returns to somewhere in first

Wenn Sie dann thirdAnrufe fourthhaben:

fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first

Wenn jede Funktion aufgerufen wird, müssen mehr Informationen zum "Zurückgeben" irgendwo gespeichert werden.

Wenn eine Funktion zurückgegeben wird, werden die Informationen zum Zurückgeben verwendet und nicht mehr benötigt. Wenn Sie zum Beispiel zu einem Ort fourthzurückkehren, an dem Sie sich befinden, thirdwird die Menge der Informationen, zu denen Sie zurückkehren möchten, wie folgt:

third returns to somewhere in second
second returns to somewhere in first

Grundsätzlich gilt; "Funktionsaufrufsemantik" impliziert Folgendes:

  • Sie müssen Informationen darüber haben, wohin Sie zurückkehren können
  • Die Informationsmenge wächst, wenn Funktionen aufgerufen werden, und verringert sich, wenn Funktionen zurückkehren
  • Der erste Teil der gespeicherten "Rückgabeort" -Information ist der letzte Teil der verworfenen "Rückgabeort" -Information

Dies beschreibt einen FILO / LIFO-Puffer oder einen Stapel.

Wenn Sie versuchen, einen Baumtyp zu verwenden, hat jeder Knoten im Baum nie mehr als ein untergeordnetes Element. Hinweis: Ein Knoten mit mehreren untergeordneten Knoten kann nur dann auftreten, wenn eine Funktion zwei oder mehr Funktionen gleichzeitig aufruft. Dies erfordert eine gewisse Parallelität (z. B. Threads, Fork () usw.) und wäre keine "Funktionsaufrufsemantik". Wenn jeder Knoten in der Baumstruktur niemals mehr als ein Kind haben wird; dann würde dieser "Baum" nur als ein FILO / LIFO-Puffer oder ein Stapel verwendet werden; und weil es nur als FILO / LIFO-Puffer oder Stapel verwendet wird, kann man mit Recht behaupten, dass der "Baum" ein Stapel ist (und der einzige Unterschied sind Wortspiele und / oder Implementierungsdetails).

Dasselbe gilt für jede andere Datenstruktur, die möglicherweise zur Implementierung der "Funktionsaufrufsemantik" verwendet wird. Sie wird als Stapel verwendet (und der einzige Unterschied besteht in Wortspielen und / oder Implementierungsdetails). es sei denn, es unterbricht die "Funktionsaufrufsemantik". Hinweis: Wenn möglich, würde ich Beispiele für andere Datenstrukturen bereitstellen, mir fällt jedoch keine andere Struktur ein, die leicht plausibel ist.

Natürlich ist die Implementierung eines Stacks ein Implementierungsdetail. Dies kann ein Speicherbereich sein (in dem Sie den Überblick über einen "aktuellen Stapel" behalten), eine Art verknüpfte Liste (in dem Sie den Überblick über einen "aktuellen Eintrag in der Liste" behalten) oder eine Implementierung in einigen andere Weise. Es spielt auch keine Rolle, ob die Hardware eine integrierte Unterstützung hat oder nicht.

Anmerkung: Wenn zu einem Zeitpunkt nur ein Aufruf einer Prozedur aktiv sein darf. Anschließend können Sie statisch Speicherplatz für Informationen zum Zurückkehren zuweisen. Dies ist immer noch ein Stapel (z. B. eine verknüpfte Liste von statisch zugewiesenen Einträgen, die auf FILO / LIFO-Weise verwendet werden).

Beachten Sie auch, dass es einige Dinge gibt, die nicht der "Funktionsaufrufsemantik" folgen. Zu diesen Dingen gehören "möglicherweise sehr unterschiedliche Semantiken" (z. B. Continuation Passing, Actor Model); und enthält auch allgemeine Erweiterungen für "Funktionsaufrufsemantik" wie Parallelität (Threads, Fasern, was auch immer), setjmp/ longjmp, Ausnahmebehandlung usw.

Brendan
quelle
Ein Stack ist per Definition eine LIFO-Sammlung: Last in, first out. Eine Warteschlange ist eine FIFO-Sammlung.
John R. Strohm
Ist ein Stack also die einzig akzeptable Datenstruktur? Wenn ja warum?
Lorenzo Dematté
@ JohnR.Strohm: Behoben :-)
Brendan
1
Für Sprachen ohne Rekursion (direkt oder mutal) ist es möglich, für jede Methode eine Variable statisch zuzuweisen, die den Ort identifiziert, von dem aus diese Methode zuletzt aufgerufen wurde. Wenn der Linker sich solcher Dinge bewusst ist, kann er solche Variablen auf eine Weise zuordnen, die nicht schlechter ist als die, die ein Stack tun würde, wenn jeder statisch mögliche Ausführungspfad tatsächlich genommen würde .
Supercat
4

Die Spielzeug-Verkettungssprache XY verwendet eine Anrufwarteschlange und einen Datenstapel zur Ausführung.

Bei jedem Berechnungsschritt wird lediglich das nächste auszuführende Wort dekomprimiert. Bei integrierten Funktionen werden der Datenstapel und die Aufrufwarteschlange als Argumente durch die interne Funktion oder mit Benutzerdefinitionen an den Anfang der Warteschlange verschoben.

Wenn wir also eine Funktion zum Verdoppeln des obersten Elements haben:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Dann funktioniert das Komponieren +und duphat die folgenden Stack- / Queue-Typ-Signaturen:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

Und paradoxerweise doublesieht das so aus:

double [X Y] -> [X dup^+^Y]

In gewissem Sinne ist XY also stapellos.

Karl Damgaard Asmussen
quelle
Wow, danke! Ich werde das untersuchen ... nicht sicher, ob es wirklich für Funktionsaufrufe gilt, aber einen Blick wert
Lorenzo Dematté
1
@ Karl Damgaard Asmussen "die Wörter, aus denen er besteht, in die vorderste Reihe schieben" "die vorderste Reihe schieben" Ist das nicht ein Stapel?
@ guesttttttt222222222 nicht wirklich. Ein Callstack speichert Return-Zeiger, und wenn die Funktion zurückkehrt, wird der Callstack gepoppt. In der Ausführungswarteschlange werden nur Zeiger auf Funktionen gespeichert. Wenn die nächste Funktion ausgeführt wird, wird sie auf ihre Definition erweitert und an den Anfang der Warteschlange verschoben. In XY ist die Ausführungswarteschlange tatsächlich eine Warteschlange, da es Vorgänge gibt, die auch auf der Rückseite der Ausführungswarteschlange funktionieren.
Karl Damgaard Asmussen