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

Question

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

Also habe ich sie hinzugefügt ... aber wollen "beweisen", dass sie so, dass ich sie hinzugefügt habe, korrekt ist.

Mein Scheme-Interpreter unterstützt jedoch nicht den "mutierenden" Zustand - alles ist unveränderlich.

So war es ziemlich einfach, einen Unit-Test zu schreiben „nach oben“ Fortsetzungen zu belichten:

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

Aber ich mag auch einen Komponententest schreiben, dass „entkommt“, dann die noch zeigt, wenn die Fortsetzung auch funktioniert:

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

Aber natürlich würde die oben nur testen, dass „ich eine Fortsetzung bekommen“ ... nicht, dass es tatsächlich eine gültige Fortsetzung ist.

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

Was ist das einfachste Schema-Beispiel, das die richtige Unterstützung für Rückwärts-Fortsetzungen zeigt, ohne sich auf Mutationen zu verlassen?

Sind rückwärts Fortsetzungen jede Verwendung ohne Mutation? Ich fange an zu vermuten, dass sie es nicht sind, weil Sie es nur benutzen könnten, um genau die gleiche Berechnung erneut auszuführen ... was bedeutungslos ist, wenn es keine Nebenwirkungen gibt. Haskell hat deshalb keine Fortsetzungen?

Answer 1

Ich weiß nicht, ob dies der einfachste ist, aber hier ist ein Beispiel für die Verwendung rückwärts Fortsetzungen ohne Aufruf 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 8 bewerten.

Etwas 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 6! berechnet (das heißt, sollte es zu 720 bewerten).

Sie können sogar das gleiche 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)) 

(. Man, Stackoverflow der Syntax-Hervorhebung nicht massiv auf Schema)

Answer 2

Ich denke, du hast recht - ohne Mutation, rückwärts Fortsetzungen tun nichts, das Vorwärts Fortsetzungen nicht können.

Answer 3

Hier ist das Beste, was ich gekommen bin oben mit:

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

Nicht erstaunlich, aber es ist eine Rückwärtsfortsetzung, die ich dann mit der tatsächlichen Funktion "rufe", 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 mit Jacob B zustimmen - ich glaube nicht, es ohne wandelbaren Zustand, nützlich ist ... aber würde sei immer noch an einem Gegenbeispiel interessiert.

Answer 4

Funktionale Themen:

können Sie eine rekursive Schleife verwenden Zustand ohne Mutation zu aktualisieren. einschließlich des Zustands der nächsten anzurufenden Fortsetzung. Jetzt ist das komplizierter als die anderen gegebenen Beispiele, aber alles, was Sie wirklich brauchen, ist die thread-1 und main Schleife. Der andere Thread und die "update" -Funktion 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 Namen let. Dies kann in eine äquivalente Form übersetzt werden, die mit define-Anweisungen erstellt wird.

Beispiel:

(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

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