Turchin's Relation for Call-by-Name Computations: A Formal Approach

Antonina Nepeivoda

Supercompilation is a program transformation technique that was first described by V. F. Turchin in the 1970s. In supercompilation, Turchin's relation as a similarity relation on call-stack configurations is used both for call-by-value and call-by-name semantics to terminate unfolding of the program being transformed. In this paper, we give a formal grammar model of call-by-name stack behaviour. We classify the model in terms of the Chomsky hierarchy and then formally prove that Turchin's relation can terminate all computations generated by the model.

In Geoff Hamilton, Alexei Lisitsa and Andrei P. Nemytykh: Proceedings of the Fourth International Workshop on Verification and Program Transformation (VPT 2016), Eindhoven, The Netherlands, 2nd April 2016, Electronic Proceedings in Theoretical Computer Science 216, pp. 137–159.
Published: 6th July 2016.

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