The simplest example of backward continuation in a Scheme without an explicit mutation

Question

I wrote a small Schema interpreter in C # and realized that the way I implemented it, it was very easy to add support for the right sequels.

So, I added them ... but I want to "prove" that they added them correctly.

The translator of My Scheme, however, does not have support for the “mutating” state - everything is the same.

So it was pretty easy to write unit test to bring up the continuation:

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

However, I also want to write a unit test, which demonstrates that if the continuation is "slipping away" then it still works:

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

But, of course, the above will simply verify that “I have a sequel” ... no, that is really a valid continuation.

However, all the examples I can find always use "set!". to demonstrate accelerated sequel.

What is the simplest example of a scheme that demonstrates proper support for backward continuation without relying on a mutation?

Are reverse extensions any use without mutation? I am beginning to suspect that this is not so, because you can only use it to repeat the same calculation ... which is pointless if there are no side effects. Is this why Haskell has no sequels?

Answer 1

I don’t know if this is the easiest, but here is an example of using reverse extensions without calling set! or similar:

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

This should be rated as 8 .

A little more interesting is:

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

which calculates 6! (that is, it should be rated as 720 ).

You can do the same with 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 syntax highlighting is inefficiently generated by the scheme.)

Answer 2

I think that you are right - without a mutation, reverse continuations do nothing, that further continuation cannot.

Answer 3

Here is the best I came up with:

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

Not surprisingly, this is the opposite continuation, which I then “call” with the actual function that I want to call, a function that returns the number 5.

Oh, and I also came up with this as a good unit test case:

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

I agree with Jacob B - I do not find this useful without a volatile state ... but will still be interested in a counter example.

Answer 4

Functional Streams:

You can use a recursive loop to update state without mutation. including the state of the next sequel to be named. Now it is more complicated than the other examples given, but all you really need is a thread-1 and main loop. Another thread and the “update” function show that the continuation can be used for a more than trivial example. Also, for this example, you need an implementation called let. This can be converted to an equivalent form created using define statements.

Example:

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

What are the exits

 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