Simplest example of backwards continuations in Scheme without explicit mutation

Question

I've written a small Scheme interpreter in C#, and realised that the way I had implemented it, it was very easy to add support for proper continuations.

So I added them... but want to "prove" that they way that I've added them is correct.

My Scheme interpreter however has no support for "mutating" state - everything is immutable.

So it was pretty easy to write a unit test to expose "upwards" continuations:

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

However, I also want to write a unit test that demonstrates that if the continuation "escapes" then that still works too:

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

But of course, the above would just test that "I got a continuation"... not that it's actually a valid continuation.

All of the examples I can find, however, always end up using "set!" to demonstrate the escaped continuation.

What's the simplest Scheme example that demonstrates proper support for backwards continuations without relying on mutation?

Are backwards continuations any use without mutation? I am beginning to suspect that they are not, because you could only use it to execute the exact same calculation again... which is meaningless if there are no side-effects. Is this why Haskell does not have continuations?

Answer 1

I don't know if this is the simplest, but here's an example of using backwards continuations without any call to set! or similar:

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

This should evaluate to 8.

Slightly more interesting is:

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

which computes 6! (that is, it should evaluate to 720).

You can even do the same thing 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's syntax highlighting fails massively on scheme.)

Answer 2

I think you're right -- without mutation, backwards continuations do nothing that forward continuations can't.