Continuation Passing Style in C and the Cost of Tail-call Elimination with GCC
Dave Mason · 1999
Continuation-Passing-Style has been used as a programming style as well as a compilation technique in functional programming languages for over 20 years. Recently it has been discovered that CPS resolves a longstanding structural problem in the composition of software reliability. While this provides yet another argument in favour of functional programming, the broad acceptance of the technique requires a convenient embedding of CPS in C. This paper explores several possible approaches to expressing CPS in C. The largest problem to deal with is the general lack of tail-call elimination. Several features in GCC provide possible solutions, and the relative costs are explored. 1 Introduction For over 20 years Continuation-Passing-Style (CPS) has been a convenient approach to building compilers for functional languages including Scheme, ML, and Haskell. Current software reliability estimation methods use testing of complete systems to obtain failure data which drives underlying mathematic...