From Push/Enter to Eval/Apply by Program Transformation

Maciej Piróg
(University of Oxford)
Jeremy Gibbons
(University of Oxford)

Push/enter and eval/apply are two calling conventions used in implementations of functional languages. In this paper, we explore the following observation: when considering functions with multiple arguments, the stack under the push/enter and eval/apply conventions behaves similarly to two particular implementations of the list datatype: the regular cons-list and a form of lists with lazy concatenation respectively. Along the lines of Danvy et al.'s functional correspondence between definitional interpreters and abstract machines, we use this observation to transform an abstract machine that implements push/enter into an abstract machine that implements eval/apply. We show that our method is flexible enough to transform the push/enter Spineless Tagless G-machine (which is the semantic core of the GHC Haskell compiler) into its eval/apply variant.

In Olivier Danvy and Ugo de'Liguoro: Proceedings of the Workshop on Continuations (WoC 2015), London, UK, April 12th 2015, Electronic Proceedings in Theoretical Computer Science 212, pp. 53–62.
Published: 19th June 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.212.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org