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

[T.J. Usiyan]

## 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151205/e4fea1bd/attachment.html>