Tail call optimization

[levi]

Do you plan to add tail call optimization to Go eventually?

Thanks,
Levi

[Ian Lance Taylor]

levi <greensp...@googlemail.com> writes:

> Do you plan to add tail call optimization to Go eventually?

It is already there in 6g/8g for certain cases, and in gccgo somewhat
more generally.

We do not currently plan to change the language to require that
compilers implement tail call optimization in all cases. If you must
have a tail call, you use a loop or a goto statement.

Ian

[Sebastian Sylvan]

Please reconsider this. Loops and gotos are do not supplant tail calls.

Of particular relevance is the fact that tail calls are extremely useful in message passing concurrency where you can do a switch on a message and then proceed to the next "state" in the message protocol by tail calling a totally separate function that only deals with what's needed in *that* particular state. This keeps things nice and compositional, rather than having to manage some horrible big loop with a giant switch for every possible message and manually tracking which state you're in or using gotos etc. etc.

Read some Erlang code for examples of how this looks. As I understand it this style of concurrency would work nicely in Go already, as long as tail call elimination was mandated.

--
Sebastian Sylvan

[jimmy frasche]

I have always found the example in the Blue PIL (the book "Programming
in Lua") to be a very clean example of why tail call "optimization" is
important and useful: http://www.lua.org/pil/6.3.html

[John]

On Nov 13, 6:37 pm, Ian Lance Taylor <i...@google.com> wrote:
> levi <greenspan.l...@googlemail.com> writes:
> > Do you plan to addtailcall optimization to Go eventually?

>
> It is already there in 6g/8g for certain cases, and in gccgo somewhat
> more generally.
>
> We do not currently plan to change the language to require that

> compilers implementtailcall optimization in all cases.  If you must
> have atailcall, you use a loop or a goto statement.

A loop or goto only work for cases where you would do a recursive tail
call, but the ability *reliably* tail call other functions opens up a
whole host of new possibilities - continuation passing style programs,
construction of complex control abstractions, thread interpreters,
etc.

I am very happy to have GC, closures, and multi-value return all in
one language - but I am going to take this opportunity to be greedy
and ask for "strong tail calls" too. I would be fine with using a
different syntax, maybe "leave tail-expression" instead of "return
[ ExpressionList ]", and have the complier flag an error if tail-
expression wasn't a tail call.

Never hurts to ask, right?

[TerryP]

I would have to agree, it would be nice :-).

At this stage however, a decent compiler is more important then ideal
tail call support.

On Nov 14, 11:23 pm, John <jwfmccl...@gmail.com> wrote:
> Never hurts to ask, right?

As long as you don't expect askin' to be gettin' anyway.

--
TerryP.
Just Another Computer Geek.

[smosher]

I have to second this. Erlang's use of tail calls is exemplary, and
Go's general flow is encouraging me to do exactly the same thing.

If we can get this even with some reasonable (i.e. usable for state
propagation) constraints, with perhaps compiler warnings (probably
need a pragma for that though ~sigh~) when we get it wrong that would
be good enough for me.

I don't want to sound arrogant, but Go really is begging for this and
it would be throwing away a rather powerful simplification process to
ignore it. (Ugh, now I think I know how the "exceptions" crowd feels.
Sorry.)

On Nov 13, 9:03 pm, Sebastian Sylvan <sebastian.syl...@gmail.com>
wrote:
> On Fri, Nov 13, 2009 at 11:37 PM, Ian Lance Taylor <i...@google.com> wrote:

[John]

I would argue that "proper tail call" support is different from
exceptions. We have had exceptions for over 35 years and I am not sure
we really understand how to use them, so while I am a little
disappointed not to have them, I appreciate the trepidation expressed
in the language FAQ (and I am curious to see how far multi-value
return gets us).

Proper tail calls seem a lot simpler, while they can make a language
much more expressive, unlike exceptions they can be easily ignored or
isolated, so the risks seem much lower.

On Nov 14, 8:13 pm, smosher <dark.nowh...@gmail.com> wrote:
> I have to second this. Erlang's use oftailcalls is exemplary, and

> Go's general flow is encouraging me to do exactly the same thing.
>
> If we can get this even with some reasonable (i.e. usable for state
> propagation) constraints, with perhaps compiler warnings (probably
> need a pragma for that though ~sigh~) when we get it wrong that would
> be good enough for me.
>
> I don't want to sound arrogant, but Go really is begging for this and
> it would be throwing away a rather powerful simplification process to
> ignore it. (Ugh, now I think I know how the "exceptions" crowd feels.
> Sorry.)
>
> On Nov 13, 9:03 pm, Sebastian Sylvan <sebastian.syl...@gmail.com>
> wrote:
>
>
>
> > On Fri, Nov 13, 2009 at 11:37 PM, Ian Lance Taylor <i...@google.com> wrote:
>
> > > levi <greenspan.l...@googlemail.com> writes:
>

> > > > Do you plan to addtailcall optimization to Go eventually?

>
> > > It is already there in 6g/8g for certain cases, and in gccgo somewhat
> > > more generally.
>
> > > We do not currently plan to change the language to require that

> > > compilers implementtailcall optimization in all cases.  If you must
> > > have atailcall, you use a loop or a goto statement.

>
> > Please reconsider this. Loops and gotos are do not supplanttailcalls.
>

> > Of particular relevance is the fact thattailcalls are extremely useful in

> > message passing concurrency where you can do a switch on a message and then

> > proceed to the next "state" in the message protocol bytailcalling a

[Ben Tilly]

On Sat, Nov 14, 2009 at 7:19 PM, John <jwfmc...@gmail.com> wrote:
> I would argue that "proper tail call" support is different from
> exceptions. We have had exceptions for over 35 years and I am not sure
> we really understand how to use them, so while I am a little
> disappointed not to have them, I appreciate the trepidation expressed
> in the language FAQ (and I am curious to see how far multi-value
> return gets us).
>
> Proper tail calls seem a lot simpler, while they can make a language
> much more expressive, unlike exceptions they can be easily ignored or
> isolated, so the risks seem much lower.

The one drawback with tail call optimization is that they don't
cooperate with examining stack backtraces. Call frames that were
optimized away will be missing.

Cheers,
Ben

[Alan Watson]

> The one drawback with tail call optimization is that they don't
> cooperate with examining stack backtraces.  Call frames that were
> optimized away will be missing.

True, but you can arrange that the stack trace reports the first N
tail calls, the last N tail calls, and notes that M tail calls have
been elided. That gets you most of the way there.

Regards,

Alan

[zambal]

On Nov 15, 2:13 am, smosher <dark.nowh...@gmail.com> wrote:
> I have to second this. Erlang's use of tail calls is exemplary, and
> Go's general flow is encouraging me to do exactly the same thing.

I was thinking exactly the same. It's very convenient to write a
server loop as a bunch of recursive functions in Erlang. Of course,
since variables are not mutable in Erlang, recursion is the only way
to loop, so having tail call optimisation is essential there. The need
for tail call optimisation in Go is much less vital than in Erlang,
but I still think it would allow writing more elegant and easier to
reason about server code in Go. Further more, adding this feature
wouldn't interfere with current idiomatic Go code.

-
vincent

[Dave Bayer]

There's a pragmatic, self-interested reason why go should fully
support tail call optimization: If go could become the implementation
language of choice for many other languages, then a slew of talent
will make the open-source compiler produce faster code for everyone.

When I heard this team was rewriting C, the first language I thought
of was C--. As it stands, the publicly available version of C-- isn't
really there yet for production use, but GHC Haskell uses an in-house
version for their back end. The idea is exactly to avoid imposing the
quirks C imposes that make it unsuitable as the implementation
language for other kinds of language design.

Let's note in passing that "tail call optimization" is a dangerously
misleading phrase. The Scheme language requires that tail calls be
implemented correctly, in a way that doesn't blow the stack. Nowhere
does it require compilers to optimize functions that are nearly tail
calls into true tail calls, by automatically writing a helper function
or accumulation variable to push into the call. And guess what? No
compiler does this. One looks at the optimizations that GHC Haskell
applies, and they're in an entirely different reading group. So a lot
of people have moved from Lisp-like languages to Haskell, to sit
closer to the fire.

[John]

On Nov 14, 10:24 pm, Ben Tilly <bti...@gmail.com> wrote:
> On Sat, Nov 14, 2009 at 7:19 PM, John <jwfmccl...@gmail.com> wrote:
> > I would argue that "propertailcall" support is different from

> > exceptions. We have had exceptions for over 35 years and I am not sure
> > we really understand how to use them, so while I am a little
> > disappointed not to have them, I appreciate the trepidation expressed
> > in the language FAQ (and I am curious to see how far multi-value
> > return gets us).
>

> > Propertailcalls seem a lot simpler, while they can make a language

> > much more expressive, unlike exceptions they can be easily ignored or
> > isolated, so the risks seem much lower.
>

> The one drawback withtailcall optimization is that they don't

> cooperate with examining stack backtraces.  Call frames that were
> optimized away will be missing.

One way to address this is to view proper tail call support not as an
optimization, but instead as a language feature. In the limit on can
imagine introducing syntax for tail calls. Maybe add a new key word to
signal a tail call out of a function, so instead instead of "return
tail-call-expression", maybe "leave", "goto", or "jump"? That way
programers won't be surprised by the missing stack frames and will
also be told by the compiler when they think they have crafted a tail
call, but in fact have not (crafting a proper tail call can be subtile
after all).

Of course this is a nice example of how in software no feature is
"trivial", even the simplest things require a lot of thought (if only
more managers understood this....)

[TerryP]

On Nov 15, 3:19 am, John <jwfmccl...@gmail.com> wrote:
> I would argue that "proper tail call" support is different from
> exceptions. We have had exceptions for over 35 years and I am not sure
> we really understand how to use them, so while I am a little
> disappointed not to have them, I appreciate the trepidation expressed
> in the language FAQ (and I am curious to see how far multi-value
> return gets us).

I would however argue that after 35 years, we understand how to use
them fine. The problem is who the heck understands how to implement
exception handling, in a way that would make every ones teeth chatter
eventually :-P. The way Go code handles errors IMHO is easier to
handle (and read) then using exceptions, and the only real bonus
offered by exceptions are for recoverables that would other wise cause
a program crash; just take a look at Python.


Tail calls are way more interesting subject matter then exceptions,
and TCO less likely to complicate Go's internals, even half as much as
adding exceptions would. Not to mention there is no need to break
source compatibility to add TCO to the language.


Tail call optimisation and being able to do tail recursion without
*eventually* pushing your stack out the window, are not quite
synonymous but often make great bed fellows. There are surely ways of
implementing tail recursion like Scheme, but without paying much
penalty on regular function returns. TCO is arguably less brain-
busting then some of the optimisation tricks you'll find in the
compiler field, and the math might not strangle the rest of us :-P.
Recursive tail calls should also be as understood (by most) just as
easily as looping or recursion in general, although implementing that
feature might (and should likely) be unimportant right now. It would
be great to have in the long run.

Maybe I'm just a freak, that sees little difference between if+goto,
looping, and function calls, as long as the code yields the same
computation. I've often had to write iterative solutions to avoid
recursive edge cases, due to language implementations.

--
TerryP
Just Another Computer Geek

[jimmy frasche]

I just realized how strange the arguments against tail calls are. I
don't mean to sound snotty, but the two arguments often seen together
are:

1) Just use a loop, and
2) There are no stack traces.

But you don't get stack traces with a loop either!

I understand the "things that are different should look different"
argument and this is the best one against tail calls, imo. Which is
why I think the proposed "leave funccall()" is the perfect solution.
This wouldn't fit in some languages but since Go already has "go" and
"defer" it feels like a nice fit and to quote the Zen of Python:
"Explicit is better than implicit" anyway.

However, I would like to reiterate that this is hardly issue #1 with
me, but I would like the arguments for tail call removal to be heard
by our beneficent language implementers and considered for
introduction at an appropriate time. It would make a great language
even better.

[Ben Tilly]

On Sun, Nov 15, 2009 at 11:02 AM, jimmy frasche <soapbo...@gmail.com> wrote:
> I just realized how strange the arguments against tail calls are. I
> don't mean to sound snotty, but the two arguments often seen together
> are:
>
> 1) Just use a loop, and
> 2) There are no stack traces.
>
> But you don't get stack traces with a loop either!

Not strange at all. Anyone who regularly debugs with stack backtraces
knows that there is value in being somewhat selective about how much
context you have to look at during debugging. Every iteration of a
loop would be far too much detail. That said, though, tail call
optimization is able to optimize flow of control constructs that
aren't expressible as simple loops.

That said, I'm not strongly opposed to tail call optimization. I just
don't want the decision to be made without knowing that there is a
trade-off.

> I understand the "things that are different should look different"
> argument and this is the best one against tail calls, imo. Which is
> why I think the proposed "leave funccall()" is the perfect solution.
> This wouldn't fit in some languages but since Go already has "go" and
> "defer" it feels like a nice fit and to quote the Zen of Python:
> "Explicit is better than implicit" anyway.

If you want it to look different, there is always the option of using
trampoline functions.

Cheers,
Ben

[Alan Watson]

On Nov 15, 7:18 am, Dave Bayer <ba...@cpw.math.columbia.edu> wrote:
> There's a pragmatic, self-interested reason why go should fully
> support tail call optimization: If go could become the implementation
> language of choice for many other languages,

I am a huge fan of TCO, however Go might still be an interesting
target language even without it. When translating from a language with
TCO, one could emit a single Go function representing the whole
program, and handle calls by using goto and an explicitly managed
stack. Since speed of compilation is an explicit aim, this might work
quite well.

Regards,

Alan

[Hugo Vincent]

> I understand the "things that are different should look different"
> argument and this is the best one against tail calls, imo. Which is
> why I think the proposed "leave funccall()" is the perfect solution.
> This wouldn't fit in some languages but since Go already has "go" and
> "defer" it feels like a nice fit and to quote the Zen of Python:
> "Explicit is better than implicit" anyway.

I really like this idea of a leave keyword too!

[smosher]

On Nov 15, 2:02 pm, jimmy frasche <soapboxcic...@gmail.com> wrote:
> I understand the "things that are different should look different"

> argument and this is the best one againsttailcalls, imo. Which is

> why I think the proposed "leave funccall()" is the perfect solution.

At first I thought being explicit was adding too much (since then it
must be language-supported, not just implementation supported) but
this would solve most of the problems. No worries about missing stack
traces and it doesn't even need to be mandated in the spec--a compiler
could error on the keyword in any scenario where it can't be
optimized. (Though I prefer "tail" as a keyword, it's not a big deal.)

I was also thinking it would be useful even if the functions involved
had some very tight constraints, such as sharing the same call+return
signature.

[smosher]

On Nov 14, 10:19 pm, John <jwfmccl...@gmail.com> wrote:
> I would argue that "propertailcall" support is different from
> exceptions.

Of course, I just noticed that I was being pretty adamant about it in
the same way people are about exceptions. Personally I don't want
exceptions in any form that is recognizable. I have some ideas on what
I'd like to see fill that void, but they're kinda specialized so...

It also occurs to me that instead of doing a tail call,

go nextstate(....);
return;

is pretty much all you need. It's not like waiting on return values
from service processes is necessary. The problem is that doing this
may be less efficient if tail calls are optimized in a given
implementation, and so you have the (imo bigger) problem of disparity
between implementations. Adding a keyword could make this simpler,
i.e. use the most efficient method implemented by the compiler. You
could then restrict the use of the keyword to only empty return
cases.

It's not like we're goofing off with recursive computations, we're in
a separate process, hoping never to return until the job is done. Any
results are going back through channels anyway.