[swift-evolution] Proposal: Tail Call Optimization keyword/attribute
griotspeak at gmail.com
Mon Dec 7 16:41:59 CST 2015
Since this clearly seems to have legs, I have started a gist with the
suggested additions here
Please feel free to continue discussion here or there.
On Tue, Dec 8, 2015 at 2:04 AM, Joe Groff <jgroff at apple.com> wrote:
> On Dec 7, 2015, at 12:30 PM, Mark Lacey <mark.lacey at apple.com> wrote:
> On Dec 7, 2015, at 10:58 AM, Joe Groff via swift-evolution <
> swift-evolution at swift.org> wrote:
> On Dec 5, 2015, at 10:52 AM, Joe Groff <jgroff at apple.com> wrote:
> On Dec 5, 2015, at 10:45 AM, T.J. Usiyan <griotspeak at gmail.com> wrote:
> I did paint ARC as the sole culprit, didn't I? It makes sense that there
> are other complications and it is interesting to note that ARC isn't the
> the primary reason.
> On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <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.
> Yeah, that's an interesting idea. It's possibly useful to have defers run
> after the tail call converges (though arguably you're probably better off
> just writing the loop version at this point).
> 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.
> For ARC stuff it seems to me we can ensure all parameters are
> callee-consumed @owned or @in, and move any non-argument cleanups before
> the tail call, which eliminates the need for any continuation to be passed.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the swift-evolution