Esempio più semplice di continuazioni all'indietro in Schema senza mutazione esplicita

Question

Ho scritto un piccolo interprete Scheme in C# e mi sono reso conto che il modo in cui l'avevo implementato, era molto facile aggiungere supporto per le corrette continuazioni.

Quindi li ho aggiunti ... ma voglio "provare" che il modo in cui li ho aggiunti è corretto.

Il mio interprete di Schema tuttavia non supporta lo stato "mutante": tutto è immutabile.

quindi era piuttosto facile scrivere uno unit test per esporre "verso l'alto" continuazioni:

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

Tuttavia, ho anche voglia di scrivere uno unit test che dimostra che se la continuazione "sfugge", quindi che ancora lavora troppo:

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

Ma, naturalmente, quanto sopra sarebbe solo verificare che "ho avuto una continuazione" ... non che in realtà è una continuazione valida.

Tutti gli esempi che riesco a trovare, tuttavia, finiscono sempre per utilizzare "set!" per dimostrare la continuazione evasa.

Qual è l'esempio Scheme più semplice che dimostra il supporto adeguato per le continue all'indietro senza fare affidamento sulla mutazione?

Le sequenze all'indietro sono utilizzabili senza mutazione? Comincio a sospettare che non lo siano, perché potresti solo usarlo per eseguire di nuovo lo stesso calcolo ... che è privo di significato se non ci sono effetti collaterali. È per questo che Haskell non ha continuazioni?

Answer 1

Non so se questo è il più semplice, ma ecco un esempio di utilizzo all'indietro continuazioni senza alcuna chiamata a set! o simili:

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

Questo dovrebbe valutare a 8.

leggermente più interessante è:

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

che calcola 6! (cioè, dovrebbe valutare a 720).

Si può anche fare la stessa cosa con let*:

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

(. L'uomo, l'evidenziazione della sintassi di StackOverflow fallisce in maniera massiccia su schema)

Answer 2

Penso che tu abbia ragione - senza mutazione, le continuazioni al contrario non fanno nulla che le continuazioni in avanti non possano fare.

Answer 3

Ecco il meglio che è venuta in mente:

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

Non sorprendente, ma è una continuazione all'indietro che quindi "richiamo" con la funzione effettiva che desidero invocare, una funzione che restituisce il numero 5.

Ah e ho anche venire con questo come un buon banco di prova unità:

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

sono d'accordo con Jacob B - Non credo che sia utile che senza stato mutevole ... ma sarebbe essere ancora interessato a un contro-esempio.

Answer 4

Discussioni funzionali:

È possibile utilizzare un ciclo ricorsivo per aggiornare lo stato, senza mutazione. compreso lo stato della prossima continuazione da chiamare. Ora questo è più complicato degli altri esempi forniti, ma tutto ciò di cui hai veramente bisogno è il ciclo thread-1 e main. L'altro thread e la funzione "update" sono lì per mostrare che le continuazioni possono essere utilizzate per qualcosa di più di un semplice esempio. Inoltre, per far funzionare questo esempio è necessaria un'implementazione con let. Questo può essere tradotto in un modulo equivalente realizzato con dichiarazioni definite.

Esempio:

(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))))) 

quali uscite

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