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

[T.J. Usiyan]

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.

On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff at apple.com> wrote:

> 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/20151206/65b8a10c/attachment-0001.html>