Wie kann man Theorie und Implementierung für while-Schleifen überbrücken?

8

Ich arbeite an meiner eigenen kleinen Programmiersprache für Bildungszwecke und bin auf ein kleines Problem gestoßen. Es gibt ein paar verschiedene Lösungen dafür, aber alle scheinen unelegant - und nach meinem Verständnis unnötig. Aber wenn ich die Bücher, die ich habe, und die Google-Suche durchlese, kann ich die elegante Lösung nicht finden.

Das Problem ist also, dass ich die grundlegende Lambda-Rechnung so aufbaue, wie ich sie verstehe. Ich habe wahr / falsch als Abstraktionsbegriffe definiert. Ich kann diese mit Funktionen kombinieren, um zu tun, ob / dann / sonst Verhalten. Das Problem kommt mit Schleifen. Ich kann eine grundlegende while-Schleife durch Rekursion definieren, aber in der Praxis führt dies zu einem Stapelüberlauf. Nach meinem Verständnis besteht die übliche Lösung darin, die Tail Call-Optimierung durchzuführen, aber ich sehe nicht, wie ich das kann - Bedingungen werden in der Sprache definiert. Aus diesem Grund weiß der Compiler nicht , dass sich der Körper der while-Schleife in der Endposition befindet.

Das Drachenbuch konzentriert sich auf die Implementierung der Schleife, vorausgesetzt, es gibt Labels und Gotos. Das könnte ich sicher tun. Es sieht so aus, als ob andere Sprachen, die keine Schleifenkonstrukte enthalten, zumindest Bedingungen einbauen und dann TCO ausführen. Und das könnte ich natürlich auch. Mein Verständnis ist jedoch, dass, solange ich Abstraktionen anwenden und Reduktionen durchführen kann, Schleifen (und alles andere) aus diesen Grundblöcken erstellt werden können sollten.

Also, was vermisse ich? Oder ist dies einer der Fälle, in denen "Sie können alles modellieren, wenn Sie X und Y haben" nicht dasselbe ist wie "Sie können alles modellieren, wenn Sie X und Y auf einem echten Computer haben" und integrierte Funktionen für die Praxis erforderlich sind Zwecke?

Telastyn
quelle
Ich denke, Sie haben in diesem letzten Absatz Ihre eigene Frage beantwortet. Nur weil die Theorie besagt, dass man etwas tun kann, heißt das nicht, dass es praktisch ist, es zu tun.
Svick
1
Viele Sprachen haben Bedingungen und Rekursionen und implementieren die Tail-Call-Optimierung. Suche jenseits des Drachenbuchs.
Dave Clarke
Lassen Sie mich das klarstellen : Sie gehen von reinem Kalkül aus? Das heißt, es hat nichts als λ und Abstraktionen? λλ
Andrej Bauer
svick - sicher, aber als Lernender kann ich nicht sagen, ob dies hier der Fall ist oder ob ich etwas nicht weiß. Dave Clarke - Viele Sprachen haben Bedingungen eingebaut und implementieren die Tail-Call-Optimierung. Ich habe getan , Durchsuchung und ergebnislos für in-Sprache bedingten und TCO. Wenn Sie eine Referenz haben, die ich übersehen habe ... Andrej Bauer - nicht ganz, aber nah genug. Keine eingebauten Typen, keine eingebauten Funktionen. Sie können Funktionen deklarieren und Funktionen anwenden. Eine eingehende Betrachtung meiner besonderen Situation würde zu einer schlechten Frage führen.
Telastyn
1
@Raphael In den 1970er und 1980er Jahren war es eine große Sache, Lambda-Kalkül als Zwischensprache zu verwenden. Ich glaube, die Absicht war es, semantische Optimierungen zu erkennen. Mein Verständnis (Vorsicht, ich bin kein Experte für Kompilierungstechniken) ist, dass semantische Optimierungen wirklich schwierig sind, während lokale Optimierungen viel kosten können und in einer Sprache mit Registerzuweisungen und moderater Verwendung von goto leichter zu erkennen sind. Nichtsdestotrotz sind Ideen aus der Lambda-Rechnung für das Compiler-Design relevant, zum Beispiel die Idee der Einzelzuweisung und das Konzept der Fortsetzung.
Gilles 'SO - hör auf böse zu sein'

Antworten:

5

Also habe ich es heute geschafft, dieses Problem zu lösen. Der Code für meine while-Schleife:

while (condition: ~>bool) (body: ~>void) => void {
    if condition { 
        body; 
        while condition body; 
    };
}

Wenn ich dies in CIL einbaue (eine stapelbasierte Laufzeit, wichtig für den Pseudocode, nicht wichtig für die Antwort), sieht es so aus:

ldarg 0
<build closure from { body; while condition body; }>
call if

Das Wichtige, was mir gefehlt hat, ist, dass im whileCode die Bedingung das Ding in der Schwanzposition war. Aus Sicht des Compilers sind der Block und die while-Funktion zwei separate Funktionen mit zwei separaten "Tails". Jedes von diesen kann leicht auf seine Heckposition hin bewertet werden, wodurch die Optimierung trotz des Fehlens integrierter Bedingungen realisierbar ist.

Telastyn
quelle
5

Ich denke, Sie vermissen den Begriff der Fortsetzung . Obwohl sich Ihr Compiler möglicherweise nicht auf diesen Begriff verlässt, ist es als Compiler-Designer mit einer funktionalen Sprache als Quell- oder Zwischen- (oder Ziel-) Sprache wichtig, diesen Begriff zu verstehen und dies zu berücksichtigen.

Die Fortsetzung eines Codeteils beschreibt, worauf der Code hinausläuft. Imperativ ausgedrückt verkörpert es nicht nur den Ort, an den der Code springt oder fällt, sondern auch den Programmstatus (Stapel und Heap) an diesem Punkt. In der Lambda-Rechnung ist die Fortsetzung eines Subterms der Kontext, in dem es bewertet wird.

Wenn Sie imperativen Code in eine funktionale Sprache übersetzen, besteht eine der Schwierigkeiten darin, mit Code umzugehen, der auf verschiedene Arten beendet werden kann. Beispielsweise kann Code eine Ausnahme zurückgeben oder auslösen. Oder der Körper einer Schleife kann entweder die Bedingung erneut überprüfen oder die Schleife vollständig verlassen ( breakKonstrukt). Es gibt zwei Möglichkeiten, um damit umzugehen:

  • Multiplexing: Lassen Sie den Code einen Summentyp für alle möglichen Exits zurückgeben. Im Fall eines Schleifenkörpers wäre das Continue | Break.
  • Continuation-Passing-Stil : Übersetzen Sie Code in eine Funktion, die einen zusätzlichen Parameter benötigt, der als nächstes ausgeführt werden soll. Dieser zusätzliche Parameter ist die Fortsetzung der Funktion. Code, der auf unterschiedliche Weise beendet werden kann, erhält für jede der Möglichkeiten einen solchen Parameter.

λx,y.xλx,y.yxy

Im Stil der Fortsetzung,

while (condition) body

wird übersetzt in

let rec f (continuation) =
  if (condition, body (f (continuation)), continuation)

Bei der Übersetzung eines Programms in eine typische imperative Sprache im Continuation-Passing-Stil ist die Fortsetzung immer das Letzte, was ein Code ausführt. Zum Beispiel wird die Fortsetzung von bodyoben nach dem gesamten Code von ausgeführt body, so dass die Tail-Call-Optimierung dazu führt, dass alle lokalen Variablen bodyunmittelbar vor dem Ausführen der Fortsetzung freigegeben werden.

Einige Sprachen bieten erstklassige Fortsetzungen mit einem Konstrukt wie Call-with-Current-Continuation . Call / cc ist im Allgemeinen nicht für die Tail-Call-Optimierung geeignet - es kann in der Tat eine ziemlich teure Operation sein, da dies dazu führen kann, dass der gesamte Programmstatus dupliziert wird.

Gilles 'SO - hör auf böse zu sein'
quelle