scheme: how to use call/cc for backtracking

Question

I have been playing around with continuations in scheme (specifically guile) over the last couple of days and am a little puzzled by the results that some of the functions have and was wondering if anyone could explain exactly what is going on here.

There is a function called (get-token) that will retrieve the next found token in a given file. For example, if the next 3 tokens were "a", "b", and "c", calling (get-token) would return "a" the first time it is called, "b" the second time it is called, and "c" the third time it is called.

What I would like to do is have a function (peek-token) that will call (get-token), return the token, and then return to a state before the (get-token) function was called. I have attempted a number of different methods to achieve this result, and the one I currently have is:

;; make things a little easier to write
(define-syntax bind/cc
  (syntax-rules ()
    ((bind/cc var . body)
     (call/cc (lambda (var) . body)))))

;; function should return next token and then
;; revert to previous state
(define (peek-token)
  (bind/cc return
           (let ((token (get-token)))
             (return token))))

How I understand it right now, the bind/cc will save a continuation at the first return and then execute the following block of code. Then when return is hit again, the program jumps back to where the continuation was bound and the token value is given as a result.

However, when I run the above function the results are exactly the same as the original (get-token) function.

I would be very grateful if anyone could explain where I am going wrong, or express a better way to get the same result (I know some people hate going the way of call/cc).

Answer 1

To hack a Mark Twain misquote to pieces: The reports of call/cc's capabilities are greatly exaggerated.

More specifically, call/cc captures call state, not program state. That means that it captures information about where the flow of code goes when the continuation is invoked. It does not capture information on variables, and in particular, if your get-token saves its iteration state by set!ting a variable, that is not going to be restored when you invoke your continuation.

In fact, your expression of (call/cc (lambda (k) (let ((token (get-token))) (k token)))) should behave identically to simply (get-token); there should not be any observable differences between the two expressions.