scheme continuation inside a for-each

Question

I'm currently studying Scheme for a course at my university, while looking at some exercises I got stuck on this particular one. Professor has yet to answer my previous mails therefore I have more chances to receive an answer here faster.

Given this code

(define (list-iter-cc lst)
  (call/cc 
    (lambda (return) 
      (for-each               
          (lambda (x)
            (call/cc (lambda (next-step)
                       (return (cons x next-step))))) 
          lst)
     'end)))

I have to use it to write the iter macro whose syntax is

(iter <a variable symbol> in <a list> <code>)

example:

(iter x in '(1 2 3) 
    (display x)
    (newline))

Since I couldn't understand list-iter-cc i went to see the solution, which i don't understand as well. The solution:

(define-syntax iter2
  (syntax-rules (-> in)
    ((_ var in lst code ...)
     (let loop ((head (list-iter-cc lst)))
       (unless (eq? head 'end)
         (let ((var (car head)))
           code ... 
           (loop ((cdr head)))))))))

To unravel the macro I tried writing the following

> (define head (list-iter-cc '(1 2 3 4)))
> head
'(1 . #<continuation>)
> (let ( (var (car head))) (display var))
1
> (define head2 (cdr head))
> (let ( (var2 (car head2)) ) (display var2))
Xxx X car: contract violation
  expected: pair?
  given: #<continuation>
>

which is exactly what I thought would happen.

list-iter-cc's return continuation is called at the first iteration of the for-each inside the first lambda, returning with cons x next-step. x is the first element of the list and next-step is a continuation.

1). what is the content of next-step? the following iteration of the for-each? how can it evaluate to 'end after the last iteration?

2). assuming that in the macro head (list-iter-cc lst) is '(1 . #<continuation>) , the car is 1 and it gets displayed, but after looping over its cdr, var (car head) will be the car of the continuation! how can it possibly evaluate to 2 and then 3 and then 'end, and why this does not happen in the code I tried writing to understand it?

Any help would be appreciated, especially one that could guide me step by step.

Will Ness Will Ness · Accepted Answer · 2017-10-26T16:46:21

We can re-write it as

(define list-iter-cc 
  (lambda (lst)
    (call/cc 
      (lambda (return) 
        (for-each               
            (lambda (x)
              (call/cc (lambda (next-step)
                         (return (cons x next-step))))) 
            lst)
        'end))))

So it's a lambda function, with a parameter named lst. When this function is called, lst is set up to hold the actual argument of the function call, as usual. Then, call/cc sets up the continuation named return to hold the current continuation ... which is what? At this point, the next-thing-to-do is just to return a value to the list-iter-cc's caller.

This means, calling (return a) will return the value of a immediately to list-iter-cc's caller, as if the function list-iter-cc finished up its calculations.

Now,

        (for-each               
            (lambda (x)
              (call/cc (lambda (next-step)
                         (return (cons x next-step))))) 
            lst)

is entered. It calls its lambda argument for each element in a list lst, which consequently gets the name x.

So, for the very fist x in a lst, what happens?

              (call/cc (lambda (next-step)
                         (return (cons x next-step))))

is called. I.e. it sets up next-step to hold the current continuation and returns from the whole function list-iter-cc at once!

What does it return? The pair (x . <next-step>). And what does it mean to call (next-step)? It means to return into the body of for-each, which will proceed to the next element in lst, if any. If not, the loop body of for-each is exited, and 'end is normally returned as last expression's value from the function list-iter-cc, which thus finishes its calculations!

So, how can we use it? For example, like this:

(define (qq lst)
  (let ([a ;; <<=                    ; control returns here
           (list-iter-cc lst)])
    (unless (eq? a 'end)             ; if it's not past-last-element
       (let ([val (car a)])          ; take the actual value
         (display val)               ; use it
         (newline)
         ((cdr a))))))               ; run the `next-step` continuation

When the continuation in (cdr a) is run, the control jumps back to list-iter-cc's call site. Remember, "the next-thing-to-do" was "just to return a value to the list-iter-cc's caller"? The outer let's body is then re-entered with the next value from the list.

This needs to be translated to a macro then, which should be straightforward.

I notice your prof used named loop there, and the macro calls (loop ((cdr a))). The continuation does not return its value though, and so the next iteration of loop is not entered because of the call to loop. The control jumps as part of the continuation, as seen in my sample function (it worked, when I tested it in DrRacket).

update: Regarding your transcript, head2 is already a #<continuation>, it doesn't have a car – it is not a pair?. Instead, see the following:

> (define head #| <<= |# (list-iter-cc '(1 2 3 4)))   ; control returns here
> head
'(1 . #<continuation>)
> (let ( (var (car head))) (display var))             ; your code
1
> ((cdr head))                                        ; this is how we run it!
> head
'(2 . #<continuation>)
>

What? Have you seen what just happened? head got redefined! And again,

> ((cdr head))
> head
'(3 . #<continuation>)
>

Why? Because running a continuation means the control returns to its call site – which, here, means "define a variable head to hold the supplied value, and return to the REPL".

scheme continuation inside a for-each

1 Answers