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.

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?