Exemple le plus simple de continuations arrières dans Scheme sans mutation explicite

Question

J'ai écrit un petit interpréteur Scheme en C#, et j'ai réalisé que de la façon dont je l'avais implémenté, il était très facile d'ajouter un support pour des suites correctes. Donc, je les ai ajoutés ... mais je veux "prouver" que leur façon de les ajouter est correcte.

Mon interpréteur Scheme ne supporte cependant pas l'état de "mutation" - tout est immuable.

Il était assez facile d'écrire un test unitaire pour exposer « vers le haut » continuations:

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

Cependant, je veux aussi écrire un test unitaire qui démontre que si la poursuite « échappe », alors que toujours fonctionne aussi:

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

Mais bien sûr, le serait au-dessus de tout tester: « Je suis une suite » ... pas que c'est en fait une continuation valide. Tous les exemples que je peux trouver, cependant, finissent toujours par utiliser "set!" pour démontrer la continuation échappée.

Quel est l'exemple de schéma le plus simple qui démontre un support approprié pour les continuations vers l'arrière sans dépendre de la mutation?

Les continuations vers l'arrière sont-elles utilisables sans mutation? Je commence à soupçonner qu'ils ne le sont pas, parce que vous ne pouviez l'utiliser que pour refaire exactement le même calcul ... ce qui n'a pas de sens s'il n'y a pas d'effets secondaires. Est-ce la raison pour laquelle Haskell n'a pas de suites?

Answer 1

Je ne sais pas si cela est le plus simple, mais voici un exemple d'utilisation en arrière continuations sans appel à set! ou similaire:

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

Cela devrait évaluer à 8.

Un peu plus intéressant est la suivante:

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

qui calcule 6! (qui est, il faut évaluer à 720).

Vous pouvez même faire la même chose avec let*:

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

(. L'homme, la mise en évidence de la syntaxe de stackoverflow échoue massivement sur le schéma)

Answer 2

Je pense que vous avez raison - sans mutation, les continuations en arrière ne font rien que les continuations en avant ne peuvent pas.

Answer 3

Voici le meilleur que je suis venu avec:

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

Pas étonnant, mais c'est une continuation en arrière que j'appelle alors avec la fonction que je souhaite appeler, une fonction qui renvoie le chiffre 5.

Ah et je suis aussi venu avec cela comme un bon cas de test unitaire:

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

Je suis d'accord avec Jacob B - Je ne pense pas qu'il soit utile que sans état mutable ... mais je être toujours intéressé par un contre-exemple.

Answer 4

Threads fonctionnels:

Vous pouvez utiliser une boucle récursive de mettre à jour l'état sans mutation. y compris l'état de la prochaine continuation à appeler. Maintenant, c'est plus compliqué que les autres exemples donnés, mais tout ce dont vous avez vraiment besoin est la boucle thread-1 et main. L'autre thread et la fonction "update" sont là pour montrer que les suites peuvent être utilisées pour plus d'un exemple trivial. De plus, pour que cet exemple fonctionne, vous avez besoin d'une implémentation avec let let. Cela peut être traduit en une forme équivalente faite avec des instructions define.

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

qui sort

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