Something from Alef - the become statement
David Leimbach
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
Evan Shaw
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
;-)
David Leimbach
On Feb 14, 3:18 pm, "Thomas Bushnell, BSG" <tbushn...@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.
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
> of the language that "return" do so. Scheme has shown that this can be done
>
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.)
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
> it's a Pretty Big Decision.
>
in this, the way it was done in Alef.
Thomas Bushnell, BSG
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 :-).
David Leimbach
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.
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
On Feb 14, 4:59 pm, "Thomas Bushnell, BSG" <tbushn...@google.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
James McKaskill
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.
Evan Shaw
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
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
Rob 'Commander' Pike
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
> 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
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
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
it needn't be a recursion.
-rob
⚛
> 'become' (which is more general than tail recursion, for those following along at home).
Impossible!
The only difference I see is that 'become' is imperative/explicit.
⚛
be:
func f(args...) {
analyse-call-chain
if analysis-yielded-something-useful then
tail-call
else
no-tail-call
}
roger peppe
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
You could use state functions to get much the same code structure as you would have with tail calls:
Thomas Bushnell, BSG
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
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.
Thomas Bushnell, BSG
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.
Thomas Bushnell, BSG
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.
⚛
> 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,
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
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
⚛
> 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
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
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
Ian Lance Taylor
> 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
>
>
> > 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.
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.
replaced on the stack with the new function that's been 'become`d'
>
> - Evan
Michael Jones
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
⚛
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
Thomas Bushnell, BSG
David Leimbach
> 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.
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
On Feb 15, 12:17 pm, David Leimbach <leim...@gmail.com> wrote:
> > 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.
jimmy frasche
defer f()
return g() //invoke f after g
defer f()
become g() //invoke f after g
If you disallowed defer and become intermingling what happens if I
call a function w that becomes a function w' from a function with a
defer? You get an error? That would be obnoxious because you'd have to
know the implementation details of w.
That said, I'm on the fence about become. There's part of me that
really wants it. But I really want ice cream. That doesn't mean it's
good for me. I don't think I'd use it in practice much.
But I don't use panic in practice much (well now that the new toy
shine has come off it :)), but when I do I need it in that it would be
annoying not to have it. It being there simplifies my life a lot.
I think become falls into that category. I could write a trampoline
function and that—I have to agree with Rob, here—is fun and cool.
However, perhaps, my intention is much more clearly expressed with
become.
On the whole I'm going to +1 become: IF it can be made to work with
defer sanely without complicating things. I'd be sad if it ended up
not getting it, but I wouldn't be heartbroken.
Thomas Bushnell, BSG
David Leimbach
> P.S. I've done something this in my own code in GCC. I use its magic
> computed goto.http://gcc.gnu.org/onlinedocs/gcc-3.2/gcc/Labels-as-Values.html
>
https://github.com/quartzjer/js0n/blob/master/js0n.c
I have code that's very similar, and though it's nonstandard C, it
seems to work well in clang and gcc (with the right options).
If I had "become" in C, I wouldn't need this non-standard stuff to
produce nice looking code that works the same way. It's an assembly
jump table in my mind.
Skip Tavakkolian
go nuts()
be nuts()
On Tue, Feb 14, 2012 at 3:29 PM, Michael Jones <m...@google.com> wrote:
> You could call it "stay" as the opposite of "go" ...
>
> qsort:
> split
> go qsort(left)
> stay qsort(right)
>
> ;-)
>
> On Tue, Feb 14, 2012 at 3:18 PM, Thomas Bushnell, BSG <tbus...@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.
>>
>> 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
>>
>> On Tue, Feb 14, 2012 at 2:58 PM, David Leimbach <lei...@gmail.com> wrote:
>>>
>>> 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?
jimmy frasche
I understand what you're saying.
If you had a bunch of defer calls within a tail recursive function
it's not constant space. But that's not a misinteraction of language
features. That's as much an error as leaving out the base case. (Maybe
there are even some cases where you want to do that because sure you
have n defers to make but at least it's not n defers and n rets—but I
would assume that's an error unless the comment contained a written
apology, in which case I'd only suppose it was an error.)
However, one could very reasonably expect to call or become a tail
recursive implementation of, say, factorial from a function that has a
defer'd resource.Close(). Maybe you open a file f, defer f.Close(),
read an int n from f, and then become fact(n). That example is stupid
and horrible but that sort of thing would come up, or perhaps more
accurately sneak up. If you don't allow that then functions that use
become or functions that use functions that use become become weird
second class citizens.
become would break the current implementation of defer (as is my
understanding of it) since you have to pass the linked list of defers
into the become'd calls somehow in certain cases and become would have
to know that if there are any and if so to invoke them.
That complicates the implementation of defer, and that could very well
be a deal breaker if it turns out to be too complicated or fiddly.
Or perhaps balancing defer and become in your head as you code would
in practice be too complicated to make become a net benefit to Go. If
that's what you're saying then I can see your point.
But I don't see how the possibility of someone using defer in a tail
recursive function breaks the semantics of defer or become.
Thomas Bushnell, BSG
James McKaskill
become would break the current implementation of defer (as is my
understanding of it) since you have to pass the linked list of defers
into the become'd calls somehow in certain cases and become would have
to know that if there are any and if so to invoke them.
That complicates the implementation of defer, and that could very well
be a deal breaker if it turns out to be too complicated or fiddly.
Thomas Bushnell, BSG
Vanja Pejovic
Michael Jones
Thomas Bushnell, BSG
I mostly agree with you, but here are a few things to consider, and keep in mind that I think the deferred call should be made after the become.- If you use continuation passing style to eliminate non-tail calls, you are allocating more memory
- Either you, or someone else mentioned earlier that Scheme keeps track of method invocations in its implementation of tail call optimization. I imagine this also allocates more memory for each call
Neither of these uses constant space.I don't think tail call optimization has to guarantee running in constant space. If you have a recursive function that build a list and on each call adds a node to the list, it uses more memory the more calls are made. This is essentially what defer does. It allocates memory and puts it in a linked list. Sure, there is no make() or new() call, but every use of it allocated memory and the programmer should be aware of that.
Michael Jones
Vanja Pejovic
David Leimbach
On Feb 14, 8:42 pm, Ken Thompson <k...@google.com> wrote:
> 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.
>
This makes a lot of sense to me the more I think about it. In fact I
would go so far as to say that "become" in the case of a "defer" just
is a return. There were conditions on become avoiding stack
consumption in Alef too.
Defers appear to be idiomatically used in situations of resource
allocation and release, or recovering from panic. In either case, I
think become is still an interesting optimization one can reach for if
a particular computation can be expressed without side effects that
would warrant a defer.
For the record I'd often thought about why become didn't end up in
Limbo also.