Home

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]

By Dave Herman at 2006-03-02 02:43 | Implementation | Semantics | Theory | other blogs | 10450 reads

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.

By Josef Svenningsson at Thu, 2006-03-02 22:54 | login or register to post comments

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.

By Charles Stewart at Fri, 2006-03-03 14:52 | login or register to post comments

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).

By Dave Herman at Fri, 2006-03-03 16:18 | login or register to post comments

Thanks!

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.

By Charles Stewart at Mon, 2006-03-06 17:46 | login or register to post comments

Updated link

Updated link

By naasking at Tue, 2013-10-01 15:34 | login or register to post comments