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 think you're right -- without mutation, backwards continuations do nothing that forward continuations can't.

Answer 2

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 3

Here's the best I've come up with:

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

Not amazing, but it is a backwards continuation which I then "call" with the actual function I wish to invoke, a function that returns the number 5.

Ah and I've also come 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 don't think it's that useful without mutable state... but would be still be interested in a counter-example.