Scheme - converting to continuation-passing style

Question

I kinda understand how to convert elementary functions such as arithmetics to continuation-passing style in Scheme. But what if the function involves recursion? For example,

(define funname 
     (lambda (arg0 arg1)
                (and (some procedure)
                      (funname (- arg0 1) arg1))))

Please give me advices. Thank you in advance.

Answer 1

(define (func x y k)
  (some-procedure
   (lambda (ret)
     (if ret
         (- x 1
            (lambda (ret)
              (func ret y k)))
         (k #f))))

You are lacking a base case, which is why the only explicit call to the continuation is (k #f). If you have a base case, then you'd pass the base case return value to the continuation, also. For example:

(define (func x y k)
  (zero? x
         (lambda (ret)
           (if ret
               (k y)
               (some-procedure
                (lambda (ret)
                  (if ret
                      (- x 1
                         (lambda (ret)
                           (func ret y k)))
                      (k #f))))))))

Answer 2

One place that has a good explanation on continuations and CPS is Krishnamurthi's PLAI book. The relevant part (VII) doesn't depend on other parts of the book so you can jump right in there. There is specifically an extended example of converting code to CPS manually, and tackling recursive functions (the first part of chapter 17).

In addition, I wrote an extended version of that text for my class, which has more examples and more details on the subject -- you might find that useful too. In addition to the PLAI text, I cover some common uses of continuations like implementing generators, the ambiguous operator and more. (But note that PLAI continues with a discussion of implementation strategies, which my text doesn't cover.)

Answer 3

This partly duplicates Chris Jester-Young's answer, but well, I hope I can explain it better :-).

In CPS, the difference you're seeking is between these two things (roughly):

• You can invoke a procedure, and pass it the continuation you were passed. That's the equivalent of a direct-style optimized tail call.
• Or, you can invoke a procedure, and pass in as its continuation a new procedure that does something with the "return value," passing in your original continuation. This is the equivalent of a direct-style stack call.

The latter is what the lambdas in Chris's example are doing. Basically, evaluating a lambda creates a closure—and these closures are used to do the same job that stack frames do in the execution of a a direct-style program. In place of the return address in a stack frame, the closure contains a binding for a continuation function, and the code for the closure invokes this.