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 ***@***.***> 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 👍 on being explicit.

[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. </heresy>

[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

#22624 (comment)

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 🤣

[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

#22624 (comment)

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.