Groups keyboard shortcuts have been updated
Dismiss
See shortcuts

Something from Alef - the become statement

408 views
Skip to first unread message

David Leimbach

unread,
Feb 14, 2012, 5:58:28 PM2/14/12
to golang-nuts
Was thinking a little about Alef today. Seemed like a pretty darned
nice language really that I hardly knew, and one of the things I
thought was rather novel about it was the "become" statement.

From the Alef User's Guide found here: http://doc.cat-v.org/plan_9/2nd_edition/papers/alef/ug

"The become statement transfers control in one of two ways. If its
operand evaluates to anything other than a function, become behaves as
a return statement yielding the result of the evaluation. When the
operand is a function returning exactly the same type as the current
function, the current function is replaced by the operand function and
control is transferred to the beginning of that function. There is a
crucial difference between a subroutine call and this form of function
invocation: the former creates a new subroutine context on the stack
before transferring control; the latter replaces the current function
context with the new context and transfers control. When a function
invokes itself or when several functions invoke each other via mutual
recursion using become, the computation runs in constant space. When
used in this form, the become statement is useful for implementing
functional style programs.
"

I think this could be an interesting addition to Go, especially around
interface types. It could enable some kinds of CPS style programming
that isn't really easily achieved in C or C++ without setjmp/longjmp
or ucontext stuff.

Anyone else think this is interesting?

Thomas Bushnell, BSG

unread,
Feb 14, 2012, 6:18:49 PM2/14/12
to David Leimbach, golang-nuts
I think this is very interesting.

It is called "tail call optimization", and is hardly an Alef invention. You can just spell it "return", and get the same effect; the compiler can simply detect the fact of the tail call and do the optimization.

The advantage of "become" is that it requires the compiler to do the tail call optimization, but that can be done as well by making it a requirement of the language that "return" do so. Scheme has shown that this can be done to great effect, and that when programmers are guaranteed that the tail call optimization will happen, possibilities of considerable power show up.

You also give some things up. For example, if you wish to target the JVM, it is all but impossible to do it efficiently, because the JVM imposes rules about stack frames which make it impossible. (You can do it with trampolines, but at a considerable efficiency cost.)

I think it would be interesting to see what happens if something like this were done in Go, but experience shows that if you make it an optional thing the compiler might do (which is what GCC does, for example), then you don't get much benefit from it as a programmer; and if you make it a rule which the compiler must do, then programmers depend on it, and you can't remove the requirement without turning working code into broken code. So it's a Pretty Big Decision.

Thomas

Evan Shaw

unread,
Feb 14, 2012, 6:47:21 PM2/14/12
to Thomas Bushnell, BSG, David Leimbach, golang-nuts
It's an interesting idea, but I think I would rarely use this feature
in practice. I'll default to being opposed to adding it.

On Wed, Feb 15, 2012 at 12:18 PM, Thomas Bushnell, BSG
<tbus...@google.com> wrote:
> It is called "tail call optimization", and is hardly an Alef invention. You
> can just spell it "return", and get the same effect; the compiler can simply
> detect the fact of the tail call and do the optimization.
>
> The advantage of "become" is that it requires the compiler to do the tail
> call optimization, but that can be done as well by making it a requirement
> of the language that "return" do so. Scheme has shown that this can be done
> to great effect, and that when programmers are guaranteed that the tail call
> optimization will happen, possibilities of considerable power show up.

It's been made pretty clear in the past that Go will probably not ever
require tail call optimization on return.
https://groups.google.com/d/msg/golang-nuts/nOS2FEiIAaM/miAg83qEn-AJ

> You also give some things up. For example, if you wish to target the JVM, it
> is all but impossible to do it efficiently, because the JVM imposes rules
> about stack frames which make it impossible. (You can do it with
> trampolines, but at a considerable efficiency cost.)

Go is already difficult to compile to JVM bytecode, so I don't think
this is such a problem.

- Evan

Michael Jones

unread,
Feb 14, 2012, 6:29:17 PM2/14/12
to Thomas Bushnell, BSG, David Leimbach, golang-nuts
You could call it "stay" as the opposite of "go" ...

qsort:
    split
    go qsort(left)
    stay qsort(right)

;-)
--
Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

David Leimbach

unread,
Feb 14, 2012, 7:57:21 PM2/14/12
to golang-nuts


On Feb 14, 3:18 pm, "Thomas Bushnell, BSG" <tbushn...@google.com>
wrote:
> I think this is very interesting.
>
> It is called "tail call optimization", and is hardly an Alef invention. You
> can just spell it "return", and get the same effect; the compiler can
> simply detect the fact of the tail call and do the optimization.

No it's not an Alef invention. I actually like being explicit, as you
say below :-).

Sometimes you want to be able to get a stack trace, and other times
you want the TCO to happen. You can let other people argue about
whether it's good to be implicit or explicit about this :-).

>
> The advantage of "become" is that it *requires *the compiler to do the tail
> call optimization, but that can be done as well by making it a requirement
> of the language that "return" do so. Scheme has shown that this can be done
> to great effect, and that when programmers are *guaranteed *that the tail
> call optimization will happen, possibilities of considerable power show up.
>

Actually require is like return in the cases where it could not be
tail call optimized.

> You also give some things up. For example, if you wish to target the JVM,
> it is all but impossible to do it efficiently, because the JVM imposes
> rules about stack frames which make it impossible. (You can do it with
> trampolines, but at a considerable efficiency cost.)

Clojure has a special syntax to recur to the same function as the only
non-stack consuming looping construct, but it can only do looping, not
CPS style computation.

>
> I think it would be interesting to see what happens if something like this
> were done in Go, but experience shows that if you make it an optional thing
> the compiler *might *do (which is what GCC does, for example), then you
> don't get much benefit from it as a programmer; and if you make it a rule
> which the compiler *must *do, then programmers depend on it, and you can't
> remove the requirement without turning working code into broken code. So
> it's a Pretty Big Decision.
>

I agree it's a big decision, I'm just interested if anyone sees value
in this, the way it was done in Alef.

Thomas Bushnell, BSG

unread,
Feb 14, 2012, 7:59:32 PM2/14/12
to David Leimbach, golang-nuts
On Tue, Feb 14, 2012 at 4:57 PM, David Leimbach <lei...@gmail.com> wrote:

Sometimes you want to be able to get a stack trace, and other times
you want the TCO to happen.  You can let other people argue about
whether it's good to be implicit or explicit about this :-).

Most Scheme systems deal with this by tracing function invocations, which (it turns out) is usually even more valuable than a stack trace. They maintain a (variably sized) buffer which you can use to hold as many as you want.

Thomas

David Leimbach

unread,
Feb 14, 2012, 8:37:34 PM2/14/12
to golang-nuts


On Feb 14, 3:47 pm, Evan Shaw <eds...@gmail.com> wrote:
> It's an interesting idea, but I think I would rarely use this feature
> in practice. I'll default to being opposed to adding it.

On deeper reflection I'm beginning to agree with you.

In trying to explore this further a bit I'm having some trouble coming
up with a good way for this to work out with respect to panic/recover.

func OpenCPS(name string, onError func(Error), next func(*File)) {
file, err := os.Open(string)
if file != nil {
become next(file)
}
else if err != nil {
become onError(err)
}
}

A couple things look a bit weird here.

1. Become doesn't feel like it would work very well the way Go
currently works with return statements. With the version of Go I have
installed, Go would complain if I used "return" where "become" is
here. Become would have to be the last statement of the function to
avoid that and that seems to mean that I'd need to capture both the
function in some external var as well as the arguments to it that are
appropriate. It would be a function of interface{} with an
interface{} var. Messy.

2. What happens with Panic/Recover when one becomes another function?

This could get really hairy really fast I reckon.

Go really doesn't need to be a functional language anyway :-).

Dave

David Leimbach

unread,
Feb 14, 2012, 8:38:15 PM2/14/12
to golang-nuts


On Feb 14, 4:59 pm, "Thomas Bushnell, BSG" <tbushn...@google.com>
wrote:
> On Tue, Feb 14, 2012 at 4:57 PM, David Leimbach <leim...@gmail.com> wrote:
>
> > Sometimes you want to be able to get a stack trace, and other times
> > you want the TCO to happen.  You can let other people argue about
> > whether it's good to be implicit or explicit about this :-).
>
> Most Scheme systems deal with this by tracing function invocations, which
> (it turns out) is usually even more valuable than a stack trace. They
> maintain a (variably sized) buffer which you can use to hold as many as you
> want.
>

It's like a built-in Writer Monad!

> Thomas

James McKaskill

unread,
Feb 14, 2012, 11:24:29 PM2/14/12
to Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts
On Tue, Feb 14, 2012 at 18:47, Evan Shaw <eds...@gmail.com> wrote:
It's an interesting idea, but I think I would rarely use this feature
in practice. I'll default to being opposed to adding it.


I've always found tail calls a great way of writing non-trivial state machines to the point that these days I write them using tail calls first and then convert to a goto mess with explicit state variables for languages that lack it. Considering how nice go is for network servers and the like, I would find tail calls very handy. However I think an explicit tail call ala become would be by far the best way to go because:

A) Implicit tail calls only work when all implementations provide it, which requires that its a language requirement from the start. Otherwise your code _may_ blow up on some implementations but not on others without rhyme nor reason. I remember seeing a similar argument for why python shouldn't have tail calls.

B) Its more in the go spirit of explicit over implicit

Personally the use case for explicit tail calls is quite different for implicit TCO. I quite agree with not necessarily having TCO since it makes stack traces useless, but explicit tail calls tend to replace horribly complex switch-while loops which don't use stack anyways.

As for dealing with defer, panic and recover have the "become" construct completely pop the existing stack including calling all of the defer statements. Since an explicit become doesn't look like "return SubroutineCall()" it can have different semantics.

-- James

Evan Shaw

unread,
Feb 14, 2012, 11:32:23 PM2/14/12
to David Leimbach, golang-nuts
I'm not sure why I'm defending this feature since I don't support it, but...

On Wed, Feb 15, 2012 at 2:37 PM, David Leimbach <lei...@gmail.com> wrote:
> func OpenCPS(name string, onError func(Error), next func(*File))  {
>    file, err := os.Open(string)
>    if file != nil {
>        become next(file)
>    }
>    else if err != nil {
>        become onError(err)
>    }
> }
>
> A couple things look a bit weird here.
>
> 1. Become doesn't feel like it would work very well the way Go
> currently works with return statements. With the version of Go I have
> installed, Go would complain if I used "return" where "become" is
> here.

This doesn't seem like such a problem. Your code is not very
idiomatic. Normally you'd handle the error in an if, omit the else,
and on the regular path assume that file != nil.

> 2. What happens with Panic/Recover when one becomes another function?

I think the only decision to make is what happens to deferred calls.
There are two options:
1. Deferred calls are executed on become statements
2. Deferred calls are executed when the "became" function returns

#1 is probably the way to go. #2 would add some overhead to all
function returns since a function couldn't statically know whether or
not it has any deferred calls to execute.

- Evan

Ken Thompson

unread,
Feb 14, 2012, 11:42:01 PM2/14/12
to Evan Shaw, David Leimbach, golang-nuts
i wouldn't mind adding become to go.
with it, the spec would explicitly state
how tail recursion would work rather
than leaving it up to compiler implementation.

as for defer, it should act as if the become
statement was a call followed by a return.
thus defers should be executed when the
bcome-er returns.

Steven Blenkinsop

unread,
Feb 15, 2012, 12:50:57 AM2/15/12
to James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts
You could use state functions to get much the same code structure as you would have with tail calls:

Rob 'Commander' Pike

unread,
Feb 15, 2012, 2:11:42 AM2/15/12
to Steven Blenkinsop, James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts
I have a soft spot for
type state func() state
myself, but then I also have a soft spot for 'become' (which is more general than tail recursion, for those following along at home).

roger peppe

unread,
Feb 15, 2012, 5:04:39 AM2/15/12
to Rob 'Commander' Pike, Steven Blenkinsop, James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts
On 15 February 2012 07:11, Rob 'Commander' Pike <r...@google.com> wrote:
> myself, but then I also have a soft spot for 'become' (which is more general than tail recursion, for those following along at home).

how is it more general?

chris dollin

unread,
Feb 15, 2012, 5:10:25 AM2/15/12
to roger peppe, Rob 'Commander' Pike, Steven Blenkinsop, James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts

Presumaby it doesn't need to appear as a tail action.

EG

if whatever {
partone
if wossname become g(y)
parttwo
}
partthree

g(y) isn't a tail call but as I read the description of `become` it's
use there is OK.

Chris

--
Chris "head-recursive" Dollin

roger peppe

unread,
Feb 15, 2012, 5:19:04 AM2/15/12
to chris dollin, Rob 'Commander' Pike, Steven Blenkinsop, James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts

isn't that exactly equivalent to this?

if whatever {
partone
if wossname {
return g(y)
}
parttwo
}
partthree


of course with functions that return nothing, the return statement
should immediately follow the call, but i don't think this
makes tail call optimisation less general.

(interestingly, Limbo specifically allowed a function that
returned nothing to "return" a call to another such function,
to make tail call analysis easier, although tail call optimisation
was never implemented, for the reasons mentioned in this thread).

i'd be happy with an explicit "become" BTW.

Rob 'Commander' Pike

unread,
Feb 15, 2012, 6:09:34 AM2/15/12
to roger peppe, Steven Blenkinsop, James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts

it needn't be a recursion.

-rob

unread,
Feb 15, 2012, 6:20:33 AM2/15/12
to golang-nuts
On Feb 15, 8:11 am, Rob 'Commander' Pike <r...@google.com> wrote:
> 'become' (which is more general than tail recursion, for those following along at home).

More general than tail recursion?

Impossible!

The only difference I see is that 'become' is imperative/explicit.

unread,
Feb 15, 2012, 6:25:52 AM2/15/12
to golang-nuts
In my opinion, an example of "more general than tail recursion" would
be:

func f(args...) {
analyse-call-chain
if analysis-yielded-something-useful then
tail-call
else
no-tail-call
}

roger peppe

unread,
Feb 15, 2012, 7:15:35 AM2/15/12
to Rob 'Commander' Pike, Steven Blenkinsop, James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts

it's not more general than tail call optimisation though, is it?
(that's what i was thinking about, even though you said "recursion").

James McKaskill

unread,
Feb 15, 2012, 7:57:49 AM2/15/12
to Steven Blenkinsop, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts

You could use state functions to get much the same code structure as you would have with tail calls:


I'm not sure what that link shows. It just shows up as a series of slides with numbers ....

If you're thinking of a state machine with just a plain function representing each state than that's only half way there. The advantage of tail calls for state machines is that the state specific data are just the variables for the function. So rather than

type allstatedata struct{
state1var...
state2var...
}
func state1(allstatedata)
func state2(allstatedata)

you can have

func state1(state1var ...)
func state2(state2var ...)


Thinking over the defers, I've actually switched to agreeing with Ken. Defer should occur after the becomer returns otherwise code like the following would be weird:

f := os.Open(...)
defer f.Close()

become stateThatUsesFile(f)

That approach has the disadvantage of not completely removing all state from the first function when becoming a second. However the defer mechanism already has to deal with a variably sized list of functions to defer. So we just have to tack on to this list of things to clean up once an actual return comes through and then get rid of the stack frame before jumping to the next function.

-- James

Thomas Bushnell, BSG

unread,
Feb 15, 2012, 9:08:18 AM2/15/12
to Rob 'Commander' Pike, golang-nuts, David Leimbach, James McKaskill, Steven Blenkinsop, Evan Shaw, roger peppe

Become is more general than tail recursion, but not more general than proper tail call elimination...since it is merely a syntax for the latter.

Vanja Pejovic

unread,
Feb 15, 2012, 9:12:34 AM2/15/12
to James McKaskill, golang-nuts, Thomas Bushnell, BSG, David Leimbach, Steven Blenkinsop, Evan Shaw

The way I understand it is: become can handle cases where the call is not a tail call. For example:

func f() int {
    // ... a bunch of work and state
    return q(somevar), + y(othervar);
}

This cant be tail call optimised, but become could replace the return statement with a function that returns int and whose body is

    return q(somevar) + y(othervar)

I quite like the idea.

On Feb 15, 2012 7:57 AM, "James McKaskill" <ja...@foobar.co.nz> wrote:

Thomas Bushnell, BSG

unread,
Feb 15, 2012, 9:16:09 AM2/15/12
to Michael Jones, golang-nuts, David Leimbach, Steven Blenkinsop, James McKaskill, Evan Shaw

You're confusing tail calls with tail recursion. The latter is more limited. Scheme, which requires proper tail call elimination, mandates the case you describe here under become.

As for defer, my inclination would be to say that a function cannot use become if it also uses defer since it isn't in tail position. If you execute the defer early (before making jump) then you've changed the meaning of defer. And if you do it late (after the jumped function returns) then you break the space expectations of become, because you must keep an implicit bit of stack frame around somewhere. Whether on the heap or not, you would no longer be able to have an unbounded number of become operations in progress.

That inconsistency is enough reason to keep it out of Go IMO.

Thomas

On Feb 15, 2012 5:41 AM, "Michael Jones" <m...@google.com> wrote:
It is certainly more general. Why is clear when you think of the implementation:

tail call: if final statement in code path is a recursive call, then play with input argument settings and JUMP rather than CALL to the first bit of this function's machine code.

become (or "stay" in my parlance, since if we can "go" we should also be able to "stay"): if arbitrary called function has same argument and return signature, and programmer says so, then play with input argument settings and JUMP rather than CALL to the first bit of named function's machine code.

The latter can happen anywhere in the function and can JUMP to any other function that matches the calling functions signature. It makes stack trace unwinding a bit muddy as to how the instruction pointer got there, but that's the price of freedom. This is GOTO for functions.

Can we agree that this is more general?

P.S. I've done something this in my own code in GCC. I use its magic computed goto.

Thomas Bushnell, BSG

unread,
Feb 15, 2012, 9:18:53 AM2/15/12
to Vanja Pejovic, golang-nuts, Steven Blenkinsop, David Leimbach, James McKaskill, Evan Shaw

The originally stated semantic for become said that it only does a go to when the value is an explicit function call, not an addition.

unread,
Feb 15, 2012, 9:26:11 AM2/15/12
to golang-nuts
On Feb 15, 3:12 pm, Vanja Pejovic <vvaf...@gmail.com> wrote:
> The way I understand it is: become can handle cases where the call is not a
> tail call. For example:
>
> func f() int {
>     // ... a bunch of work and state
>     return q(somevar), + y(othervar);
>
> }
>
> This cant be tail call optimised,

A tail call can be optimized in exactly the same way as you suggested
below. It is only a matter of implementing the optimization.

Don't trust the Commander! Tail calls and 'become' are equivalent. The
only difference is that 'become' is an explicit request to the
compiler about what it has to do with the code.

Henrik Johansson

unread,
Feb 15, 2012, 9:33:58 AM2/15/12
to Thomas Bushnell, BSG, golang-nuts, James McKaskill, David Leimbach, Steven Blenkinsop, Vanja Pejovic, Evan Shaw

Become seems really powerful. I would settle for tail call optimization but if become works as a manual tco then it has my vote.

/Henrik

Michael Jones

unread,
Feb 15, 2012, 8:41:02 AM2/15/12
to James McKaskill, Steven Blenkinsop, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts
It is certainly more general. Why is clear when you think of the implementation:

tail call: if final statement in code path is a recursive call, then play with input argument settings and JUMP rather than CALL to the first bit of this function's machine code.

become (or "stay" in my parlance, since if we can "go" we should also be able to "stay"): if arbitrary called function has same argument and return signature, and programmer says so, then play with input argument settings and JUMP rather than CALL to the first bit of named function's machine code.

The latter can happen anywhere in the function and can JUMP to any other function that matches the calling functions signature. It makes stack trace unwinding a bit muddy as to how the instruction pointer got there, but that's the price of freedom. This is GOTO for functions.

Can we agree that this is more general?

P.S. I've done something this in my own code in GCC. I use its magic computed goto.

unread,
Feb 15, 2012, 10:24:20 AM2/15/12
to golang-nuts
On Feb 15, 2:41 pm, Michael Jones <m...@google.com> wrote:
> It is certainly more general. Why is clear when you think of the
> implementation:
>
> tail call: if final statement in code path is a recursive call, then play
> with input argument settings and JUMP rather than CALL to the first bit of
> this function's machine code.
>
> become (or "stay" in my parlance, since if we can "go" we should also be
> able to "stay"): if arbitrary called function has same argument

'become' doesn't require same input-argument types.

> and return
> signature, and programmer says so, then play with input argument settings
> and JUMP rather than CALL to the first bit of named function's machine code.
>
> The latter can happen anywhere in the function and can JUMP to any other
> function that matches ...

You seem to be saying that some tail calls cannot happen where
'become' can happen. I disagree. What would those "tail calls that
cannot happen where 'become' can happen" look like?

Steven Blenkinsop

unread,
Feb 15, 2012, 11:19:23 AM2/15/12
to James McKaskill, Evan Shaw, Thomas Bushnell, BSG, David Leimbach, golang-nuts
On Feb 15, 2012, at 7:57 AM, James McKaskill <ja...@foobar.co.nz> wrote:


You could use state functions to get much the same code structure as you would have with tail calls:


I'm not sure what that link shows. It just shows up as a series of slides with numbers ....

It's supposed to be the slides from this talk:
http://www.youtube.com/watch?v=HxaD_trXwRE

Apparently some devices don't show them.

If you're thinking of a state machine with just a plain function representing each state than that's only half way there. The advantage of tail calls for state machines is that the state specific data are just the variables for the function. So rather than

Yeah, basically, and tail calling would be returning the state function to be called. Note that you could use closures to get the effect you describe of being able to supply the arguments from the scope of the previous state function. However, in many state machines, there would be a persistent state element that would be best kept in a struct passed to each function.

Anyways, this isn't to say that become wouldn't be useful. I'm just showing that there is a third, reasonably attractive, option, besides tail calls and state switches.

Ian Lance Taylor

unread,
Feb 15, 2012, 11:25:24 AM2/15/12
to ⚛, golang-nuts
⚛ <0xe2.0x...@gmail.com> writes:

> Don't trust the Commander! Tail calls and 'become' are equivalent. The
> only difference is that 'become' is an explicit request to the
> compiler about what it has to do with the code.

I see two important distinctions. First, a problem with the general
tail call optimization is that it makes debugging more difficult and
makes stack traces less useful; an explicit become indicates that the
programmer is willing to accept that. Second, the general tail call
optimization can be defeated in various ways in a language like Go whose
types are not all the same size; an explicit become tells the compiler
that it must succeed or explicitly fail, whereas the optimization may
simply not be applied in cases where the programmer expects it to
succeed.

(An example of a case where the general optimization will not be applied
would be something like a function F which ends with return G(H()) where
H returns a struct that must be passed to G partially on the stack and
partially in registers. Doing this as a tail call requires a lot of
stack shuffling to ensure that when G returns it will return to the
caller of F with the stack in the right place, or it requires abandoning
other, on average more powerful, optimizations such as frame pointer
elimination. When tail calls are just an optimization, not a
requirement, this is typically not worth doing. Languages like Scheme
that mandate tail calls do not have this kind of issue.)

Ian

David Leimbach

unread,
Feb 15, 2012, 12:21:35 PM2/15/12
to golang-nuts

>
>
> > func OpenCPS(name string, onError func(Error), next func(*File))  {
> >    file, err := os.Open(string)
> >    if file != nil {
> >        become next(file)
> >    }
> >    else if err != nil {
> >        become onError(err)
> >    }
> > }
>
> > A couple things look a bit weird here.
>
> > 1. Become doesn't feel like it would work very well the way Go
> > currently works with return statements. With the version of Go I have
> > installed, Go would complain if I used "return" where "become" is
> > here.
>
> This doesn't seem like such a problem. Your code is not very
> idiomatic. Normally you'd handle the error in an if, omit the else,
> and on the regular path assume that file != nil.

Yeah I find the way I have to handle errors in Go to be pretty
tiresome actually. If there was a way to dump all the "if"
boilerplate around calls that return multiple values with an error
value, I'd jump on it in a second. I blame Haskell and the Maybe
parametric type.

>
> > 2. What happens with Panic/Recover when one becomes another function?
>
> I think the only decision to make is what happens to deferred calls.
> There are two options:
> 1. Deferred calls are executed on become statements
> 2. Deferred calls are executed when the "became" function returns
>
> #1 is probably the way to go. #2 would add some overhead to all
> function returns since a function couldn't statically know whether or
> not it has any deferred calls to execute.

#2 should never happen, you don't return to become. Your function is
replaced on the stack with the new function that's been 'become`d'


>
> - Evan

Michael Jones

unread,
Feb 15, 2012, 10:15:10 AM2/15/12
to Thomas Bushnell, BSG, golang-nuts, David Leimbach, Steven Blenkinsop, James McKaskill, Evan Shaw
OK. I can see that. (Perhaps I am too influenced by Steve Slade's T) This leaves us with the notion of "if args and return sig match then a JUMP is possible in place of a CALL" and should there be an explicit request or an implicit requirement. It is certainly true that knowing when it will happen is necessary for choosing certain coding strategies given efficiency and space concerns. It came up in my edits to the big library's nat.go functions -- I made a loop at the function prologue to implement what I commented as "poor man's tail call optimization."


On Wed, Feb 15, 2012 at 6:16 AM, Thomas Bushnell, BSG <tbus...@google.com> wrote:
You're confusing tail calls with tail recursion. The latter is more limited. Scheme, which requires proper tail call elimination, mandates the case you describe here under become.



Michael Jones

unread,
Feb 15, 2012, 10:38:05 AM2/15/12
to ⚛, golang-nuts
I was wrong to include input argument signature in my comments.

unread,
Feb 15, 2012, 2:09:05 PM2/15/12
to golang-nuts
Ok, I think I see why you wrote that 'become' is more general than
tail recursion. By tail recursion you meant: a function calling the
same function:

func f(i int) int { return f(i+1) }

The problem is indirect recursion. By just looking at the following
code in isolation:

func F(i int) int { return otherPackage.G(i+1) }

it cannot be determined whether this leads to recursion or not (will G
call F?). Therefore, in a language that eliminates tail recursion, the
compiler needs to consider *all tail calls* - not just recursive
calls.

Not to mention this:

type T func (int, T) int
func f(i int, g T) int { return g(i+1, next_g(i)) }

Thomas Bushnell, BSG

unread,
Feb 15, 2012, 2:41:49 PM2/15/12
to Ian Lance Taylor, ⚛, golang-nuts
Thanks for this, Ian. I think this highlights why "become" should probably not be added to Go.

Though, I agree that if a proper tail call feature were to be added, the argument here is very compelling that simply requiring "return" to do tail call elimination whenever it's in tail position would be a bad idea.

Languages are not just bags of features, and the fact that Go can return complex data as values (rather than only as pointers) is a very significant difference in the implementation of tail call elimination which I had not considered.

Thomas

Thomas Bushnell, BSG

unread,
Feb 15, 2012, 2:45:09 PM2/15/12
to ⚛, golang-nuts
The standard example in Scheme is the odd/even pair, which should be able to complete without memory exhaustion with any non-negative argument. (Actually, the requirement of the Scheme standard is even stricter than this; even if it's not recursion of any source--indirect or direct--it must work. In a language with call/cc where you can use tail calls as a way of switching between threads, this becomes important.)

(define (odd n)
  (and (not (= n 0)) (even (- n 1))))
(define (even n)
  (or (= n 0) (odd (- n 1))))

Thomas

David Leimbach

unread,
Feb 15, 2012, 3:17:56 PM2/15/12
to golang-nuts
> As for defer, my inclination would be to say that a function cannot use
> become if it also uses defer since it isn't in tail position. If you
> execute the defer early (before making jump) then you've changed the
> meaning of defer. And if you do it late (after the jumped function returns)
> then you break the space expectations of become, because you must keep an
> implicit bit of stack frame around somewhere. Whether on the heap or not,
> you would no longer be able to have an unbounded number of become
> operations in progress.

> That inconsistency is enough reason to keep it out of Go IMO.

Go has inconsistencies already though, for convenience. See how one
appends to a map and the talk of a parametric type which is
unavailable to all other functions in the language.

While consistency of a language makes it really much easier to reason
about the language itself, I'm not sure how much it helps the
programmer in a practical sense.

That said, I've also argued that defer is a little tricky in light of
become and also possibly drives become into the inconsistent space
that makes me uncomfortable, though Ken seems to think it's not too
bad.

I'd be very willing to experiment with become and see what it looks
like. Right now I'm just hypothesizing. Paralysis by analysis if you
will.

Dave

David Leimbach

unread,
Feb 15, 2012, 3:21:37 PM2/15/12