Description
Modern optimizer compilers can automatically transform functions with complex patterns of use of Call Stack in functions that operate in constant space on the call stack. Particular cases of these are, for well behaved terminal recursive functions. A powerful technique for performing this operation is called continuation passing style (CPS) transformation.
Objectives
The purpose of this project is to implement such a mechanism as a OCaml programming language extension that operates automatically via a particular extension of the syntax. This extension should be usable in an implementation methodology. algorithms that allow each natural implementation considered (provided by a programmer) to be automatically instrumented and then performed step by step in a direct or inverse manner (ie undo) and such that each implementation has the ability to show its internal state (for example, complementing the CPS transformation with monads, etc.).
Publications
- Code: https://gitlab.com/releaselab/factor/cps-defuncionalization
- Programação funcional com estilo e sem custo: Transformação CPS "à la carte" - Tiago Roxo, Mário Pereira, and Simão Melo de Sousa - [pdf]
In this paper we explore the use of CPS as an automatic program transformation. CPS is a programming style that allows one to convert any non-tail recursive function into a terminal recursive one, using constant stack space. Hence, Stack Overflow problems are eliminated by construction, assuming the underlying compiler is able to optimize tail-recursive implementations. The code transformation phase is done via an OCaml syntactic extension, called a PPX. In this paper, we describe how we automate the CPS transformation mechanism, how it is transparently integrated into the compilation scheme, and we assess perform differences between CPS and direct implementations.