Re: proper tail calls
On 21/01/2008, Erik Arvidsson <[EMAIL PROTECTED]> 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. Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Igor Bukanov <[EMAIL PROTECTED]> 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. >From http://www.haskell.org/onlinereport/intro.html : > 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 _|_). Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008 5:34 AM, Igor Bukanov <[EMAIL PROTECTED]> wrote: > On 21/01/2008, Igor Bukanov <[EMAIL PROTECTED]> 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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 20, 2008 8:01 PM, Brendan Eich <[EMAIL PROTECTED]> 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), > > http://lambda-the-ultimate.org/node/472#comment-3511 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 http://c2.com/cgi/wiki?TailCallOptimization Peter ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Mon, Jan 21, 2008 at 8:57 AM, Peter Michaux <[EMAIL PROTECTED]> 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? -- erik ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: 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: http://lambda-the-ultimate.org/node/472#comment-3568 and especially: http://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 > > http://c2.com/cgi/wiki?TailCallOptimization Yes, it' s a common TLA but citing one use of it doesn't settle the debate. Please read more. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Peter Michaux <[EMAIL PROTECTED]> wrote:
> On Jan 20, 2008 8:01 PM, Brendan Eich <[EMAIL PROTECTED]> 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.
Regards, Igor
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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?
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/21/08, Jon Zeppieri <[EMAIL PROTECTED]> wrote:
> On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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.
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Jon Zeppieri <[EMAIL PROTECTED]> wrote:
> On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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).
>
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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? ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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? -Graydon ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Graydon Hoare <[EMAIL PROTECTED]> 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?
Regards, Igor
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 > > http://c2.com/cgi/wiki?TailCallOptimization 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: http://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 [*] http://citeseer.ist.psu.edu/clinger98proper.html ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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.
-Jon
>
> Regards, Igor
>
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 http://wiki.ecmascript.org/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 http://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: 1. explicit vs. implicit, 2. whether to have a tail annotation if implicit, 3. statement vs. expression if explicit, and 4. 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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Jon Zeppieri <[EMAIL PROTECTED]> wrote:
> On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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.
Regards, Igor
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Igor Bukanov <[EMAIL PROTECTED]> wrote: > On 21/01/2008, Jon Zeppieri <[EMAIL PROTECTED]> 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. ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008 9:59 AM, Erik Arvidsson <[EMAIL PROTECTED]> wrote: > On Mon, Jan 21, 2008 at 8:57 AM, Peter Michaux <[EMAIL PROTECTED]> 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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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. ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. > 1. 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. > 2. whether to have a tail annotation if implicit, Ditto. It won't aid in ensuring portability of code. > 3. statement vs. expression if explicit, and N/A > 4. whether explicit is required for debug-ability. PTC should not be for improving debug-ability. Jd ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Jon Zeppieri <[EMAIL PROTECTED]> 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. Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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. -Jon ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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". >> 1. 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. >> 2. 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. >> 4. 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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
> 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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. >>> 1. 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. > >>> 2. 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? Jd > >>> 4. 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. > > /be > ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 22/01/2008, Jon Zeppieri <[EMAIL PROTECTED]> 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: 1. 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. 2. 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. Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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). 2. 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 1. 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? 2. 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? /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. Dave Igor Bukanov wrote: > On 21/01/2008, Igor Bukanov <[EMAIL PROTECTED]> 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. > >> From http://www.haskell.org/onlinereport/intro.html : > >> 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 _|_). > > Regards, Igor ___ > Es4-discuss mailing list Es4-discuss@mozilla.org > https://mail.mozilla.org/listinfo/es4-discuss ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008, at 4:05 PM, Brendan Eich wrote: > 2. 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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 22/01/2008, Brendan Eich <[EMAIL PROTECTED]> wrote: > 2. 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). Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
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) 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. Dave ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
> 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) 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. > Thanks. That would work. But I can still see the "average" user being confused when debugging, and not knowing what is going on. Peter ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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? Regards, Maciej ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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?
Regards,
Maciej
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 http://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 http://bugs.ecmascript.org/ticket/
323#comment:10
* Let f be the function-value result of evaluating the callee
portion of
* Let args be the result of evaluating the argument portion of
* 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.
/be
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 http://bugs.ecmascript.org/ticket/323. Again, the ticket is just sitting there, you don't need me transcribing it into this list :-/. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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: http://lambda-the-ultimate.org/node/472#comment-3599 /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 (http://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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008 10:50 PM, Brendan Eich <[EMAIL PROTECTED]> 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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
> > On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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.
--
David "liorean" Andersson
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 http://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. Cheers, Maciej ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
