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)))))
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
routine can simply omit invoking its continuation parameter (presumably choosing some other continuation to run instead). This means that operations like (short-circuiting)
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)))