How to write a Scheme function that uses call/cc to calculate factorial?

Question

I've recently started learning Scheme, and have written a function to compute factorials using CPS:

(define (fact-cps n k)
  (if (<= n 1)
      (k 1)
      (fact-cps (- n 1)
           (lambda (r)
            (k (* n r))))))

I know that call/cc can construct the continuation of current expression, which should avoid explicitly passing the continuation parameter k in the function. I'm not quite sure how to do this, though; can you give any hints?

Answer 1

I think you misunderstand what call/cc does. Imagine you write the code (+ (* 2 3) (* 4 5)). The order of execution of (* 2 3) and (* 4 5) is not known since the implementation can do it any way. A Scheme that does CPS-conversions might make something like this:

(*& 4 5
    (lambda (v1)
      (*& 2 3
          (lambda (v2)
            (+& v1 v2 halt)))))

So imagine instead of 5 we have (call/cc (lambda (k) (k 33))). It will force the first *& to never happen and rather just call the continuation with 33 as the first multiplication.

In this regard you can use the argument call/cc function gets, aka the continuation, as a goto that you have available even though you don't write in CPS style. Eg. this is typical:

(define (pair-up lst)
  (call/cc 
   (lambda (abort)
     (let helper ([lst lst])          
       (cond [(null? lst) '()]
             [(null? (cdr lst)) (abort '())]
             [else `((,(car lst) ,(cadr lst)) 
                     ,@(helper (cddr lst)))])))))

(pair-up '(1 2 3 4))   ; ==> ((1 2) (3 4))
(pair-up '(1 2 3 4 5)) ; ==> '()

Without call/cc you'll need avoid filling the stack by making nested continuations for the default and rather throw these in the situation where we have odd elements. Of course, it's just as simple todo 2 passes where the first one just counts the elements. The big O would be the same and doing it in one pass can be thought of as micro optimization.