A Tail-Recursive Machine with Stack Inspection

John Clements, Northeastern University
Matthias Felleisen, Northeastern University

Article comments

© ACM, 2005. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Programming Languages and Systems and is available at http://dx.doi.org/10.1145/1034774.1034778.

NOTE: At the time of publication, the author John Clements was not yet affiliated with Cal Poly.

Abstract

Security folklore holds that a security mechanism based on stack inspection is incompatible with a global tail call optimization policy; that an implementation of such a language must allocate memory for a source-code tail call, and a program that uses only tail calls (and no other memory allocating construct) may nevertheless exhaust the available memory. In this article, we prove this widely held belief wrong.We exhibit an abstract machine for a language with security stack inspection whose space consumption function is equivalent to that of the canonical tail call optimizing abstract machine. Our machine is surprisingly simple and suggests that tail calls are as easy to implement in a security setting as they are in a conventional one.