Why continuation passing style
Asked Answered
L

2

29

In The Scheme Programming Language by Kent Dybvig (4th edition) section 3.4, he describes very clearly what continuation passing style is. For the why he gives two reasons:

  1. pass more than one result to its continuation, because the procedure that implements the continuation can take any number of arguments.
  2. CPS also allows a procedure to take separate continuations ..., which may accept different numbers of arguments.

Since the first reason can also be done using the values procedure and the second using case-lambda, I'm not clear the advantages of using continuation passing style. Could someone show me some examples of where continuation passing style is appropriate, where it makes the code better, clearer, etc.?

Limited answered 17/12, 2011 at 10:33 Comment(0)
P
17

Dybvig uses the explicit continuations in this section to motivate having call/cc as part of the language. The main point is made near the end of the section when he mentions that writing code without it requires a global tranformation of all code that is used, including functions that you call. So in Scheme you usually build your own construct using macros, and continuations are one of these useful constructs -- but you cannot implement them via macros since they implement only local transformations.

But using a CPS style directly can still be useful: for example, as he mentions, you could write a function that has more than one continuation, possibly with different arrities -- like a parsing function that receives a single-input function to send a parses value to and a nullary failure function to call when parsing fail (and this function might abort with an error or backtrack and try using other parsing rules). Another possible use is when you want to control exactly what goes into the continuation rather than letting call/cc grab the full context.

There also the obvious case of writing code in a language that has no first-class continuation, making CPSed code your only choice. An example of that would be lots of node.js programs that use IO and pretty much force you to write code in explicit CPS.

Pulpy answered 17/12, 2011 at 15:38 Comment(0)
G
8

Since the first reason can also be done using the values procedure and the second using case-lambda I'm not clear the advantages of using continuation passing style.

...except that the definition of values specifies that it calls its continuation with multiple arguments.

My favorite example of a problem where continuation passing style is helpful is writing pattern matchers. This is a kind of macro that's like case on steroids; it takes a value and tries to match its structure against a sequence of patterns built from pairs, symbols (standing for variables) and non-symbol atoms (standing for values). If a match succeeds, then it binds the identifiers in the pattern to the corresponding subparts of the value, and executes a consequent for that pattern. If it fails, then it tries the next pattern.

It's pretty straightforward to write this sort of macro in a form of continuation passing style, using two different continuations to represent "what to do if a match succeeds" (the success continuation) and "what to do if a match fails" (the failure continuations).

Take this (simplified) fragment of a pattern matching macro I once wrote (I apologize if you don't know syntax-case or syntax-rules; and since I adapted it on the fly, I sure hope it works too!). I'm going to focus on the rule that matches a pair pattern. This is a pattern that consists of a pair of two patterns, a head pattern and a tail pattern; it matches pairs whose head matches the head pattern and whose tail matches the tail-pattern.

;;;
;;; Outer "driver" macro; the meat is in pmatch-expand-pattern.
;;;
(define-syntax pmatch
  (syntax-rules ()
    ((pmatch value-expr (pattern . exprs) . clauses)
     (let* ((value value-expr)
            (try-next-clause
             (lambda () (pmatch value . clauses))))
       (pmatch-expand-pattern pattern
                              value
                              ;; success-k
                              (begin . exprs)
                              ;; failure-k
                              (try-next-clause))))))

(define-syntax pmatch-expand-pattern
  (lambda (stx)
    (syntax-case stx ()

      ;; Cases for constants and quoted symbols omitted, but they're trivial.

      ;; Match a pair pattern.  Note that failure-k is expanded three times; 
      ;; that's why pmatch encapsulates its expansion inside a thunk!
      ((pmatch-expand-pattern (head-pat . tail-pat) value success-k failure-k)
       (syntax
        (if (pair? value)
            (pmatch-expand-pattern head-pat 
                                   (car value)
                                   ;; If we successfully match the head, then
                                   ;; the success continuation is a recursive
                                   ;; attempt to match the tail...
                                   (pmatch-expand-pattern tail-pat
                                                          (cdr value)
                                                          success-k 
                                                          failure-k)
                                   failure-k))
            failure-k))

      ;; Match an identifier pattern.  Always succeeds, binds identifier
      ;; to value
      ((pmatch-expand-pattern identifier value success-k failure-k)
       (identifier? (syntax identifier))
       (syntax (let ((identifier value)) success-k)))
      )))

Note the success-k and failure-k subforms in the pmatch-expand-pattern macro expressions. These represent expressions that are being used as the "continuation," in a slightly loose term, for the pattern matcher. The success continuation is used when the pattern under consideration matches the value under consideration; the failure continuation is used when it doesn't. The success continuation is, depending on whether we've matched all of the current top-level pattern yet, either an expression that will match the rest of the pattern, or the consequent that we execute when a pattern is done matching. The failure continuations are used when a pattern fails to match, in order to backtrack to the next choice point.

As I mentioned, the term "continuation" is being used a bit loosely in the code above, since we're using expressions as continuations. But this is just a detail about how to implement this as a macro—the algorithm could be implemented purely at runtime with actual procedures as the continuations. (Also, the try-next-clause procedures are continuations in the literal sense.)

Grundyism answered 18/12, 2011 at 1:43 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.