<div dir="ltr">Hello all,<div><br></div><div><br><div><span style="font-size:27px;color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif">Introduction</span><br><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">Tail call optimization can be a powerful tool when implementing certain types of algorithms. Unfortunately, Tail call optimization cannot be consistently used in Swift code. Developers cannot be sure that opportunities for this particular optimization to be applied are, in fact, being realized. This discrepancy can cause dramatic differences from expected and actual performance. An attribute, similar to Scala’s <code style="line-height:1">tailrec</code>, along with LLVM warnings, could allow a clear indicator of when such optimizations are not guaranteed to work.</p><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">Swift-evolution thread: <a href="https://lists.swift.org/pipermail/swift-evolution/2015-December/000359.html" style="color:rgb(13,110,161);text-decoration:none">https://lists.swift.org/pipermail/swift-evolution/2015-December/000359.html</a></p><h2 id="motivation" style="color:rgb(17,17,17);font-size:27px;line-height:42px;margin-top:42px;margin-bottom:21px;font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif">Motivation</h2><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">LLVM will perform tail call optimization when possible but cannot currently guarantee when applied. This is partially explained by Joe Groff in swift-evolution</p><blockquote style="margin-top:21px;margin-bottom:21px;color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;font-size:15px"><p style="word-wrap:break-word;margin:1.3125em 0px;font-size:17px;line-height:1.6em;font-style:italic">“… 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.”</p></blockquote><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">Swift developers currently have no insight into when TCO can or will occur.</p><pre style="margin-top:21px;margin-bottom:21px;color:rgb(17,17,17);font-size:15px;height:246px;background-color:rgb(248,248,248)"><code class="" style="line-height:inherit;display:block;padding:0.5em;color:rgb(51,51,51);height:auto"><span class=""><span class="" style="font-weight:bold">func</span> <span class="" style="color:rgb(153,0,0);font-weight:bold">fact</span><span class="">(input: Int)</span></span> -> <span class="">Int</span> {
<span class=""><span class="" style="font-weight:bold">func</span> <span class="" style="color:rgb(153,0,0);font-weight:bold">_fact</span><span class="">(n: Int, value: Int)</span></span> -> (n: <span class="">Int</span>, value:<span class="">Int</span>) {
<span class="" style="font-weight:bold">if</span> n <= <span class="" style="color:rgb(0,153,153)">0</span> {
<span class="" style="font-weight:bold">return</span> (<span class="" style="color:rgb(0,153,153)">0</span>, value)
} <span class="" style="font-weight:bold">else</span> {
<span class="" style="font-weight:bold">return</span> _fact(n - <span class="" style="color:rgb(0,153,153)">1</span>, value: n * value)
}
}
<span class="" style="font-weight:bold">return</span> _fact(input, value: <span class="" style="color:rgb(0,153,153)">1</span>).value
}</code></pre><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">the provided example, the developer can be reasonably sure that tail call optimization is possible but, without either a universal guarantee or something like the proposed attribute, there is no way to be sure that such an optimization will occur.</p><h2 id="proposed-solution" style="color:rgb(17,17,17);font-size:27px;line-height:42px;margin-top:42px;margin-bottom:21px;font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif">Proposed solution</h2><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">Adding an attribute would provide developers with concrete knowledge of when TCO can and will be performed by LLVM in compiling their swift code.</p><pre style="margin-top:21px;margin-bottom:21px;color:rgb(17,17,17);font-size:15px;height:183px;background-color:rgb(248,248,248)"><code class="" style="line-height:inherit;display:block;padding:0.5em;color:rgb(51,51,51);height:auto"><span class=""><span class="" style="font-weight:bold">func</span> <span class="" style="color:rgb(153,0,0);font-weight:bold">fact</span><span class="">(input: Int)</span></span> -> <span class="">Int</span> {
@tailrec
<span class=""><span class="" style="font-weight:bold">func</span> <span class="" style="color:rgb(153,0,0);font-weight:bold">_fact</span><span class="">(n: Int, value: Int)</span></span> -> (n: <span class="">Int</span>, value:<span class="">Int</span>) {
...
}
<span class="" style="color:rgb(153,153,136);font-style:italic">// Call site where TCO is expected</span>
tail <span class="" style="font-weight:bold">return</span> fact(<span class="" style="color:rgb(0,153,153)">3</span>)</code></pre><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">this attribute and return modifier combination, 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.<br>We should, at first, work to support the simplest cases and only allow self-recursive tail calls, which avoid some of the aforementioned stack and memory management problems that can be encountered in arbitrary tail call.<br>If the user attempts to use <code style="line-height:1">@tailrec</code> and <code style="line-height:1">defer</code> together, the compiler should emit and error , as deferred blocks occur after the return expression is evaluated. We should also provide feedback to the developer so that they understand that the defer is blocking TCO.</p><h2 id="detailed-design" style="color:rgb(17,17,17);font-size:27px;line-height:42px;margin-top:42px;margin-bottom:21px;font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif">Detailed design</h2><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">In the minimal case, implementation of this feature can consist solely of the attribute and output from LLVM indicating whether or not the requested optimization can be guaranteed. To quote Joe Groff once more, guaranteed support for self recursive tail calls ‘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.’.</p><h2 id="impact-on-existing-code" style="color:rgb(17,17,17);font-size:27px;line-height:42px;margin-top:42px;margin-bottom:21px;font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif">Impact on existing code</h2><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">This should not have any breaking impact as it is strictly additive and diagnostic.</p><h2 id="future-enhancements" style="color:rgb(17,17,17);font-size:27px;line-height:42px;margin-top:42px;margin-bottom:21px;font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif">Future Enhancements</h2><p style="color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;word-wrap:break-word;margin:1.3125em 0px;font-size:1.1429em;line-height:1.3125em">This proposal is meant to clarify when tail call optimization will be applied and lay the foundation for expansion of supported cases. Possible cases which we could support in the future are</p><ul style="margin-top:21px;margin-bottom:21px;padding-left:1.5em;color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;font-size:15px"><li style="font-size:17px">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,</li><li style="font-size:17px">allowing tail calls between functions in the same module or external functions marked with a ‘@tail_callable’ attribute.</li></ul><h2 id="alternatives-considered" style="color:rgb(17,17,17);font-size:27px;line-height:42px;margin-top:42px;margin-bottom:21px;font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif">Alternatives considered</h2><ul style="margin-top:21px;margin-bottom:21px;padding-left:1.5em;color:rgb(17,17,17);font-family:'Helvetica Neue',Helvetica,Arial,Verdana,sans-serif;font-size:15px"><li style="font-size:17px">We could add the keyword without expanding the supported cases in any way.</li><li style="font-size:17px">We could allow deferred blocks to be executed before the expression in a <code style="line-height:1">tail return</code> if there is a motivating reason.<ul style="margin-top:0px;margin-bottom:0.4em;padding-left:1.5em"><li>Slava Pestov pointed out that this could prove troublesome for code similar to</li></ul><p style="word-wrap:break-word;margin:0.5em 0px;line-height:1.3125em"><code style="line-height:1">swift func f() -> String { let fd = open(...) defer { close(fd) } return read(fd) }</code></p><ul style="margin-top:0px;margin-bottom:0.4em;padding-left:1.5em"><li>Mark Lacey suggests that<blockquote style="margin-top:21px;margin-bottom:21px"><p style="word-wrap:break-word;margin:0.5em 0px;font-size:18px;line-height:1.6em;font-style:italic">“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.</p><p style="word-wrap:break-word;margin:0.5em 0px;font-size:18px;line-height:1.6em;font-style:italic">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."</p></blockquote><pre style="margin-top:21px;margin-bottom:21px;height:38px;background-color:rgb(248,248,248)"><code class="" style="line-height:inherit;display:block;padding:0.5em;color:rgb(51,51,51);height:auto">Though, according <span class="" style="font-weight:bold">to</span> Joe Groff,
</code></pre><blockquote style="margin-top:21px;margin-bottom:21px"><p style="word-wrap:break-word;margin:0.5em 0px;font-size:18px;line-height:1.6em;font-style:italic">“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.”</p></blockquote><pre style="margin-top:21px;margin-bottom:21px;height:122px;background-color:rgb(248,248,248)"><code class="" style="line-height:inherit;display:block;padding:0.5em;color:rgb(51,51,51);height:auto">This may <span class="" style="font-weight:bold">not</span> be desirable as <span class="">it</span> would change the semantics <span class="" style="font-weight:bold">of</span> the <span class="" style="font-weight:bold">function</span> where the original goal <span class="" style="font-weight:bold">of</span> <span class="" style="font-weight:bold">this</span> proposal <span class="" style="font-weight:bold">is</span> <span class="" style="font-weight:bold">to</span> <span class="" style="font-weight:bold">let</span> the developer assert <span class="">that</span> TCO <span class="" style="font-weight:bold">is</span> desired <span class="" style="font-weight:bold">and</span> allow the compiler <span class="" style="font-weight:bold">to</span> emit an error <span class="" style="font-weight:bold">when</span> <span class="">it</span> cannot guarantee TCO. </code></pre></li></ul></li></ul></div></div></div>