Re: proper tail calls
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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/24/08, Nathan de Vries [EMAIL PROTECTED] 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. --lars ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 smime.p7s Description: S/MIME cryptographic signature ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
2008/1/24 Nathan de Vries [EMAIL PROTECTED]: 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 [EMAIL PROTECTED] 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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/24/08, Lars T Hansen [EMAIL PROTECTED] 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. ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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). /be On Jan 24, 2008, at 4:26 PM, Nathan de Vries wrote: 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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss --===1938984673==-- ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 smime.p7s Description: S/MIME cryptographic signature ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 23/01/2008, Lars Hansen [EMAIL PROTECTED] 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. Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. Dave 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. 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. 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. ___ 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
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 ;-) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Neil Mix Sent: Tuesday, January 22, 2008 7:46 AM To: Brendan Eich Cc: Peter Hall; Dave Herman; es4-discuss@mozilla.org; Jeff Dyer; Erik Arvidsson Subject: Re: proper tail calls 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 (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. 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. ___ 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 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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
RE: proper tail calls
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. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Neil Mix Sent: Tuesday, January 22, 2008 11:03 AM To: Dave Herman Cc: Peter Hall; Brendan Eich; es4-discuss@mozilla.org; Jeff Dyer; Erik Arvidsson Subject: Re: proper tail calls 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:07 AM, Dave Herman wrote: 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. Dave 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. 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. 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
Re: proper tail calls
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 [EMAIL PROTECTED] 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? -- David liorean Andersson ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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? ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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? ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. --lars ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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). /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/22/08, Steven Johnson [EMAIL PROTECTED] wrote: On 1/22/08 12:14 PM, Lars T Hansen [EMAIL PROTECTED] 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.) --lars ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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. ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
RE: proper tail calls
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Dave Herman Sent: 21. januar 2008 16:58 To: Peter Hall Cc: Brendan Eich; es4-discuss@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) 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. 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) --lars ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
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 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
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 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 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
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 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 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.
/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
Re: proper tail calls
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. -- erik ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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), http://lambda-the-ultimate.org/node/472#comment-3511 which has useful links. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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 http://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? /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 18, 2008 10:49 PM, Brendan Eich [EMAIL PROTECTED] 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 ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: 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
http://bugs.ecmascript.org/ticket/323
and it seems there is a suggestion that the spec will only require
proper tail calls with a goto statement.
That's the ticket's initial proposal, but as you can see opinions
vary. I see two major axes of division:
E/I: explicit or implicit
S/X: statement or expression form
with the valid combinations being:
I,X: implicit, expression form, the original wiki'd proposal;
E,X: lth's proposal in the initial comment of the ticket;
E,S: graydon's proposal in comment 10.
I,S does not make sense. You can read the arguments for and against
in the ticket. Graydon's recent comment includes this text:
If, in order make the presence of an explicit form convenient, we
have to add sugar for it as an additional form of expression-closure
-- goto call-expr() means {goto call-expr();} -- I don't think
it's the end of the world. I do think, at present, we're meandering
aimlessly towards a system that claims to provide a way to make tail
calls, but in which nobody can ever figure out where or when they're
actually getting tail calls. I don't think it'll be useful to ship
such a language.
I think this nicely summarizes the problem with I, while not
finishing off the case for X instead of just S or a slight extension
to S (allowing the body of an expression closure to be a godo
statement: function state1(a,b) goto state2(a*2, b-1); -- saving
braces and using goto instead of return, four chars better). After a
brief lapse into E,S, I'm in favor of E,X: goto as an operator
required to get PTC and throwing an error if stack space must be
consumed, as lth proposed in the original ticket.
Is it not reasonable for
the spec to simply require implementations to have proper tail calls?
The I,X original proposal from the wiki required this. It's
reasonable, maybe, if we can agree on the rules and they are not
too complicated, but the crucial question is about usability, human
factors, avoiding silent bad surprises: will programmers wanting
proper tail calls be surprised when they nest an implicit (built-in
among the primitive types) conversion in a big state machine, and
silently defeat proper tail calls from that particular call site,
leading to explosive stack growth in the worst case?
This concern of course led to the ticket; the principle familiar to
Python folks is EIBTI (E Is Better Than I). Not just for readers
(clarity of intent) but for writers (I want PTC or error here).
Is it not acceptable for the spec to require certain implementation
internal optimizations?
PTC is not an optimization, it's a storage rule. Schemers know to
count on it, and do. For ~12 years, JS hackers have lacked it, on the
other hand. And JS hackers have standard looping statement forms. But
PTC is helpful for state machines, which you do see on the web; you
even see setTimeout(fun, 0) flows to empty the JS stack in order to
avoid overflow. PTC is worthwhile, and we have included it among
approved proposals for a long time. The question remains: explicit or
implicit syntax; if explicit, statement only or operator form?
/be
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
