# Call with Current Continuation as Recursive Return

## Use of Call/CC in Scheme to “return” early from recursive definitions

## What is a Continuation

When a function calls another function, it waits for a return value to do something with. For example, in the expression `(+ 1 (f x))`

,`(+ 1 _)`

is the continuation for the execution of `(f x)`

. The continuation is what is going to handle and what is waiting on the return value from `(f x)`

.

## Call/CC

call/cc takes a lambda expression with a single argument, and passes the current continuation to the function as its argument.

`(+ 1 (call/cc `

(lambda (cont)

(cont 5))))

This code is fairly simple, but we can see the current continuation `( + 1 _) `

gets passed to the lambda expression as `cont`

.

`cont`

is itself a lambda expression, if we call it with an argument it will take that argument as the argument to the continuation and execute the continuation. We can use this almost like returning from a function. We can pass a value straight to the function’s continuation instead of waiting for the function to exit normally.

In the example above, we simply pass 5 to `cont`

. `( + 1 5)`

then gets executed and this snippet exits with a value of 6.

Lets look at another 2 code snippets

`(+ 1 (call/cc `

(lambda (cont)

(+ 3 3))))

And

`(+ 1 (call/cc `

(lambda (cont)

(cont 5)

(+ 3 3))))

The first snippet simply exits with a value of 7, doing nothing with the continuation. The second however, passes 5 straight to the lambda’s continuation immediately when `cont 5`

is executed. Thus, this lambda will never actually execute `(+ 3 3)`

, and the snippet will exit with value 6. In this case, `cont 5`

is similar to

in another language. We have effectively returned from the function early.**return** 5

There are various uses of continuations, but one interesting one is an early return from a recursive function.

## Application with Multiplying Elements of a List

First define a function `multListNoCC`

which takes a list of numbers and multiplies them together recursively.

`(define multListNoCC `

(lambda (lat)

(cond

((null? lat) 1)

(#t (* (car lat) (multListNoCC (cdr lat)))))))

However, this algorithm can be made more efficient. If any element in the list is a zero, we know the final product must be zero. Therefore we can stop multiplying the elements and just return zero as the product, rather than continuing to traverse the list. However, if we just add a case in the function to return zero, it the zero will just get passed back up the recursive stack. We can use call/cc to “pop out” of all the recursive calls and return a 0 to the original caller. For example:

`(define multList `

(lambda (lat)

(call/cc (lambda (cont)

(letrec ((helper (lambda (x)

(cond

((null? x) 1)

((eq? (car x) 0) (cont 0))

(#t (* (car x) (helper (cdr x))))))))

(helper lat))))))

In the function `multList`

, `helper`

is almost exactly the same as `multListNoCC`

. We wrap helper in a few lambdas that let it have access to the original CC that the function was called from as well as the list we want to multiply. We can then add another condition to helper: when the current element equals zero, immediately stop the recursion and pass a zero to the original continuation. ie: `((eq? (car x) 0) (cont 0))`

`cont`

is the CC before the recursion started — the original caller, so passing a value to `cont`

effectively stops the recursion and returns a value straight back.

If a zero is never encountered, the function will return normally by passing values all the way back up the recursive stack.

## More examples and applications

`(define isNumInList`

(lambda (lat num)

(call/cc (lambda (cont)

(letrec ((helper (lambda (l n)

(cond

((null? l) #f)

((eq? (car l) n) (cont #t))

(#t (helper (cdr l) n ))))))

(helper lat num))))))

If we have found an instance of the number, there is no need to continue traversal.

If we get all the way down to the end of the list and haven’t found the element, pass an #f all the way back up to signal that we haven’t found the number.

`(define findFirstNumInList`

(lambda (lat num)

(call/cc (lambda (cont)

(letrec ((helper (lambda (l n index)

(cond

((null? l) -1)

((eq? (car l) n) (cont index))

(#t (helper (cdr l) n (+ index 1)))))))

(helper lat num 0))))))

Much like isNumInList but returns the index of the found element (or -1 if the element is not in the list.