leastfixedpointFolds and continuation-passing-style
Mon, 11 June 2007
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)))
Comments
On 12 June, 2007 at 1:38 pm, wrote:
On 12 June, 2007 at 2:52 pm, wrote:
Hi andrew. From what I’ve seen of your experimental language (http://www.acooke.org/cute/UnifyingOO0.html) I think you’re exploring very similar territory to me with my experimental language (http://www.eighty-twenty.org/darcsweb/index.cgi?r=smalltalk-tng;a=headblob;f=/etng-r1/boot.tng)! Have you written anything further about it?
On 12 June, 2007 at 9:00 pm, wrote:
it’s all a bit of a mess and very early but i am working on a paper. at the moment it’s as incomprehensible as the notes you linked to, but when it’s a bit more complete i’ll be happy to send you a copy.
i had a quick glance at your link and am not how how similar they are because i don’t have mutable state or continuations (which you do have, i assume, though i’m not clear how the scheme code and the smalltalk code connect).
really i need to get back to (paid!) work, but i may look again this evening. if i get distracted and you remember, send me an email in a month or two. i may even have started on an implementation by then!
On 13 June, 2007 at 1:02 pm, wrote:
But is it necessary to put the continuation code in the folding function? You could just use the continuations where you need it, e.g. a short-cicuited contains? can use the standard foldl thus:
(define (contains? predicate val elements)
(call/cc
(lambda (cont)
(foldl (lambda (elt acc)
(if (predicate elt val)
(cont #t)
#f))
#f
elements))))
On 13 June, 2007 at 1:31 pm, wrote:
See also Oleg Kiselyov’s work on the best collection traversal interface, which, amongst other things, features a “left fold enumerator supporting a premature termination”.
On 13 June, 2007 at 5:36 pm, wrote:
@Holger: You’re right, and this is the traditional way of exiting (for instance) a for-each or fold loop early in Scheme. However, what if there are no first-class continuations, no call/cc? At that point, explicit reification of the continuations involved, via the CPS foldl, becomes necessary.
On 14 June, 2007 at 10:58 am, wrote:
Ah, I see. Yes indeed that is more general.
But out of curiosity: How many languages actually guarantee the tail call optimisation needed to make the explicit CPS coding feasible? And how many of those do not offer continuations?
On 14 June, 2007 at 12:43 pm, wrote:
Good question.
Languages I know of that guarantee proper tail calls (it’s not really an optimisation, it’s more of a correctness thing ;-) ): Scheme, SML, O’Caml, Haskell. Languages that should, but don’t: Smalltalk, Javascript.
Of the properly tail-recursive languages above, only Scheme offers first-class continuations. SML/NJ has an implementation-specific extension for them. Haskell lets you work in the continuation monad for some parts of your program but provides no general continuation-reification operator.
Even in Scheme, there can be tradeoffs involved in using call/cc - some implementations make it very expensive, for instance. Sometimes explicit CPS just seems to be the Right Thing, even though call/cc is available.
On 15 June, 2007 at 5:18 pm, wrote:
In defense of Haskell (not that it was really being attacked at all), I’d probably say that the laziness gets you short circuiting for free when you need it. For example, the definition of “or” (which is || throughout a list):
or = foldr (||) False
True || _ = True
False || x = x
And it works happily on infinite lists:
Prelude> or (True: repeat False)
True
(sheesh, I hope this code doesn’t get mangled up…)
On 15 June, 2007 at 6:13 pm, wrote:
Matthew, that’s true for right folds - what about left folds?
On 16 June, 2007 at 3:36 pm, wrote:
Tony, that’s slightly a trick question.
foldr works left to right, and || shortcuts on the left, thus all is well. foldl works right to left, so if you have operators that shortcut to the right then yes, the combination of said operator with foldl would shortcut as you desire.
On 16 June, 2007 at 5:31 pm, wrote:
Sure, the kons operator will shortcut - but the left-fold will still traverse the entire list, won’t it? If that’s true, then even a shortcutting kons operator doesn’t help terminate left-folds early.
On 16 June, 2007 at 9:48 pm, wrote:
Yes, I think you’re right. The problem is that for a foldr, it’s trivial to take the head of the list and apply the operator between the head and the tail of the last. With a foldl, you need to do the inverse: finding the last elem and applying the operator between the last elem and the inits. But in order to find the last elem you’ll have to traverse the list.
It makes me wonder whether the views (Wadler, but also recently has reappeared in the dependently typed stuff) of cons as snoc would give a better angle on this. Also, maybe the amortized unit cost queues stuff would better suit this as a foldl on the whole queue is a foldr on the “reading” side followed by a foldl on the “writing” side - so long as you typically shortcut before needing the /other/ list, you’re laughing.
On 30 October, 2009 at 10:28 pm, wrote:
Looks like this thread is a bit old, but for what it’s worth, the CPS is nicly abstracted away with macros:
(See Graham’s OnLisp chapter 20). s-expr’s starting with ‘=’ are the special macros for handling passing the continuation around.
(=defun foldl-k (kons knil xs)
(if (null xs)
(=values knil)
(=bind (acc)
(=funcall kons (car xs) knil)
(foldl-k kons acc (cdr xs)))))
(defun contains? (predicate val elements)
(let ((-cont- #’identity))
(foldl-k (=lambda (elt acc)
(if (funcall predicate elt val)
t ;; note: skips the offered continuation!
(=values acc))))
nil
elements))
There’s also a decent cl-cont to facilitate Holger’s solution:
http://common-lisp.net/project/cl-cont/
thanks for posting this. i’m currently playing with an experimental (ie non-existent :o) language that includes “accumulators” in some sense (so fold can be expressed through map or sequence - it’s not a big deal except that the language is purely functional). however, it doesn’t allow short-circuits. maybe continuations is a better approach. interesting.