Folds and continuation-passing-style
In normal, direct-style programming in (mostly-)functional languages such as scheme and ML, folding is an operation that crops up all the time in various guises. Most list-manipulation libraries for such languages include implementations of left-fold and right-fold as standard. But what about the situation when you’re programming in continuation-passing style (CPS), such as when you’re writing (or trying to write) a metacircular evaluator? Library support for continuation-passing folds isn’t nearly as common.
Here’s the direct-style left-fold function:
(define (foldl kons knil xs)
(if (null? xs)
knil
(foldl kons (kons (car xs) knil) (cdr xs))))
and here’s the continuation-passing left-fold function:
(define (foldl-k kons knil xs k)
(if (null? xs)
(k knil)
(kons (car xs) knil (lambda (v) (foldl-k kons v (cdr xs) k)))))
Note that kons takes three arguments here, where in the direct-style version, it takes two.
One benefit of having CPS folds available is that they expose more control over the loop. For instance, using a normal fold, there’s no way to terminate the iteration early, but using a CPS fold, your three-argument kons routine can simply omit invoking its continuation parameter (presumably choosing some other continuation to run instead). This means that operations like (short-circuiting) contains?, any, and every can be written with CPS fold, but not with plain direct-style fold:
(define (contains? predicate val elements)
(foldl-k (lambda (elt acc k)
(if (predicate elt val)
#t ;; note: skips the offered continuation!
(k acc)))
#f
elements
(lambda (v) v)))
13 comments June 11th, 2007 tonyg