proper tail calls

Brendan Eich brendan at mozilla.org
Fri Jan 18 22:49:15 PST 2008


On Jan 18, 2008, at 9:36 PM, Peter Michaux wrote:

> Will proper tail calls be implicit in ES4 or will there be a need for
> special syntax? I hope it is just a required optimization but then I
> read this ticket
>
> http://bugs.ecmascript.org/ticket/323
>
> and it seems there is a suggestion that the spec will only require
> proper tail calls with a "goto" statement.

That's the ticket's initial proposal, but as you can see opinions  
vary. I see two major axes of division:

E/I: explicit or implicit
S/X: statement or expression form

with the valid combinations being:

I,X: implicit, expression form, the original wiki'd proposal;
E,X: lth's proposal in the initial comment of the ticket;
E,S: graydon's proposal in comment 10.

I,S does not make sense. You can read the arguments for and against  
in the ticket. Graydon's recent comment includes this text:

"If, in order make the presence of an explicit form convenient, we  
have to add sugar for it as an additional form of expression-closure  
-- "goto call-expr()" means "{goto call-expr();} -- I don't think  
it's the end of the world. I do think, at present, we're meandering  
aimlessly towards a system that claims to provide a way to make tail  
calls, but in which nobody can ever figure out where or when they're  
actually getting tail calls. I don't think it'll be useful to ship  
such a language."

I think this nicely summarizes the problem with I, while not  
finishing off the case for X instead of just S or a slight extension  
to S (allowing the body of an expression closure to be a godo  
statement: function state1(a,b) goto state2(a*2, b-1); -- saving  
braces and using goto instead of return, four chars better). After a  
brief lapse into E,S, I'm in favor of E,X: goto as an operator  
required to get PTC and throwing an error if stack space must be  
consumed, as lth proposed in the original ticket.

> Is it not reasonable for
> the spec to simply require implementations to have proper tail calls?

The I,X original proposal from the wiki required this. It's  
"reasonable", maybe, if we can agree on the rules and they are not  
too complicated, but the crucial question is about usability, human  
factors, avoiding silent bad surprises: will programmers wanting  
proper tail calls be surprised when they nest an implicit (built-in  
among the primitive types) conversion in a big state machine, and  
silently defeat proper tail calls from that particular call site,  
leading to explosive stack growth in the worst case?

This concern of course led to the ticket; the principle familiar to  
Python folks is EIBTI (E Is Better Than I). Not just for readers  
(clarity of intent) but for writers (I want PTC or error here).

> Is it not acceptable for the spec to require certain implementation
> internal optimizations?

PTC is not an optimization, it's a storage rule. Schemers know to  
count on it, and do. For ~12 years, JS hackers have lacked it, on the  
other hand. And JS hackers have standard looping statement forms. But  
PTC is helpful for state machines, which you do see on the web; you  
even see setTimeout(fun, 0) flows to empty the JS stack in order to  
avoid overflow. PTC is worthwhile, and we have included it among  
approved proposals for a long time. The question remains: explicit or  
implicit syntax; if explicit, statement only or operator form?

/be

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.mozilla.org/pipermail/es-discuss/attachments/20080118/a1c61f30/attachment-0002.html 


More information about the Es4-discuss mailing list