Cps Transformation

CPS transformation is the automated or manual transformation of a program source from direct style to ContinuationPassingStyle. Automated CPS transformation is a popular technique for the implementation of FunctionalProgrammingLanguages like SchemeLanguage or MlLanguage. See e.g. AndrewAppel's book CompilingWithContinuations, Lambda The Ultimate Declarative (ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-379.pdf) and RABBIT: A Compiler for SCHEME (ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-474.pdf).

Naive CPS transformation introduces many "administrative" closures that are usually removed by the compiler in the next optimization step. Modern compilers combine these two steps by transforming the program source into "A-normal form" (ANF). See e.g. AmrSabry?'s Ph.D. thesis "The Formal Relationship between Direct and Continuation-Passing Style Optimizing Compilers: A Synthesis of Two Paradigms" (1991) and several other papers referenced from JimBender's online bibliography of Scheme-related research at http://library.readscheme.org/page6.html.

Manual CPS transformation can be used to transform a recursive algorithm into TailRecursive form, which can then be transformed into iterative form. See e.g. the book EssentialsOfProgrammingLanguages.

View edit of January 6, 2005 or FindPage with title or text search