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
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 :-).
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 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
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.
how is it more general?
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
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.
it needn't be a recursion.
-rob
it's not more general than tail call optimisation though, is it?
(that's what i was thinking about, even though you said "recursion").
You could use state functions to get much the same code structure as you would have with tail calls:
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.
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.
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
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.
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.
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
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
> 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
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.