Curio
Curio

Reputation: 1371

Draw the call stack for a cc/call in Racket

Everyone says that with call/cc the stack is saved and then restored back when I call the continuation. In literally all answers and questions here, I've never seen a picture of their explanations with the stack. Fine, so I decided to draw the stack in order to understand the mechanism better. For me right now, call/cc is just like a goto with the possibility to carry a value (e.g. when calling (my-continuation 4)), but I think I'm wrong.

Consider this example. I'm going to draw the stack step by step.

#lang racket

(define saved-cont #f) ; place to save k
(define (test-cont)
   (let (( x 0))
     (call/cc
       (lambda (k) ; k contains the continuation
               (set! saved-cont k))) ; here is saved
     ;; this *is* the continuation
     (set! x (+ x 1))
     (display x)
     (newline))          ;; ADDR 6789
)                           

(test-cont) ;; = > 1       ADDR 1234
(saved-cont) ;; = > 2

First thing first, we call (test-cont).

Our stack looks like this:

STACK:
- Return address from (test-cont), i.e. ADDR 1234 in the code above

Then it's time for the let. The (let ((x 0)) ...) gets traslated into ( (lambda(x) ...) 0), so:

STACK:
- Return address from (test-cont), i.e. ADDR 1234 in the code above.
- Return address from lambda (let), i.e. ADDR 6789.
- x 0

Now call/cc gets called and I don't know if the stack is saved in this exact moment. Let's say it does, so the saved stack is:

STACK:
- Return address from (test-cont), i.e. ADDR 1234 in the code above.
- Return address from lambda, I mean let, i.e. ADDR 6789.
- x 0

Then we save the corrent continuation into k, we increment x, display its value (i.e. 1), get out from the let (which is just a lambda, hence the stack frame of this lambda is discarded) and finally come back right before (saved cont), i.e. at ADDR 1234.

Now I invoke the continuation, hence I go at call/cc like it's a goto and I restore the saved stack:

STACK:
- Return address from (test-cont), i.e. ADDR 1234 in the code above.
- Return address from lambda, I mean let, i.e. ADDR 6789.
- x 0

Sadly, this is all wrong, because:

  1. x is 1, so it will be printed 2 after the increment.
  2. If the continuation returned from (test-cont) right before (saved-cont) at ADDR 1234, I would end up in a loop, but it doesn't.

For point number 2), I checked this question Scheme Continuation: What's the difference between call 'call/cc' in top level and non-top level?, but still didn't really get why it doesn't loop (see question 2 below). I mean, the continuation should be:

(set! x (+ x 1))
(display x)
(newline)) 

AND finally (saved-cont), but according to the output, (saved-cont) is not part of the continuation (and in fact it doesn't loop)!

So, my questions are:

  1. How does the stack look like while executing the code above step by step (like I tried it before, but without success)? The debugger of DrRacket is helpful, but it doesn't say anything about return addresses.
  2. Consider the code (test-cont) or (saved-cont) (i.e. the code OUTSIDE the functions). Can I consider it like the main function? I mean, (test-cont) is called when I run the program, so it must be inside a kind of main function! But if it's a main function (and so I save the return address to that point when I call (test-cont) ), why doesn't the code loop when I call (saved-cont)?
  3. At which point is the stack actually saved? When I call call/cc? Or at another point?
  4. Why is x equal to 1 when I call (saved-cont)? When I reach call/cc at the beginning, the value of x is 0.

More than the output of the code, I'd like to understand why that happens, the mechanism. Actually, thanks to reverse-engineering examples and thumb rules I can guess the output of snippets with call/cc (even the example above), but I never got why it behaves like that! Thanks in advance :)

Upvotes: 1

Views: 70

Answers (0)

Related Questions