Proposal: Tail Call Optimization keyword/attribute


(TJ Usiyan) #1

## 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.


(Joe Groff) #2

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


(Matthew Johnson) #3

I like this proposal and I like the general approach even more. Allow the programmer to make an assertion about performance and receive a warning or error when the compiler cannot guarantee the assertion will be met. This will make it easier to reason about the performance of code in a language where performance is extremely reliant on optimizations.

···

Sent from my iPad

On Dec 5, 2015, at 7: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


(Per Melin) #4

I have primarily worked in functional languages with guaranteed tail call
elimination for many years. Turning to Swift, I (grudgingly) try to avoid
recursion altogether simply because of the risk of blowing the stack.

···

On Sat, Dec 5, 2015 at 2:55 PM, T.J. Usiyan <griotspeak@gmail.com> wrote:

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.


(TJ Usiyan) #5

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.

- 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@apple.com> wrote:

On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@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@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


(Joe Groff) #6

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

-Joe

···

On Dec 5, 2015, at 10:45 AM, T.J. Usiyan <griotspeak@gmail.com> wrote:

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@apple.com <mailto:jgroff@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.


(Joe Groff) #7

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated. Either we accept this (which seems reasonable to me), or allow deferred blocks to be executed before the expression in a `tail return`, if there's a motivating reason.

-Joe

···

On Dec 5, 2015, at 10:52 AM, Joe Groff <jgroff@apple.com> wrote:

On Dec 5, 2015, at 10:45 AM, T.J. Usiyan <griotspeak@gmail.com <mailto:griotspeak@gmail.com>> wrote:

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@apple.com <mailto:jgroff@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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.


(Slava Pestov) #8

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.

- 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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated. Either we accept this (which seems reasonable to me), or allow deferred blocks to be executed before the expression in a `tail return`, if there's a motivating reason.

Wouldn't the latter potentially break code?

func f() -> String {
  let fd = open(...)
  defer { close(fd) }
  return read(fd)
}

In other languages with TCO, defer-like constructs inhibit the optimization, and I see no reason to deviate from that here.

Slava

···

On Dec 7, 2015, at 10:58 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 5, 2015, at 10:52 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 5, 2015, at 10:45 AM, T.J. Usiyan <griotspeak@gmail.com <mailto:griotspeak@gmail.com>> wrote:
On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

-Joe

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Mark Lacey) #9

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.

- 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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.

It seems like 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.

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.

Mark

···

On Dec 7, 2015, at 10:58 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 5, 2015, at 10:52 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 5, 2015, at 10:45 AM, T.J. Usiyan <griotspeak@gmail.com <mailto:griotspeak@gmail.com>> wrote:
On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

Either we accept this (which seems reasonable to me), or allow deferred blocks to be executed before the expression in a `tail return`, if there's a motivating reason.

-Joe

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Joe Groff) #10

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.

- 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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.

It seems like 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.

Yeah, that's an interesting idea. It's possibly useful to have defers run after the tail call converges (though arguably you're probably better off just writing the loop version at this point).

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.

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.

-Joe

···

On Dec 7, 2015, at 12:30 PM, Mark Lacey <mark.lacey@apple.com> wrote:

On Dec 7, 2015, at 10:58 AM, Joe Groff via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 5, 2015, at 10:52 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 5, 2015, at 10:45 AM, T.J. Usiyan <griotspeak@gmail.com <mailto:griotspeak@gmail.com>> wrote:
On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:


(Chris Lattner) #11

Why not just make “tail” a modifier on return that guarantees you’ll either get a tail call, or a compile time error?

Use of “tail return foo()” in a context with a defer in flight could/should just produce that compile time error then. This would provide the predictable programming model that people are seeking, and can provide good QoI so people know how to solve the problem if they really want the tail call (remove or change the defer).

-Chris

···

On Dec 7, 2015, at 12:30 PM, Mark Lacey via swift-evolution <swift-evolution@swift.org> wrote:

On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.

It seems like 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.

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.


(John McCall) #12

Right, I think we want both a modifier on calls and an attribute on functions that allows them to be used with the call modifier. Joe is right that we can’t reliably do interprocedural tail calls without CC support, which is why the attribute is necessary; and I completely agree that the modifier which specifically requests a tail call is a must.

John.

···

On Dec 7, 2015, at 3:03 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 7, 2015, at 12:30 PM, Mark Lacey via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.

It seems like 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.

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.

Why not just make “tail” a modifier on return that guarantees you’ll either get a tail call, or a compile time error?

Use of “tail return foo()” in a context with a defer in flight could/should just produce that compile time error then. This would provide the predictable programming model that people are seeking, and can provide good QoI so people know how to solve the problem if they really want the tail call (remove or change the defer).


(Mark Lacey) #13

If you really don’t want to support defer in functions that have tail calls, I think what you're suggesting is the right approach. As Joe pointed out the optimization I had in mind wouldn’t be necessary if we had support for just transferring ownership at the point of these tail calls (as opposed to the retain/release we emit around the call for these arguments today).

Mark

···

On Dec 7, 2015, at 3:03 PM, Chris Lattner <clattner@apple.com> wrote:

On Dec 7, 2015, at 12:30 PM, Mark Lacey via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.

It seems like 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.

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.

Why not just make “tail” a modifier on return that guarantees you’ll either get a tail call, or a compile time error?

Use of “tail return foo()” in a context with a defer in flight could/should just produce that compile time error then. This would provide the predictable programming model that people are seeking, and can provide good QoI so people know how to solve the problem if they really want the tail call (remove or change the defer).


(TJ Usiyan) #14

Since this clearly seems to have legs, I have started a gist with the
suggested additions here
https://gist.github.com/griotspeak/093ad8ec61d07dfcb8a2

Please feel free to continue discussion here or there.
TJ

···

On Tue, Dec 8, 2015 at 2:04 AM, Joe Groff <jgroff@apple.com> wrote:

On Dec 7, 2015, at 12:30 PM, Mark Lacey <mark.lacey@apple.com> wrote:

On Dec 7, 2015, at 10:58 AM, Joe Groff via swift-evolution < > swift-evolution@swift.org> wrote:

On Dec 5, 2015, at 10:52 AM, Joe Groff <jgroff@apple.com> wrote:

On Dec 5, 2015, at 10:45 AM, T.J. Usiyan <griotspeak@gmail.com> wrote:

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@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.

This seems like a reasonable evolution path. Getting only self-tail-calls
working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to
describe how it interacts with `defer`. As currently specified, `defer`
would have to block tail calling, since the deferred blocks occur after the
return expression is evaluated.

It seems like 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.

Yeah, that's an interesting idea. It's possibly useful to have defers run
after the tail call converges (though arguably you're probably better off
just writing the loop version at this point).

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.

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.

-Joe


(Joe Groff) #15

The function attribute is at least theoretically inferrable if for self-tail calls or calls between functions in the same module. It's only strictly necessary for public API that wants to be externally tail-callable.

-Joe

···

On Dec 7, 2015, at 3:08 PM, John McCall via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 7, 2015, at 3:03 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 7, 2015, at 12:30 PM, Mark Lacey via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.

It seems like 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.

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.

Why not just make “tail” a modifier on return that guarantees you’ll either get a tail call, or a compile time error?

Use of “tail return foo()” in a context with a defer in flight could/should just produce that compile time error then. This would provide the predictable programming model that people are seeking, and can provide good QoI so people know how to solve the problem if they really want the tail call (remove or change the defer).

Right, I think we want both a modifier on calls and an attribute on functions that allows them to be used with the call modifier. Joe is right that we can’t reliably do interprocedural tail calls without CC support, which is why the attribute is necessary; and I completely agree that the modifier which specifically requests a tail call is a must.


(Chris Lattner) #16

I would really prefer that a “tail return” not change the semantics of the function, it merely is an assertion that the tail call is guaranteed. This means that defer cannot be used, but we can exploit the “early destroy’s are ok” aspect of ARC to solve its issues.

I agree that this isn’t enough to solve the calling convention issue, an attribute or magic for self recursion seems fine to me.

-Chris

···

On Dec 7, 2015, at 3:18 PM, Mark Lacey <mark.lacey@apple.com> wrote:

It seems like 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.

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.

Why not just make “tail” a modifier on return that guarantees you’ll either get a tail call, or a compile time error?

Use of “tail return foo()” in a context with a defer in flight could/should just produce that compile time error then. This would provide the predictable programming model that people are seeking, and can provide good QoI so people know how to solve the problem if they really want the tail call (remove or change the defer).

If you really don’t want to support defer in functions that have tail calls, I think what you're suggesting is the right approach. As Joe pointed out the optimization I had in mind wouldn’t be necessary if we had support for just transferring ownership at the point of these tail calls (as opposed to the retain/release we emit around the call for these arguments today).


(John McCall) #17

Good point.

John.

···

On Dec 7, 2015, at 3:20 PM, Joe Groff <jgroff@apple.com> wrote:

On Dec 7, 2015, at 3:08 PM, John McCall via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 7, 2015, at 3:03 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 7, 2015, at 12:30 PM, Mark Lacey via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Sat, Dec 5, 2015 at 9:00 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@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.

This seems like a reasonable evolution path. Getting only self-tail-calls working is indeed much simpler, and 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.

One small thing: for completeness, any tail call proposal would have to describe how it interacts with `defer`. As currently specified, `defer` would have to block tail calling, since the deferred blocks occur after the return expression is evaluated.

It seems like 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.

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.

Why not just make “tail” a modifier on return that guarantees you’ll either get a tail call, or a compile time error?

Use of “tail return foo()” in a context with a defer in flight could/should just produce that compile time error then. This would provide the predictable programming model that people are seeking, and can provide good QoI so people know how to solve the problem if they really want the tail call (remove or change the defer).

Right, I think we want both a modifier on calls and an attribute on functions that allows them to be used with the call modifier. Joe is right that we can’t reliably do interprocedural tail calls without CC support, which is why the attribute is necessary; and I completely agree that the modifier which specifically requests a tail call is a must.

The function attribute is at least theoretically inferrable if for self-tail calls or calls between functions in the same module. It's only strictly necessary for public API that wants to be externally tail-callable.


(TJ Usiyan) #18

Hello,

I've updated the proposal and created a pull request. Please let me know if
it needs further updates
https://github.com/apple/swift-evolution/pull/103

TJ

···

On Tue, Dec 8, 2015 at 1:08 AM, Chris Lattner via swift-evolution < swift-evolution@swift.org> wrote:

On Dec 7, 2015, at 3:18 PM, Mark Lacey <mark.lacey@apple.com> wrote:

It seems like 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.

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.

Why not just make “tail” a modifier on return that guarantees you’ll
either get a tail call, or a compile time error?

Use of “tail return foo()” in a context with a defer in flight
could/should just produce that compile time error then. This would provide
the predictable programming model that people are seeking, and can provide
good QoI so people know how to solve the problem if they really want the
tail call (remove or change the defer).

If you really don’t want to support defer in functions that have tail
calls, I think what you're suggesting is the right approach. As Joe pointed
out the optimization I had in mind wouldn’t be necessary if we had support
for just transferring ownership at the point of these tail calls (as
opposed to the retain/release we emit around the call for these arguments
today).

I would really prefer that a “tail return” not change the semantics of the
function, it merely is an assertion that the tail call is guaranteed. This
means that defer cannot be used, but we can exploit the “early destroy’s
are ok” aspect of ARC to solve its issues.

I agree that this isn’t enough to solve the calling convention issue, an
attribute or magic for self recursion seems fine to me.

-Chris

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution