Verwendung von Scala-Fortsetzungen mit While-Schleifen

Question

Ich weiß, dies ist gegen den üblichen Sinn von SO-Fragen, aber der folgende Code funktioniert, obwohl ich denke, dass es nicht funktionieren sollte. Unten ist ein kleines Scala-Programm, das Fortsetzungen mit einer while-Schleife verwendet. Nach meinem Verständnis der Art der Fortsetzungsübergabe sollte dieser Code einen Stack-Überlauffehler erzeugen, indem für jede Iteration der while-Schleife ein Frame zum Stack hinzugefügt wird. Es funktioniert jedoch gut.

import util.continuations.{shift, reset} 


class InfiniteCounter extends Iterator[Int] { 
    var count = 0 
    var callback: Unit=>Unit = null 
    reset { 
     while (true) { 
      shift {f: (Unit=>Unit) => 
       callback = f 
      } 
      count += 1 
     } 

    } 

    def hasNext: Boolean = true 

    def next(): Int = { 
     callback() 
     count 
    } 
} 

object Experiment3 { 

    def main(args: Array[String]) { 
     val counter = new InfiniteCounter() 
     println(counter.next()) 
     println("Hello") 
     println(counter.next()) 
     for (i <- 0 until 100000000) { 
      counter.next() 
     } 
     println(counter.next()) 
    } 

} 

Die Ausgabe lautet:

1 
Hello 
2 
100000003 

Meine Frage ist: Warum gibt es keinen Stack-Überlauf? Tut der Scala-Compiler die Tail-Call-Optimierung (was ich nicht mit Fortsetzungen machen konnte) oder gibt es noch etwas anderes?

(Dieses Experiment ist auf Github zusammen mit der sbt Konfiguration ist es erforderlich laufen. https://github.com/jcrudy/scala-continuation-experiments Siehe commit 7cec9befcf58820b925bb222bc25f2a48cbec4a6)

Answer 1

Der Grund, dass Sie nicht einen Stapelüberlauf hier, weil die Art und Weise Sie verwenden erhalten Sie shift und callback() verhält sich wie ein trampoline.

Jedes Mal, wenn der Ausführungs-Thread das shift Konstrukt erreicht hat, setzt es callback gleich die aktuelle Fortsetzung (a Verschluss), und kehrt dann sofort zum Unit rufenden Kontext. Wenn Sie next() aufrufen und callback() aufrufen, führen Sie den Fortsetzungsabschluss aus, der nur count += 1 ausführt, springt dann zurück zum Anfang der Schleife und führt die shift erneut aus.

Einer der Hauptvorteile der CPS-Transformation besteht darin, dass sie den Steuerungsfluss in der Fortsetzung erfasst und nicht den Stapel verwendet. Wenn Sie callback = f für jede "Iteration" festlegen, überschreiben Sie Ihre einzige Referenz auf die vorherige Fortsetzung/den vorherigen Status der Funktion, und dies ermöglicht das Sammeln von Garbage Collection.

Der Stapel hier erreicht nur eine Tiefe von ein paar Frames (es ist wahrscheinlich etwa 10 wegen der verschachtelten Verschlüsse). Jedes Mal, wenn Sie die shift ausführen, erfasst es den aktuellen Status in einem Abschluss (im Heap), und dann wird der Stapel auf Ihren Ausdruck for zurückgesetzt.

Ich fühle mich wie ein Diagramm würde dies klarer - aber Schritt durch den Code mit Ihrem Debugger wäre wahrscheinlich genauso nützlich. Ich denke, der entscheidende Punkt hier ist, da Sie im Wesentlichen ein Trampolin gebaut haben, werden Sie nie den Stapel blasen.