On the Overhead of CPS
Olivier Danvy, Belmina Dzafic, Frank Pfenning · 1996
Continuation-passing style (CPS) is often criticized to be more expensive than the usual direct style of functional programming. By structure, CPS functions indeed are passed one extra argument (the continuation), and each intermediate result indeed occurs in a function call (to the continuation). As higher-order functions, continuations are also more expensive. However, by structure also, CPS exhibits a great deal of syntactic regularity. We show how to exploit this regularity to implement CPS with two stacks --- one for continuation parameters and one for the parameters of continuations --- in a way that reduces the extra price of CPS to managing those two stacks. In effect, the stack for continuation parameters acts as a control stack for calls and returns, and the stack for parameters of continuations acts as a data stack for intermediate results. This demonstrates that CPS is just about as expensive as direct style, where calls, returns, and intermediate results also have to be de...