Coroutining Folds with Hyperfunctions

J. Launchbury
S. Krstic
T. E. Sauerwein

Fold functions are a general mechanism for computing over recursive data structures. First-order folds compute results bottom-up. With higher-order folds, computations that inherit attributes from above can also be expressed. In this paper, we explore folds over a form of recursive higher-order function, called hyperfunctions, and show that hyperfunctions allow fold computations to coroutine across data structures, as well as compute bottom up and top down. We use the compiler technique of foldr-build as an exemplar to show how hyperfunctions can be used.

In Anindya Banerjee, Olivier Danvy, Kyung-Goo Doh and John Hatcliff: Semantics, Abstract Interpretation, and Reasoning about Programs: Essays Dedicated to David A. Schmidt on the Occasion of his Sixtieth Birthday (Festschrift for Dave Schmidt), Manhattan, Kansas, USA, 19-20th September 2013, Electronic Proceedings in Theoretical Computer Science 129, pp. 121–135.
It is a privilege to submit a paper for the Festschrift symposium held to honor Dave Schmidt's lifetime of contributions on the occasion of his 60th birthday. Many years ago, as a fresh PhD student, Dave's excellent book on Denotational Semantics opened my eyes to rich possibilities of building functions over functions (recursively!) and our continued interactions over the years were always insightful. So it seemed appropriate to offer a paper whose foundations rely on the same mathematical models that Dave so ably expounded all those years ago, constructing recursive function spaces in a way that is not possible in traditional set-theoretic models. – John Launchbury, 2013.
Published: 19th September 2013.

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