Strictification of Circular Programs

The paper is available via the ACM DL Author-ize feature:

ACM DL Author-ize service Strictification of Circular Programs

Authors: J.P. Fernandes, J. Saraiva, D. Seidel, and J. Voigtländer
Published: In Workshop on Partial Evaluation and Program Manipulation (PEPM'11, acceptance rate 15/35), Austin, Texas, Proceedings, pages 131-140, ACM, January 2011.
DOI: 10.1145/1929501.1929526
BibTeX: FSSV11.bib
Abstract: Circular functional programs (necessarily evaluated lazily) have been used as algorithmic tools, as attribute grammar implementations, and as target for program transformation techniques. Classically, Richard Bird [1984] showed how to transform certain multitraversal programs (which could be evaluated strictly or lazily) into one-traversal ones using circular bindings. Can we go the other way, even for programs that are not in the image of his technique? That is the question we pursue in this paper. We develop an approach that on the one hand lets us deal with typical examples corresponding to attribute grammars, but on the other hand also helps to derive new algorithms for problems not previously in reach.
Download: (free)
Slides: I gave a talk on this paper at IFIP WG 2.1 meeting #66, slides are here.