A Tail-Recursive Machine with Stack Inspection

A Tail-Recursive Machine with Stack Inspection. John Clements and Matthias Felleisen, TOPLAS 2004.

Security folklore holds that a security mechanism based on stack inspection is incompatible with a global tail call optimization policy... In this article, we prove this widely held belief wrong. ... 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.

I don't believe we've discussed this paper before, although it was mentioned in this thread. Tail calls have been a topic of discussion here several times. [1][2][3]

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Cool paper!

I just want to say that I think this paper is really cool. In the programming language community we are not used to see results that go against our intuition. Sure, people can come up with new and amazing designs but nothing that really alters the way we view the world.

Previously I was convinced that tail-recursion and stack inspection was totally incompatible. But then I see this paper and I'm completely baffled. I still have a hard time accepting that it is possible. That's a kind of result we're not spoiled with.

Kent Pitman's remark

I seem to recall Kent Pitman saying, maybe in the Slashdot interview, that he spoke to a Sun engineer (he named no names) who said that they knew how to combine Java's security policy, which is based on stack inspection, with tail recursion. I think maybe some people have known how to do this for some time.

Question 9

Question 9 of Kent's Slashdot story addresses this, but he only suspects that there's a problem with integrating the stack and the security model. I don't see any hint that he knows of a solution (other than choosing a different security mechanism).


There's less to his remark than I recalled. It leaves a lot to interpretation: Kent seems to think the Java security model doesn't need stack inspection, which makes my remark somewhat moot, but it's not clear the Sun engineer(s) thought the same. I'll email this story to Kent, it may be that he'd like to say something.

Updated link