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 return 5 in another language. We have effectively returned from the function early.

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.

About the author

Eric Breyer is a computer science undergrad at Rice University. You can find him at his website, as well as on GitHub and LinkedIn.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store