Was ist ein Beispiel für eine Fortsetzung, die nicht als Prozedur implementiert wurde?

15

Ein interessantes Diskussion über die Unterscheidung zwischen Rückrufen und Fortsetzungen bei SO hat diese Frage aufgeworfen. Per Definition ist eine Fortsetzung eine abstrakte Darstellung der Logik, die zur Vervollständigung einer Berechnung benötigt wird. In den meisten Sprachen wird dies als eine Prozedur mit einem Argument dargestellt, an die Sie den Wert übergeben, der weiter verarbeitet werden muss.

In einer rein funktionalen Sprache (in der alle Funktionen reine und erstklassige Bürger sind) würde ich denken, dass eine Fortsetzung vollständig als Funktion modelliert werden könnte. So habe ich ja bisher Fortsetzungen verstanden. Die Welt ist jedoch staatlich (seufzend) und die allgemeine Definition erfordert nicht, dass ein Programmstatus für die Fortsetzung erfasst wird - es muss nur die Absicht umfassen.

Kann zum besseren Verständnis ein Beispiel in einer funktionalen Sprache angegeben werden, in der die Fortsetzung abstrakter ausgedrückt wird als eine Funktion? Ich weiß, dass Scheme es Ihnen ermöglicht, die aktuelle Fortsetzung auf erstklassige Weise zu erfassen (call / cc), aber trotzdem scheint es, dass die Prozedur mit einem Argument, die an call / cc übergeben wird, einfach die aktuelle Fortsetzung in Form einer anderen gegeben wird Argumentprozedur, auf die die Funktion call / cc'd das Ergebnis anwenden kann.

David Cowden
quelle
Vielleicht der Schnittpunkt von Kontinuitäten und Defunktionalisierung als: Kontinuitäten können durch Defunktionalisierung in Datenstrukturen umgewandelt werden; Vielleicht ist es ein interessanter Bereich, den man sich ansehen sollte.
Dan D.
@DanD. Haben Sie Vorschläge für interessante Literatur, die ich lesen kann? Das Thema klingt nützlich.
David Cowden

Antworten:

11

tl; dr; Der Typ ist die übergreifende Abstraktion über eine Fortsetzung


Eine Fortsetzung ist die Art ihrer Ein- und Ausgänge

Das, was Sie einer nicht prozedurbasierten Fortsetzung am nächsten kommen, ist wahrscheinlich die Fortsetzungsmonade in Haskell, da sie als Typ ausgedrückt wird, für den viele Funktionen verwendet werden können, um mit dem Typ zu interagieren, um ihn zu unterbrechen, fortzusetzen, zurückzuverfolgen usw.

Sie können diesen Verschluss in einer Art, wie die kapseln ContTyp in Haskell , wo Sie die Monade Abstraktion als „höhere Ebene Abstraktion“ erhalten, und es gibt andere Formen der Abstraktion über Fortsetzungen erhalten Sie , wenn Sie auf die Fortsetzung als aussehen Art statt Zum Beispiel einfach eine Prozedur

  • Sie können zwei Fortsetzungen nehmen und eine Alternative zwischen ihnen machen, wenn der Typ den Gesetzen folgt, ein Monoid zu sein
  • Sie können über den Typ abstrahieren, um die Eingabe- oder Ausgabetypen der Fortsetzung zu ändern, wenn Sie den Abschluss in einen Typ einkapseln, der die Gesetze eines Funktors einhält
  • Sie können Ihre Fortsetzung beliebig und teilweise anwenden oder mit Funktionen wie Eingabevalidierung oder Eingabekonvertierung versehen, wenn Sie den Abschluss in einen Typ einkapseln, der den Gesetzen eines anwendbaren Funktors folgt

Abschluss vs. Verfahren

Am Ende des Tages haben Sie im Grunde recht; Eine Fortsetzung ist eine "Prozedur", obwohl ich sie eher als Abschluß bezeichnen würde. Oft werden Fortsetzungen am besten als erstklassige Abschlüsse ausgedrückt, die eine gebundene Umgebung umschlossen haben. In einer reinen funktionalen Sprache könnte man sagen, dass dies nicht besonders sinnvoll ist, weil Sie keine Referenzen haben. Dies ist wahr, aber Sie können Werte einschließen, und durch eine einzelne Zuweisung wird das Einschließen des Werts gegenüber der Referenz genau gleich. Daraus ergibt sich in Haskell:

(\x -> \y -> insideYIcanAccess x (and y))

In einer Sprache, die nicht in der Lage ist, eine verbindliche Umgebung einzuschließen, fehlen möglicherweise technisch gesehen erstklassige Abschlüsse, aber selbst dann gibt es eine Umgebung (im Allgemeinen die globale), die für den Abschluss verfügbar ist.

Daher würde ich sagen, dass es genauer ist, eine Fortsetzung wie folgt zu beschreiben: Ein Verschluss, der auf eine bestimmte Art und Weise verwendet wird.


Fazit

Auf die Frage "Ist eine Fortsetzung anders als durch eine Prozedur umsetzbar?" Nein. Wenn Sie keine First-Class-Funktionen haben, können Sie wirklich keine Fortsetzungen als solche haben (Ja, Funktionszeiger zählen als First-Class-Funktionen, sodass alternativ ein beliebiger Speicherzugriff ausreichen kann).

Nun zur Frage "Gibt es Möglichkeiten, eine Fortsetzung abstrakter auszudrücken als eine Prozedur?" Wenn Sie es als Typ ausdrücken, erhalten Sie eine viel größere Abstraktion, sodass Sie die Fortsetzung auf sehr allgemeine Weise behandeln können, sodass Sie mit der Fortsetzung auf viel mehr Arten interagieren können, als nur sie auszuführen.

Jimmy Hoffa
quelle
1
Dies verallgemeinert auf "Eine Fortsetzung kann einfach alles sein, was Sie das Ergebnis des Restes des Programms erhalten lassen". Da dies normalerweise Code erfordert (der Rest des Programms), verwenden die meisten Sprachen Funktionen. Theoretisch kann man aus allem eine Fortsetzung konstruieren. Bei der Fortsetzung der Konvertierung in meinen Compilern habe ich teilweise gefüllte Bäume verwendet.
Daniel Gratzer
1
@jozefg teilweise gefüllte Bäume sind eine korrekte Darstellung einer Berechnung als Ausdruck, aber am Ende des Tages ist der tatsächlich geschriebene Code eine Art Ausdruck, der sich nicht identifizierbar von einer Prozedur unterscheidet, wie ich sie verstehe. Abgesehen davon sind teilweise gefüllte Bäume die Compilerdarstellung. Die Entwicklervertretung ist erwartungsgemäß ein normativer Rechenausdruck mit der Syntax und Semantik der Sprache, der 99% der Entwickler als "Prozedur", "Funktion" oder auf andere Weise erscheinen würde. Sie denken aus der Perspektive des Compilerentwicklers heh
Jimmy Hoffa
2

Ein Beispiel, das Ihnen gefallen könnte, sind Koroutinen. Die Coroutinen von Lua oder die Iteratoren / Generatoren von Python oder C # haben beispielsweise eine ähnliche Leistung wie One-Shot-Fortsetzungen (Fortsetzungen, die Sie nur einmal aufrufen dürfen), die Fortsetzung wird jedoch nicht explizit in eine Funktion umgewandelt. Stattdessen haben Sie Möglichkeiten, die Coroutine bis zur nächsten "Yield" -Anweisung zu verschieben.

Betrachten Sie beispielsweise das folgende Python-Programm:

def my_iterator():
   yield 1
   yield 2
   yield 3

def main():
   it = my_iterator()
   x = it.next()
   y = it.next()
   z = it.next()
   print x + y + z

Es ähnelt dem folgenden Javascript-Programm mit expliziten Rückrufen:

function my_iterator()
  return function(cb1){
    cb1(1, function(cb2){
      cb2(2, function(cb3){
        cb3(3, function(cb4){
          throw "stop iteration";
        });
      });
    });
  });
}

function main(){
   var getNext1 = my_iterator();
   getNext1(function(x, getNext2){
      getNext2(function(y, getNext3){
         getNext3(function(z, getNext4){
            console.log(x + y + z);
         });
      });
   });
}

Das Javascript-Beispiel ist etwas verrauscht, weil jeder Schritt zusätzlich zur Rückgabe des ermittelten Werts die nächste Fortsetzung zurückgeben muss (in Python wird die Fortsetzung im ite verfolgt)

hugomg
quelle