0
$\begingroup$

I'm stuck on something in in Shan's article Shift to Control, about CPS. On page three he writes the CPS transform

x --> (lambda (c) (c x))

(lambda (x) E) --> (lambda (c) (c (lambda (x) E)))

(E1 E2) --> (lambda (c) (E1 (lambda (f) (E2 (lambda (x) ((f x) c))))))

Shouldn't the innermost expression on the third line be (c (f x)) instead? With c being the continuation applied to the value f x?

$\endgroup$

1 Answer 1

1
$\begingroup$

I would recommend trying a few examples for yourself to see how the transformation works.

Think of the CPS transformation this way:

  • Results are passed to continuations.
  • Continuations are passed to functions as the last argument.

Remember that in the application rule, f is a CPS transformed version of the lambda, not the lambda itself.

Consider transforming the identity function (lambda (x) x). You get:

(lambda (c') (c' (lambda (x) (lambda (c) (c x)))))

I have renamed the continuation in the outer lambda to make things clear. I want you to notice what this part means:

(lambda (x) (lambda (c) (c x))

This is a function of two arguments, x and c, and it returns (c x). The continuation is passed as the last argument. The effect is that a transformed lambda "swaps" the position of x with c.

When you use this function in an application, the continuation is passed as the last argument to the lambda, ((f x) c). It's not backwards, because the transformed lambda, f swaps them back into the correct order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.