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

[Joe Groff]

Requiring an explicit 'tail' annotation for tail calls is definitely the right way to approach this. However, ARC is not the only (or even the primary) reason tail recursion is problematic for Swift. ARC operations are not strictly ordered, unlike C++ destructors; the compiler is free to release values at any point after their last use. As long as a tail-callable function uses a convention where the callee takes ownership of all of its refcounted parameters, then ARC can avoid interfering with tail calls. However, there are other low-level resources that need to be managed in the case of an arbitrary tail call, such as space on the callstack and memory for indirectly-passed parameters. Being able to manage these would require a special machine-level calling convention that would have overhead we don't want to spend pervasively to make arbitrary functions tail-callable. Because of this, we'd have to put further restrictions on what can be tail-called. Some options, in rough order of complexity, include:

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

-Joe

> On Dec 5, 2015, at 5:55 AM, T.J. Usiyan <griotspeak at gmail.com> wrote:
> 
> ## Introduction
> 
> Tail call optimization can be a powerful tool when implementing certain types of algorithms. Unfortunately, ARC's semantics interfere with our ability to handle all possible cases of tail call recursion. An attribute, similar to Scala's `tailrec`, along with LLVM warnings, could allow a clear indicator of when such optimizations are not guaranteed to work.
> 
> ## Motivation
> 
> LLVM will, currently, perform tail call optimization when possible cannot guarantee such optimizations. ARC can interfere with tail call recursion by inserting a method call after the intended 'last' recursive call. The ability to insert this call is fundamental to ARC and, because of this, swift developers currently have no insight into when TCO can/will occur.
> 
> ``` swift
> func fact(input: Int) -> Int {
>     func _fact(n: Int, value: Int) -> (n: Int, value:Int) {
>         if n <= 0 {
>             return (0, value)
>         } else {
>             return _fact(n - 1, value: n * value)
>         }
>     }
> 
>     return _fact(input, value: 1).value
> }
> ```
> In the provided example, the developer can be sure that tail call optimization is possible but, without either a universal guarantee or something like the proposed attribute, there is no wait to be sure that such an optimization will occur.
> 
> ## Proposed solution
> 
> Providing an attribute would provide developers with concrete klnowledge of when TCO can and will be performed by LLVM in compiling their swift code. 
> 
> ``` swift
> func fact(input: Int) -> Int {
> 	@tailrec
>     func _fact(n: Int, value: Int) -> (n: Int, value:Int) {
>         ...
> ```
> With this attribute, the developer can express the desire for TCO and warnings can be emitted if TCO cannot be guaranteed. If there are currently only a few such cases, developers are made aware of what those cases are and can design implementations with this information at hand. As LLVM's ability to provide TCO increases, the allowed cases simply grow with no effect for the initial narrow cases.
> 
> 
> ## Detailed design
> In an ideal situation, implementation of this feature can consist solely of the attribute and output from LLVM indicating whether or not the requested ptimization can be guaranteed. This proposal does not call for an expansion of accepted cases.
> 
> ## Impact on existing code
> 
> This should not have any breaking impact as it is strictly additive and diagnostic.
> 
>  _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151205/1f5fc2da/attachment.html>