First Class Call Stacks: Exploring Head Reduction

Philip Johnson-Freyd
(University of Oregon)
Paul Downen
(University of Oregon)
Zena M. Ariola
(University of Oregon)

Weak-head normalization is inconsistent with functional extensionality in the call-by-name λ-calculus. We explore this problem from a new angle via the conflict between extensionality and effects. Leveraging ideas from work on the λ-calculus with control, we derive and justify alternative operational semantics and a sequence of abstract machines for performing head reduction. Head reduction avoids the problems with weak-head reduction and extensionality, while our operational semantics and associated abstract machines show us how to retain weak-head reduction's ease of implementation.

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. 18–35.
Published: 19th June 2016.

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