Einfachstes Beispiel für Rückwärtsfortsetzungen in Scheme ohne explizite Mutation

Question

Ich habe einen kleinen Scheme-Interpreter in C# geschrieben und festgestellt, dass die Art und Weise, wie ich ihn implementiert hatte, es sehr einfach war, Unterstützung für richtige Fortsetzungen hinzuzufügen.

Ich habe sie also hinzugefügt... möchte aber "beweisen", dass die Art und Weise, wie ich sie hinzugefügt habe, korrekt ist.

Mein Scheme-Interpreter hat jedoch keine Unterstützung für "mutating" Zustand - alles ist unveränderlich.

Es war also ziemlich einfach, einen Unit-Test zu schreiben, um Fortsetzungen "nach oben" aufzudecken:

AssertEqual(Eval("(call/cc (lambda (k) (+ 56 (k 3))))"), 3);

Ich möchte jedoch auch einen Einheitstest schreiben, der zeigt, dass die Fortsetzung auch dann noch funktioniert, wenn sie "ausbricht":

AssertEqual(Eval("(call/cc (lambda (k) k))", <some continuation>);

Aber natürlich würde die oben genannten nur testen, dass "Ich habe eine Fortsetzung" ... nicht, dass es tatsächlich eine gültige Fortsetzung ist.

Alle Beispiele, die ich finden kann, enden jedoch immer mit "set!", um die escaped continuation zu demonstrieren.

Was ist das einfachste Scheme-Beispiel, das die richtige Unterstützung für rückwärts gerichtete Fortsetzungen demonstriert, ohne sich auf Mutation zu verlassen?

Sind rückwärts gerichtete Fortsetzungen ohne Mutation überhaupt sinnvoll? Ich fange an zu vermuten, dass sie es nicht sind, weil man sie nur benutzen könnte, um genau dieselbe Berechnung noch einmal auszuführen... was sinnlos ist, wenn es keine Nebeneffekte gibt. Ist das der Grund, warum es in Haskell keine Fortsetzungen gibt?

Answer 1

Ich weiß nicht, ob dies der einfachste Weg ist, aber hier ist ein Beispiel für die Verwendung von Rückwärtsfortsetzungen ohne Aufruf von set! oder ähnlich:

(apply
  (lambda (k i) (if (> i 5) i (k (list k (* 2 i)))))
  (call/cc (lambda (k) (list k 1))))

Dies sollte zu folgenden Ergebnissen führen 8 .

Ein wenig interessanter ist:

(apply
  (lambda (k i n) (if (= i 0) n (k (list k (- i 1) (* i n)))))
  (call/cc (lambda (k) (list k 6 1))))

die Folgendes berechnet 6! (d.h. es sollte zu 720 ).

Das Gleiche können Sie auch tun mit let* :

(let* ((ka (call/cc (lambda (k) `(,k 1)))) (k (car ka)) (a (cadr ka)))
      (if (< a 5) (k `(,k ,(* 2 a))) a))

(Mann, die Syntaxhervorhebung von Stackoverflow versagt massiv bei Schemata).

Answer 2

Ich denke, Sie haben Recht - ohne Mutation tun rückwärts gerichtete Fortsetzungen nichts, was vorwärts gerichtete Fortsetzungen nicht auch können.

Answer 3

Hier ist das Beste, was mir eingefallen ist:

AssertEqual(Eval("((call/cc (lambda (k) k)) (lambda (x) 5))", 5);

Es ist nicht erstaunlich, aber es ist eine Rückwärtsfortsetzung, die ich dann mit der eigentlichen Funktion "aufrufe", die ich aufrufen möchte, eine Funktion, die die Zahl 5 zurückgibt.

Ah, und ich habe auch mit diesem als eine gute Einheit Testfall kommen:

AssertEqual(Eval("((call/cc call/cc) (lambda (x) 5))", 5);

Ich stimme Jacob B zu - ich glaube nicht, dass es ohne veränderbaren Zustand so nützlich ist... wäre aber trotzdem an einem Gegenbeispiel interessiert.

Answer 4

Funktionale Fäden:

Sie können eine rekursive Schleife verwenden, um den Status ohne Mutation zu aktualisieren, einschließlich des Status der nächsten aufzurufenden Fortsetzung. Dies ist komplizierter als die anderen Beispiele, aber alles, was Sie wirklich brauchen, ist die thread-1 y main Schleife. Der andere Thread und die "Update"-Funktion dienen dazu, zu zeigen, dass Fortsetzungen für mehr als ein triviales Beispiel verwendet werden können. Damit dieses Beispiel funktioniert, benötigen Sie außerdem eine Implementierung mit dem genannten let. Diese kann in eine äquivalente Form mit define-Anweisungen übersetzt werden.

Exemple :

(let* ((update (lambda (data) data))                ;is identity to keep simple for example
       (thread-1                                    
         (lambda (cc)                               ;cc is the calling continuation
           (let loop ((cc cc)(state 0))
             (printf "--doing stuff       state:~A~N" state)
             (loop (call/cc cc)(+ state 1)))))      ;this is where the exit hapens
       (thread-2
         (lambda (data)                             ;returns the procedure to be used as 
           (lambda (cc)                             ;thread with data bound
             (let loop ((cc cc)(data data)(state 0))
               (printf "--doing other stuff state:~A~N" state)
               (loop (call/cc cc)(update data)(+ state 1)))))))
  (let main ((cur thread-1)(idle (thread-2 '()))(state 0))
    (printf "doing main stuff    state:~A~N" state)
    (if (< state 6)
        (main (call/cc idle) cur (+ state 1)))))

Welche Ausgaben

doing main stuff    state:0
--doing other stuff state:0
doing main stuff    state:1
--doing stuff       state:0
doing main stuff    state:2
--doing other stuff state:1
doing main stuff    state:3
--doing stuff       state:1
doing main stuff    state:4
--doing other stuff state:2
doing main stuff    state:5
--doing stuff       state:2
doing main stuff    state:6