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@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.
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.
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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
