CPS Conversion

Of the many things that I learned in Type Systems last year, CPS conversion was the one topic that was conceptually very simple, but for some reason extremely difficult to wrap my head around. Now, of course, going through Tom Murphy's thesis proposal, I realize that I don't understand CPS very well, and I am trying to go back and get a better feel for it.

As I said, CPS conversion is conceptually simple:
To every function we add an extra argument that represents the contiuation. This makes the control flow explicit, because instead of having to propagate the result of function application back up the stack to someone who knows how to use it, we have an argument 'k' that represents what we must do after the result of the application. It is somewhat analagous to passing a GOTO along with every function.

That being said, when I see the conversion rule for function application;

CPS(e1 e2,k) = CPS(e1, \f. CPS(e2,\x. f(x,k)))

my brain often begins to hurt.

So far I have found three links discussing the issue. The last one seemed to be the most helpful, but maybe that is only because I first read the other two.

• http://www.cs.cornell.edu/courses/cs611/2005fa/lectures/lec13-fa04.pdf
• http://www.cs.utah.edu/classes/cs7520/cps.pdf
• http://www.cs.berkeley.edu/~aiken/cs264/lectures/cps_code_generation