<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">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:<div class=""><br class=""></div><div class="">- only allowing self-recursive tail calls, which avoid some of the stack and memory management problems with arbitrary tail calls,</div><div class="">- 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,</div><div class="">- only allowing tail calls between functions in the same module or external functions marked with a '@tail_callable' attribute.</div><div class=""><br class=""></div><div class="">-Joe</div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Dec 5, 2015, at 5:55 AM, T.J. Usiyan <<a href="mailto:griotspeak@gmail.com" class="">griotspeak@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class=""><div class="">## Introduction</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">## Motivation</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">``` swift</div><div class="">func fact(input: Int) -> Int {</div><div class=""> func _fact(n: Int, value: Int) -> (n: Int, value:Int) {</div><div class=""> if n <= 0 {</div><div class=""> return (0, value)</div><div class=""> } else {</div><div class=""> return _fact(n - 1, value: n * value)</div><div class=""> }</div><div class=""> }</div><div class=""><br class=""></div><div class=""> return _fact(input, value: 1).value</div><div class="">}</div><div class="">```</div><div class="">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.</div><div class=""><br class=""></div><div class="">## Proposed solution</div><div class=""><br class=""></div><div class="">Providing an attribute would provide developers with concrete klnowledge of when TCO can and will be performed by LLVM in compiling their swift code. </div><div class=""><br class=""></div><div class="">``` swift</div><div class="">func fact(input: Int) -> Int {</div><div class=""><span class="" style="white-space:pre"> </span>@tailrec</div><div class=""> func _fact(n: Int, value: Int) -> (n: Int, value:Int) {</div><div class=""> ...</div><div class="">```</div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">## Detailed design</div><div class="">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.</div><div class=""><br class=""></div><div class="">## Impact on existing code</div><div class=""><br class=""></div><div class="">This should not have any breaking impact as it is strictly additive and diagnostic.</div><div class=""><br class=""></div></div></div>
<img src="https://u2002410.ct.sendgrid.net/wf/open?upn=RoDF4MveSEMYBIqIJA6ub1g8cOZ-2BVYvqV-2FqygPhjPn-2B5aNYGJ3A3RQO6-2BeOzDFKEqWTykhyMRTmH-2BVuypfOD4XPp-2BVwYCdn1Q-2Bj0HXwAyGxCSFWo4CTiYSDdecclWBli0PlqexpKV0kHj9r7MGUIvlCE-2FTfzH9-2F8QaJlF3S8Grdp0DnYHALK5Wrp1tOfnTPfnv-2FcOCkr6TKNHGn3ZMiFQPS4e0emOjJEcQGAywQ2Baw-3D" alt="" width="1" height="1" border="0" style="height:1px !important;width:1px !important;border-width:0 !important;margin-top:0 !important;margin-bottom:0 !important;margin-right:0 !important;margin-left:0 !important;padding-top:0 !important;padding-bottom:0 !important;padding-right:0 !important;padding-left:0 !important;" class="">
_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></div></body></html>