schemelispracket

Is this continuation passing style?


If function a has cc as its CPS function, and cc calls a, is a continuation passing style? For example,

(def a
    (lambda (b c)
        ...
        (a (cons (c (car b))) c))) 

(def cc
     (lambda (d)
          ...
          (fold a x y)
          (fold a u v)
...

(a '((1 2) 3) cc)

Solution

  • A lot of code written in continuation-passing-style isn't strictly continuation-passing-style, because there are some calls that don't pass their results to a continuation. Even so, the code you've written probably wouldn't be classified as CPS or even sort of semi-CPS. The point of continuation passing style is that instead of returning some result from the function, the function takes an additional argument, called the continuation, and calls that function with the "result". For instance, a CPS function to sum the elements of a list might look like:

    (define (sum-list lst k)
      (if (null? lst)
        ;; if the list is empty, then call the continuation
        ;; with the sum of the empty list, i.e., zero.
        (k 0)
        ;; Otherwise, compute the sum of the rest of the list,
        ;; but with a different continuation that will take
        ;; the sum of the rest of the list, add the first 
        ;; element of the list, and call the original continuation,
        ;; k, with that combined sum.
        (sum-list (cdr lst)
                  (lambda (sum)
                    (k (+ (car lst) sum))))))
    

    That's not strictly CPS, though, since some of the functions, namely car, cdr, and + aren't CPS; they're returning their results to their caller, not calling a continuation with the result.

    Now let's have a look at the code you've provided:

    (def a
        (lambda (b c)
            ...
            (a (cons (c (car b))) c))) 
    

    In Scheme, this would be written

    (define (a b c)
       ...
       (a (cons (c (car b))) c))
    

    The call to cons has the wrong number of arguments, but aside from that, there's no clear call to a continuation function. You're using c in a function position, so you are taking advantage of higher-order functions, and you're making a recursive call to a, but it's not anything that's obviously continuation passing style. In your second block:

    (def cc
         (lambda (d)
              ...
              (fold a x y)
              (fold a u v)
    

    it's not really clear what you're trying to accomplish. Fold isn't being used in a CPS way, and you're ignoring the results of the first call to fold. There's nothing here that looks like CPS style. In the final bit,

    (a '((1 2) 3) cc)
    

    you're calling a with a literal list and with cc, which is now, presumably, defined as a function. Passing functions around is working with first-class functions, but that doesn't make it continuation-passing style.