[plt-scheme] Re: CPS conversion example, question

From: John Clements (clements at brinckerhoff.org)
Date: Wed Jan 9 18:53:45 EST 2008

On Jan 9, 2008, at 3:35 PM, Grant Rettke wrote:

> On Jan 9, 2008 3:46 PM, Grant Rettke <grettke at acm.org> wrote:
>> Is that the right way to do it?
>
> I actually skipped a transformation in the end, so this is what it
> should have been:
>
> ;; Let style
> (define (pyth-ls x y k)
>    (let ([x2 (* x x)])
>      (let ([y2 (* y y)])
>        (let ([x2py2 (+ x2 y2)])
>          (let ([result (sqrt x2py2)])
>           (k result))))))
>
> ; CPS Style
> (define (pyth-cps x y k)
>   ((λ (x2)
>      ((λ (y2)
>         ((λ (x2py2)
>            ((λ (result)
>                (k result)) (sqrt x2py2))) (+ x2 y2))) (* y y))) (* x  
> x))

Terse answer: no, or at least not any more CPSed than your original.   
If you're imagining +,*, and sqrt as atomic, then this is in CPS form:

(define (pyth-cps x y k) (k (sqrt (+ (* y y) (* x x)))))

If, however, you're imagining that +,*, and sqrt are not atomic and  
need to be called with continuations, then the result is going to look  
something like this:

(define (pyth-cps x y k)
   (* x x
      (lambda (x2)
        (* y y
           (lambda (y2)
             (+ x2 y2
                (lambda (x2py2)
                  (sqrt x2py2
                        (lambda (result)
                          (k result))))))))))

(note that I haven't tried running this).

The point is that all of the cps-ed procedures can occur only in tail  
position.

John



Posted on the users mailing list.