Go: proposal: Go 2: add become statement to support tail calls

[ianlancetaylor]

The current Go language does not support tail calls, because they affect runtime.Callers and stack backtraces and the like. Because runtime.Callers in particular must be predictable for Go programmers, adding tail calls to the language would require a precise specification of exactly when they do and do not occur. Since people may sometimes not want them, there would have to be a way to avoid a tail call that would otherwise occur.

That said, people do want tail calls: #15304, #16798. The Alef language had a become statement, documented as follows (from http://doc.cat-v.org/plan_9/2nd_edition/papers/alef/ref):

The become statement transforms the execution of the current function into the calculation of the expression given as its argument. If expression is not itself a function call, then it must have the same type as the return value of the caller and the behavior is analogous to a return statement. If, however, it is a function call, then it need only have the same return type; the argument list may be different. When a function P executes a become whose expression is a call of Q, the effect is exactly as if the caller of P had instead called Q with the appropriate arguments from P. In particular, the stack frame for P is overwritten by the frame for Q; functions that invoke one another with become will execute in constant stack space.

This proposal is to implement a become statement with these semantics in Go. The definition would be slightly changed to permit either a list of expressions or a single function call.

[ghost]

This Go Forum topic addressed a question on functional programming.

I'm curious if there has been consideration of the use of functional programming language shells with Go.

http://nurmi-labs.blogspot.com/2016/03/es.html

http://nurmi-labs.blogspot.com/2017/04/xs.html

The es(1) and xs(1) man pages are similar.

BUGS

...

The interpreter should be properly tail recursive; that is, tail calls should not consume stack space.

http://nurmi-labs.blogspot.com/p/about.html

See: the blog posts on es (influenced by Scheme, and Tcl) and xs

http://wryun.github.io/es-shell/
https://github.com/TieDyedDevil/XS

BUGS can be fixed, the man pages' cited tail calls.

Tail call optimization
http://wiki.tcl.tk/1348

additional links presented therein

possibly of historical interest

https://blog.golang.org/first-go-program

the program parses and prints an S-expression

The es and xs shells can be extended, and notably the latter added a configure option as "--enable-lisptrees".

xs is written in C++, and I've expressed interest here in seeing code
added to xs for a feature to work with ndb(6)-like data structures

[robpike]

Become comes from Newsqueak, of which Alef was a descendant.

By the way, Newsqueak had only become; it had no return statement. And it was aggressive about tail call compaction.

From the informal spec:

The become statement

become expression;

is legal only inside a prog. Its effect is to replace the execution of the prog by the evaluation
of the expression. The resulting value is returned to the caller of the prog as its value.
For example, consider the prog

rec sumorial:=prog(n,sum:int) of int{
  if(n==0) become sum;
  become sumorial(n-1, sum+n);
};

If n is zero, the first become yields to the caller the value of sum. Otherwise, the second
become replaces the executing prog by a version of itself with different arguments. In general,
when a prog P executes a become whose expression is a call of Q, the effect is exactly as
if the caller of P had instead called Q with the appropriate arguments. No new stack space is
consumed; become is a form of process call.

[ianlancetaylor]

@forskning This is not the place to discuss functional shells.

@robpike Thanks for the correction, didn't come across that.

[l3x]

@robpike If I read you comment correctly, become would avoid creating a new stack by making the last call in a recursion the function itself. This is just another way of saying Tail Call Optimization (TCO), right? Would you say that this would be a relatively low impact new feature? (Where "low impact" means it would not break existing code and likely will not cause unintended ill side effects.)

[huguesb]

@l3x introducing a new keyword would very likely break some existing code. Stack frame reuse is likely to lead to some issues/confusion, especially when debugging, regardless of how it is implemented. And the implementation would probably be complex and fraught with GC-related issues similar to #22350

So, no, this is definitely not "low impact".

[magical]

If this is adopted, I'd like to propose that "become" be spelled "goto", and that it be restricted to function calls, not arbitrary expressions. This has some precedent in perl's goto &sub form [1], and avoids introducing a new keyword. Restricting it to function calls fits in with defer and go being special forms of function calls in Go.

Rob's example would look like this:

func sumorial(n, sum int) int {
  if n == 0 { return sum }
  goto sumorial(n-1, sum+n)
}

[robpike]

@huguesb Yes, the become statement is a form of tail call optimization. However, the usual definition of TCO is that the implementation applies it as it chooses. Instead, in Newsqueak (and in Alef when become was used instead of return), the "optimization" was always done. That is, the stack frame was always overwritten when the become's expression was a function call.

I believe @ianlancetaylor is proposing what Alef did, which is controlling the action according to which keyword is used.

[DeedleFake]

It's an interesting solution. It could be quite useful for a project I'm working on, actually. I've got two questions, though:

• How would this affect defers in the function that it's used in?
• How would this work with multiple returns values?

[ianlancetaylor]

Yes, I am proposing using two different keywords, one (return) that does a normal call and one (become) that does a tail call.

@magical The suggestion of goto f() is an interesting one since it avoids adding another keyword. I would be open to that. I guess the question is whether people would find it too cryptic.

@DeedleFake Deferred functions would be handled as usual, which is to say that they would remain on the defer stack and would be executed when the tail-called function returns. That is, if you write return f() deferred calls are not executed until f() returns, and the same would be true for become f().

Similarly, writing return f() is only permitted when f() has the same number and type of results as the calling function, and the same would be true of become f().

@l3x @huguesb This proposal would be fairly low-impact in the sense that it would not affect any existing code that does not use become as an identifier. Or, if we take the goto f() suggestion, then it would not affect any existing code at all. The actual implementation of this would be difficult in general, as it would require potentially copying the stack to get more room and rewriting the stack map.

[l3x]

IMHO: become is not bad, but goto f() seems to be more closely aligned with what's going on with TCO.

@ianlancetaylor Perhaps, a better name would be copyStackRewriteStackAndGoto, but seriously ... That sounds like a lot of work. What do you think the net result would be in terms of execution time?

[jimmyfrasche]

@ianlancetaylor

This proposal is to implement a become statement with these semantics in Go. The definition would be slightly changed to permit either a list of expressions or a single function call.

How would it work with multiple return values? The only way I can think of is it's always become f() where the returns of f are the same as the invoking function.

---

I think goto is more evocative of what's happening (JMP vs CALL). That may actually make it easier to explain.

However,

goto f()

is uncomfortably close to

go f()

in terms of edit-distance, at least. It would be easy to read one as the other when skimming or when you've been debugging a little too long without a break. Likewise, accidentally writing one instead of the other would create a "fun" bug to catch.

If that's a serious ergonomic concern, I suppose one way to get around that would be to double up on the keywords and have to write return goto f() or goto return f().

Perhaps it would be better to create a new keyword instead of trying to C++ it in.

---

As far as stack traces, I understand that a common trick in languages with tail calls is to create a circular buffer of traces when entering the first tail call. It allows collection of the last n calls for debugging while preventing the stack from growing without bound.

---

I'd like this, but it seems it would require rather involved changes to the runtime.

TCO is easily simulated with a trampoline without those changes, so I don't know if the benefit is worth the cost.

[randall77]

However,

goto f()
is uncomfortably close to

go f()

I don't expect this would typically be a problem, because we'd define goto f() to be a terminating statement, so if any code is after the goto f() (which would typically be the case if you meant go f()) then vet will report it as unreachable.

I'm still not sure how we would actually implement this, the stack surgery is tricky.

[ianlancetaylor]

@jimmyfrasche become would handle multiple values exactly the way return handles them. become with a list of values, rather than a single function call, would be identical to return.

[jimmyfrasche]

So become f(), nil would be the same as return f(), nil? I don't really see the point since that's not what was intended. It seems confusing. Restricting it to a single function call makes it clear when you can and cannot use it and means that it always does the same thing.

[dpinela]

I don't like this idea. Semantically, become f() and return f() accomplish the same thing - return the result of f() to the caller - thus, it's little more than an optimisation hint to the compiler, which is something that Go seems to otherwise avoid.

In addition, I think it would be hard to explain clearly to anyone not familiar with this topic - especially beginners - when they should use one construct or the other, and why. Almost every other feature of the language, by contrast, has a fairly clear-cut use case. I think Go should either support TCO without any special syntax - and with whatever instrumentation is needed to give good stack traces, if it's truly that important - or not have it at all.

TL;DR: TCO is an implementation detail, and Go should treat it as such if it implements it.

[bradfitz]

@dpinela, Go also values debuggability, and automatic TCO destroys stack trace information. One argument for become is that by using it, the programmer is explicitly saying they don't need the stack info.

[griesemer]

@bradfitz Understood, but there's a question how far one should go for that. Is it more important to provide all stack info, or keeping the number of language constructs simple? I'd be ok with lost stack information as long as it's clearly identified as TCO related. (There's also the option of trying to emulate that stack transparently, but that's a whole different ballgame.)

[randall77]

Another possibility is allow TCO by default for return f(). If you really want the stack trace, do r := f(); return r.
Of course, that presumes you know you want the complete stack trace ahead of time, which is probably not typically the case.

[cherrymui]

Does become requires the compiler to generate tail call? Or does it simply mean "I don't care my call frame and you may do optimizations when appropriate"? If the latter, we may start with the easy ones where we don't need to do the stack moving stuff.

[griesemer]

@randall77 That's what I am suggesting. One could effectively obtain the same result by wrapping the function body in a loop and do the TCO "manually". Maybe there could be a counter showing how many frames have gone "missing" but I suspect that in most cases we'd be just fine. In short, I think the compiler should do TCO under the covers where it's easy, and not bother otherwise.

[bcmills]

If [become means “optimize when appropriate”], we may start with the easy ones where we don't need to do the stack moving stuff.

I think the compiler should do TCO under the covers where it's easy, and not bother otherwise.

Making tail-call optimization implementation-dependent seems worse than not doing it at all. The point of TCO is to ensure that tail calls are safe, not just fast, and if it's safe sometimes but not others (or changes from release to release or from compiler to compiler), we'll end up in a state in which tail-recursion is technically possible but not portable: where some libraries will assume that it occurs and break badly when it does not.

That is: the difference between O(1) and O(N) behavior seems much more significant than most optimizations, which instead tweak the constant factors on behaviors with the same asymptotic behavior.

[dpinela]

@randall77 I'm not sure an obscure workaround is better than having an "obscure" feature in the language. For a reader, that construct would seem pointlessly redundant; it reminds me of the trick for getting a closure to properly capture a loop variable, which is similarly non-intuitive even for the writer, let alone the reader.

[griesemer]

@bcmills If the spec says that a self-recursive call in a return (the easy case) is translated via TCO (or TCElimination, perhaps more precisely), it seems pretty well-defined and probably covers 90% of the ground.

[olopierpa]

On Wed, Nov 8, 2017 at 10:40 PM, Robert Griesemer [e-mail]
wrote:

@bcmills https://github.com/bcmills If the spec says that a
self-recursive call in a return (the easy case) is translated via TCO (or
TCElimination, perhaps more precisely), it seems pretty well-defined and
probably covers 90% of the ground.

But the self-recursive case is the least interesting one. it adds little
expressive power to the language. A generally available TCE instead opens
the way to new programming styles and would really add to the expressivity
of the language.

I'm rooting for this feature!

[jimmyfrasche]

@griesemer every time I've wanted this it was for state machines not converting a recursive function into a loop (though that can be clearer sometimes, certainly), so only self-recursive would cover effectively 0.05% of the ground for me.

Tail call elimination is an optimization the way using a more appropriate data structure is an optimization. I wouldn't expect the compiler to say "you used a slice here but you really meant a map so I'm just going to change it for you—you didn't care about the order, right?".

Making it explicitly opt-in with a keyword means

• the intent is in the code
• it's clear that it requires TCE to work properly and will not explode if compiled with an older versions of Go
• the compiler/static-analyzers can tell you if you did something wrong
• you never lose any stack information unless you explicitly say so

But given how easy it is to simulate this feature vs. how hard it is to implement in the language in any form, I'm not really sure it's worth a slot on the limited Go2 feature list. If it does make the cut I'm :+1: on being explicit.

[griesemer]

@jimmyfrasche Fair point. I'd still be in favor of not having an explicit construct if we can clearly outline in the spec when a tail call must be eliminated (with self-recursive calls being the easiest first step).

[jimmyfrasche]

@griesemer if you want to cover all the places that tail calls can be eliminated isn't it just every statement in a tail position that is a single function call, with or without a return?

If you move those from can-be eliminated to must-be eliminated, that's a fairly large class of code that behaves differently now. Perhaps for the better, since it is now optimized. Though that could make a lot of function calls into tight loops if you don't inform the scheduler before the jmp.

If you only eliminate a subset then everyone's going to need to remember that subset when reading and writing code to try to figure out the space-complexity of their code and possibly how it interacts with the scheduler.

[griesemer]

@jimmyfrasche But if you had a "become" wouldn't you have to explain the same rules because only they are satisfied is the "become" valid?

[dpinela]

@griesemer I presume that any instance of become f(...) would apply TCE. Otherwise, it's not really useful, because you can't rely on it to work consistently, which as @bcmills noted, makes some recursive patterns unsafe.

[jimmyfrasche]

become is most useful if it either provides a tail call elimination or an error (or something flaggable by go vet/et al, at least).

I think it's value is clearest in a function that doesn't return anything

Without become it's not entirely clear what can be eliminated looking at the source without knowing all the rules for TCE:

func f(i int) {
  if i <= 0 {
    h() // tail call
    return
  }
  if i % 3 == 0 {
    g(i-1) // tail call
    return
  }
  f(i-2) // tail call
}

Depending on the compiler (and the definitions of g and h) that's either a tight loop or a potential stack-hog for large i.

With annotations what happens is abundantly clear and a choice of the author

func f(i int) {
  if i <= 0 {
    become h()
  }
  if i % 3 == 0 {
    become g(i-1)
  }
  become f(i-2)
}

[ianlancetaylor]

@griesemer If we adopt become, it must always do a tail call. It would not be acceptable to have it sometimes do a tail call and sometimes not.

[griesemer]

@jimmyfrasche With the rules being (roughly) that become can only be used when there's a single function call immediately before an explicit return in a function without results (or the end of the function) or a return with a single function call as result (I suspect).

@ianlancetaylor understood. Still, use of a become might be invalid, depending on place.

Now every programmer will want to think twice about whether to use a return or a become, when most of the time it doesn't matter; and most of the time one would benefit from the compiler doing the best thing it can (and not being restricted by some spec rule). Like we benefit from not telling the compiler what to inline or the runtime when to collect garbage. Speaking of which, conceptually one could argue that those activation frames that get overwritten by tail calls became unreachable and were garbage-collected. Not too far off from all that memory that we allocate and than can't reach anymore (yet, without a garbage collector we would surely see that data still lying around on the heap with all data intact, like we currently expect of stack frames).

I don't mean to be snarky, and I do appreciate being in control in code, but to me this is a slippery slope. I believe that a big selling point of Go is that there's usually one construct to do one conceptual thing (even if this simplicity comes at the cost of hiding complexity).

[griesemer]

PS: Never mind, the become would mean return so it would be not too bad, rule-wise. Still, the slippery-slope aspect remains.

[ghost]

I wrote to Perl 5 Porters, here are the responses.

Shlomi Fish

goto &sub is relatively limited, so I think we can use better support for
tail-call optimisation.

Jim Keenan

I've never used the 'goto &sub' syntax in 18 years of writing Perl 5 --
so I can't say anything about whether golang should use it as a model.

[cpansprout]

I am also coming here because I saw the message on Perl 5 Porters.

I can tell you how goto &foo is useful in Perl, but I have to leave it to others to say whether it would be good for Go.

As mentioned above in this thread, it is very convenient for writing recursive functions. (Stack space is not free; it uses memory.)

But the most common use in Perl I believe is in low-level functionality; e.g., dynamic function dispatch, tools that wrap functions for debugging and introspection purposes, etc.

It may be true that most Perl programmers do not use the feature, but they most certainly use tools that use it. (They rely on the feature without realising it.) In Perl, modules that do something to affect the calling code are quite common; hence, what appears on the stack is crucial.

Because of my particular programming style, I do have a tendency to sprinkle goto &foo all over the place, just to save stack memory when I know I don’t need it.

The only advice I can give with regard to design is: Don’t make Perl’s mistake. Don’t require the arguments to be in an array. I see the proposals above already avoid Perl’s clunkiness by using become f(args) or goto f(args) syntax. Though, you might consider also allowing become f to use the current function call’s arguments. (I concede that might be more Perlish that Goish.)

I chuckled when reading @randall77’s comment above, that ‘the stack surgery is tricky’. Indeed, look at Perl’s implementation:

https://perl5.git.perl.org/perl.git/blame/95388f2:/pp_ctl.c#l2718

It goes on for more than 200 lines. If it is any help, I could explain what is happening there. (I wrote some of it. See, e.g., https://perl5.git.perl.org/perl.git/commitdiff/049bd5ffd6.)

[DeedleFake]

It may be true that most Perl programmers do not use the feature, but they most certainly use tools that use it. (They rely on the feature without realising it.)

I realize that it's not perfectly analogous, but I've been using Go since it was first announced and I've never once used a fallthrough. I wouldn't argue for its removal, though.

[bcmills]

@ianlancetaylor

Deferred functions would be handled as usual, which is to say that they would remain on the defer stack and would be executed when the tail-called function returns.

That would be somewhat at odds with https://github.com/golang/go/issues/6980.

Moreover, it would be misleading: the benefit of become is to make recursive calls reliably consume O(1) space instead of O(N) space, but if we kept the defer stack it would regress to O(N).

I think the only sensible solution is to disallow tail calls when a defer may have been evaluated in the same function. That avoids confusion about when the defer executes, but also avoids misleading the reader about the efficiency of the call.

(Of course, it is possible to write O(N) tail-calls by other means — for example, by appending to a slice — but those aren't O(N) due to a control-flow stack.)

[jimmyfrasche]

@bcmills If we write N = S + D where S is the regular stack and D is the defer stack, we can say a regular call with defers is O(S + D) so tail calls with defers would make that O(D). Still linear but it's a practical improvement, if not an asymptotic one. It's still O(1) if there are no defers directly in the trace of the tail calls.

That might still be surprising, especially with automatic TCE, but it would probably be more surprising if the semantics of defer changed contextually.

Conceptually it's no different from using defer inside a loop, though admittedly harder to spot, even with an explicit become, unless you know to look out for it.

[bcmills]

That might still be surprising, especially with automatic TCE, but it would probably be more surprising if the semantics of defer changed contextually.

I agree, but by the proposal become is only allowed for tail-calls anyway: I'm suggesting that a function with a defer is, by definition, not a tail-call. (That is, we don't change the semantics of defer or become: we simply reject the program at compile-time if become is used after a possible defer in the same function.)

[griesemer]

Disallowing become because of a defer elsewhere in the function is the kind of non-orthogonal interaction that we tried to avoid in Go.

It's becoming increasingly clear to me that TCO is an optimization that is best left to the compiler; very much like we leave garbage collection to the garbage collector, and decisions where to allocate heap objects to escape analysis. As a programmer, I don't want to think at each return whether I should use become or not. The compiler should just do the right thing. As a reader of code I don't want to think at each become whether it's important that it's a become or whether it's just an optimization.

I don't buy the argument that we can't write certain algorithms if we don't know for sure they use O(1) stack instead of O(n): We already can't write certain algorithms if we don't know for sure that a garbage collector is cleaning up behind us; or escape analysis is making sure something gets allocated on the stack rather the heap. The point is that 99% of the time users don't care and don't want to care. By moving those decisions into the code through language constructs, we gain control in the 1% where it may make life slightly easier but we lose simplicity and ease of use in the remaining 99%. That's a bargain that leads directly to C++.

I'm not worried about runtime.Callers or debugging. By definition, runtime and debugging operations are low-level and require understanding of the implementation. There's ways to avoid TCO if need be.

[jimmyfrasche]

You still need to have the defer stack from before you entered the tail calls and for non-tail calls within a function.

I honestly can't really think of a case where mixing defer and become in a single function would be an advantageous thing to do off the top of my head. If there are some places where it's reasonable thing to do (like you only do it every 1000 iterations in a special circumstance), then you'd need to create a manual defer stack, which doesn't seem helpful.

It seems more a job for a static analyzer to warn you that that probably doesn't mean what you think and you can ignore it if you know better.

[cherrymui]

I agree with @griesemer that TCO is an optimization that is best left to the compiler.

An (probably terrible) alternative: compiler is allowed to optimize return to tail call in general, and introduce a mechanism to disable it when user really don't want it. For example, //go:notailcall or //go:keepframe, or use a temp variable. (Since this is for Go 2, we can change the behavior of runtime.Callers.)

[mdempsky]

My 2c:

I like the idea of reusing goto. I agree with the earlier arguments that conceptually tail calls are just a generalization of goto statements. (That said, to keep with current discussion conventions, I'm going to use become below instead.)

I'm not a fan of having the behavior sometimes fallback to generic return behavior. I think we should identify conditions that support tail-call semantics, and declare it an error to use become otherwise.

I think the constraints for when we can support tail calls are: calling a function or method, whose result signature is identical to the calling functions.

Note that this recommendation would disallow implicit conversions currently allowed by return such as:

func f() int { ... }

func g() interface{} {
    become f() // ERROR: got (int), want (interface{})
}

Rationale: Without disallowing interface conversions, we would need some way at f's return to know to convert the int into an interface{}.

I'm uncertain about defers. As an implementation detail, we currently have special defer unwinding code for functions that use defers. If g has a defer and tail calls f and we expect the defer to live until f returns, then f will need that unwind code too, regardless of whether it has its own defers. That would probably require a lot more unwind code.

Related to defers, what about return parameter identity? Suppose:

func f() (q int) {
    defer func() {
        q = 1 // Does this guarantee f returns 1 regardless of g's behavior?
    }()
    become g(&q)
}

func g(p *int) (r int) {
    // Does p == &r here?
}

As another implementation detail, we'll need to make sure that if f can tail call g, that f and g's calling convention match up for returns. Currently with the gc toolchain that only holds if f and g have identical signatures, but I'd expect in general we want the input parameters to be allowed to vary.

Right now, for function calls we logically place the callee's function parameters in the caller's call frame. I think we'll need to rework this so the caller builds up the parameters into the callee's frame instead. This should be transparent to Go authors, but it will affect Go assembly.

The alternative option I see is we can use compiler-inserted defers (or something logically equivalent) to handle shuffling the stack around as necessary to satisfy the original caller's expectations.

[faiface]

If there was return and become in the language, what would be the use-case for return? Would there be any real use-case any more? Because I don't see one.

I would actually suggest simply making the return keyword always do tail "optimization" when there's a function call.

[jimmyfrasche]

@griesemer those are all good points. I'm almost willing to defect to your side.

I am still a bit weary of tail call elimination in limited cases. I get that purely as an optimization transitional forms are better than nothing, but you can't really rely on it until it's all there and there are only a small number of cases:

• In a function without returns the tail positions are
  
  
  
  • the last line of the function or
  
  
  • any line directly before a return statement.
  
  
• In a function with returns the tail positions are
  
  
  
  • any line with a return statement.
  
  

whenever there's a single call in a tail position with the same return parameter types that's a tail call.

There are other things to consider like what if that call is a function pointer or a method or if it's implemented in assembler and the stuff @mdempsky pointed out above.

I think regardless of whether the ultimate plan is to

1. do nothing
2. always eliminate tail calls automatically when possible
3. have an explicit become statement to opt-in that's a compiler error if you can't make a tail call

it would be good to figure out all the exceptions and ramifications of TCE to make it clearer which of those three is the most sensible path.

If it's too hairy 1 might be best the option—you can always write a trampoline if you need it.

If the rules are very simple to understand 2 would be fine by me as long as you can rely on the fact that "after Go 1.x, these are guaranteed by the spec"

If it's possible but the rules for when TCE happens are hard to follow 3 or 1 seem preferable to me.

I'm mostly worried about a situation like @bcmills posited where you have to use a trampoline for a state machine even with automatic TCE because the rules are too baroque or implementation dependent. Maybe that still makes it a valuable optimization but without a guarantee you still have to write code as if there was no TCE at all.

[cpansprout]

@mdemsky wrote:

Rationale: Without disallowing interface conversions, we would need some way at f's return to know to convert the int into an interface{}.

I don’t know how helpful this is: Perl stores all calling context information in the call stack, so when goto &foo replaces the current function, all the information about the calling context is still there.

If f returns int and g returns interface{} (i.e., there is some implicit type coercion), is it not possible for the function that calls g to coerce whatever type it gets? Or does the type coercion that will take place need to be known when the code is compiled?

[mdempsky]

@cpansprout

If f returns int and g returns interface{} (i.e., there is some implicit type coercion), is it not possible for the function that calls g to coerce whatever type it gets? Or does the type coercion that will take place need to be known when the code is compiled?

In the gc implementation, parameters are represented on the stack the same as they are elsewhere in memory. For example, on amd64, an int is an 8-byte scalar value, while an interface{} is a 16-byte 2-pointer value.

We also currently compile functions assuming this. For example, when a function calls something that returns an int, there's no logic to verify that the callee actually returned an int.

We could abstract function return signatures and dynamically convert result parameters to their expected type, but I think that would substantially hinder function call performance.

[ianlancetaylor]

@griesemer I am of course fine with not implementing this proposal. And I'm fine with having the compiler use tail calls in some cases with appropriate adjustments, somehow, to runtime.Callers.

That said, I don't agree that we don't have to worry about runtime.Callers. Code relies on it being accurate, and if the compiler inserts tail calls when possible it must continue to work as expected.

And, I don't agree that having the compiler sometimes insert tail calls is the same as become. Compiler optimizations are fine. The reason for the proposal is that there is a style of programming, used mostly in functional languages and in Scheme, in which each function simply hands off to another function. That style of programming requires that tail calls work reliably. If they do not work reliably--if they are merely a compiler optimization that sometimes happens and sometimes doesn't--then that style of programming can not be used. That is why, for example, Scheme requires tail calls (http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11). It's fine for us to decide that style of programming can not be used with Go, but we shouldn't start thinking that a compiler optimization is the same thing as a required tail call.

[jimmyfrasche]

@ianlancetaylor

The compiler always eliminating all tail calls and it being guaranteed by the spec is like having become (without the choice). You can tail recurse with abandon and create state machines like the lexer in text/template/parse directly without worrying about stack depth. Either become or a strict guarantee suffice to enable that style of programming.

Some compilers sometimes eliminating some tail calls is exactly the same as today, though. Some code will be more optimized, but you still need to use workarounds like trampolines even if all tail calls happen to be eliminated as otherwise you're relying on implementation details that are subject to change or you require a particular version of a particular compiler.

[mdempsky]

As another implementation concern, apparently ppc64le with dynamic linking doesn't currently support tail calls: d25c3eadea9bc5c8b6451c3502d6063dd618a3af.

Perhaps that could be fixed though.

[smasher164]

I like @cherrymui's suggestion to provide the compiler a directive that is not from the language. @griesemer is correct in that introducing become will require an up-front decision on whether to use return or become. However, @bcmills is also correct in that making the optimization implementation-dependent results in non-portability.

Perhaps having a flag like go build -gcflags="-elimtailcalls" would guarantee that only a release or compiler that supports tail call elimination would compile the program.

[ghost]

https://github.com/golang/go/issues/22624#issuecomment-342653291

While my earlier comment got mixed reviews, I would add that probably its best to not pursue a continuity between a shell and programming language, golang and es/xs can coexist quite easily.

[CAFxX]

The way the feature is proposed sounds like a tradeoff between performance and debuggability ("if you want TCO, you don't get stack traces"). I don't think that's a good tradeoff if we really care about debuggability: stack traces should be always available IMHO, or you'll end up with something like:

Foo(...)
FuncThatTotallyDoesNotCallFooDirectly(...)

How is this a good debugging experience for she who did not write the code (and that does not know that maybe between those two stack frames there are tens of TCs)?

I think a design goal should be to be able to provide all stack frames, regardless of them being due to a normal call or a tail call.

(Incidentally, if this is the case, then the primary reason to provide a separate construct for "guaranteed tail calls" becomes moot)

[robpike]

@CAFxX The purpose of a tail call is to eliminate stack frames. Your objection is to the problem they solve, not to the solution.

Tail calls have a place in certain recursive systems, including mutually recursive ones, allowing easy expression of the computation without needless memory consumption. If you don't want them, don't use them.

Newsqueak had them - and only them, in fact - as an experiment. Alef added add them as an option, again as an experiment. Most functional languages provide them _ab initio_ because the idea of a tail call is really just a form of programming with function invocations. And a rather lovely one, at that.

If you don't program in that style, and most procedural programmers don't, you really have no need for tail calls. That argues that they be optional. Whether they should be optional depends on how important we feel the programming model they bring could be to Go programming.

[olopierpa]

On Wed, Nov 15, 2017 at 12:30 AM, Carlo Alberto Ferraris <
[email protected]> wrote:

The way the feature is proposed sounds like a tradeoff between performance
and debuggability ("if you want TCO, you don't get stack traces"). I don't
think that's a good tradeoff if we really care about debuggability: stack
traces should be always available IMHO, or you'll end up with something
like:

Foo(...)
FuncThatTotallyDoesNotCallFooDirectly(...)

How is this a good debugging experience for he who did not write the code
(and that does not know that maybe between those two stack frames there are
tens of TCs)?

When in a program there's a loop you don't have the history of past loop
iterations on the stack either. If you don't have Proper Tail Calls, then
what you can write with tail calls you must write with a (usually very)
convolute loop. Proper handling of tail calls doesn't take away any
debuggability as in the cases where PTC is useful there are no stack frames
anyway.

Proper Tail Calls are a way to write loops in a clearer and more modular
way.

[CAFxX]

@robpike sorry, I misworded my post. What I meant is callers, not stack frames. For debuggability, I want to know who called a certain function (that's what my example was about). And I think that this information should be available at least on demand. I'm 100% aware that reusing stack frames to implement tail calls makes this hard, but that's an implementation concern, not a design one.

How about restricting TCs to the case where, if needed, we can "synthethize" the call chain (excluding args, similarly to what's done for mid-stack inlining IIRC) from O(1) storage? That would get us debuggability and proper tail calls. I know this would be hard because that's basically turning everything into a giant state machine.

For the record, I think the argument that goes "if you don't like 'em don't use 'em" is lacking. I don't always get to choose which libraries I should use, and if the libraries that I depend on use the proposed TCs internally then I'm impacted regardless if I ~like~ use TCs in my code or not.

[robpike]

@CAFxX Since the original proposal at least involves using a different mechanism to invoke them, your concerns do not seem deal-breaking. Most programs simply won't use them. If a library uses them, the call stack will still contain the record of the point in your code that invoked them. It's somewhat like channels and concurrency: In general you can't tell which function sent a value on a channel, or which started a goroutine, but we use channels and goroutines anyway and are happy to have them. Debuggability isn't just about stacks.

Experience with the many languages that provide tail call optimizations, either explicitly or implicitly, shows that their benefits outweigh the costs when used appropriately. That's as it should be for every programming language feature.

I'm not arguing for or against the existence of a become statement in Go, I'm just saying that they are pretty nice to use in some situations and the fears I see expressed in these comments are overblown.

[carlmjohnson]

I think this code snippet is pretty common:

func MyHandler(w http.ResponseWriter, r *http.Request) {
    if url := someCondition(r); url != "" {
        http.Redirect(w, r, url, http.StatusTemporaryRedirect)
        return
    }

    ...
}

It always bugs me that I can't tear down the stack frame before redirecting. It's worth asking: should we optimize this away? Or should we make become http.Redirect(w, r, url, http.StatusTemporaryRedirect) legal? Both have downsides. In the first case, you're losing potentially useful stack info. In the second case, you're asking for programmers to micro-optimize for unclear results.

[bcmills]

In the first case, you're losing potentially useful stack info.

There is a third option, too: we could compact the stack frame without eliminating it completely (for example, chop it down to just a return address).

That would substantially reduce overhead for functions with large stack frames, although it wouldn't change tail calls from O(N) to O(1).

[jimmyfrasche]

@bcmills Scheme implementations do some interesting things wrt tail calls and stack frames. A bit hard to search for, but I found this:

MIT Scheme uses a ring-buffer to keep around the last 10-or-so frames. (Actually it is even nicer than that: it uses ringbuffer-of-ringbuffers to keep 10-or-so frames from each of the last 10-or-so non-tail recursive calls. So when debugging you can pop up the call stack, and then at each level examine the last couple interations of the loops done at that level).

From https://news.ycombinator.com/item?id=7794553

[bcmills]

A ring-buffer of stack frames only works if your stack frames have a small constant upper bound, or are heap-allocated or otherwise independently collectable.

I don't think either of those is a good idea for Go.

[subfuzion]

@robpike

Tail calls have a place in certain recursive systems, including mutually recursive ones, allowing easy expression of the computation without needless memory consumption. If you don't want them, don't use them.

True words! I take such delight in playing with Racket, a lisp dialect based on scheme. At the end of the day, I can't sacrifice the performance, libraries, ecosystem, compiled binaries and other joys of Go programming for most of my work, but oh man would I love to be able to exploit tail calls in Go 2.

[docmerlin]

You could do this with a become statement without having to wait for go 2. (because it wouldn't be a breaking change).
Also, I second the idea that we need automatic interface conversion.

[DeedleFake]

Adding a keyword is a breaking change as it becomes...

No pun intended...

It becomes unusable as an identifier.

[deanveloper]

Something that Kotlin does is a tailrec modifier on functions. So instead of

// prod starts at 1
func factorial(prod, n int) int {
    if n == 0 {
        return prod;
    }
    become factorial(prod * n, n - 1);
}

It would be

// prod starts at 1
tailrec func factorial(prod, n int) int {
    if n == 0 {
        return prod;
    }
    return factorial(prod * n, n - 1);
}

This is much more readable and still requires explicitly stating that tail recursion would be happening.

Also, tail recursion is a property of functions, not returns, so it'd make much more sense to put the attribute on the function declaration than to replace the return.

The only thing I can think of against this is that Go doesn't have any "function attributes" (stuff like private, static, strictfp, etc). This would be weird to have a function declaration that doesn't begin with func.

Another thing that could possibly be done is to make an entirely new feature (similar to how struct field tags behave, but for functions), although I'm not really sure of a clean syntax. Then some kind of "compile":tailrec tag could be added.

[bcmills]

tail recursion is a property of functions, not returns

What makes you say that? It seems like the only major difference between become and return is whether you delete the local stack frame before making the call, and we could fairly easily delete the frame along one path but preserve it along another.

[deanveloper]

@bcmills I guess I'm thinking of it a bit less down-to-earth. When I think of designing an algorithm "tail recursively" I think of designing the function that way, not the return. Therefore I think it'd make more sense to annotate something as tail-recursive in the function declaration than on the return.

I also think it would be much more readable as tailrec explicitly states that the function is tail-recursive, while "become" doesn't mean much to anyone who doesn't know that Go has support for TCO.

[bakul]

become complicates things. Now the compiler has to check if it is used properly. E.g. "become x*f()" is not tail recursive. Neither is "become f(), nil" (another argument in favor of sum types :-)). defer will defeat it as well. And the user has to decide where it makes sense to use become. Just unnecessary.

The argument about debuggability is that you can no longer see how you got to a specific function. Any trace of intermediate functions using tail-calls is gone in a traceback. This doesn't change whether TCO is automatic or a user used become liberally.

I partially agree with @griesemer. Let the compiler deal with this. But ideally I'd want Scheme like guarantee in Go that recursion can be replaced by tail-calls. This guarantee encourages people to write tail recursive functions (and often you can convert a non-tail-recursive function into one with tail recursion without much work).

Finally, aesthetically become in this context is unpleasing -- return and become feel very different. Smalltalk 's use of "become" as in "objA become: objB" at least made sense.

[saolof]

In terms of new enabled uses, I think Go would benefit a lot from having tail calls, especially when combined with Goroutines. You can create a state machine that operates on channels by defining a function for each state, and run it either sequentially or as a separate process with a goroutine, from any initial state. Very neat.

I'd support a separate syntax from return in Go (either named tailcall or become), simply because tail calls are more of a control statement like for or goto, not a return statement. The complaint about not having stack frames here is about as weird as complaining that loops don't create stack frames.

Having become or tailcall inside a function is a clear hint that you are explicitly using tail calls for control flow, which is good. With compiler enforcement it would also be incredibly useful for teaching tail calls to newbies. Considering that they often seem to be misunderstood by some people in every discussion about tail calls, having it enforced with special syntax by the compiler will likely be very beneficial.

[deanveloper]

The complaint about not having stack frames here is about as weird as complaining that loops don't create stack frames.

Not sure how much I agree with this... Go is a language that supports debugability, so if a bug happens within the TCO code, the stack trace would be all messed up and it would be hard to debug.

I would prefer tailcall greatly over become as it is _much_ clearer as to what is going on, especially to someone who is new to the language. If tailcall is used (assuming they know what TCO is) it's very obvious as to what's going on. If become is used, they would need to look up the become keyword before they knew what it did.

[ghost]

https://github.com/golang/go/issues/22624#issuecomment-342653291
https://github.com/golang/go/issues/22624#issuecomment-344160385

Noting the aforecited comments and that I'm neither an es nor an xs maintainer, anyone interested in development of those shells, and/or in testing the feasibility of utilising es/xs with golang?

[DeedleFake]

I'd support a separate syntax from return in Go (either named tailcall or become), simply because tail calls are more of a control statement like for or goto, not a return statement. The complaint about not having stack frames here is about as weird as complaining that loops don't create stack frames.

I hadn't thought about it that way before, but you're absolutely right. A tail call is not a return at all, and taking about it as if it is is quite inaccurate, I think. It's really more of a fancy goto. After all, any function with a become in it must also have a return in another control path unless you want an infinite loop.

[mitranim]

Why bother with tail calls when you have for loops?

[DeedleFake]

Because some things are significantly easier to deal with recursively. If become supports calling other functions, then that would also allow optimization of some call chains. For example, I've got a little scripting language I'm working on. The language 'compiles' down to a bunch of nested types that represent different types of expressions, essentially, which call each other when evaluated. In a good number of cases, these are tail calls, so a become would probably be more efficient than a return.

[cznic]

@Mitranim

And goto. \

[mitranim]

Please forgive my impudence, but I sincerely hope these kinds of features don't make it into the language. Not under the pretense of convenience, and certainly not under the pretense of performance, seeing as we're talking about optimizing away a few stackframes at best.

[cznic]

... few stackframes at best.

And an unbounded number of them in the worst case.

[mitranim]

Clarification: Go's apparent simplicity is both invaluable and fragile. It would only take a few features to ruin this quality. The Go team has already shown incredible restraint and conservatism, which often leads to better solutions down the road. Would be nice if this continued.

[mitranim]

@cznic As I understand, the problem lies in mutually recursive algorithms? Is there really no other way to express them stack-free?

[cznic]

Eg.: func f() { for { whatever } } is equiavalent to func f() { whatever; f() }. Under this proposal the form func f() { whatever; become f() } will not overflow the stack.

[mitranim]

As much as I ❤️ functional programming, one can make a solid argument that for functions that simply recur into themselves, TCO is no better than a simple for loop, which we already have.

I apologize if this is irrelevant or derails the discussion, but... Haskell provides a fascinating example demonstrating what happens in a language without for loops. Haskell folks have found an amazing hack that lets them emulate a for loop by exploiting lazy variable bindings. Link to the definition in GHC: [1]. Deciphering how this works is almost guaranteed to provide pleasant mental stimulation, like solving a puzzle.

I think it demonstrates the relative value of recursion and loops quite convincingly. Aside from mutual recursion, which indeed can be hard to avoid for some algorithms.

[bradfitz]

@Mitranim, @cznic, @DeedleFake, this exact conversation has already occurred several times in this thread. Let's move further discussion to Slack or golang-nuts or somewhere that doesn't spam other people subscribed to this bug.

(But yes, Go will continue to value simplicity.)

[SamWhited]

Please stop recommending Slack for these sorts of things. There are lots of contributors who are not on Slack and can't be on slack for legal reasons, accessibility reasons, etc. that may want to follow this conversation. Use the mailing list, to my knowledge everyone can find an email provider to receive emails.

[ghost]

@Mitranim

https://github.com/golang/go/issues/22624#issuecomment-392560662

http://www.stroustrup.com/hopl-almost-final.pdf

4.1.2 The STL emerges

Interesting story by the way on the background of the eventual implementation of the Standard Template Library.

[mortdeus]

So having gleamed over the discussion I take away a few things and have a few questions.

In newsqueak there is only a become statement. Does this mean that the language only ever uses one call frame? Or is there some sort of behind the scenes sorcery going on in the compiler that determines when it is smart to have normal return like behavior or goto? I also know the language is interpreted, so how does Go being a statically compiled language differ in this respect?

What I am getting at is why do we need a new keyword, when we can just make return do this? Also isn't this already how return behaves? To use a tail call optimization for functions that have calls to themselves defined within their function body?

Also as somebody mentioned earlier the use of a trampoline and the fact that a tail call optimization is to essentially replace a recursive return f() call that creates a new stack with a goto ENTRY, why shouldn't programmers just use an already existing feature?

I thought the whole rationality behind the adding of new features in Go was that we should do our best to avoid feature overlap when it makes sense.

I mean, from what I've seen people are suggesting is essentially.

tailcall func workA(x int) int{
    if x >= Limit{
        return x 
    }else{
        return work(x)
    }
}
func workB(x int) int{
    if x >= Limit{
    return x 
}else{
    return workB(x)
}

Which WorkA uses the same stack frame when it recursively calls itself and WorkB doesn't.

How is this any different?

func workA(x int) int{
Entry:
    if x >= Limit{
        return x 
    }else{
        change(x)
        goto Entry
    }
}

func workB(x int) int{
    if x >= Limit{
    return x 
}else{
    return workB(change(x))
}

[egorse]

If the go has something as runtime.UnwindStack(skip int) -- would it be close to "become" proposal? Wonder as such thing may helps as well for simpler error handling :rofl:

[ianlancetaylor]

@mortdeus The become statement, and tail calls in general, would apply when calling any function, not just for recursive calls to the same function.

@egorse Go already has that--it's called runtime.Callers--but I don't see why that is the same thing at all.

[egorse]

@ianlancetaylor the runtime.Callers returns to you stack info - can you really remove X entries from top of the stack with it?

[ianlancetaylor]

@egorse Sorry, I misunderstood your suggestion. I don't see how to implement removing stack frames from an active stack. Even if we did implement it, it seems like it could have very strange behavior.

[egorse]

@ianlancetaylor defer/recover/panic are capable to alter pc and sp without problem. hostile code can lead to strange behaviour but as well unsafe is there to shoot in the foot.

[DeedleFake]

Maybe I'm misunderstanding what you meant, but that seems a lot like saying that unrestricted goto is O.K. because calling a function is also a type of jump.

[egorse]

@DeedleFake here is what I mean:

func a(max int) int {
    return calc(0, max)
}

func calc(i int, max int) int {
    if i != 0 {
        runtime.UnwindStack(1)
    }

    if i == max {
        return i
    }

    return calc(i + 1)
}

[DeedleFake]

What happens to the stack when you call UnwindStack(1)? Does it just remove the stack frame above the current one, modifying the current one to return to where that one did? For example, like the following?

|Old Stack|New Stack|
|---------|---------|
|in: calc, ret: calc|in: calc, ret: a|
|in: calc, ret: a|<deleted>|
|in: a, ret: f|in: a, ret: f|

This seems extremely error-prone, and it also doesn't seem like it would work for several of the use cases of become. First of all, what happens if I call calc(3, 3) from a()? Does the a() frame get deleted? Second of all, what if I want to use become to call a different function than the one I'm currently in? How would I do that with UnwindStack()?

[egorse]

@DeedleFake I did not look yet how the defer/recover/panic unwinds the stack. probably there are no stack allocated variables and those all escape to heap. but if those triplets works - then it definitely possible safely remove frames from stack.

I think the top frame belongs to currently running function (otherway where the local vars are allocated?). So the runtime.UnwindStack(n) would remote top n frames out.

Lets for a while ignore difficulties with return values.
So the become could be done by two ways -

// become next(a, b, c)
runtime.UnwindStack(1)
next(a,b,c)

or via

func become(fn ...interface{}) {
    runtime.UnwindStack(2) // remove own frame and callers one
    // Use reflect to call fn and pass args
    reflect.ValueOf(fn).Call(...)
}
....
func caller() {
    ....
    become(next, a, b, c)
}

[DeedleFake]

I don't see what the benefit of this over become is, and it has a _lot_ of downsides. If you're modifying stack frames manually, you may as well be writing assembly at that point. And in that second example, I would guess that the overhead from using reflect would probably completely defeat the point of the optimization in the vast majority of cases.

[egorse]

@DeedleFake this was just funny generalisation of what might be needed for others cases.

Meanwhile become has own implementation complexity - i.e. only become to same function reasonable simple to implement (true jump), become to other known function requires call tree analysis due to local variables allocations, become to unknown function (i.e. function pointer) or in case call tree analysis did not resolve needed local stack allocation you may face local variables escaping to heap.

The reflect is not soo bad. reflect.TypeOf already does not lead to call. ValueOf lead to call but that's not big deal (if check code) and probably there is case on improvements.

[ghost]

@Mitranim

https://github.com/golang/go/issues/22624#issuecomment-392585953

A.S. failed to convince B.S. to make templates more like Ada generics.

A.S. later went on to design and implement "The STL".

Restraint and conservatism won out, the more favourable solution being implemented.

[bcmills]

@forskning, please keep the discussion on-topic. It's not at all clear to me what the design of the C++ STL has to do with tail recursion.

[bradfitz]

I'm actually just going to freeze this for now. We've adequately covered the various viewpoints in the many comments so far.

[ianlancetaylor]

We should only make changes to the language that address an important issue for many people. While this idea is interesting, it doesn't address a significant problem that people have using the language. So we are not going to do it.