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.
call/ccin Abwesenheit eines Staates keine Ausnahmen ausdrücken können . (Wie Thielecke weiter ausführt, können Ausnahmen implementiert werden, indem zwei Fortsetzungencall/ccamb-Operator und so weiter.Antworten:
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.
quelle