[swift-evolution] Proposal: Tail Call Optimization keyword/attribute

[T.J. Usiyan]

Since this clearly seems to have legs, I have started a gist with the
suggested additions here
https://gist.github.com/griotspeak/093ad8ec61d07dfcb8a2

Please feel free to continue discussion here or there.
TJ

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.
>
> -Joe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151208/c5b45f3c/attachment.html>