CODEWITHSUNDEEP
schemecallcccontinuation
Jean
Jean

Reputation: 621

Call Continuation CC in Scheme

I'm completly lost with the call continuation in Scheme. Can someone help me with this example ?

 #lang scheme


(define a-continuation '*dummy-value*)

(define (myfunction what? l)
  (cond ((null? l) 0)
        ((what? (car l)) 
         (+ 1 (call/cc (lambda (f)
                         (set! a-continuation f)
                         (myfunction what? (cdr l))))))
        (else (myfunction what? (cdr l)))))

(myfunction number? '(18 16 2015 2))

(a-continuation 2014)

I understand the first result (3) but I don't understand the result 2017.

Upvotes: 2

Views: 250

Answers (3)

Rptx
Rptx

Reputation: 1189

This can be really confusing. But maybe a simpler example can help (taken from here:

(define return #f) 

(+ 1 (call/cc 
       (lambda (cont) 
         (set! return cont) 
         1))) ;; <--- (+ 1 1)
 > 2
 (return 22)
 > 23

When you evaluate the (+ 1 (call/cc ...)) You get 2. Because the return value of the (call/cc ...) part is 1. Now we have set return to be cont in call/cc. In this scope, cont is a procedure that takes 1 argument. And when called, it will evaluate to that argument. Here is the interesting part, when you evaluate the procedure, evaluation is resumed at the spot of the call/cc. So when you call (return 22) It will evaluate to 22 up there in (+ 1 (call/cc ...)), resulting in 23.

Hope this is clear. In the page I linked to there are other more complex examples.

Upvotes: 0

Sylwester
Sylwester

Reputation: 48745

When calling (myfunction number? '(18 16 2015 2)) you will have a-continuation set to the continuation of each iteration and the last one when it has processed 18, 16, and 2015 and processing 2.

When calling (a-continuation 2014) you go back to the processing of 2 but instead of recursing you tell the answer to the continuation is 2014, thus you get (+ 1 (+ 1 (+ 1 (+ 1 2014)))) ; ==> 2018

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66371

I get this

> (myfunction number? '(18 16 2015 2))
4
> (a-continuation 2014)
2018

but this "to the best of my knowledge" explanation should still work.

(I expected the continuation to add 1 to its argument. I was wrong, so I'm trying to explain this to myself, too.)

If you remove the continuation parts, myfunction is a function that counts for how many elements the predicate what? holds.

Playing around a little in the REPL/interaction window,

> (myfunction number? '(1))
1
> (a-continuation 1)
2
> (a-continuation 2)
3

> (myfunction number? '(1 2 3 4 5 6 7 8 9 10))
10
> (a-continuation 1)
11
> (a-continuation 2)
12
> (a-continuation 3)
13

> (myfunction even? '(1 2 3 4 5 6 7 8 9 10))
5
> (a-continuation 1)
6
> (a-continuation 2)
7
> (a-continuation 3)
8

One can suspect from this pattern that the continuation adds to its argument the number of elements that myfunction found.

This is my explanation of why this is so:

If you view each call/cc as a "hole" that you can fill in later by calling the captured continuation, the first one is

(+ 1 <hole>)

the second 

(+ 1 (+ 1 <hole>))

and so on, creating a "chain" of additions, one for each time the predicate holds.
(I.e. capturing the entire recursion that's "waiting" for the continuation to continue, not just the innermost call.)

So 

(myfunction number? '(18 16 2015 2))

creates something that looks like

(+ 1 (+ 1 (+ 1 (+ 1 <hole>))))

and when you call the continuation,

(a-continuation 2014)

you evaluate

(+ 1 (+ 1 (+ 1 (+ 1 2014))))

which is, of course, 2018.

(Disclaimer: This may be completely wrong.)

Upvotes: 3

Related Questions