Was sind Scala-Fortsetzungen und warum werden sie verwendet?

Ich habe gerade die Programmierung in Scala beendet und mich mit den Änderungen zwischen Scala 2.7 und 2.8 befasst. Das wichtigste scheint das Fortsetzungs-Plugin zu sein, aber ich verstehe nicht, wofür es nützlich ist oder wie es funktioniert. Ich habe gesehen, dass es für asynchrone E / A gut ist, aber ich konnte nicht herausfinden, warum. Einige der beliebtesten Ressourcen zu diesem Thema sind:

• Abgrenzte Fortsetzungen und Scala
• Gehe in Scala
• Ein Vorgeschmack auf 2,8: Fortsetzung
• Abgrenzte Fortsetzung erklärt (in Scala)

Und diese Frage zum Stapelüberlauf:

• Was sind die größten Unterschiede zwischen Scala 2.8 und Scala 2.7?

Leider versucht keine dieser Referenzen zu definieren, wofür Fortsetzungen sind oder was die Shift / Reset-Funktionen tun sollen, und ich habe keine Referenzen gefunden, die dies tun. Ich konnte nicht erraten, wie eines der Beispiele in den verlinkten Artikeln funktioniert (oder was sie tun). Eine Möglichkeit, mir zu helfen, könnte darin bestehen, eines dieser Beispiele Zeile für Zeile durchzugehen. Auch dieser einfache aus dem dritten Artikel:

reset {
    ...
    shift { k: (Int=>Int) =>  // The continuation k will be the '_ + 1' below.
        k(7)
    } + 1
}
// Result: 8

Warum ist das Ergebnis 8? Das würde mir wahrscheinlich helfen, loszulegen.

Mein Blog erklärt, was resetund was zu shifttun ist. Vielleicht möchten Sie das noch einmal lesen.

Eine weitere gute Quelle, auf die ich auch in meinem Blog verweise, ist der Wikipedia-Eintrag zum Continuation-Passing-Stil . Dieser ist bei weitem der klarste zu diesem Thema, obwohl er keine Scala-Syntax verwendet, und die Fortsetzung wird explizit übergeben.

Das Papier über abgegrenzte Fortsetzungen, auf das ich in meinem Blog verweise, das aber anscheinend kaputt ist, enthält viele Anwendungsbeispiele.

Aber ich denke, das beste Beispiel für das Konzept der begrenzten Fortsetzung ist Scala Swarm. Darin stoppt die Bibliothek die Ausführung Ihres Codes an einem Punkt und die verbleibende Berechnung wird zur Fortsetzung. Die Bibliothek führt dann etwas aus - in diesem Fall überträgt sie die Berechnung auf einen anderen Host und gibt das Ergebnis (den Wert der Variablen, auf die zugegriffen wurde) an die Berechnung zurück, die gestoppt wurde.

Nun verstehen Sie nicht einmal das einfache Beispiel auf der Seite Scala, so kann mein Blog lesen. Darin geht es mir nur darum, diese Grundlagen zu erklären, warum das Ergebnis ist 8.

Ich fand die vorhandenen Erklärungen weniger effektiv bei der Erklärung des Konzepts als ich hoffen würde. Ich hoffe, dieser ist klar (und richtig). Ich habe noch keine Fortsetzungen verwendet.

Wenn eine Fortsetzungsfunktion cfaufgerufen wird:

1. Die Ausführung überspringt den Rest des shift Blocks und beginnt am Ende des Blocks erneut
   • Der Parameter, an den übergeben wird, cfwird vom shiftBlock "ausgewertet", wenn die Ausführung fortgesetzt wird. Dies kann für jeden Anruf bei unterschiedlich seincf
2. Die Ausführung wird bis zum Ende des resetBlocks (oder bis zu einem Aufruf von) fortgesetztreset wenn kein Block vorhanden ist).
   • Das Ergebnis des resetBlocks (oder der Parameter to reset(), wenn kein Block vorhanden ist) gibt cfzurück
3. Die Ausführung wird cfbis zum Ende desshift Blocks
4. Die Ausführung wird bis zum Ende des resetBlocks übersprungen (oder ein Aufruf zum Zurücksetzen?)

Folgen Sie in diesem Beispiel den Buchstaben von A bis Z.

reset {
  // A
  shift { cf: (Int=>Int) =>
    // B
    val eleven = cf(10)
    // E
    println(eleven)
    val oneHundredOne = cf(100)
    // H
    println(oneHundredOne)
    oneHundredOne
  }
  // C execution continues here with the 10 as the context
  // F execution continues here with 100
  + 1
  // D 10.+(1) has been executed - 11 is returned from cf which gets assigned to eleven
  // G 100.+(1) has been executed and 101 is returned and assigned to oneHundredOne
}
// I

Dies druckt:

11
101

Angesichts des kanonischen Beispiels aus dem Forschungsbericht zu Scalas begrenzten Fortsetzungen, das geringfügig modifiziert wurde, damit die Funktionseingabe shiftden Namen erhält fund somit nicht mehr anonym ist.

def f(k: Int => Int): Int = k(k(k(7)))
reset(
  shift(f) + 1   // replace from here down with `f(k)` and move to `k`
) * 2

Die Scala Plugin Transformationen dieses Beispiel derart , dass die Berechnung (innerhalb des Eingabearguments der reset) aus jedem Ausgang shiftden Aufruf resetwird ersetzt mit der Funktion ( zum Beispiel f) eingegeben shift.

Die ersetzte Berechnung wird in eine Funktion verschoben (dh verschoben) k. Die Funktion fgibt die Funktion k, wo k enthält die Berechnung ersetzt, kEingänge x: Int, und die Berechnung in kErsetzt shift(f)mit x.

f(k) * 2
def k(x: Int): Int = x + 1

Welches hat den gleichen Effekt wie:

k(k(k(7))) * 2
def k(x: Int): Int = x + 1

Beachten Sie, dass der Typ Intdes Eingabeparameters x(dh die Typensignatur von k) durch die Typensignatur des Eingabeparameters von angegeben wurde f.

Ein weiteres geliehenes Beispiel mit der konzeptionell äquivalenten Abstraktion, dh readdie Funktionseingabe für shift:

def read(callback: Byte => Unit): Unit = myCallback = callback
reset {
  val byte = "byte"

  val byte1 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "1 = " + byte1)
  val byte2 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "2 = " + byte2)
}

Ich glaube, dies würde in das logische Äquivalent von übersetzt werden:

val byte = "byte"

read(callback)
def callback(x: Byte): Unit {
  val byte1 = x
  println(byte + "1 = " + byte1)
  read(callback2)
  def callback2(x: Byte): Unit {
    val byte2 = x
    println(byte + "2 = " + byte1)
  }
}

Ich hoffe, dies verdeutlicht die kohärente gemeinsame Abstraktion, die durch die vorherige Präsentation dieser beiden Beispiele etwas verschleiert wurde. Zum Beispiel wurde das kanonische erste Beispiel in der Forschungsarbeit als anonyme Funktion anstelle meines Namens dargestellt f, so dass einigen Lesern nicht sofort klar war, dass es abstrakt analog zu dem readin der geliehenen war zweiten Beispiel war.

So abgegrenzte Fortsetzungen erzeugen die Illusion einer Umkehrung der Kontrolle von "Sie rufen mich von außen an reset" zu "Ich rufe Sie von innen an reset".

Beachten Sie den Rückgabetyp fist, aber kist nicht erforderlich , das gleiche wie der Rückgabetyp sein reset, das heißt fdie Freiheit , jeden Rückgabetyp zu erklären , hat für kso lange fzurückkehren vom gleichen Typ wie reset. Das Gleiche gilt für readund capture(siehe auch ENVunten).

Begrenzte Fortsetzungen kehren die Kontrolle des Zustands nicht implizit um, z. B. readund callbacksind keine reinen Funktionen. Somit kann der Aufrufer keine referenziell transparenten Ausdrücke erstellen und hat somit keine deklarative (auch als transparent bezeichnete) Kontrolle über die beabsichtigte imperative Semantik .

Wir können explizit reine Funktionen mit begrenzten Fortsetzungen erreichen.

def aread(env: ENV): Tuple2[Byte,ENV] {
  def read(callback: Tuple2[Byte,ENV] => ENV): ENV = env.myCallback(callback)
  shift(read)
}
def pure(val env: ENV): ENV {
  reset {
    val (byte1, env) = aread(env)
    val env = env.println("byte1 = " + byte1)
    val (byte2, env) = aread(env)
    val env = env.println("byte2 = " + byte2)
  }
}

Ich glaube, dies würde in das logische Äquivalent von übersetzt werden:

def read(callback: Tuple2[Byte,ENV] => ENV, env: ENV): ENV =
  env.myCallback(callback)
def pure(val env: ENV): ENV {
  read(callback,env)
  def callback(x: Tuple2[Byte,ENV]): ENV {
    val (byte1, env) = x
    val env = env.println("byte1 = " + byte1)
    read(callback2,env)
    def callback2(x: Tuple2[Byte,ENV]): ENV {
      val (byte2, env) = x
      val env = env.println("byte2 = " + byte2)
    }
  }
}

Dies wird aufgrund der expliziten Umgebung laut.

Tangentialerweise hat Scala keine globale Typinferenz von Haskell und konnte meines Wissens das implizite Anheben einer staatlichen Monade unit(als eine mögliche Strategie zum Verbergen der expliziten Umgebung) nicht unterstützen, da Haskells globale Typinferenz (Hindley-Milner) hängt davon ab , dass die mehrfache virtuelle Vererbung von Diamanten nicht unterstützt wird .

Die Fortsetzung erfasst den Status einer Berechnung, die später aufgerufen wird.

Stellen Sie sich die Berechnung zwischen dem Verlassen des Shift-Ausdrucks und dem Verlassen des Reset-Ausdrucks als Funktion vor. Innerhalb des Verschiebungsausdrucks heißt diese Funktion k, sie ist die Fortsetzung. Sie können es weitergeben und später sogar mehrmals aufrufen.

Ich denke, der vom Rücksetzausdruck zurückgegebene Wert ist der Wert des Ausdrucks innerhalb des Verschiebungsausdrucks nach dem =>, aber darüber bin ich mir nicht ganz sicher.

Mit Fortsetzungen können Sie also einen eher willkürlichen und nicht lokalen Code in eine Funktion einbinden. Dies kann verwendet werden, um nicht standardmäßige Kontrollabläufe wie Coroutining oder Backtracking zu implementieren.

Daher sollten Fortsetzungen auf Systemebene verwendet werden. Sie durch Ihren Anwendungscode zu streuen, wäre ein sicheres Rezept für Albträume, viel schlimmer als der schlechteste Spaghetti-Code, den goto jemals verwenden könnte.

Haftungsausschluss: Ich habe kein tiefgreifendes Verständnis der Fortsetzungen in Scala. Ich habe es nur aus dem Betrachten der Beispiele und dem Kennen der Fortsetzungen aus dem Schema abgeleitet.

Aus meiner Sicht wurde hier die beste Erklärung gegeben: http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

Eines der Beispiele:

Um den Kontrollfluss etwas klarer zu sehen, können Sie dieses Code-Snippet ausführen:

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

Hier ist die Ausgabe, die der obige Code erzeugt:

A
B
D
E
G
F
C

Ein weiterer (neuerer - Mai 2016) Artikel über Scala-Fortsetzungen ist:
" Zeitreise in Scala: CPS in Scala (Fortsetzung von Scala) " von Shivansh Srivastava ( shiv4nsh) .
Es bezieht sich auch auf Jim McBeath 's Artikel in erwähnter Dmitry Bespalov ' s Antwort .

Aber vorher beschreibt es Fortsetzungen wie folgt:

Eine Fortsetzung ist eine abstrakte Darstellung des Steuerzustands eines Computerprogramms .
Was es also tatsächlich bedeutet, ist, dass es sich um eine Datenstruktur handelt, die den Rechenprozess an einem bestimmten Punkt in der Ausführung des Prozesses darstellt. Auf die erstellte Datenstruktur kann von der Programmiersprache zugegriffen werden, anstatt in der Laufzeitumgebung versteckt zu sein.

Um es weiter zu erklären, können wir eines der klassischsten Beispiele haben:

Angenommen, Sie sind in der Küche vor dem Kühlschrank und denken an ein Sandwich. Sie nehmen genau dort eine Fortsetzung und stecken sie in Ihre Tasche.
Dann holst du etwas Truthahn und Brot aus dem Kühlschrank und machst dir ein Sandwich, das jetzt auf der Theke steht.
Sie rufen die Fortsetzung in Ihrer Tasche auf und stehen wieder vor dem Kühlschrank und denken an ein Sandwich. Aber zum Glück gibt es ein Sandwich auf der Theke, und alle Materialien, aus denen es hergestellt wurde, sind weg. Also isst du es. :-)

In dieser Beschreibung ist das sandwichTeil der Programmdaten (z. B. ein Objekt auf dem Heap), und anstatt eine make sandwichRoutine aufzurufen und dann zurückzukehren, nennt die Person eine make sandwich with current continuationRoutine, die das Sandwich erstellt und dann dort fortfährt, wo sie ausgeführt wird aufgehört.

Davon abgesehen , wie im April 2014 für Scala 2.11.0-RC1 angekündigt

Wir suchen Betreuer, die folgende Module übernehmen: Scala-Swing , Scala-Continuations .
2.12 schließt sie nicht ein, wenn kein neuer Betreuer gefunden wird .
Wir werden wahrscheinlich die anderen Module (scala-xml, scala-parser-combinators) beibehalten, aber die Hilfe wird immer noch sehr geschätzt.

Scala-Fortsetzungen anhand aussagekräftiger Beispiele

Definieren wir, from0to10dass die Idee der Iteration von 0 bis 10 ausgedrückt wird:

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i)
   }
}

Jetzt,

reset {
  val x = from0to10()
  print(s"$x ")
}
println()

Drucke:

0 1 2 3 4 5 6 7 8 9 10 

In der Tat brauchen wir nicht x:

reset {
  print(s"${from0to10()} ")
}
println()

druckt das gleiche Ergebnis.

Und

reset {
  print(s"(${from0to10()},${from0to10()}) ")
}
println()

druckt alle Paare:

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (5,10) (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (6,10) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (7,8) (7,9) (7,10) (8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8) (8,9) (8,10) (9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (9,10) (10,0) (10,1) (10,2) (10,3) (10,4) (10,5) (10,6) (10,7) (10,8) (10,9) (10,10) 

Wie funktioniert das?

Es ist der genannte Code , from0to10und die Telefonvorwahl . In diesem Fall folgt der folgende Block reset. Einer der an den aufgerufenen Code übergebenen Parameter ist eine Rücksprungadresse, die anzeigt, welcher Teil des aufrufenden Codes noch nicht ausgeführt wurde (**). Dieser Teil des aufrufenden Codes ist die Fortsetzung . Der aufgerufene Code kann mit diesem Parameter alles tun, wofür er sich entscheidet: Übergeben Sie die Kontrolle an ihn, ignorieren Sie ihn oder rufen Sie ihn mehrmals auf. Hier wird from0to10diese Fortsetzung für jede Ganzzahl im Bereich 0..10 aufgerufen.

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i) // call the continuation
   }
}

Aber wo endet die Fortsetzung? Dies ist wichtig, da der letzte returnaus der Fortsetzung die Kontrolle an den aufgerufenen Code zurückgibt from0to10. In Scala endet es dort, wo der resetBlock endet (*).

Nun sehen wir, dass die Fortsetzung als deklariert ist cont: Int => Unit. Warum? Wir rufen from0to10als auf val x = from0to10()und Intsind die Art von Wert, zu dem geht x. Unitbedeutet, dass der Block danach resetkeinen Wert zurückgeben darf (andernfalls tritt ein Typfehler auf). Im Allgemeinen gibt es 4 Typensignaturen: Funktionseingabe, Fortsetzungseingabe, Fortsetzungsergebnis, Funktionsergebnis. Alle vier müssen mit dem Aufrufkontext übereinstimmen.

Oben haben wir Wertepaare gedruckt. Drucken wir die Multiplikationstabelle. Aber wie geben wir \nnach jeder Zeile aus?

Mit dieser Funktion backkönnen wir festlegen, was zu tun ist, wenn die Steuerung zurückkehrt, von der Fortsetzung bis zum Code, der sie aufgerufen hat.

def back(action: => Unit) = shift { (cont: Unit => Unit) =>
  cont()
  action
}

backruft zuerst seine Fortsetzung auf und führt dann die Aktion aus .

reset {
  val i = from0to10()
  back { println() }
  val j = from0to10
  print(f"${i*j}%4d ") // printf-like formatted i*j
}

Es druckt:

   0    0    0    0    0    0    0    0    0    0    0 
   0    1    2    3    4    5    6    7    8    9   10 
   0    2    4    6    8   10   12   14   16   18   20 
   0    3    6    9   12   15   18   21   24   27   30 
   0    4    8   12   16   20   24   28   32   36   40 
   0    5   10   15   20   25   30   35   40   45   50 
   0    6   12   18   24   30   36   42   48   54   60 
   0    7   14   21   28   35   42   49   56   63   70 
   0    8   16   24   32   40   48   56   64   72   80 
   0    9   18   27   36   45   54   63   72   81   90 
   0   10   20   30   40   50   60   70   80   90  100 

Nun, jetzt ist es Zeit für ein paar Brain Twister. Es gibt zwei Anrufungen von from0to10. Was ist die Fortsetzung für die erste from0to10? Es folgt dem Aufruf von from0to10im Binärcode , enthält aber im Quellcode auch die Zuweisungsanweisung val i =. Es endet dort, wo der resetBlock endet, aber das Ende des resetBlocks gibt die Kontrolle nicht an das erste zurück from0to10. Das Ende des resetBlocks gibt die Kontrolle an die 2. zurück from0to10, die wiederum schließlich die Kontrolle an zurückgibt back, und es ist das back, was die Kontrolle an den ersten Aufruf von zurückgibt from0to10. Wenn der erste (ja! 1.!) from0to10Beendet wird, wird der gesamte resetBlock verlassen.

Eine solche Methode zur Rückgabe der Kontrolle wird als Backtracking bezeichnet . Es handelt sich um eine sehr alte Technik, die zumindest aus der Zeit der Prolog- und AI-orientierten Lisp-Derivate bekannt ist.

Die Namen resetund shiftsind Fehlbezeichnungen. Diese Namen sollten besser für die bitweisen Operationen belassen werden. resetDefiniert Fortsetzungsgrenzen und shiftnimmt eine Fortsetzung vom Aufrufstapel.

Anmerkungen)

(*) In Scala endet die Fortsetzung dort, wo der resetBlock endet. Ein anderer möglicher Ansatz wäre, es dort enden zu lassen, wo die Funktion endet.

(**) Einer der Parameter des aufgerufenen Codes ist eine Rücksprungadresse, die anzeigt, welcher Teil des aufrufenden Codes noch nicht ausgeführt wurde. Nun, in Scala wird dafür eine Folge von Absenderadressen verwendet. Wie viele? Alle Rücksprungadressen, die seit dem Betreten des resetBlocks auf dem Aufrufstapel platziert wurden .

UPD Teil 2 Fortsetzen verwerfen: Filtern

def onEven(x:Int) = shift { (cont: Unit => Unit) =>
  if ((x&1)==0) {
    cont() // call continuation only for even numbers
  }
}
reset {
  back { println() }
  val x = from0to10()
  onEven(x)
  print(s"$x ")
}

Dies druckt:

0 2 4 6 8 10 

Lassen Sie uns zwei wichtige Operationen herausrechnen: die Fortsetzung verwerfen ( fail()) und die Kontrolle an sie weitergeben ( succ()):

// fail: just discard the continuation, force control to return back
def fail() = shift { (cont: Unit => Unit) => }
// succ: does nothing (well, passes control to the continuation), but has a funny signature
def succ():Unit @cpsParam[Unit,Unit] = { }
// def succ() = shift { (cont: Unit => Unit) => cont() }

Beide Versionen von succ()(oben) funktionieren. Es stellt sich heraus, dass shiftes eine lustige Signatur hat, und obwohl succ()es nichts tut, muss es diese Signatur für die Typbalance haben.

reset {
  back { println() }
  val x = from0to10()
  if ((x&1)==0) {
    succ()
  } else {
    fail()
  }
  print(s"$x ")
}

wie erwartet wird gedruckt

0 2 4 6 8 10

Innerhalb einer Funktion succ()ist nicht erforderlich:

def onTrue(b:Boolean) = {
  if(!b) {
    fail()
  }
}
reset {
  back { println() }
  val x = from0to10()
  onTrue ((x&1)==0)
  print(s"$x ")
}

wieder druckt es

0 2 4 6 8 10

Definieren wir nun onOdd()über onEven():

// negation: the hard way
class ControlTransferException extends Exception {}
def onOdd(x:Int) = shift { (cont: Unit => Unit) =>
  try {
    reset {
      onEven(x)
      throw new ControlTransferException() // return is not allowed here
    }
    cont()
  } catch {
    case e: ControlTransferException =>
    case t: Throwable => throw t
  }
}
reset {
  back { println() }
  val x = from0to10()
  onOdd(x)
  print(s"$x ")
}

Wenn oben gerade xist, wird eine Ausnahme ausgelöst und die Fortsetzung wird nicht aufgerufen. Wenn dies xungerade ist, wird die Ausnahme nicht ausgelöst und die Fortsetzung wird aufgerufen. Der obige Code wird gedruckt:

1 3 5 7 9