3

In the book Lisp in Small Pieces, there is the following example code, which is intended to demo that call/cc could simulate goto.

(define (fact n)
   (let ((r 1) (k 'void))
      (call/cc (lambda (c) (set! k c) 'void))
      (set! r (* r n))
      (set! n (- n 1))
      (if (= n 1) r (k 'recurse))))

However, I'm not sure if I'm misunderstanding something, but I cannot see that this is the way call/cc would simulate goto. When k is applied in the last line, the restored continuation has the r and n of the original continuation, whose values are not changed by the two set! applications. So the entire loop will never terminate.

Is the book wrong in this example? Or did I miss anything?

Alexis King
  • 43,109
  • 15
  • 131
  • 205
Dong Feng
  • 61
  • 3

1 Answers1

1

the restored continuation has the r and n of the original continuation, whose values are not changed by the two set! applications.

Nope; that's the important part; the changes to the values are visible. They're not reset. I'm not sure whether the question should be considered a duplicate or not, but this came up in call-with-current-continuation - state saving concept as well, where the asker noted that (look at the question for the whole context):

Calling next 3 times produces 0, 1 and 'done. That means when state used the function k given by generator it didn't restore the state of the program.

You could test this very simply by printing the values of r and n after saving the continuation. You'll see that the updated values are there. For instance:

(define (fact n)
  (let ((r 1) (k 'void))
    (call-with-current-continuation (lambda (c) (set! k c) 'void))
    (display "r: ") (display r) (newline)
    (display "n: ") (display n) (newline)
    (set! r (* r n))
    (set! n (- n 1))
    (if (= n 1) r (k 'recurse))))


> (fact 6)
r: 1
n: 6
r: 6
n: 5
r: 30
n: 4
r: 120
n: 3
r: 360
n: 2
720

Related Questions:

Also see:

Community
  • 1
  • 1
Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
  • IMO there's nothing particularly special here about `k` being a continuation (in terms of understanding what happens to `n` and `r`). The important point is that it is a closure, and it closes over the same context that it is called from. – Nate C-K Feb 12 '15 at 22:22
  • 1
    @NateC-K Well, yes and no. call/cc is kind of special because it's got the whole program state saved, except that, as we see, it doesn't *copy* the environment when the program state is saved. Not many languages have a "save the whole state of the program" operation like call/cc, and I think that as a result, it's often imagined that it's like taking a snapshot of the program. The issue is that it's not really a snapshot. It's like bundling the rest of the computation up in a *closure over the current environment*. That's where the disconnect arises for a lot of people. – Joshua Taylor Feb 12 '15 at 22:25
  • That's kinda what I'm getting at, which is why I'm suggesting that some part of the answer to this should mention closures. (Your answer doesn't and none of the answers that you link to do.) – Nate C-K Feb 12 '15 at 22:33
  • So, if you would just work your above comment into your answer somehow, I think it would be a better answer :) – Nate C-K Feb 12 '15 at 22:38
  • @JoshuaTaylor I agree with your notes "it doesn't copy the environment". But my puzzle is whether n and r are part of environment or of the state. To me, they seems allocated on stack and therefore part of state. I heard that the continuation of some languages actually duplicate the full-stack. I think your conclusion is correct (and is verified by executing code) but I don't know what causes the mismatch between my understanding and the conclusion. – Dong Feng Feb 12 '15 at 23:13
  • 1
    @DongFeng Let go of "allocated on the stack" and similar semantics when working in a language as high-level as Scheme. The point is that `set!` mutates the *values* of bindings, so all scopes that close over those bindings see the results of `set!`. – Alexis King Feb 13 '15 at 04:48
  • @DongFeng Yes, like Alexis King said, the concept of stack allocated or heap allocated doesn't mean as much (though it's still relevant to the implementation). After all, if you return a closure over some local variables (e.g., `(define (over-x) (let ((x 42)) (lambda () (set! x (+ 1 x)) x)))`), you can keep calling the result and getting bigger numbers. That means that *whereever* the storage for `x` is, the environment that it's in must be preserved after `over-x` returns, because the lambda function closed over it. – Joshua Taylor Feb 13 '15 at 18:06
  • I understand and grateful for all your explanation. But I just don't want to give up the chance to understand from the perspective of "allocated on the stack." Fortunately, I find this paper _Implementation Strategies for First-Class Continuations_ in which it says explicitly that, if continuation is implemented as copying stack, on-stack variable is not allowed. – Dong Feng Feb 25 '15 at 06:28