Wie funktioniert eine stackless Sprache?

StackOverflow https://stackoverflow.com/questions/1016218

Frage

Ich habe von stackless Sprachen gehört. Allerdings habe ich keine Ahnung, wie eine solche Sprache umgesetzt werden würde. Kann jemand erklären?

War es hilfreich?

Lösung

Die modernen Betriebssystemen haben wir (Windows, Linux) arbeiten mit dem, was ich die „Big Stack Modell“ nennen. Und das Modell ist falsch, manchmal, und motiviert die Notwendigkeit für „stackless“ Sprachen.

Das „große Stapelmodell“ werden davon ausgegangen, dass ein kompiliertes Programm „Stack-Frames“ zuteilen für die Funktion in einem zusammenhängenden Bereich des Speichers aufruft, Maschinenbefehlen unter Verwendung von Registern einzustellen, um den Stapelzeiger (und optional Stapelrahmenzeiger) sehr schnell enthalten. Dies führt zu einem schnellen Funktionsaufruf / Rückkehr, um den Preis für den Stapel über einen großen, zusammenhängenden Bereich. Da 99,99% aller unter diesem modernen OSes liefen Programme funktioniert gut mit dem großen Stapel-Modell, die Compiler, Ladern und sogar das Betriebssystem „weiß“ über diesen Stapelbereich.

Ein häufiges Problem alle solche Anwendungen ist, "Wie groß sollte mein Stack sein?" . Schmutz billig zu sein, vor allem mit dem Gedächtnis, was passiert ist, dass ein großer Teil beiseite für den Stapel (MS standardmäßig auf 1 MB) festgelegt ist, und typische Anwendungsaufrufstruktur wird nie irgendwo in der Nähe zu verwenden es auf. Aber wenn eine Anwendung tut es verwenden, um alle auf, es stirbt mit einem ungültigen Speicherverweis ( „Es tut mir leid Dave, kann ich nicht tun“), durch das Ende seines Stapels erreicht wird.

Die meisten sogenannten genannt „stackless“ Sprachen sind nicht wirklich stackless. Sie verwenden einfach nicht die angrenzenden Stapel von diesen Systemen zur Verfügung gestellt. Was sie tun, ist stattdessen einen Stack-Frame aus dem Heap auf jedem Funktionsaufruf zuordnen. Die Kosten pro Funktionsaufruf nach oben geht etwas; wenn Funktionen in der Regel komplex sind, oder die Sprache ist interpretierende, diese zusätzlichen Kosten sind unbedeutend. (Man kann auch Anruf DAGs im Programmaufrufgraphen bestimmen und ein Heap-Segment zuteilen die gesamte DAG zu decken; diese Weise können Sie sowohl Heapzuordnung und die Geschwindigkeit der klassischen Big-Stack-Funktion ruft für alle Anrufe innerhalb des Anrufs DAG bekommen) <. / p>

Es gibt mehrere Gründe für die Verwendung von Heapzuordnung für Stapelrahmen:

1) Wenn das Programm funktioniert tiefere Rekursion abhängig von dem spezifischen Problem ist zu lösen, es ist sehr schwer, einen „großer Stapel“ -Bereich im Voraus preallocate weil die benötigte Größe nicht bekannt ist. Man kann ungeschickt anordnen Funktion um zu überprüfen, ruft, wenn es genug Stapel gelassen, und wenn nicht, umverteilen einen größeren Teil, kopieren Sie den alten Stapel und nachjustieren alle Zeiger in den Stapel; das ist so peinlich, dass ich weiß nicht von irgendwelchen Implementierungen. Zuteilen Stapelrahmen bedeutet, die Anwendung hat nie seine leider zu sagen, bis es wahrsten Sinne des Wortes nicht zuweisbaren Speicher links.

2) Die Programm Gabeln Unteraufgaben. Jede Teilaufgabe benötigt einen eigenen Stapel, und daher nicht den einen „großen Stapel“ versehen können. Deshalb braucht man Stapel für jede Teilaufgabe zuzuordnen. Wenn Sie Tausende von möglichen Teilaufgaben haben, müssen Sie jetzt Tausende von „Big Stacks“ und der Speicherbedarf wird plötzlich lächerlich. Stapelrahmen Zuteilen löst dieses Problem. Oft ist die Teilaufgabe „Stacks“, um die übergeordneten Aufgaben verweisen lexikalisches Scoping umzusetzen; als Unteraufgaben Gabel wird ein Baum von „Teilstapel“ genannt erstellt ein „Kaktus-Stack“.

3) Ihre Sprache hat Fortsetzungen. Diese erfordern, dass die Daten in lexikalischen Gültigkeitsbereich sichtbar für die aktuelle Funktion irgendwie für eine spätere Wiederverwendung aufbewahrt werden. Dies kann durch das Kopieren von Eltern Stapelrahmen implementiert werden, den Kaktus-Stack hinauf, und fortfahren.

Die PARLANSE Programmierung implementiert Langauge I tut 1) und 2). Ich arbeite an 3).

Andere Tipps

Stackless Python hat noch einen Python-Stack (obwohl es Endaufruf Optimierung und andere Aufrufrahmen haben Tricks verschmelzenden ), aber es aus dem C-Stack des Interpreters vollständig geschieden wird.

Haskell (wie allgemein implementiert) kein Call-Stack; Bewertung basiert auf Graphenreduktion .

Es gibt einen schönen Artikel über den Sprachrahmen Parrot unter http: // www .Linux-mag.com / cache / 7373 / 1.html . Parrot nicht den Stapel für den Aufruf und in diesem Artikel erläutert die Technik ein wenig.

In der stackless Umgebungen Ich bin mehr oder weniger vertraut mit (Turing-Maschine, Montag und Brainfuck) ist es üblich, Ihren eigenen Stack zu implementieren. Es gibt nichts Grundlegendes über einen Stapel in die Sprache eingebaut haben.

In den meisten praktischen davon, Montage, Sie wählen nur einen Speicherbereich zur Verfügung, stellen Sie das Stack-Register auf den Boden zu zeigen, dann erhöhen oder verringern Ihre Schübe und Knacken zu implementieren.

EDIT: Ich weiß, dass einige Architekturen gewidmet Stacks haben, aber sie sind nicht erforderlich

.

Es gibt eine einfache Beschreibung von Fortsetzungen zu diesem Artikel verstehen: http: // www. defmacro.org/ramblings/fp.html

Fortsetzungen sind etwas, das Sie in eine Funktion in einer Stack-basierten Sprache passieren können, die aber auch durch eine Sprache der eigenen Semantik verwendet werden, um es zu machen „Stackless“. Natürlich ist der Stapel immer noch da, aber wie Ira Baxter beschrieben, es ist nicht ein großes zusammenhängendes Segment.

Sagen Sie bitte stackless C. Das erste, was realisieren wollen, ist zu erkennen, dass dies nicht einen Stapel benötigt: 

a == b

Aber, tut das? 

isequal(a, b) { return a == b; }

Nein. Da ein Smart-Compiler Anrufe Inline wird isequal, sie in a == b drehen. Also, warum nicht einfach alles Inline? Klar, werden Sie mehr Code generieren, aber wenn der Stapel loszuwerden ist es wert zu Ihnen, dann ist dies einfach mit einem kleinen Kompromiss.

Was ist Rekursion? Kein Problem. Eine Schwanz-rekursive Funktion wie: 

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

noch inlined werden kann, weil wirklich ein, es ist nur für Schleife in der Verkleidung: 

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

In der Theorie ein wirklich intelligenter Compiler könnte das für Sie herausfinden. Aber ein weniger intelligent man noch es als goto abflachen könnte: 

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

Es gibt einen Fall, in dem man aus einen kleinen Handel zu machen. Dies kann nicht inline sein: 

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

Stackless C einfach kann dies nicht tun. Geben Sie eine Menge auf? Nicht wirklich. Das ist etwas, normale C nicht sehr gut entweder tun. Wenn Sie glauben mir nicht nur fib(1000) anrufen und sehen, was auf Ihre wertvollen Computer passiert.

Rufen Sie mich an alte, aber ich kann mich erinnern, wenn die Fortran-Standards und COBOL nicht rekursive Aufrufe unterstützt hat, und erfordern daher nicht einen Stapel. Tatsächlich erinnere ich mich an die Implementierungen für CDC 6000-Serie Maschinen, bei denen es keine Stapel war, und Fortran würde seltsame Dinge tun, wenn Sie versucht rekursiv ein Unterprogramm aufrufen.

Für die Aufzeichnung anstelle eines Call-Stack, der CDC 6000 Serie Befehlssatz der RJ-Befehl verwendet, um ein Unterprogramm aufzurufen. Das sparte die aktuelle PC-Wert auf den Ruf Zielort und verzweigt sich dann an die Stelle danach. Am Ende würde ein Unterprogramm einen indirekten Sprung zum Aufruf Zielort durchführen. Das neu geladen gespeichert PC, effektiv an den Anrufer zurück.

Offensichtlich ist, dass das nicht mit rekursiven Aufrufen arbeiten. (Und meine Erinnerung ist, dass die CDC Fortran IV Compiler gebrochen Code erzeugen würden, wenn Sie versuchen, Rekursion tun ...)

Bitte fühlen Sie sich frei, mich zu korrigieren, wenn ich falsch, aber ich würde denken, dass für jeden Funktionsaufruf Rahmen würde dazu führen, Dreschen extreme Speicher auf dem Heap-Speicher zugewiesen wird. Das Betriebssystem hat nach all diesen Speicher zu verwalten. Ich würde denken, dass die Art und Weise, diesen Speicher Abreibung zu vermeiden, wäre ein Cache für Call-Frames sein. Also, wenn Sie einen Cache sowieso benötigen, können wir auch machen es contigous im Speicher und nennen es einen Stapel.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top