proper tail calls
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
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?
On Jan 18, 2008 10:49 PM, Brendan Eich <brendan at mozilla.org> wrote:
On Jan 18, 2008, at 9:36 PM, Peter Michaux wrote:
[snip]
Some of the shorthand terminology that has developed in the conversations is a bit unfamiliar to me. Hopefully my questions below are not ridiculous.
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?
I'm thinking in terms of Scheme and tail calls. If a Scheme programmer puts a recursive call in a non tail position they get explosive stack growth. If the programmer was required to explicitly state they wanted a tail call then the explicit system you are suggesting would throw an error, correct?
It seems like having types in ES4 is adding quite a bit of difficulty to when a proper tail call can occur. The Scheme folks don't have to deal with that, I suppose.
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?
I think implicit tail calls are one of the most exciting proposals for ES4. Can it be implicit with the option of making it explicit so that it throws an error if the call is not in tail position and will produce the explosive stack growth? This would have the same feel that the language is "unsafe" but has optional "safety" features like optional types. ES3 doesn't have any mandatory safety syntax and to me it would be best to keep all safety syntax optional.
Peter
On Jan 19, 2008, at 12:31 AM, Peter Michaux wrote:
It seems like having types in ES4 is adding quite a bit of difficulty to when a proper tail call can occur. The Scheme folks don't have to deal with that, I suppose.
Contract systems in Scheme may use space, so this is a problem that
has been studied.
ES4 has no user-defined implicit conversions, but the built-in ones
could require stack space so that's the hazard, as I understand things.
The C syntax makes it harder to see tail positions compared to
Scheme, so types are not the only issue. Really, the question is a
human factors one.
I think implicit tail calls are one of the most exciting proposals for ES4. Can it be implicit with the option of making it explicit so that it throws an error if the call is not in tail position and will produce the explosive stack growth? This would have the same feel that the language is "unsafe" but has optional "safety" features like optional types. ES3 doesn't have any mandatory safety syntax and to me it would be best to keep all safety syntax optional.
This is an interesting way of looking at it, and indeed jaz (Jon
Zeppieri) in comments 23 and 25 in
bugs.ecmascript.org/ticket/323
brought up the idea of an assertion "I want a PTC here:" that could
be attached to a call, with implicit proper tail calls. I should have
represented this as an option; thanks for bringing it to light on the
list. Call it I,X (Implicit, eXpression tail calls) + A (Assert-PTC-
here).
Even with the explicit syntax for guaranteed PTCs, most of us can't
see ruling out as non-conforming an implementation that uses PTC
implicitly too. Given that allowance for further PTC without explicit
"opt-in" syntax, the assertion jaz proposed makes a lot of sense.
My concern that people won't know to use it is weak. Either lack of
it will burn people and they'll learn of it and use it, or it won't
be needed anyway. Sort of like optional type annotations, as you
note. The important point is that leaving out such an assertion, with
explicit or implicit PTC (where the explicit case still allows
further PTC to be done implicitly), enters the programmer in a
guessing game.
I,X (no way to assert PTC here or error) I,X+A (original wiki'd proposal + Jon Zeppieri's assertion idea) E,X (+A anyway in case of further PTC at implementation's discretion?) E,S (+A for the same reason?)
Looking at it this way, there's a case for A. And given A plus
implementation freedom to optimize more PTC than required by the
spec, is E really necessary?
My concern with E (or A for that matter) is that it requires additional syntax. I'd prefer if we could keep the syntax small. I don't think implicit PTC is an issue. It is an optimization that the interpreter/compiler should do. What are the problems with I? It does not change the semantics of the language.
On Jan 20, 2008, at 5:22 PM, Erik Arvidsson wrote:
My concern with E (or A for that matter) is that it requires additional syntax. I'd prefer if we could keep the syntax small. I don't think implicit PTC is an issue. It is an optimization that the interpreter/compiler should do. What are the problems with I? It does not change the semantics of the language.
Proper tails calls are not an optimization; they certainly do change
semantics, insofar as you can't write certain programs without them
being guaranteed. I'll defer to Dave's 2005 LtU comment (he may have
newer ones he prefers),
lambda-the-ultimate.org/node/472#comment-3511
which has useful links.
On 21/01/2008, Erik Arvidsson <erik.arvidsson at gmail.com> wrote:
My concern with E (or A for that matter) is that it requires additional syntax. I'd prefer if we could keep the syntax small.
The explicit syntax has one extra flow. Since the type checker is optional, even with explicit syntax the program may still compile just to throw an exception 100% when it reaches the tail call due to the runtime type checks.
I would bye the arguments about the explicit syntax if its semantics would guarantee the tail call as long as the code compiles without relining on optional parts of E4X. But since this is not possible, then I would prefer to make the tail calls an optional optimization in the same way as the type checker is optional.
, Igor
On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
then I would prefer to make the tail calls an optional optimization in the same way as the type checker is optional.
And if Haskell language specs can leave the issue of tail call optimization up to implementations, then I do not see why ES4 can not do the same.
This report defines the syntax for Haskell programs and an informal abstract semantics for the meaning of such programs. We leave as implementation dependent the ways in which Haskell programs are to be manipulated, interpreted, compiled, etc. This includes such issues as the nature of programming environments and the error messages returned for undefined programs (i.e. programs that formally evaluate to |).
, Igor
On Jan 21, 2008 5:34 AM, Igor Bukanov <igor at mir2.org> wrote:
On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
then I would prefer to make the tail calls an optional optimization in the same way as the type checker is optional.
And if Haskell language specs can leave the issue of tail call optimization up to implementations, then I do not see why ES4 can not do the same.
I think Haskell and ES are in different situations as a developer chooses a Haskel implementation for execution. ES4 code for the web is almost certainly going to run on multiple ES4 implementations. If there are no requirements for proper tail calls then they cannot be depended upon and are useless.
Peter
On Jan 20, 2008 8:01 PM, Brendan Eich <brendan at mozilla.org> wrote:
On Jan 20, 2008, at 5:22 PM, Erik Arvidsson wrote:
My concern with E (or A for that matter) is that it requires additional syntax. I'd prefer if we could keep the syntax small. I don't think implicit PTC is an issue. It is an optimization that the interpreter/compiler should do. What are the problems with I? It does not change the semantics of the language.
Proper tails calls are not an optimization; they certainly do change semantics, insofar as you can't write certain programs without them being guaranteed.
I've been trying to find out how they are not an optimization. I haven't read anyone else that thinks they are not an optimization but I have read other people refer to them as an optimization. I think that from an application programmers point of view they are an optimization since the same program will run without proper tail calls if the computer has infinite resources.
I'll defer to Dave's 2005 LtU comment (he may have newer ones he prefers),
He only mentions that transforming non tail-call application code into tail-call application code is "a standard optimization technique" in a language that has proper tail calls. He doesn't mention whether or not proper tail calls in the language are to be considered a optimization.
which has useful links.
Following one of those links leads to a wiki and the wiki has the following page which discusses proper tail calls as an optimization in the language
c2.com/cgi/wiki?TailCallOptimization
Peter
On Mon, Jan 21, 2008 at 8:57 AM, Peter Michaux <petermichaux at gmail.com> wrote:
I think Haskell and ES are in different situations as a developer chooses a Haskel implementation for execution. ES4 code for the web is almost certainly going to run on multiple ES4 implementations. If there are no requirements for proper tail calls then they cannot be depended upon and are useless.
As long as all the implementations have the exact same call stack limitation then that holds true. However, I think it is unreasonable to enforce one call stack size fits all.
I think we can all agree on that having explicit tail calls at compile time enforces all runtimes to have proper tail calls?
On Jan 21, 2008, at 9:08 AM, Peter Michaux wrote:
Proper tails calls are not an optimization; they certainly do change semantics, insofar as you can't write certain programs without them being guaranteed.
I've been trying to find out how they are not an optimization. I haven't read anyone else that thinks they are not an optimization but I have read other people refer to them as an optimization.
Read more, then :-/. The Scheme and Pre-Scheme histories are
interesting (in Pre-Scheme you used GOTO for a tail call -- explicit
syntax I favor for ES4).
See, for instance, Anton van Straaten's fine comment in the same LtU
post I cited:
lambda-the-ultimate.org/node/472#comment-3568
and especially:
lambda-the-ultimate.org/node/472#comment-3549
Quote:
"The ironic thing is that we're talking about a bug whose presence in
the language implementation, and in people's minds, makes it
difficult to detect that it is a bug. They don't think it's a bug,
because they "know" recursion is unnatural and even dangerous — but
the only reason they "know" that, is because their language
implementation has a bug which makes it so. It's a recursive bug,
which is particularly difficult to detect when one makes a habit of
avoiding recursion..."
I think that from an application programmers point of view they are an optimization since the same program will run without proper tail calls if the computer has infinite resources.
And if my mother had wheels, she'd be a trolley-car. Meanwhile, back
in reality, no computer has infinite resources, and as you pointed
out to Igor, making "TCO" an option makes it useless on the web --
browsers have different, or no, stack quotas or redzoning. Semantics
are not about the meanings of programs assuming infinite resources.
Following one of those links leads to a wiki and the wiki has the following page which discusses proper tail calls as an optimization in the language
Yes, it' s a common TLA but citing one use of it doesn't settle the
debate. Please read more.
On 21/01/2008, Peter Michaux <petermichaux at gmail.com> wrote:
On Jan 20, 2008 8:01 PM, Brendan Eich <brendan at mozilla.org> wrote: ...
Proper tails calls are not an optimization; they certainly do change semantics, insofar as you can't write certain programs without them being guaranteed.
I've been trying to find out how they are not an optimization.
I second that. Consider the following case:
let f2;
function f(a) { f2 = function() { return a; } goto return g(); }
function g() {f2 = null; ... }
Here in f "return g()" is in tail position yet the frame of f can not be eliminated completely since it is referenced through a global variable. On the other hand a smart implementation may figure out that, given the structure of g, there is no leak of the frame and it can be eliminated completely.
So in reality due to this closure leakage there is no guarantees about the space complexity unless one restricts the code that can present in a function with a tail call. As such a tail call can be treated only as an optimization hint as in general it is not possible to ensure O(1) in space behavior for calls in the tail positions.
, Igor
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
let f2;
function f(a) { f2 = function() { return a; } goto return g(); }
function g() {f2 = null; ... }
Here in f "return g()" is in tail position yet the frame of f can not be eliminated completely since it is referenced through a global variable.
I don't understand your claim. You're saying that the "frame of f" is "referenced through a global variable"? Clearly, f2 is the global variable, you're referring to. f2 may be bound to a function value that closes over a, which is part of f's activation frame -- or, more specifically, part of f's closure environment. But how would this prevent the call to g from being a tail call? Are you assuming that a must be on the stack?
On 1/21/08, Jon Zeppieri <jaz at bu.edu> wrote:
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
let f2;
function f(a) { f2 = function() { return a; } goto return g(); }
function g() {f2 = null; ... }
To clarify, space is consumed by the evaluation of:
f2 = function() { return a; }
...which constructs (and binds) a closure.
goto return g();
...on the other hand, does not consume space. a is still live, but it's live as part of f2's closure, not as part of f's activation frame.
On 21/01/2008, Jon Zeppieri <zeppieri at gmail.com> wrote:
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
let f2;
function f(a) { f2 = function() { return a; } goto return g(); }
function g() {f2 = null; ... } ...
I don't understand your claim. You're claiming that the "frame of f" is "referenced through a global variable"? Clearly, f2 is the global variable, you're referring to. f2 may be bound to a function value that closes over a, which is part of f's activation frame -- or, more specifically, part of f's closure environment. But how would this prevent the call to g from being a tail call? Are you assuming that a would be on the stack? That is not a warranted assumption.
I am saying that even for calls in the tail position an implementation may not eliminate the parent frame completely as it still may be exposed via closures. As such the tail call optimization cannot guarantee that the space complexity of the tail recursion is O(1).
I think talking about stacks and stack overflows might be muddying
this discussion. The language is a garbage-collected language and a
function context (stack frame) should be subject to garbage collection
just like any other object. A stack frame that is no longer
'reachable' (because it will be returned through) should be
collected. A clever implementation trick is to notice this at compile
time and simply reuse the frame.
The use of goto is darn cute, and a nice way to make that assertion
to the compiler and give a clue to the reader. It's a lot like
delete though. delete doesn't mean that the referenced object
will actually be collected, it just drops that reference. You may
intend that by deleting a reference an object will be collected, but
the language has no way for you to assert that.
You could still argue that in strict mode the compiler should complain
if a frame you goto out of is not going to be unreachable (and hence
collected) after all (either because you don't really have a tail
call, or because a closure or type error may capture the frame). But
by the same token, I might like the compiler to warn me if I am
allocating closures in a loop (easy to overlook).
What I wonder is, why are we obsessing about this particular garbage
collection problem? Because there is a clever implementation trick
that solves it? Do we have other requirements on implementation's of
garbage collection? Or just a general assumption that the garbage
collector has to work?
If I re-write my recursive tail-call algorithm as a loop that
allocates a state object each time around the loop (and drops the
reference to the previous state), do we require all implementations to
not run out of space because I have a 'proper' bounded resource
algorithm?
Igor Bukanov wrote:
I am saying that even for calls in the tail position an implementation may not eliminate the parent frame completely as it still may be exposed via closures. As such the tail call optimization cannot guarantee that the space complexity of the tail recursion is O(1).
This is much like saying "if the function in the tail call appends a value to an array, it is not O(1)". We're talking about stack growth, not side-effects on escaped heap objects. They have indefinite lifetime anyways. Who's to say the storage is even freed when g() runs and nulls out f2?
On 21/01/2008, Graydon Hoare <graydon at mozilla.com> wrote:
Igor Bukanov wrote:
I am saying that even for calls in the tail position an implementation may not eliminate the parent frame completely as it still may be exposed via closures. As such the tail call optimization cannot guarantee that the space complexity of the tail recursion is O(1).
This is much like saying "if the function in the tail call appends a value to an array, it is not O(1)". We're talking about stack growth, not side-effects on escaped heap objects. They have indefinite lifetime anyways. Who's to say the storage is even freed when g() runs and nulls out f2?
Consider another example:
function f(a) { function f2 { return a * 2; } if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
One may expect that this would require O(1) space. But this is not the case as the implementation may not eliminate f2. Moreover, even for a case like:
function f(a) { if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
the implementation is still allowed to use heap for integers. So even in this example the space complexity may be O(N). Hence the questions: how useful to specify the details of tail call optimizations without putting restrictions on the rest of the runtime?
, Igor
Peter Michaux wrote:
I've been trying to find out how [proper tail calls] are not an optimization. I haven't read anyone else that thinks they are not an optimization but I have read other people refer to them as an optimization. I think that from an application programmers point of view they are an optimization since the same program will run without proper tail calls if the computer has infinite resources. ... Following one of those links leads to a wiki and the wiki has the following page which discusses proper tail calls as an optimization in the language
There's a distinction between the space efficiency property known as "proper tail recursion" and the implementation technique called "tail call optimization". For some discussion of this, see:
groups.google.com/group/comp.lang.lisp/msg/0b8eb4a54bff7857
In that post, Will Clinger makes the point that there's a distinction between:
"* a syntactic concept (tail calls, aka tail recursion)
- implementation techniques (tail call optimization, tail merging)
- space efficiency property (proper tail recursion)"
The abstract of Clinger's original paper[*] about proper tail recursion mentions this point:
"Proper tail recursion is not the same as ad hoc tail call optimization in stack-based languages. Proper tail recursion often precludes stack allocation of variables, but yields a well-defined asymptotic space complexity that can be relied upon by portable programs."
Proper tail calls are a property that programmers can rely on in languages which offer it. How that is implemented is not that important to an application programmer. The fact that one can implement proper tail recursion, in part, with a technique known as tail-call optimization, doesn't make proper tail calls an optimization, any more than optimizations in a garbage collector make garbage collection an optimization.
Anton
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
Consider another example:
function f(a) { function f2 { return a * 2; } if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
One may expect that this would require O(1) space. But this is not the case as the implementation may not eliminate f2.
But the above example does only require O(1) space. On each call to f, a new closure is constructed, but it's dropped on the floor as soon as the next iteration occurs. PTC makes no guarantees about when garbage collection will or will not occur.
Moreover, even for a case like:
function f(a) { if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
the implementation is still allowed to use heap for integers. So even in this example the space complexity may be O(N).
What is N here? Surely, it's has nothing to do with the number of calls to f. This example has nothing do to with PTC.
Hence the questions: how useful to specify the details of tail call optimizations without putting restrictions on the rest of the runtime?
In my experience, very.
On Jan 21, 2008, at 9:59 AM, Erik Arvidsson wrote:
I think we can all agree on that having explicit tail calls at compile time enforces all runtimes to have proper tail calls?
Yes, if we agree on explicit tail call syntax, and if you mean by "at
compile time enforces" that explicit tail call syntax used in a non-
tail position results in a compile-time error.
Just to recap a bit:
The standing proposal at doku.php?
id=proposals:proper_tail_calls (which is not a spec, not bug-fixed
against the rest of the proposed language, but still the accepted
proposal of long standing) is for implicit proper tail calls. Many
still favor this. The ticket at bugs.ecmascript.org/ticket/323
proposes explicit syntax, but it is not clear to me that this will be
accepted.
I think we want something like what Jon Zeppieri proposed in the
ticket, an explicit "tail call here or error, please" assertion or
annotation by the programmer, useful to readers as well. This is good
no matter what the spec says about implicit vs. explicit PTC. In the
explicit case of course this assertion is expressed directly by the
PTC syntax -- no need for two ways to say the same thing, or for
implicit tail calls to be asserted when the programmer could have
been explicit in how the call itself was written.
Another point of contention is statement vs. expression explicit
syntax, but I think it would be wrong to have expression closures,
but not to consider the calls to g and h as proper tail calls in:
function f(a, b, c) a ? g(b) : h(c);
With explicit syntax, we have to argue about the keyword. My
enthusiasm for explicit syntax using a "goto" operator is not shared
by folks who still see disdain and horror among their colleagues in
reaction to this word. Dave Herman wrote me recently that it might as
well be spelled "donttouchme" (I was going to guess something
unprintable ;-).
The concern waldemar raised about debugger-driver confusion due to
implicit tail calls was thrashed in that lambda-the-ultimate thread I
cited, and elsewhere. I personally don't think it is a decisive
argument for explicit syntax, but it adds some weight.
So the axes of disagreement seem to me to be:
- explicit vs. implicit,
- whether to have a tail annotation if implicit,
- statement vs. expression if explicit, and
- whether explicit is required for debug-ability.
Your point that IF we agree on explicit syntax for PTCs, THEN
conforming implementations must check at compile time is probably
not controversial, provided the check is purely for tail call
syntactic position. Conversions (implicit and hardcoded among the
built-in types representing and wrapping primitives) that might
defeat PTC may not be evident until runtime, where the result would
be a TypeError or possibly a new Error subtype.
On 21/01/2008, Jon Zeppieri <jaz at bu.edu> wrote:
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
Consider another example:
function f(a) { function f2 { return a * 2; } if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
One may expect that this would require O(1) space. But this is not the case as the implementation may not eliminate f2.
But the above example does only require O(1) space. On each call to f, a new closure is constructed, but it's dropped on the floor as soon as the next iteration occurs.
You can not deduce that from ES4 specs that it does not require that f should be ever dropped.
function f(a) { if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
the implementation is still allowed to use heap for integers. So even in this example the space complexity may be O(N).
What is N here? Surely, it's has nothing to do with the number of calls to f. This example has nothing do to with PTC.
Even with the tail call optimization implemented, the space complexity of f(N) with f from the above example can be O(N) if the implementation uses heap to allocate integers.
Hence the questions: how useful to specify the details of tail call optimizations without putting restrictions on the rest of the runtime?
In my experience, very.
I was not able to construct a single useful example where one can reason about the space complexity of the tail calls given that ES4 does not specify the space complexity of other aspects of the runtime. For this reason goto return looks very strange in ES4. It allows to assert a very specific space complexity property yet it is not possible to assert that, say a - 1 should not use heap allocation.
, Igor
On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
On 21/01/2008, Jon Zeppieri <jaz at bu.edu> wrote:
But the above example does only require O(1) space. On each call to f, a new closure is constructed, but it's dropped on the floor as soon as the next iteration occurs.
You can not deduce that from ES4 specs that it does not require that f should be ever dropped.
Sorry for bad English here. I wanted to say:
You can not deduce that from ES4 specs. The specs does not require that closures created during execution of a function would ever be dropped.
On Jan 21, 2008 9:59 AM, Erik Arvidsson <erik.arvidsson at gmail.com> wrote:
On Mon, Jan 21, 2008 at 8:57 AM, Peter Michaux <petermichaux at gmail.com> wrote:
I think Haskell and ES are in different situations as a developer chooses a Haskel implementation for execution. ES4 code for the web is almost certainly going to run on multiple ES4 implementations. If there are no requirements for proper tail calls then they cannot be depended upon and are useless.
As long as all the implementations have the exact same call stack limitation then that holds true. However, I think it is unreasonable to enforce one call stack size fits all.
I think we can all agree on that having explicit tail calls at compile time enforces all runtimes to have proper tail calls?
I think "enforces" would be better as "strongly encourage". An non-conforming implementation could pretend it is conforming and just lie. "Suurrre we'll do that as a proper tail call, no problem, good idea." ;-)
Peter
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
You can not deduce that from ES4 specs that it does not require that f should be ever dropped.
f has nothing to do with it. f2 is the closure that is constructed on each iteration (assuming it is not optimized away in the specific example you cited -- and I am stipulating that it is not optimized away for the sake of argument).
At each iteration, the previous value of f2 is not reachable. Therefore, it no longer consumes space. If the ES4 spec makes no mention of this, I'm not sure what to say. Why would anyone want unreachable objects to consume space (except for debugging purposes)?
Even with the tail call optimization implemented, the space complexity of f(N) with f from the above example can be O(N) if the implementation uses heap to allocate integers.
How? I think there may be a basic misunderstanding here. Let's assume the integers are heap allocated. So, on each iteration, we heap allocate an integer. However, the integer that we allocated for the previous iteration is no longer reachable. It can be garbage collected. Therefore, it does not take up space. Again, PTC does not guarantee that the garbage collector will not run.
Yes, I am assuming that ES4 mandates that unreachable objects do not consume space. That doesn't seem like a terribly bold assumption to me.
On 1/21/08 12:35 PM, Brendan Eich wrote:
So the axes of disagreement seem to me to be:
We need to agree on the primary purpose of proper tail calls. I say it is portability of code, and that all other concerns do not have enough weight to influence this proposal.
- explicit vs. implicit,
Since PTC is about portability of code then what matters most is that implementations agree on what a tail call is. If the spec is unambiguous about what a tail call is, then implementations will have little trouble agreeing. Anyway, an explicit marking won't help.
- whether to have a tail annotation if implicit,
Ditto. It won't aid in ensuring portability of code.
- statement vs. expression if explicit, and
N/A
- whether explicit is required for debug-ability.
PTC should not be for improving debug-ability.
On 21/01/2008, Jon Zeppieri <jaz at bu.edu> wrote:
Yes, I am assuming that ES4 mandates that unreachable objects do not consume space. That doesn't seem like a terribly bold assumption to me.
ES4 does not guarantee that. Moreover, in most current implementations of ES3 the unreachable objects do consume space until GC collects them, but with a conservative GC even that can not be relied upon.
, Igor
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
ES4 does not guarantee that. Moreover, in most current implementations of ES3 the unreachable objects do consume space until GC collects them, but with a conservative GC even that can not be relied upon.
The "until GC collects them" part does not modify what I wrote. When I use the phrase "does not consume space," I do not mean that the data must not exist anywhere in the computer's memory. I mean only that the data is not live. Unreachable objects do not consume space precisely because they can be collected and their space re-used. Whether or not they have actually been collected is wholly irrelevant. From the point of view of the running program, an unreachable object simply doesn't exist.
Your point about conservative GC is well taken, but that's the price one pays for using an approximate method of reclaiming memory.
On Jan 21, 2008, at 1:11 PM, Jeff Dyer wrote:
On 1/21/08 12:35 PM, Brendan Eich wrote:
So the axes of disagreement seem to me to be:
We need to agree on the primary purpose of proper tail calls. I say
it is portability of code, and that all other concerns do not have enough
weight to influence this proposal.
I'm pretty sure you mean the primary purpose (or reason) for
specifying proper tail calls, not the purpose of proper tail calls
for state machines, loops, and other call graphs that (absent other
allocations) must not accumulate space. If we wanted to dig in our
heels and repeat "use iteration" (Python sticks to this gun), we could.
But we have accepted the proper tail calls proposal for a long while,
to serve such currently poorly-served use-cases. We have to evaluate
the syntax as well as semantics against usability and other criteria
in light of those use-cases. Portability is an end, but not the only
end.
The mention of GC is apposite: if implementations don't agree on GC
scheduling, or some use ref-counting, you can write programs that
fall over (as in, hit a hard memory limit) by coding for one
particular memory manager. That's obviously a bad idea, but the ES4
spec can't require a particular memory management algorithm "for
portability".
- explicit vs. implicit,
Since PTC is about portability of code then what matters most is that implementations agree on what a tail call is. If the spec is
unambiguous about what a tail call is, then implementations will have little
trouble agreeing. Anyway, an explicit marking won't help.
Sure, that's clear. But ticket 323 cites benefits of explicit syntax:
automated checking for the programmer, clues to the readers
(especially the debugger drivers), new syntax for a new (to ES1-3 and
real JS implementations) storage rule.
In other words, humans programming in the langauge might benefit from
explicit syntax, even if compilers and the (fewer, more expert)
humans who write them can get implicit proper tail calls right.
- whether to have a tail annotation if implicit,
Ditto. It won't aid in ensuring portability of code.
That's not the only end; another good to serve here is correctness.
- whether explicit is required for debug-ability.
PTC should not be for improving debug-ability.
The argument (which I do not think is decisive) is that PTC breaks
debugability.
The argument (which I do not think is decisive) is that PTC breaks debugability.
I am a bit out of my depth in this discussion, but explicit syntax feels wrong to me. However, if it's going to be implicit, it has to be completely invisible (aside from the benefits) - developers are going to want their debugging tools to work as before.
Is there a practical approach to recursion counting, that ES4 could require, so that Error.getStackTrace() can use it to produce the "expected" result? I must admit, It doesn't feel as trivial in my head as that sentence reads...
Peter
On 2008-01-21, at 18:13, Peter Hall wrote:
The argument (which I do not think is decisive) is that PTC breaks
debugability.I am a bit out of my depth in this discussion, but explicit syntax
feels wrong to me. However, if it's going to be implicit, it has to
be completely invisible (aside from the benefits) - developers are
going to want their debugging tools to work as before.Is there a practical approach to recursion counting, that ES4 could
require, so that Error.getStackTrace() can use it to produce the
"expected" result?
Tail calls do not have to be self recursive. Only a stack could
maintain the necessary state...
— Gordon
Unfortunately, this issue has become confused, and I've helped confuse it.
First of all, I'm sure you're right that ES4 does not mandate the reclamation of memory for unreachable objects. R6RS doesn't mandate it either: "The reason that implementations of Scheme do not (usually!) run out of storage is that they are permitted to reclaim the storage occupied by an object if they can prove that the object cannot possibly matter to any future computation." Permitted, not required.
On the other hand R6RS does mandate PTC, which "allows the execution of an iterative computation in constant space..."
Note the word 'allows.' Obviously, it can't guarantee that an arbitrary iterative computation can be performed in constant space, since the computation may depend on allocating memory on every iteration. The only guarantee is that the activation frame of the tail-callee does not need to preserve the activation frame of the caller. As you've demonstrated, a procedure may close over some variable that's part of the caller's activation frame, requiring that variable to be preserved, but the frame itself does not need to be preserved. It's possible that all of the variables in the frame will need to be preserved (if they all occur free in the inner closure), but this doesn't mean that the call isn't a proper tail call. It just means that the storage needs to be preserved for reasons that have nothing to do with the call semantics.
(I can imagine an implementation that might actually use the same data structure for an activation frame and a closure environment. Such an implementation might heap allocate all of its activation frames and keep a frame live -- from the GC's perspective -- if a closure needs access to any of its bindings. Unless the spec requires safe-for-space closure representations, this would be perfectly legal -- though wasteful -- and would still have nothing to do with PTC.)
This brings us back to Graydon's and my original responses to your message from early this afternoon. While the examples you gave do allocate memory on each iteration, the allocation doesn't prevent the calls in tail position from being proper tail calls.
Really, all of our back-and-forth since those messages has been pretty much off topic.
On 1/21/08 2:14 PM, Brendan Eich wrote:
On Jan 21, 2008, at 1:11 PM, Jeff Dyer wrote:
On 1/21/08 12:35 PM, Brendan Eich wrote:
So the axes of disagreement seem to me to be:
We need to agree on the primary purpose of proper tail calls. I say it is portability of code, and that all other concerns do not have enough weight to influence this proposal.
I'm pretty sure you mean the primary purpose (or reason) for specifying proper tail calls, not the purpose of proper tail calls for state machines, loops, and other call graphs that (absent other allocations) must not accumulate space.
Yes. Thanks for clarifying that.
If we wanted to dig in our heels and repeat "use iteration" (Python sticks to this gun), we could.
But we have accepted the proper tail calls proposal for a long while, to serve such currently poorly-served use-cases. We have to evaluate the syntax as well as semantics against usability and other criteria in light of those use-cases. Portability is an end, but not the only end.
My point is that some of those poorly served use cases have nice solutions that might work on some, but not all, implementations without a definition of PTCs in ES4. I think we agree about this.
The mention of GC is apposite: if implementations don't agree on GC scheduling, or some use ref-counting, you can write programs that fall over (as in, hit a hard memory limit) by coding for one particular memory manager. That's obviously a bad idea, but the ES4 spec can't require a particular memory management algorithm "for portability".
I agree. In the case of PTC, portability comes from the requirement that certain recursive calls exhibit asymptotic memory use, not from a specific memory management algorithm.
- explicit vs. implicit,
Since PTC is about portability of code then what matters most is that implementations agree on what a tail call is. If the spec is unambiguous about what a tail call is, then implementations will have little trouble agreeing. Anyway, an explicit marking won't help.
Sure, that's clear. But ticket 323 cites benefits of explicit syntax: automated checking for the programmer, clues to the readers (especially the debugger drivers), new syntax for a new (to ES1-3 and real JS implementations) storage rule.
In other words, humans programming in the langauge might benefit from explicit syntax, even if compilers and the (fewer, more expert) humans who write them can get implicit proper tail calls right.
Okay, I'll take that up in the bug. Suffice to say here that I think clarity and debug-ability are at odds with portability, the greater good.
- whether to have a tail annotation if implicit,
Ditto. It won't aid in ensuring portability of code.
That's not the only end; another good to serve here is correctness.
In practice, correctness is only served if implementations are forbidden to implement PTC behavior for any but the sanctioned tail call syntaxes. And that is not what is being proposed. Am I mistaken?
On 22/01/2008, Jon Zeppieri <jaz at bu.edu> wrote:
Really, all of our back-and-forth since those messages has been pretty much off topic.
To bring this back to the topic. I do not think an explicit syntax for tail calls is useful for the following reasons:
-
It does not guarantee at the compile time that the call is in PTC position since the type checker is optional in the language. As such it can not be used as an universal static assert.
-
Given that ES4 does not specify a particular space bounds on most of runtime operations, the explicit syntax may mislead a reader about the execution complexity of the code. An implicit PCT at least does not emphasis itself syntactically and, as a consequence, the reader may consider all aspects of the code like GC pressure, operation complexity etc when reasoning about the space and time behavior.
, Igor
On Jan 21, 2008, at 3:33 PM, Jeff Dyer wrote:
But we have accepted the proper tail calls proposal for a long while, to serve such currently poorly-served use-cases. We have to evaluate the syntax as well as semantics against usability and other criteria in light of those use-cases. Portability is an end, but not the only end.
My point is that some of those poorly served use cases have nice
solutions that might work on some, but not all, implementations without a
definition of PTCs in ES4. I think we agree about this.
Not sure whether you mean some implementations might implement PTC
even if the spec does not require it, or something else (some
implementations might have big stacks -- but no, that's can't be
right). So yeah, if only some (and currently I think the count is
zero among popular browsers -- Opera folks please correct me if I am
wrong) implementations support PTC, then anyone writing portable code
can't rely on PTC working cross-browser. I believe everyone who has
spoken up in the committee has favored some kind of PTC, implicit or
explicit.
But again, we don't specify detailed storage requirements that would
improve portability for other use-cases. It's precisely the use-cases
for PTC that motivate our concern that PTC be reliably portable. That
makes the use-cases for PTC primary in my book, and portability
secondary (not more or less important, but dependent on the first
condition: that the use-cases are worth the language facility).
In other words, humans programming in the langauge might benefit from explicit syntax, even if compilers and the (fewer, more expert) humans who write them can get implicit proper tail calls right.
Okay, I'll take that up in the bug. Suffice to say here that I
think clarity and debug-ability are at odds with portability, the greater good.
Wait, you were arguing that portability is the only good (not so),
and that since it wasn't aided by explicit syntax, explicit syntax
should be dropped. Now you're making a false dilemma between
portability and explicit syntax for language-user benefits. But
explicit syntax does not harm portability, you never made that case
(and it's silly to say explicit syntax for tail calls as a normative
part of the spec harms portability).
- whether to have a tail annotation if implicit,
Ditto. It won't aid in ensuring portability of code.
That's not the only end; another good to serve here is correctness.
In practice, correctness is only served if implementations are
forbidden to implement PTC behavior for any but the sanctioned tail call
syntaxes. And that is not what is being proposed. Am I mistaken?
No, I'm talking about correctness, as in
-
The programmer uses the explicit syntax, let's say "goto f(x)",
where the call to f is not in tail position. We would like an error
here. With implicit PTC, the programmer fails to get a tail call and
the stack may grow, but does QA find out in time? -
The programmer uses "goto f(x)" where f returns T and the call is
in g returning Y, and there's a space-accumulating (built-in)
conversion from X to Y. We would like a strict error if this can be
detected statically. Without the explicit syntax signalling PTC
intent, the implementation will just do the conversion and accumulate
stack space. Will QA find out in time?
Comparing ES4 and Haskell is like comparing apples and orangutans. Haskell is a lazy language, where the control flow (and space consumption thereof) are far more complex than in a call-by-value language like JavaScript or Scheme. It's well-known that tail recursion is hard to reason about in Haskell because the accumulation of suspensions consumes space in non-local ways, which means that tail calls can't simply be determined by inspection of the nesting of expressions of a program, but rather by flow-sensitive strictness analyses. So this is a totally irrelevant analogy.
As for making it optional, I'll probably repeat this many times: if you make proper tail calls optional, you might as well not put them in the spec at all. If programmers can't rely on them, they can't use them.
On Jan 21, 2008, at 4:05 PM, Brendan Eich wrote:
- The programmer uses "goto f(x)" where f returns T and the call is in g returning Y, and there's a space-accumulating (built-in) conversion from X to Y.
s/T/X/, obviously.
On 22/01/2008, Brendan Eich <brendan at mozilla.org> wrote:
- The programmer uses "goto f(x)" where f returns T and the call is in g returning Y,
A quality implementation may still implement the tail call in this case as the type conversion does not depend on the activation frame. Yet given such implementation the programmer would not be able to take advantage of that and would be forced to use return f(x) instead of goto f(x).
, Igor
I am a bit out of my depth in this discussion, but explicit syntax feels wrong to me. However, if it's going to be implicit, it has to be completely invisible (aside from the benefits) - developers are going to want their debugging tools to work as before.
Is there a practical approach to recursion counting, that ES4 could require, so that Error.getStackTrace() can use it to produce the "expected" result? I must admit, It doesn't feel as trivial in my head as that sentence reads...
You can easily circumvent an expression being in tail position. For example, if EXP is in tail position and you want it not to be, just wrap it as:
let (r = EXP) r
The program behaves the same, except for the fact that EXP is no longer in tail position, so it cannot perform a tail call.
Tail calls do not have to be self recursive. Only a stack could maintain the necessary state...
Ah yes, I see that now. Duh.
You can easily circumvent an expression being in tail position. For example, if EXP is in tail position and you want it not to be, just wrap it as:
let (r = EXP) rThe program behaves the same, except for the fact that EXP is no longer in tail position, so it cannot perform a tail call.
Thanks. That would work. But I can still see the "average" user being confused when debugging, and not knowing what is going on.
Peter
On Jan 21, 2008, at 12:35 PM, Brendan Eich wrote:
Conversions (implicit and hardcoded among the built-in types representing and wrapping primitives) that might defeat PTC may not be evident until runtime, where the result would be a TypeError or possibly a new Error subtype.
Isn't this case (implicit conversion) exactly what motivated the idea
that programmers may not be able to easily tell if a call is in tail
position?
, Maciej
On Jan 18, 2008, at 10:49 PM, Brendan Eich wrote:
"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."
Is "goto" the only option being considered for how to identify tail
position? It seems to me this could easily be confused with what
"goto" means in languages like C, Pascal or C#. "return" might be a
good choice of syntax if it weren't for the implicit conversion
problem. How about something like "tailcall" or "tailreturn".
Here is another thing I don't understand: if goto must flag runtime
errors in cases where otherwise implicit type conversion would occur,
then does that not itself break proper tail recursion (something has
to hang around to do the typecheck on the actually returned type)? Or
is the intent that it throws a runtime error before the call if it
can't statically prove that return types match? Does that mean you can
never goto an untyped function from one with a declared return type?
, Maciej
On Jan 21, 2008, at 8:12 PM, Maciej Stachowiak wrote:
On Jan 18, 2008, at 10:49 PM, Brendan Eich wrote:
"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."Is "goto" the only option being considered for how to identify tail position?
See bugs.ecmascript.org/ticket/323#comment:10 where precedent
from other languages suggests alternatives such as "become" and "jump".
It seems to me this could easily be confused with what "goto" means in languages like C, Pascal or C#.
It might, and at least one JS implementation has supported computed
goto (to support a port of an old Adventure game, IIRC), but never mind.
"return" might be a good choice of syntax if it weren't for the implicit conversion problem.
It would, indeed: return and yield would both then be low-precedence
unary operators.
How about something like "tailcall" or "tailreturn".
Or just "tail f(x, y)", Dave Herman's suggestion.
Here is another thing I don't understand: if goto must flag runtime errors in cases where otherwise implicit type conversion would occur, then does that not itself break proper tail recursion (something has to hang around to do the typecheck on the actually returned type)? Or is the intent that it throws a runtime error before the call if it can't statically prove that return types match? Does that mean you can never goto an untyped function from one with a declared return type?
From Graydon's comment at bugs.ecmascript.org/ticket 323#comment:10
* Let f be the function-value result of evaluating the callee
portion of <CallExpression>
* Let args be the result of evaluating the argument portion of
<CallExpression>
* Let S be the return-type of f
* Let T be the return-type of the current activation
* Confirm the dynamic typecheck S <* T, or throw TypeError
* Replace the current activation with an activation of
Function.apply(f,args)
So: no, yes, and yes.
The ticket and wiki'ed proposal and discussion pages are worth a
read, or re-read.
On Jan 21, 2008, at 8:02 PM, Maciej Stachowiak wrote:
On Jan 21, 2008, at 12:35 PM, Brendan Eich wrote:
Conversions (implicit and hardcoded among the built-in types representing and wrapping primitives) that might defeat PTC may not be evident until runtime, where the result would be a TypeError or possibly a new Error subtype.
Isn't this case (implicit conversion) exactly what motivated the idea that programmers may not be able to easily tell if a call is in tail position?
Indeed:
"ES4 has proper tail calls, but their constraints are sometimes
subtle, especially with regard to conversions or type checks inserted
at the return point. It may be that the "Explicit Is Better Than
Implicit" principle once again finds application here."
First paragraph in bugs.ecmascript.org/ticket/323. Again, the
ticket is just sitting there, you don't need me transcribing it into
this list :-/.
On Jan 21, 2008, at 10:50 PM, Brendan Eich wrote:
"return" might be a good choice of syntax if it weren't for the implicit conversion problem.
It would, indeed: return and yield would both then be low-precedence unary operators.
(Low-level grammatical quibble with myself, probably only of interest
to a few folks:)
Not quite: the comma operator bites (there, I said it). Although in
js1.7 and 1.8 (firefox2 and 3) we make it an error if you don't
parenthesize |yield expr| in |foo(yield expr, arg2)|, a statement |
return expr, expr2| is already defined by a production whose right
nonterminal is a comma expression (ListExpression in ES4's grammar).
To avoid confusion in argument lists vs. comma expressions, and to
relieve users from having to over-parenthesize yield and let
expressions, and expression closures, when they are in an actual
parameter list or enclosing comma expression, ES4 makes the right
nonterminal be AssignmentExpression for all of yield expressions, let
expressions, and expression closures.
This works well enough as far as I can tell, although the js1.7-1.8
extra error check is more Pythonicly paranoid/pedantic, and we lack
deep usability data to judge whether it is justified. Savvy hackers
will overparenthesize where there is the slightest chance of
confusion, but not excessively (Python requires foo((yield bar)),
e.g., which is just silly).
Since return may involve a conversion, it's off the table, so this is
all moot. But it's attractive as a tail operator and some languages
have used it that way. Again, Anton in that LtU thread:
On Jan 21, 2008 10:50 PM, Brendan Eich <brendan at mozilla.org> wrote:
On Jan 21, 2008, at 8:12 PM, Maciej Stachowiak wrote:
How about something like "tailcall" or "tailreturn".
Or just "tail f(x, y)", Dave Herman's suggestion.
"tail" looks great and any of these three suggestions seem far better than "goto".
(I'm still hoping this explicit version is optional.)
Peter
On Jan 21, 2008, at 5:26 PM, Peter Hall wrote:
Thanks. That would work. But I can still see the "average" user being confused when debugging, and not knowing what is going on.
Would you think an explicit keyword syntax for mandatory tail call
would help such a user?
To the claim that debugging in the face of PTCs will become madness-
inducing, Schemers and others retort "do you want to see every state
of an iteration?" (A loop is a tail call in Scheme.) The right answer
is "yes". Yes, I want a debugger that remembers all program states
(code.google.com/p/chronomancer) and runs in near real-time
(not chronomancer, alas -- not yet). I want the moon, as a debugger
user (and yet I still suffer in this day and age with gdb!).
My point is that debugging is a specialized task with immature
(frozen in the last days of disco!) tools; the debugger tail should
not wag the dog.
Separately, poring over crashdumps (which is not the same as
debugging, and not a task for "average" users), many C++ hackers have
had to deal with good old "TCO". It's a pain, but we keep the
optimization levels high for production builds and suffer the entrail-
reading horror when investigating crashes.
I've heard Schemers testify that tail calls seldom impair debugging,
but I'll invite those Schemer among the many on this list who are so
inclined to re-testify.
On Jan 21, 2008, at 10:52 PM, Brendan Eich wrote:
On Jan 21, 2008, at 8:02 PM, Maciej Stachowiak wrote:
On Jan 21, 2008, at 12:35 PM, Brendan Eich wrote:
Conversions (implicit and hardcoded among the built-in types representing and wrapping primitives) that might defeat PTC may not be evident until runtime, where the result would be a TypeError or possibly a new Error subtype.
Isn't this case (implicit conversion) exactly what motivated the idea that programmers may not be able to easily tell if a call is in tail position?
Indeed:
"ES4 has proper tail calls, but their constraints are sometimes
subtle, especially with regard to conversions or type checks
inserted at the return point. It may be that the "Explicit Is Better
Than Implicit" principle once again finds application here."First paragraph in bugs.ecmascript.org/ticket/323. Again, the
ticket is just sitting there, you don't need me transcribing it into
this list :-/.
What I meant to point out is that the motivating use case for
additional up-front checking can't in general be checked until
runtime, which somewhat undermines the point you made that many non-
tail cases could be caught at compile time.
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
Consider another example:
function f(a) { function f2 { return a * 2; } if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
One may expect that this would require O(1) space. But this is not the case as the implementation may not eliminate f2.
On 21/01/2008, Jon Zeppieri <jaz at bu.edu> wrote:
But the above example does only require O(1) space. On each call to f, a new closure is constructed, but it's dropped on the floor as soon as the next iteration occurs.
On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
You can not deduce that from ES4 specs that it does not require that f should be ever dropped.
Unless I'm entirely mistaken, neither ES3 nor ES4 places any significant requirements on the implementation of memory allocation, dead object detection or garbage collection systems used in an engine. They leave all that up to the common sense of the engine developers.
However, once f has exited, there's no single live reference to it's closure in that example. And it's closure is the only reference to f2. That means that, at the discretion of the DoD and GC systems, the memory could at any time be reclaimed. If the recursion exhibits a space growth such that GC may be called for, then all those closures should be collected, including the f2 from each closure and any other heap stored values whose only reference comes from one of those closures.
On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
function f(a) { if (a == 0) return 0; goto return f(a - 1); }
f(1 << 20);
the implementation is still allowed to use heap for integers. So even in this example the space complexity may be O(N).
What is N here? Surely, it's has nothing to do with the number of calls to f. This example has nothing do to with PTC.
Even with the tail call optimization implemented, the space complexity of f(N) with f from the above example can be O(N) if the implementation uses heap to allocate integers.
IIRC, at least ES3 (and probably ES4 as well... since I haven't seen any actual spec text written for ES4, I can't say either way) makes no statements whatsoever about the internal storage used by the engine. ES3 doesn't even contain the word "heap", and the only uses of the word "stack" are the following two:
10 Execution Contexts
When control is transferred to ECMAScript executable code, control is
entering an execution context. Active execution contexts logically
form a stack. The top execution context on this logical stack is the
running execution context.
Even when a stack is mentioned it's just a logical stack, it doesn't say anything about the actual implementation of anything.
Hence the questions: how useful to specify the details of tail call optimizations without putting restrictions on the rest of the runtime?
In my experience, very.
I was not able to construct a single useful example where one can reason about the space complexity of the tail calls given that ES4 does not specify the space complexity of other aspects of the runtime. For this reason goto return looks very strange in ES4. It allows to assert a very specific space complexity property yet it is not possible to assert that, say a - 1 should not use heap allocation.
Well, I make a difference here between the live objects space and the dead objects space. Whether there are tons of dead objects or not makes no difference as to the space consumption of the live object space. And the live object space in presence of proper tail calls will grow only by the last closure unless the function explicitly makes values externally reachable.
On 21/01/2008, Jon Zeppieri <jaz at bu.edu> wrote:
But the above example does only require O(1) space. On each call to f, a new closure is constructed, but it's dropped on the floor as soon as the next iteration occurs.
On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
You can not deduce that from ES4 specs that it does not require that f should be ever dropped.
On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
Sorry for bad English here. I wanted to say:
You can not deduce that from ES4 specs. The specs does not require that closures created during execution of a function would ever be dropped.
You can't deduce that any memory needed at any time by an ES3 engine will be recovered, either. Garbage collection is left up to the engine implementors.
On Jan 21, 2008, at 11:37 PM, Maciej Stachowiak wrote:
What I meant to point out is that the motivating use case for
additional up-front checking can't in general be checked until
runtime, which somewhat undermines the point you made that many non- tail cases could be caught at compile time.
My (imputed, but I don't disagree) "many" needs proof, but so does
your "somewhat undermines". Upon this question of how often implicit
conversions actually gum up the compile-time checking hangs much of
the debate. But not all: suppose we had implicit tail calls as
proposed in the wiki. Jon Zeppieri argues for the value of a "tail"
assertion, an annotation on a call expression, assuming implicit PTC
and independent of compile- vs. runtime checking.
ES4 is a dynamic language, and the strict mode (optional to
implementations) won't catch everything. The * type is an intentional
loophole in the static type checker. But there are lots of programs
that benefit from such a checker, even with the loopholes and their
uses. It's not all-or-nothing. Same goes for explicit tail syntax of
some sort. I'm warming up to the idea that tail annotations are like
type annotations and should be optional, even with mandatory and
implicit PTC.
Thanks. That would work. But I can still see the "average" user being confused when debugging, and not knowing what is going on.
Would you think an explicit keyword syntax for mandatory tail call would help such a user?
I do.
To the claim that debugging in the face of PTCs will become madness- inducing, Schemers and others retort "do you want to see every state of an iteration?" (A loop is a tail call in Scheme.) The right answer is "yes". Yes, I want a debugger that remembers all program states (code.google.com/p/chronomancer) and runs in near real-time (not chronomancer, alas -- not yet). I want the moon, as a debugger user (and yet I still suffer in this day and age with gdb!).
My point is that debugging is a specialized task with immature (frozen in the last days of disco!) tools; the debugger tail should not wag the dog.
I can't argue the sentiment. But exactly how soon will such advanced
debugging tools be generally available and in the hands of the
programmers we're discussing? Before ES4 has given way to ES5/6/7?
Separately, poring over crashdumps (which is not the same as debugging, and not a task for "average" users), many C++ hackers have had to deal with good old "TCO". It's a pain, but we keep the optimization levels high for production builds and suffer the entrail- reading horror when investigating crashes.
Without forcing you to declare your age ;) I must point out that it's
common these days for programmers to have over a decade's experience
without any coredump debugging experience. (I'm almost an example
of this.) I'm having a hard time swallowing the argument that it's
OK for a modern language like ES4 to require the skillsets used for
assembly++. (I'm not arguing that those aren't good skillsets to
have, just pointing out the reality of next-generation programmers.)
I've heard Schemers testify that tail calls seldom impair debugging, but I'll invite those Schemer among the many on this list who are so inclined to re-testify.
I think that's skewing the sample. We're not talking about schemers
here, we're talking about scripters. They don't read language specs,
they use tutorials and references, and they just so happen to vastly
outnumber the people on this list. Advanced PLT concepts are "over
engineered" from their perspective. They have no frame of reference
for incomplete stack traces. Implicit PTC will confuse the heck out
of them, they'll go straight to bugzilla and file a bug on the
interpreter. ;) At least Explicit gives them a fighting chance.
They might just ask, "what the heck does that keyword mean, anyway?"
and go look it up in their favorite reference.
I think the implicit-hurts-debugability argument has a lot more
weight than you're giving it, especially in the near-term.
Neil,
I understand your points. But I wouldn't want to defeat an important feature simply because novices wouldn't understand how to use it. Especially in this case, where it should be possible for the feature to coexist with novices without them tripping over it.
People's primary concern with "tripping over tail calls" appears to be with debugging. You say Brendan's debugger wish list is on steroids, but creating a debugger that is compatible with tail calls doesn't have to be a dramatic engineering challenge. One approach some debuggers (I believe recent builds of SML/NJ do this) is for the debugger to hang on to some bounded queue of the most recent tail calls (this is applicable to loop iterations if that would be useful too). That way it's still only consuming a constant amount of space, but a stack trace or checkpoint could see the recent "trail" of tail calls. This isn't hard to implement.
I can't argue the sentiment. But exactly how soon will such advanced debugging tools be generally available and in the hands of the programmers we're discussing? Before ES4 has given way to ES5/6/7?
Flex Builder represents such a tool and it exists today. Sure you have squint your eyes to equate AS3 with ES4 but its not far off. At first blush I would think the debugger would just disable this feature and have a setting to turn it back on if it caused problems. When its on the debugger could highlight this somehow with a stack frame annotation of some sort. The profiler could just represent it with an iteration count on the stack frame or something. Anyway I agree with Brendan's sentiment that the tail shouldn't wag the dog and that the debuggability issue can be adequately handled by the debugger and therefore shouldn't exert any influence on this feature.
As an aside I think looking at the nature of web browsers and the web's history I think ES4 might have quite a long shelf life and we shouldn't be tempted to push things off to future revs. That said my earlier comments about kicking Santa in the shins if ES4 isn't done by Christmas still apply ;-)
On Jan 22, 2008, at 7:45 AM, Neil Mix wrote:
Thanks. That would work. But I can still see the "average" user
being confused when debugging, and not knowing what is going on.Would you think an explicit keyword syntax for mandatory tail call would help such a user?
I do.
Others argue that this syntactic penalty box means no one will use
PTC; the cursed view of tail calls and recursion will not fade away.
My point is that debugging is a specialized task with immature (frozen in the last days of disco!) tools; the debugger tail should not wag the dog.
I can't argue the sentiment. But exactly how soon will such advanced debugging tools be generally available and in the hands of the programmers we're discussing? Before ES4 has given way to ES5/6/7?
Dave followed up, but I wanted to point out that adapting Firebug and
the JS Debugger API it sits on to have a bounded queue of frames, and
turn this overhead on only when debugging, is not going to take long
to hack, or tie up all your machine resources -- not on modern fat
desktops.
Anyway, dog before tail.
Separately, poring over crashdumps (which is not the same as debugging, and not a task for "average" users), many C++ hackers have had to deal with good old "TCO". It's a pain, but we keep the optimization levels high for production builds and suffer the
entrail- reading horror when investigating crashes.Without forcing you to declare your age ;) I must point out that it's common these days for programmers to have over a decade's experience without any coredump debugging experience. (I'm almost an example of this.) I'm having a hard time swallowing the argument that it's OK for a modern language like ES4 to require the skillsets used for assembly++.
No, you misread me (and yes, I'm old). Hard cases make bad law, they
teach in law school. The hard case I cite is probably not a common
one that "average users" will face, even if implicit PTCs are common
in ES4.
I think that's skewing the sample. We're not talking about schemers here, we're talking about scripters. They don't read language specs, they use tutorials and references, and they just so happen to vastly outnumber the people on this list.
The testimony I'm thinking of, and you can find it in that LtU thread
I'm tired of citing (but it could use more detailed and colorful
anecdotes) suggests that debugger drivers don't often go back up the
stack to find overwritten frames' variables. Or something like that
-- I need backup here.
And if not, the queue stands ready. I'm not being glib. I really do
think debuggers should not distort the design too much.
I think the implicit-hurts-debugability argument has a lot more weight than you're giving it, especially in the near-term.
You are with Waldemar then, and this is one of those axes of
disagreement. I just find it hard to believe it's the decisive high-
order one.
Not sure if this was clear, but I'm not arguing against PTC
altogether, just implicit PTC. I have no qualms about explicit
PTC. (I'm even fairly sympathetic to arguments for implicit PTC, I'm
just worried -- based on Brendan's statements -- that debugability
isn't getting the weight it deserves.)
I also want to make clear: this isn't about debugging code that uses
PTC intentionally -- that tradeoff is up to the developer. This is
about the novice coder who finds a stack trace on a production system
from code that he doesn't own which just happens to be invoking PTC
implicitly. Say what you will about Java (I've probably said worse),
but stack traces in production logs are a godsend for problem
solving. Implicit PTC concerns me for that reason -- how do you
"turn off" an implicit language feature? How do you craft a coding
standard to avoid implicit PTC?
That said, if meaningful stack traces can be generated in spite of
implicit PTC (you and Thomas Reilly mentioned debuggers, I wasn't so
clear on traces), I'll happily scurry back into my little corner and
shush. ;)
On Jan 22, 2008, at 11:03 AM, Neil Mix wrote:
I also want to make clear: this isn't about debugging code that uses PTC intentionally -- that tradeoff is up to the developer. This is about the novice coder who finds a stack trace on a production system from code that he doesn't own which just happens to be invoking PTC implicitly.
I've already copped to low expectations about current-era debuggers,
and it is possible the same dismal view applies to logging traces, at
least on my part. Having to deal with a stack backtrace where you
(n00b or l33t, doesn't matter) have to hop around in 3, or 30, source
files to see how the heck control flowed from function f to g when f
doesn't call g, is Not Fun. The lack of stack traces in ECMA-262, and
anything like Python's much better backtrace support in JS
implementations, may be remedied, and then we'll all feel PTC pain.
But why won't we feel it, as trace-readers, just as much when the
PTCs were explicit? This, I don't follow. The programmer and the
debugger-driver are often very different people, in general skills,
familiarity with the source at hand, etc.
Depends on what you mean by meaningful stack trace. Do you actually want to see the same function name repeated N times for each invocation? I would think not, I would just come up with some notation to decorate the stack trace.
Its probably important to go back to Brendan's point about this being a feature and not an optimization. Even in Java the stack traces you get are very distantly related to the actual code running when all the inlining, escape analysis, and traditional optimizations are applied. They jump through a lot of hoops to give you that valuable stack trace in spite of all those optimizations and ES4 implementation will have to do the same. As a language feature and not just an optimization it makes sense to have a notation for stack traces even if that's an implementation detail. Maybe we could even have something in the non-normative part of the spec or just agree to follow the RI's lead and have it do something agreeable.
On Jan 22, 2008, at 11:03 AM, Neil Mix wrote:
I also want to make clear: this isn't about debugging code that uses PTC intentionally -- that tradeoff is up to the developer. This is about the novice coder who finds a stack trace on a production system from code that he doesn't own which just happens to be invoking PTC implicitly.
On 22/01/2008, Brendan Eich <brendan at mozilla.org> wrote:
I've already copped to low expectations about current-era debuggers, and it is possible the same dismal view applies to logging traces, at least on my part. Having to deal with a stack backtrace where you (n00b or l33t, doesn't matter) have to hop around in 3, or 30, source files to see how the heck control flowed from function f to g when f doesn't call g, is Not Fun. The lack of stack traces in ECMA-262, and anything like Python's much better backtrace support in JS implementations, may be remedied, and then we'll all feel PTC pain.
Maybe it'd make sense to have some "use ImplicitTailCallElimination=bool;" directives that can be used to make sure an implementation has or lacks implicit tail call elimination when running the code, still having explicit TCE possible even with "use ImplicitTailCallElimination=false;", leaving the default behaviour for implicit TCE up to the implementation? Or would that be three ways too many to handle it?
On Jan 22, 2008, at 11:27 AM, Thomas Reilly wrote:
Depends on what you mean by meaningful stack trace. Do you actually want to see the same function name repeated N times for each
invocation? I would think not, I would just come up with some notation to decorate the stack trace.
Tail call != recursion. Not even indirect recursion. The point is you
may see gaps in the stack where control seems to flow from f to g,
but nothing in tail position in f could possibly call g, and you
wonder what might have intervened.
Its probably important to go back to Brendan's point about this
being a feature and not an optimization. Even in Java the stack traces you
get are very distantly related to the actual code running when all the inlining, escape analysis, and traditional optimizations are applied. They jump through a lot of hoops to give you that valuable stack trace in spite of all those optimizations and ES4 implementation will
have to do the same.
This is a good point, but the standard may have little to do with it
(we have no standard backtrace methods or properties on Error objects
proposed at this point). The ControlInspector could be used by
programmers, but it is not mandated as part of the spec to help hide
PTC or other transformations. This leaves implementations to compete
on quality of debugging and tracing, which is likely to be a growth
area.
Others argue that this syntactic penalty box means no one will use PTC; the cursed view of tail calls and recursion will not fade away.
Interesting -- I'd love to know more about why that is. Dave
Herman's example in the ticket isn't so bad once the annotation is
placed on the function call. If this is such a highly desired
feature, how is it that it will be shunned if given a light syntactic
overhead?
But why won't we feel it, as trace-readers, just as much when the
PTCs were explicit? This, I don't follow. The programmer and the
debugger-driver are often very different people, in general skills,
familiarity with the source at hand, etc.
We will, but the point is: you (or someone you work with) made the
decision that the benefit was worth the risk. Implicit PTC turns
that choice into an irreversible default. I'm not worried about
those who choose to use it, I'm worried about those who'd like to
choose not to.
Its probably important to go back to Brendan's point about this
being a feature and not an optimization. Even in Java the stack traces
you get are very distantly related to the actual code running when all the inlining, escape analysis, and traditional optimizations are applied. They jump through a lot of hoops to give you that valuable stack
trace in spite of all those optimizations and ES4 implementation will
have to do the same.This is a good point, but the standard may have little to do with
it (we have no standard backtrace methods or properties on Error
objects proposed at this point). The ControlInspector could be used
by programmers, but it is not mandated as part of the spec to help
hide PTC or other transformations. This leaves implementations to
compete on quality of debugging and tracing, which is likely to be
a growth area.
I also admit this is a good point. If it's likely that
implementations will go to the trouble of providing useful stack
traces, than my arguments against implicit PTC are moot. So the
question (which I rely on you to judge for me since I have no skin in
the implementation game) is, how big is that "if"?
One issue with requiring the explicit syntax is that the requirement isn't worth anything as a restriction. The compiler will have to figure out whether a phrase could be a tail call to find out if the ditto phrase using explicit syntax is a legal tail call. It is but a short step from that to optimizing the call even if the explicit syntax is not used; in fact, the implementer would almost be delinquent in not doing so. Ergo some implementations will have this improvement; users will start depending on it; other implementations will follow; and the explicit syntax is useful only as an assert that the tail call can in fact take place, and will be useful only to people who know about it and value it. Like type annotations, I guess.
Maciej asked:
Here is another thing I don't understand: if goto must flag runtime errors in cases where otherwise implicit type conversion would occur, then does that not itself break proper tail recursion (something has to hang around to do the typecheck on the actually returned type)? Or is the intent that it throws a runtime error before the call if it can't statically prove that return types match? Does that mean you can never goto an untyped function from one with a declared return type?
IMO it would have to check before the call, and throw then. Also IMO, this is another nail in the coffin for requiring explicit syntax, because it would mean that people don't get the benefit of tail calls unless they ask for them, and then they have to be really sure that they will always work. This straightjacket is probably unacceptable to most.
IMO, the best design is that (a) a call that is syntatically in tail position is executed as a tail call when that is possible, but as a non-tail call when type conversions or type checking interferes, and that this happens without the programmer having to think about it, and (b) an annotation ("goto", whatever) can be used to check that the tail call is in fact possible, and it will cause an error (at compile time in strict mode, possible) if that is not possible. Thus we have tail call annotations like we have type annotations; people use them if they feel that provides benefit. For everyone else it "just works except when it doesn't" -- again, exactly like typing.
Tail call != recursion. Not even indirect recursion. The point is you may see gaps in the stack where control seems to flow from f to g, but nothing in tail position in f could possibly call g, and you wonder what might have intervened.
My bad, thinking about the scheme looping special case. Anyways the point remains that just because the implementation was clever and optimized away f's frame, or reused it or whatever doesn't mean a debugger can't remember it and show it as either still being there or as being ghosted out or something. I think the feature is too valuable to rule it out b/c it places constraints on the debugger. And I wouldn't want any constraints to be levied by the language/spec. I would even think it reasonable for implementation to have a policy where you had to turn the VM into interpreter mode to get the whole picture.
To back up my point about this feature being important I'll bring up Flex and code generation. A Flex application has this nesting notion where the XML nesting of your Flex components is translated into a chunk of nesting AS3 code for initialization purposes. Thus as its implemented your Flex component nesting is bounded by your available stack space. The ease at which MXML facilitates component nesting means that some day we'll either have to change this to initialize using an explicit heap data structure but maybe if explicit tail call support existed they could keep using it and feel safe to keep on doing it this way. Basically its automatic vs manual memory management and a scripting language shouldn't force people to do manual memory management.
My vote is to have an explicit syntax with the optional implicit allowed (encouraged?) caveat.
On Jan 22, 2008, at 12:14 PM, Lars T Hansen wrote:
Ergo some implementations will have this improvement; users will start depending on it; other implementations will follow; and the explicit syntax is useful only as an assert that the tail call can in fact take place, and will be useful only to people who know about it and value it. Like type annotations, I guess.
Ding ding ding....
IMO, the best design is that (a) a call that is syntatically in tail position is executed as a tail call when that is possible, but as a non-tail call when type conversions or type checking interferes, and that this happens without the programmer having to think about it, and (b) an annotation ("goto",
"tail" ;-)
whatever) can be used to check that the tail call is in fact possible, and it will cause an error (at compile time in strict mode, possible) if that is not possible. Thus we have tail call annotations like we have type annotations; people use them if they feel that provides benefit. For everyone else it "just works except when it doesn't" -- again, exactly like typing.
This works for me. The desire for explicitude was well-intentioned
but misdirected. It has found its target: an optional syntax for
asserting a tail call. Thanks to all (esp. Jon Zeppieri for putting
the assertion idea down in the bug) for this discussion (it helped
crystalize things for me, at least).
Neil Mix wrote:
Others argue that this syntactic penalty box means no one will use PTC; the cursed view of tail calls and recursion will not fade away.
Interesting -- I'd love to know more about why that is. Dave
Herman's example in the ticket isn't so bad once the annotation is
placed on the function call. If this is such a highly desired
feature, how is it that it will be shunned if given a light syntactic
overhead?
In functional languages, proper tail calls are something that just happen automatically (to varying degrees depending on the language), and programmers don't need to think about them most of the time, if at all.
If an annotation is required to achieve proper tail calls, it means that you have to be aware of when you're relying on a tail call, and remember to use the annotation, or you'll have runtime problems when you implicitly rely on tail call behavior that's not there. Like most runtime problems, this could happen in some circumstances but not others, e.g. after your program is deployed, but not in testing.
At the same time, you can't use the annotation in the wrong place, or you'll also get an error.
So you have two additional classes of error that don't exist in languages with implicit tail calls, and it requires more knowledge and care to use tail calls than it does in languages where they are implicit.
I also find it a bit ironic that errors that result from forgetting to use the tail annotation are the same general class of errors that the annotation is ostensibly intended to guard against: cases where a tail call is expected, but doesn't happen. It's not unlikely that requiring this annotation could create more instances of this bug than it prevents, with the amusing property that the bugs it creates are the exact kind it's intended to prevent.
This is the sort of thing that you see in low-level languages, like bytecodes or intermediate languages, where code is usually generated by machine, so the machine is doing the reasoning about which construct to use where. C-- is an example of this, mentioned in ticket #323. However, such pickiness doesn't seem appropriate for a high-level language, if the intent is that tail calls are a feature to be used by human programmers.
I'm not aware of any high level language that has a feature like this. The other two examples mentioned in the ticket, Newsqueak and Aleph a.k.a. Afnix, are either experimental or with extremely small user bases, and their keywords relating to tail calls don't work in the above way. If there's anything to be learned from them, it may be that a tail-calling construct might be useful if it didn't throw an error when used on a non-tail expression, since both of them appear to work that way.
Anton
On 1/22/08 12:14 PM, "Lars T Hansen" <lth at acm.org> wrote:
IMO, the best design is that (a) a call that is syntatically in tail position is executed as a tail call when that is possible, but as a non-tail call when type conversions or type checking interferes, and that this happens without the programmer having to think about it, and (b) an annotation ("goto", whatever) can be used to check that the tail call is in fact possible, and it will cause an error (at compile time in strict mode, possible) if that is not possible. Thus we have tail call annotations like we have type annotations; people use them if they feel that provides benefit. For everyone else it "just works except when it doesn't" -- again, exactly like typing.
I think you've hit the nail on the head with this one. IMHO this fits well with rest of the optional-type-annotation mode of operation in ES4.
I don't really care what the syntax is, but I do very much like the idea of an obvious directive that means "I expect this to be a tail call; please fail immediately if it can't be one".
Question: should an implementation be required to execute a tail call as a Proper Tail Call when possible, even if said syntax is not present? (or merely permitted to do so?)
On Jan 22, 2008 12:44 PM, Steven Johnson <stejohns at adobe.com> wrote:
On 1/22/08 12:14 PM, "Lars T Hansen" <lth at acm.org> wrote:
Question: should an implementation be required to execute a tail call as a Proper Tail Call when possible, even if said syntax is not present? (or merely permitted to do so?)
If there is no guarantee then the implicit proper tail calls feature is useless to someone writing code for a variety of implementations (eg web browsers.) If there are implicit proper tail calls then I need to know when I can count on them and I will only use them in those situations listed in the ES4 spec.
Peter
On 1/22/08, Steven Johnson <stejohns at adobe.com> wrote:
On 1/22/08 12:14 PM, "Lars T Hansen" <lth at acm.org> wrote:
IMO, the best design is that (a) a call that is syntatically in tail position is executed as a tail call when that is possible, but as a non-tail call when type conversions or type checking interferes, and that this happens without the programmer having to think about it, and (b) an annotation ("goto", whatever) can be used to check that the tail call is in fact possible, and it will cause an error (at compile time in strict mode, possible) if that is not possible. Thus we have tail call annotations like we have type annotations; people use them if they feel that provides benefit. For everyone else it "just works except when it doesn't" -- again, exactly like typing.
I think you've hit the nail on the head with this one. IMHO this fits well with rest of the optional-type-annotation mode of operation in ES4.
I don't really care what the syntax is, but I do very much like the idea of an obvious directive that means "I expect this to be a tail call; please fail immediately if it can't be one".
Question: should an implementation be required to execute a tail call as a Proper Tail Call when possible, even if said syntax is not present? (or merely permitted to do so?)
Required -- or we have nothing. Virtually nobody will use the annotation. (As I've noted in the ticket I actually oppose the idea. But since it's optional and basically free to the implementation, I don't care too much if it gets adopted anyway, as long as programs that don't use it are not treated as second class.)
If there is no guarantee then the implicit proper tail calls feature is useless to someone writing code for a variety of implementations (eg web browsers.) If there are implicit proper tail calls then I need to know when I can count on them and I will only use them in those situations listed in the ES4 spec.
My assumption here was that coders relying on PTC would use the specific syntax, and implicit PTC might be reserved as an implementation optimization in other cases.
Required -- or we have nothing. Virtually nobody will use the annotation.
And this is where my assumption falls down. Agreed, few people will use the annotation.
On Jan 22, 2008, at 11:51 AM, Neil Mix wrote:
But why won't we feel it, as trace-readers, just as much when the PTCs were explicit? This, I don't follow. The programmer and the debugger-driver are often very different people, in general skills, familiarity with the source at hand, etc.
We will, but the point is: you (or someone you work with) made the decision that the benefit was worth the risk.
On the www, everyone is my colleague. I'm not kidding (have to talk
to management about the quality of hiring lately :-P).
Implicit PTC turns that choice into an irreversible default. I'm not worried about those who choose to use it, I'm worried about those who'd like to choose not to.
The program will diverge if someone chooses not to implement PTC, so
it's going to be required. The confusing traces and debugging views
of the stack (which is not a program history!) can be mitigated.
But to your point, I think the party of the first part (the
programmer who wrote code that uses tail calls) must prevail, whether
or not they intended tail calls or expressed them explicitly. Lars
made this point recently: unless we ban implicit PTC even when not
elected by the programmer using explicit syntax, code will come to
depend on PTC and we'll need it implicitly "on" everywhere. All that
remains is the assertion.
-----Original Message----- From: es4-discuss-bounces at mozilla.org [mailto:es4-discuss-bounces at mozilla.org] On Behalf Of Dave Herman Sent: 21. januar 2008 16:58 To: Peter Hall Cc: Brendan Eich; es4-discuss at mozilla.org; Jeff Dyer; Erik Arvidsson Subject: Re: proper tail calls
I am a bit out of my depth in this discussion, but explicit syntax feels wrong to me. However, if it's going to be implicit, it has to be completely invisible (aside from the benefits) - developers are going to want their debugging tools to work as before.
Is there a practical approach to recursion counting, that ES4 could require, so that Error.getStackTrace() can use it to produce the "expected" result? I must admit, It doesn't feel as trivial in my head as that sentence reads...
You can easily circumvent an expression being in tail position. For example, if EXP is in tail position and you want it not to be, just wrap it as:
let (r = EXP) rThe program behaves the same, except for the fact that EXP is no longer in tail position, so it cannot perform a tail call.
Of course some implementations would optimize away r, and EXP would be back in tail position. ISTR that the R5RS made a point of saying that an implementation would be allowed to do that, and I think this ought to be true for ES4 too. Ditto, interprocedural analysis and/or inlining may prove that the body of a "try" can't throw an exception, thereby allowing the exception handler to be removed, thereby exposing a possibility for TCO. And so on.
Maybe we need a directive for turning off tail calls:
please don't goto f(37)
The confusing traces and debugging views of the stack (which is not a program history!) can be mitigated.
Yes! That's my only concern. (And yes, after years of debugging
asynchronous callbacks I'm acutely aware of the difference between
stack traces and program history. In fact, I got so sick of it I
hacked our test suite to store traces at key jump-off points so that
I could capture stack from asynchronous callbacks back up to their
originating callers. But I digress. :P)
But to your point, I think the party of the first part (the programmer who wrote code that uses tail calls) must prevail, whether or not they intended tail calls or expressed them explicitly. Lars made this point recently: unless we ban implicit PTC even when not elected by the programmer using explicit syntax, code will come to depend on PTC and we'll need it implicitly "on" everywhere. All that remains is the assertion.
Oh yes, Lars and Anton have convinced me that requiring explicit PTC
is not desirable. As I stated early on, as long as meaningful stack
traces are doable with implicit PTC, I'll happily shush. So consider
me shushed.
On 23/01/2008, Lars Hansen <lhansen at adobe.com> wrote:
Ditto, interprocedural analysis and/or inlining may prove that the body of a "try" can't throw an exception, thereby allowing the exception handler to be removed, thereby exposing a possibility for TCO. And so on.
This nicely shows the weakness of the explicit TCO enforced at the compile time. It is not future proof. If an implementation can turn return 2 * f(args) into a tail call, a programmer would not be able to write tail return 2 * f(args). since this is not a valid syntax. So the programmer who needs this fine control over space complexity would not be able to state that.
, Igor
Anton van Straaten wrote:
In functional languages, proper tail calls are something that just happen automatically (to varying degrees depending on the language), and programmers don't need to think about them most of the time, if at all.
Because of the language semantics, not the implicit/explicit issue.
If an annotation is required to achieve proper tail calls, it means that you have to be aware of when you're relying on a tail call, and remember to use the annotation, or you'll have runtime problems when you implicitly rely on tail call behavior that's not there.
But this is the case anyway: you have to be aware of when you're relying on a tail call that might not actually be a tail call.
Like most runtime problems, this could happen in some circumstances but not others, e.g. after your program is deployed, but not in testing.
I agree that failing earlier is better than later.
At the same time, you can't use the annotation in the wrong place, or you'll also get an error.
Well, as you point out, if you are relying on a tail call when you aren't getting one, you already have an error. The question is: would you rather fail early or later? As I said, I agree with you: failing early is better. :)
So you have two additional classes of error that don't exist in languages with implicit tail calls, and it requires more knowledge and care to use tail calls than it does in languages where they are implicit.
It does require more knowledge and care to depend on tail call semantics in ES4 than in other languages. This has nothing to do with implicit vs explicit.
The problem is not implicit vs explicit. The problem is the language semantics making tail calls not obvious.
I also find it a bit ironic that errors that result from forgetting to use the tail annotation are the same general class of errors that the annotation is ostensibly intended to guard against: cases where a tail call is expected, but doesn't happen.
:P You could make the same argument about any kind of error checking, couldn't you? Finding errors earlier is better than later.
Chris
Chris Pine wrote:
Anton van Straaten wrote:
In functional languages, proper tail calls are something that just happen automatically (to varying degrees depending on the language), and programmers don't need to think about them most of the time, if at all.
Because of the language semantics, not the implicit/explicit issue.
It's a bit of both. My point is just that an explicit annotation that's required to achieve tail calls, and not allowed elsewhere, will require more thinking in more places than would be the case otherwise.
If an annotation is required to achieve proper tail calls, it means that you have to be aware of when you're relying on a tail call, and remember to use the annotation, or you'll have runtime problems when you implicitly rely on tail call behavior that's not there.
But this is the case anyway: you have to be aware of when you're relying on a tail call that might not actually be a tail call.
I agree that the situation can occur either way. An optional annotation, such as Lars recently described, is a fine way to address this: if you know you need a tail call and are unsure of whether you're going to get one, annotate. But I'm saying that a required annotation is undesirable.
At the same time, you can't use the annotation in the wrong place, or you'll also get an error.
Well, as you point out, if you are relying on a tail call when you aren't getting one, you already have an error.
My point was mainly that with a required annotation, it is necessary to annotate everywhere you need a tail call, and you can't mitigate this requirement by using a strategy of "when in doubt, annotate", unless you're willing to deal with the resulting additional error messages.
It does require more knowledge and care to depend on tail call semantics in ES4 than in other languages. This has nothing to do with implicit vs explicit.
Even so, I believe that a required explicit annotation would make things worse, not better.
The problem is not implicit vs explicit. The problem is the language semantics making tail calls not obvious.
An optional assertion-style annotation would give programmers a way to address this without getting in their way when they don't they need it.
If the language semantics are such that you end up having to use the optional annotation on every tail call anyway, then my argument would fail. But I suspect that it's more likely that programmers will be fine using the annotations a little like parentheses are often used in expressions: you put them in either for readability or when you're not sure of the precedence rules, but otherwise leave them out where you can.
I also find it a bit ironic that errors that result from forgetting to use the tail annotation are the same general class of errors that the annotation is ostensibly intended to guard against: cases where a tail call is expected, but doesn't happen.
:P You could make the same argument about any kind of error checking, couldn't you?
I don't think so. Part of the problem is that a required annotation isn't just an error check, it's an instruction that affects semantics. If it were just an error check, i.e. an assertion, it'd be fine.
Finding errors earlier is better than later.
That's only unequivocally true if all other things are equal. But I notice that ES4 doesn't require that all types be declared, for example, even though requiring that would find more errors earlier.
Anton
Anton van Straaten wrote:
If an annotation is required to achieve proper tail calls, it means that you have to be aware of when you're relying on a tail call, and remember to use the annotation, or you'll have runtime problems when you implicitly rely on tail call behavior that's not there.
But this is the case anyway: you have to be aware of when you're relying on a tail call that might not actually be a tail call.
I agree that the situation can occur either way. An optional annotation, such as Lars recently described, is a fine way to address this: if you know you need a tail call and are unsure of whether you're going to get one, annotate. But I'm saying that a required annotation is undesirable.
Ahhh, I see. Maybe that part wasn't communicated on-list, but was discussed in the trac ticket (or in the phone meeting? can't remember). It was agreed that implementations would always be free to implement PTC, and where pages depend on it from one browser, others will have to support it there, too. So, practically speaking, I assumed that it was an assertion, not a requirement, and that we would all implement it where we could.
Chris
Chris Pine wrote:
Ahhh, I see. Maybe that part wasn't communicated on-list, but was discussed in the trac ticket (or in the phone meeting? can't remember).
I'm just an observer, and have only seen the one ticket (#323) and the discussion here. The ticket proposes a required annotation to activate PTC. On this list, Neil argued against implicit PTC if it was going to compromise debug traces (a very valid concern, IMO), and later asked why some required syntactic overhead for tail calls would be such a bad thing. I was responding to that question.
It was agreed that implementations would always be free to implement PTC, and where pages depend on it from one browser, others will have to support it there, too. So, practically speaking, I assumed that it was an assertion, not a requirement, and that we would all implement it where we could.
You know that the minute there's some PTC around, people will implement crazy CPS-based programs and then complain about how browser X won't run them. So y'all are going to have to get cracking. ;-P
Anton
On Thu, 2008-01-24 at 20:04 +0100, Chris Pine wrote:
It was agreed that implementations would always be free to implement PTC...
Really? That wasn't the impression I got. My understanding is that if PTC isn't a requirement, it should not exist. As a programmer, I don't want to need to keep track of whether which implementations support my programming style. Do we really want "ES4" and "Stackless ES4" (for example)?
Peter Michaux put it nicely when he said:
If there are no requirements for proper tail calls then they cannot be depended upon and are useless.
Portability is a huge requirement for me, and if there's a valid reason for leaving PTC out of an implementation history shows that someone will.
Cheers,
-- Nathan de Vries
PS: What's the go with everyone including long lists of CCs? Isn't everyone here on es4-discuss at mozilla.org?
On 1/24/08, Nathan de Vries <nathan at atnan.com> wrote:
On Thu, 2008-01-24 at 20:04 +0100, Chris Pine wrote:
It was agreed that implementations would always be free to implement PTC...
Really? That wasn't the impression I got. My understanding is that if PTC isn't a requirement, it should not exist. As a programmer, I don't want to need to keep track of whether which implementations support my programming style. Do we really want "ES4" and "Stackless ES4" (for example)?
Peter Michaux put it nicely when he said:
If there are no requirements for proper tail calls then they cannot be depended upon and are useless.
Portability is a huge requirement for me, and if there's a valid reason for leaving PTC out of an implementation history shows that someone will.
Either the spec will mandate proper tail calls in a set of clearly defined situations, or it will not mention them at all. The set should be ambitiously large, but it also needs to be describable. Anyhow, an implementation will always be allowed to handle more tail call situations (exposed by sophisticated analysis or an ambitious implementation, say) than the spec defines.
2008/1/24 Nathan de Vries <nathan at atnan.com>:
On Thu, 2008-01-24 at 20:04 +0100, Chris Pine wrote:
It was agreed that implementations would always be free to implement PTC...
Really? That wasn't the impression I got. My understanding is that if PTC isn't a requirement, it should not exist. As a programmer, I don't want to need to keep track of whether which implementations support my programming style. Do we really want "ES4" and "Stackless ES4" (for example)?
I believe that is the situation now with ES3 and that an ES3 implementation can use proper tail calls if it wishes to. The string "tail" doesn't even appear in the ES3 spec.
[snip]
PS: What's the go with everyone including long lists of CCs? Isn't everyone here on es4-discuss at mozilla.org?
For this list, "reply" doesn't default to the list. To post to the list, I think folks just hit "reply all" and don't clean up the list of CCs.
Peter
On 1/24/08, Lars T Hansen <lth at acm.org> wrote:
Either the spec will mandate proper tail calls in a set of clearly defined situations, or it will not mention them at all. The set should be ambitiously large, but it also needs to be describable. Anyhow, an implementation will always be allowed to handle more tail call situations (exposed by sophisticated analysis or an ambitious implementation, say) than the spec defines.
Yes, and this brings up a point I mentioned briefly in the trac ticket. Assuming that both implicit tail calls and an explicit tail assertion end up in the spec, the assertion's behavior should be specified in terms of the conditions under which implicit tail calls must occur in any conforming implementation.
In other words, even though implementations are allowed to handle more tail call situations than specified, the assertion should only succeed in the specified situations. Otherwise, the assertion is useless for writing portable code.
On Thu, 2008-01-24 at 16:09 -0800, Peter Michaux wrote:
For this list, "reply" doesn't default to the list.
Mailman (which Mozilla uses) allows the following which works quite nicely (although it's a highly religious topic in some circles):
reply_goes_to_list = 1 # 1 = "This list"
-- Nathan de Vries
Yes, but there have been hot flame wars (probably still burning)
about the advisability of setting reply-to-list. I'm not in favor
myself. Is this a big problem, or only a sporadic nuisance (possibly
much less of a problem than the reverse: private replies
inadvertently going to the list).
On Thu, 2008-01-24 at 16:48 -0800, Brendan Eich wrote:
Is this a big problem, or only a sporadic nuisance...
The latter.
-- Nathan de Vries
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
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. Is it not reasonable for the spec to simply require implementations to have proper tail calls? Is it not acceptable for the spec to require certain implementation internal optimizations?
Peter