[swift-evolution] Proposal: Tail Call Optimization keyword/attribute
jgroff at apple.com
Mon Dec 7 17:20:47 CST 2015
> On Dec 7, 2015, at 3:08 PM, John McCall via swift-evolution <swift-evolution at swift.org> wrote:
>> On Dec 7, 2015, at 3:03 PM, Chris Lattner via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>> On Dec 7, 2015, at 12:30 PM, Mark Lacey via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>>>>> On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff at apple.com <mailto:jgroff at apple.com>> wrote:
>>>>>> - only allowing self-recursive tail calls, which avoid some of the stack and memory management problems with arbitrary tail calls,
>>>>>> - only allowing tail calls between functions in the same module, so that the compiler has enough information to use the tail-callable convention only where needed,
>>>>>> - only allowing tail calls between functions in the same module or external functions marked with a '@tail_callable' attribute.
>>>>>> Even if none of these can be supported immediately, there is a case for adding the attribute with the note that there are almost no supported cases. Guaranteed support for self recursive tail calls, even if that is all we added, would be a huge addition, in my opinion.
>>>>>> I don't know how useful the third option would be but the second case is compelling. I am thinking of parser combinators in particular being a case where the second option could help.
>>>>> This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and can likely be implemented mostly in SILGen by jumping to the entry block, without any supporting backend work. Arbitrary tail calls can be supported in the fullness of time.
>>>> One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.
>>> It seems like this could also be handled by passing continuations that should be run on the return paths of callees. The continuation a function passes to its callee would wrap the continuation passed to it by its caller, so they would get executed in the original order. That’s an ABI change though, and a potentially expensive one.
>>> We’ve considered doing something like this as an optimization to enable more proper tail calls in other cases (e.g. for the ARC case where you release after return). This would be done by cloning callees, and adding a new parameter. It’s not clear how worthwhile it would be to pursue this, and how expensive it would be in terms of code bloat.
>> Why not just make “tail” a modifier on return that guarantees you’ll either get a tail call, or a compile time error?
>> Use of “tail return foo()” in a context with a defer in flight could/should just produce that compile time error then. This would provide the predictable programming model that people are seeking, and can provide good QoI so people know how to solve the problem if they really want the tail call (remove or change the defer).
> Right, I think we want both a modifier on calls and an attribute on functions that allows them to be used with the call modifier. Joe is right that we can’t reliably do interprocedural tail calls without CC support, which is why the attribute is necessary; and I completely agree that the modifier which specifically requests a tail call is a must.
The function attribute is at least theoretically inferrable if for self-tail calls or calls between functions in the same module. It's only strictly necessary for public API that wants to be externally tail-callable.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the swift-evolution