1. Coroutining Folds with Hyperfunctions
- Author
-
Launchbury, J., Krstic, S., and Sauerwein, T. E.
- Subjects
Computer Science - Programming Languages ,Computer Science - Logic in Computer Science ,D.1.1 - Abstract
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., Comment: In Proceedings Festschrift for Dave Schmidt, arXiv:1309.4557. 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
- 2013
- Full Text
- View/download PDF