Kann Schemes call / cc alle bekannten Kontrollflussstrukturen implementieren?

12

Die Seite "Advanced Scheme: Some Naughty Bits" lautet:

Fortsetzungen sind ein mächtiges Kontrollflusskonstrukt, aus dem sich nahezu jede andere Kontrollflussstruktur ableiten lässt.

Ich dachte, dass Schemas call/cc, die mit dem J-Operator von Peter Landin verwandt sind (*), verwendet werden könnten, um eine bekannte Kontrollflussstruktur zu implementieren ?

Bei "Kontrollflussstruktur" denke ich speziell an die Beschreibung von Wikipedia , z. B. Ausnahmen, Koroutinen, grüne Fäden und so weiter.

Gibt es Beispiele für Kontrollflussstrukturen, die nicht mithilfe von implementiert werden können call/cc?

(*) Ich konnte kein Papier ausgraben, das call/ccso leistungsfähig ist wie der J-Operator. Eine Arbeit von Felleisen (die ich nicht gelesen habe und zugegebenermaßen Probleme damit habe, sie vollständig zu verstehen) untersucht dies und scheint zu dem Schluss zu kommen, dass sie formal gleichwertig sind, obwohl sie verschiedenen Komplexitätsklassen angehören.

(Beachten Sie auch, dass ich die Frage basierend auf den Kommentaren unten aktualisiert habe.)

Aktualisieren

Basierend auf der hervorragenden Antwort von @Neel unten habe ich mir Websites angesehen, die begrenzte und nicht begrenzte Fortsetzungen kommentieren , und es scheint in der Tat, dass es zwar call/ccnicht ausreichend ist, nicht begrenzt zu sein. In der Zwischenzeit können erstklassige, begrenzte Fortsetzungen (wie shift/reset) verwendet werden, um eine beliebige Kontrollflussstruktur auszudrücken.

csl
quelle
5
Was ist die formale Definition einer "Kontrollflussstruktur"?
Huck Bennett
4
Re: unbegrenzte Fortsetzungen. Haben Sie den referierten Artikel von Hayo Thielecke gelesen? Die tatsächliche Behauptung ist, dass unbegrenzte Fortsetzungen, wie sie von bereitgestellt werden, call/ccin Abwesenheit eines Staates keine Ausnahmen ausdrücken können . (Wie Thielecke weiter ausführt, können Ausnahmen implementiert werden, indem zwei Fortsetzungen call/cc
umgangen werden
@Rici: Ich habe nur die ersten Seiten überflogen. (Das Lesen von Zeitungen dauert sehr lange. ) Danke für den Kommentar!
CSL
@HuckBennett Ich habe keine formale Definition, aber informell ich meine , was es beschrieben en.wikipedia.org/wiki/Control_flow - ich speziell bedeuten , dass Sie Fortsetzungen verwenden können , zum Ausdruck bringen, und was noch wichtiger ist , zu implementieren, Koroutinen, grüne Fäden, Ausnahmen, Escape-Anweisungen, der amb-Operator und so weiter.
CSL
2
@csl Sie müssen nicht nur präzisieren, was "Kontrollflussstruktur" bedeutet, sondern auch klarer definieren, was es bedeutet, etwas "auszudrücken". Dies ist ein schwieriges Problem, und die Antwort auf Ihre Frage hängt stark davon ab, was Sie als Ausdruck betrachten. Schließlich können Sie eine Turing-Maschine, die einen Interpreter einer Sprache mit Ausnahmen (z. B. Java) codiert, immer irgendwie codieren. Aber das ist wahrscheinlich nicht das, was Sie im Sinn haben. Daher müssen Sie das Konzept des "Ausdrucks" stark einschränken (z. B. Komposition und / oder vollständige Abstraktion).
Martin Berger

Antworten:

10

In dieser Antwort verstehe ich "ausdrückbar" als "makroausdrückbar" im Sinne von Felleisen 1991, Über die Ausdruckskraft von Programmiersprachen . (Intuitiv ist ein Sprachfeature makroexprimierbar, wenn Sie es als lokale Quelltransformation definieren können, ohne eine Ganzprogrammtransformation zu verwenden.)

Mit dieser Definition lautet die Antwort nein : Begrenzte Steuerung ist im Lambda-Kalkül + call / cc nicht makroexprimierbar. Begrenzte Steueroperatoren mit call / cc ausdrücken. Um die Steuerelementbegrenzer (den Reset-Teil von Shift / Reset) zu implementieren, benötigen Sie einen bestimmten Status, um die Fortsetzungsmarken zu simulieren. Im Wesentlichen müssen Sie einen Stapel codieren, um die dynamischen Lebensdauern der Fortsetzungsmarken zu simulieren.

Begrenzte Kontrolle ist jedoch ein universeller Effekt im folgenden Sinne. In seiner Dissertation , Andrzej Filinski zeigte , dass jede exprimierbaren Nebenwirkung ist kodierbaren entweder begrenzt Fortsetzungen oder Ruf- / cc und eine einzelne Zelle von Zustand verwendet wird . Grob gesagt ist ein "ausdrückbarer Nebeneffekt" jeder Effekt, dessen monadischer Typ in Bezug auf die Typen der Programmiersprache definiert werden kann.

Überraschenderweise scheint diese Idee in der Praxis sehr interessant zu sein. In den letzten zehn Jahren haben Gordon Plotkin und John Power die Idee einer algebraischen Semantik von Effekttheorien vertreten: Sie spezifizieren die für Sie interessanten Nebenwirkungsoperationen und die Gleichungen, die sie erfüllen sollen, und dann Sie können generisch eine Semantik erhalten, indem Sie die freie Monade über diese Theorie nehmen.

Matija Pretnar und Andrej Bauer verfolgten diesen mathematischen Ansatz und implementierten ihn in ihrer Eff-Sprache , um ein neues Sprachkonstrukt zu erfinden, das als "Effekthandler" bezeichnet wird: Sie können Code schreiben, der eine Reihe von Imperativfunktionen verwendet, und den Imperativfunktionen dann eine Semantik zuweisen indem Sie eine Reihe von Handlern schreiben, die angeben, wie jede effektive Operation implementiert werden soll.

Neel Krishnaswami
quelle
Lautet die Definition jedoch: "Können Sie mithilfe von Scheme und call / cc eine beliebige Kontrollflussstruktur implementieren " (ohne Emulation), muss die Antwort " Ja" lauten ? In der LtU-Diskussion lambda-the-ultimate.org/node/966 scheint Oleg Kiselyouv alle vier F-Operatoren in Scheme mit call / cc: okmij.org/ftp/continuations/… - excerpt " implementiert zu haben on call / cc für die Erfassung nicht begrenzter Fortsetzungen und verwendet eine globale veränderbare Zelle. Es stellt sich heraus, dass dies ausreicht, um die anderen [...] F-Operatoren zu implementieren. " ... "-F- bis + F + F".
CSL
Ich erkenne an, dass Sie Felleisens "Makroausdruckbarkeit" als Rahmen für Ihre Antwort verwendet haben, aber wie Sie sehen, hatte ich meine Frage bereits so geändert, dass sie spezifisch "mit call / cc [im Schema] implementieren" bedeutet. Und während Oleg Kiselyov eine globale veränderbare Zelle einführen muss, um alle vier F-Operatoren für begrenzte Fortsetzungen zu implementieren, glaube ich nicht, dass dies eine "große globale Umstrukturierung des Programms" bedeutet - praktisch natürlich.
CSL
Ich werde diese Antwort akzeptieren. Ich möchte auch auf den Text unter okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim verweisen, der zusätzliche Verweise enthält. Es scheint auch, dass erstklassige, begrenzte Fortsetzungen wie Verschieben / Zurücksetzen verwendet werden können, um eine beliebige Kontrollflussstruktur zu implementieren. Aus dem Link: "Erstklassige, abgegrenzte Fortsetzungen können jeden ausdrücklichen Recheneffekt ausdrücken, einschließlich Ausnahmen und veränderlichen Zustands."
CSL