Re: proper tail calls still out of es4?
Hi Brendan, Thanks for the reply... On Sun, Jul 6, 2008 at 3:52 PM, Brendan Eich <[EMAIL PROTECTED]> wrote: > My belief is that if proper tail calls are to make a come-back, it will be > through implementors leading the way. As discussed in the linked documents > cited above, support by popular implementations on the web would tend to > force a de-facto standard. This might not be evident by the time ES4 is > standardized, but it could be folded into a successor standard. How could one go about campaigning for Spidermonkey to lead the way by including proper tail calls? Peter ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls still out of es4?
On Jul 6, 2008, at 3:14 PM, Peter Michaux wrote: > Hi, > > I'm just curious if there has been any discussion about adding proper > tail calls back into es4 or if it is definitely out for good. Background links: http://wiki.ecmascript.org/doku.php?id=proposals:proper_tail_calls http://wiki.ecmascript.org/doku.php?id=discussion:proper_tail_calls http://bugs.ecmascript.org/ticket/215 http://bugs.ecmascript.org/ticket/323 Since we aren't done and we are implementing before standardizing, it's impossible to say "for good", but our work is easier as spec- writiers, and implementors of prototype specs have it easier too, if there are fewer requirements operating on the syntactic analysis and runtime semantics. My belief is that if proper tail calls are to make a come-back, it will be through implementors leading the way. As discussed in the linked documents cited above, support by popular implementations on the web would tend to force a de-facto standard. This might not be evident by the time ES4 is standardized, but it could be folded into a successor standard. /be ___ 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
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: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
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
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, 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 20:04 +0100, Chris Pine wrote: > It was agreed that implementations would always be free to implement > PTC... Really? That wasn't the impression I got. My understanding is that if PTC isn't a requirement, it should not exist. As a programmer, I don't want to need to keep track of whether which implementations support my programming style. Do we really want "ES4" and "Stackless ES4" (for example)? Peter Michaux put it nicely when he said: > If there are no requirements for proper tail calls then they cannot be > depended upon and are useless. Portability is a huge requirement for me, and if there's a valid reason for leaving PTC out of an implementation history shows that someone will. Cheers, -- Nathan de Vries PS: What's the go with everyone including long lists of CCs? Isn't everyone here on [EMAIL PROTECTED] 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
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
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: > 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: > 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
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
> The confusing traces and debugging views > of the stack (which is not a program history!) can be mitigated. Yes! That's my *only* concern. (And yes, after years of debugging asynchronous callbacks I'm acutely aware of the difference between stack traces and program history. In fact, I got so sick of it I hacked our test suite to store traces at key jump-off points so that I could capture stack from asynchronous callbacks back up to their originating callers. But I digress. :P) > But to your point, I think the party of the first part (the > programmer who wrote code that uses tail calls) must prevail, whether > or not they intended tail calls or expressed them explicitly. Lars > made this point recently: unless we ban implicit PTC even when not > elected by the programmer using explicit syntax, code will come to > depend on PTC and we'll need it implicitly "on" everywhere. All that > remains is the assertion. Oh yes, Lars and Anton have convinced me that requiring explicit PTC is not desirable. As I stated early on, as long as meaningful stack traces are doable with implicit PTC, I'll happily shush. So consider me shushed. ___ 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 Jan 22, 2008, at 11:51 AM, Neil Mix wrote: >> But why won't we feel it, as trace-readers, just as much when the >> PTCs were explicit? This, I don't follow. The programmer and the >> debugger-driver are often very different people, in general skills, >> familiarity with the source at hand, etc. > > We will, but the point is: you (or someone you work with) made the > decision that the benefit was worth the risk. On the www, everyone is my colleague. I'm not kidding (have to talk to management about the quality of hiring lately :-P). > Implicit PTC turns > that choice into an irreversible default. I'm not worried about > those who choose to use it, I'm worried about those who'd like to > choose not to. The program will diverge if someone chooses not to implement PTC, so it's going to be required. The confusing traces and debugging views of the stack (which is not a program history!) can be mitigated. But to your point, I think the party of the first part (the programmer who wrote code that uses tail calls) must prevail, whether or not they intended tail calls or expressed them explicitly. Lars made this point recently: unless we ban implicit PTC even when not elected by the programmer using explicit syntax, code will come to depend on PTC and we'll need it implicitly "on" everywhere. All that remains is the assertion. /be ___ 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
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
On Jan 22, 2008 12:44 PM, Steven Johnson <[EMAIL PROTECTED]> wrote: > > On 1/22/08 12:14 PM, "Lars T Hansen" <[EMAIL PROTECTED]> wrote: > Question: should an implementation be *required* to execute a tail call as a > Proper Tail Call when possible, even if said syntax is not present? (or > merely *permitted* to do so?) If there is no guarantee then the implicit proper tail calls feature is useless to someone writing code for a variety of implementations (eg web browsers.) If there are implicit proper tail calls then I need to know when I can count on them and I will only use them in those situations listed in the ES4 spec. Peter ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
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?)
___
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 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
> Tail call != recursion. Not even indirect recursion. The > point is you may see gaps in the stack where control seems to > flow from f to g, but nothing in tail position in f could > possibly call g, and you wonder what might have intervened. My bad, thinking about the scheme looping special case. Anyways the point remains that just because the implementation was clever and optimized away f's frame, or reused it or whatever doesn't mean a debugger can't remember it and show it as either still being there or as being ghosted out or something. I think the feature is too valuable to rule it out b/c it places constraints on the debugger. And I wouldn't want any constraints to be levied by the language/spec. I would even think it reasonable for implementation to have a policy where you had to turn the VM into interpreter mode to get the whole picture. To back up my point about this feature being important I'll bring up Flex and code generation. A Flex application has this nesting notion where the XML nesting of your Flex components is translated into a chunk of nesting AS3 code for initialization purposes. Thus as its implemented your Flex component nesting is bounded by your available stack space. The ease at which MXML facilitates component nesting means that some day we'll either have to change this to initialize using an explicit heap data structure but maybe if explicit tail call support existed they could keep using it and feel safe to keep on doing it this way. Basically its automatic vs manual memory management and a scripting language shouldn't force people to do manual memory management. My vote is to have an explicit syntax with the optional implicit allowed (encouraged?) caveat. ___ 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
>> 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
> 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
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
> 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: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
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 &
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
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 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 ke
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
> 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
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
>> 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
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 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 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
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 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 8:02 PM, Maciej Stachowiak wrote: > On Jan 21, 2008, at 12:35 PM, Brendan Eich wrote: > >> Conversions (implicit and hardcoded among the >> built-in types representing and wrapping primitives) that might >> defeat PTC may not be evident until runtime, where the result would >> be a TypeError or possibly a new Error subtype. > > Isn't this case (implicit conversion) exactly what motivated the idea > that programmers may not be able to easily tell if a call is in tail > position? Indeed: "ES4 has proper tail calls, but their constraints are sometimes subtle, especially with regard to conversions or type checks inserted at the return point. It may be that the "Explicit Is Better Than Implicit" principle once again finds application here." First paragraph in http://bugs.ecmascript.org/ticket/323. Again, the ticket is just sitting there, you don't need me transcribing it into this list :-/. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008, at 8:12 PM, Maciej Stachowiak wrote:
> On Jan 18, 2008, at 10:49 PM, Brendan Eich wrote:
>
>> "If, in order make the presence of an explicit form convenient, we
>> have to add sugar for it as an additional form of expression-closure
>> -- "goto call-expr()" means "{goto call-expr();} -- I don't think
>> it's the end of the world. I do think, at present, we're meandering
>> aimlessly towards a system that claims to provide a way to make tail
>> calls, but in which nobody can ever figure out where or when they're
>> actually getting tail calls. I don't think it'll be useful to ship
>> such a language."
>
> Is "goto" the only option being considered for how to identify tail
> position?
See http://bugs.ecmascript.org/ticket/323#comment:10 where precedent
from other languages suggests alternatives such as "become" and "jump".
> It seems to me this could easily be confused with what
> "goto" means in languages like C, Pascal or C#.
It might, and at least one JS implementation has supported computed
goto (to support a port of an old Adventure game, IIRC), but never mind.
> "return" might be a
> good choice of syntax if it weren't for the implicit conversion
> problem.
It would, indeed: return and yield would both then be low-precedence
unary operators.
> How about something like "tailcall" or "tailreturn".
Or just "tail f(x, y)", Dave Herman's suggestion.
> Here is another thing I don't understand: if goto must flag runtime
> errors in cases where otherwise implicit type conversion would occur,
> then does that not itself break proper tail recursion (something has
> to hang around to do the typecheck on the actually returned type)? Or
> is the intent that it throws a runtime error before the call if it
> can't statically prove that return types match? Does that mean you can
> never goto an untyped function from one with a declared return type?
From Graydon's comment at http://bugs.ecmascript.org/ticket/
323#comment:10
* Let f be the function-value result of evaluating the callee
portion of
* Let args be the result of evaluating the argument portion of
* Let S be the return-type of f
* Let T be the return-type of the current activation
* Confirm the dynamic typecheck S <* T, or throw TypeError
* Replace the current activation with an activation of
Function.apply(f,args)
So: no, yes, and yes.
The ticket and wiki'ed proposal and discussion pages are worth a
read, or re-read.
/be
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 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 12:35 PM, Brendan Eich wrote: > Conversions (implicit and hardcoded among the > built-in types representing and wrapping primitives) that might > defeat PTC may not be evident until runtime, where the result would > be a TypeError or possibly a new Error subtype. Isn't this case (implicit conversion) exactly what motivated the idea that programmers may not be able to easily tell if a call is in tail position? Regards, Maciej ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
> 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
> 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
On 22/01/2008, Brendan Eich <[EMAIL PROTECTED]> wrote: > 2. The programmer uses "goto f(x)" where f returns T and the call is > in g returning Y, A quality implementation may still implement the tail call in this case as the type conversion does not depend on the activation frame. Yet given such implementation the programmer would not be able to take advantage of that and would be forced to use return f(x) instead of goto f(x). Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008, at 4:05 PM, Brendan Eich wrote: > 2. The programmer uses "goto f(x)" where f returns T and the call is > in g returning Y, and there's a space-accumulating (built-in) > conversion from X to Y. s/T/X/, obviously. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
Comparing ES4 and Haskell is like comparing apples and orangutans. Haskell is a lazy language, where the control flow (and space consumption thereof) are far more complex than in a call-by-value language like JavaScript or Scheme. It's well-known that tail recursion is hard to reason about in Haskell because the accumulation of suspensions consumes space in non-local ways, which means that tail calls can't simply be determined by inspection of the nesting of expressions of a program, but rather by flow-sensitive strictness analyses. So this is a totally irrelevant analogy. As for making it optional, I'll probably repeat this many times: if you make proper tail calls optional, you might as well not put them in the spec at all. If programmers can't rely on them, they can't use them. Dave Igor Bukanov wrote: > On 21/01/2008, Igor Bukanov <[EMAIL PROTECTED]> wrote: >> then I would prefer to make the tail calls an optional optimization >> in the same way as the type checker is optional. > > And if Haskell language specs can leave the issue of tail call > optimization up to implementations, then I do not see why ES4 can not > do the same. > >> From http://www.haskell.org/onlinereport/intro.html : > >> This report defines the syntax for Haskell programs and an informal >> abstract semantics for the meaning of such programs. We leave as >> implementation dependent the ways in which Haskell programs are to >> be manipulated, interpreted, compiled, etc. This includes such >> issues as the nature of programming environments and the error >> messages returned for undefined programs (i.e. programs that >> formally evaluate to _|_). > > Regards, Igor ___ > Es4-discuss mailing list Es4-discuss@mozilla.org > https://mail.mozilla.org/listinfo/es4-discuss ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008, at 3:33 PM, Jeff Dyer wrote: >> But we have accepted the proper tail calls proposal for a long while, >> to serve such currently poorly-served use-cases. We have to evaluate >> the syntax as well as semantics against usability and other criteria >> in light of those use-cases. Portability is an end, but not the only >> end. > > My point is that some of those poorly served use cases have nice > solutions > that might work on some, but not all, implementations without a > definition > of PTCs in ES4. I think we agree about this. Not sure whether you mean some implementations might implement PTC even if the spec does not require it, or something else (some implementations might have big stacks -- but no, that's can't be right). So yeah, if only some (and currently I think the count is zero among popular browsers -- Opera folks please correct me if I am wrong) implementations support PTC, then anyone writing portable code can't rely on PTC working cross-browser. I believe everyone who has spoken up in the committee has favored some kind of PTC, implicit or explicit. But again, we don't specify detailed storage requirements that would improve portability for other use-cases. It's precisely the use-cases for PTC that motivate our concern that PTC be reliably portable. That makes the use-cases for PTC primary in my book, and portability secondary (not more or less important, but dependent on the first condition: that the use-cases are worth the language facility). >> In other words, humans programming in the langauge might benefit from >> explicit syntax, even if compilers and the (fewer, more expert) >> humans who write them can get implicit proper tail calls right. > > Okay, I'll take that up in the bug. Suffice to say here that I > think clarity > and debug-ability are at odds with portability, the greater good. Wait, you were arguing that portability is the only good (not so), and that since it wasn't aided by explicit syntax, explicit syntax should be dropped. Now you're making a false dilemma between portability and explicit syntax for language-user benefits. But explicit syntax does not harm portability, you never made that case (and it's silly to say explicit syntax for tail calls as a normative part of the spec harms portability). 2. whether to have a tail annotation if implicit, >>> >>> Ditto. It won't aid in ensuring portability of code. >> >> That's not the only end; another good to serve here is correctness. > > In practice, correctness is only served if implementations are > forbidden to > implement PTC behavior for any but the sanctioned tail call > syntaxes. And > that is not what is being proposed. Am I mistaken? No, I'm talking about correctness, as in 1. The programmer uses the explicit syntax, let's say "goto f(x)", where the call to f is not in tail position. We would like an error here. With implicit PTC, the programmer fails to get a tail call and the stack may grow, but does QA find out in time? 2. The programmer uses "goto f(x)" where f returns T and the call is in g returning Y, and there's a space-accumulating (built-in) conversion from X to Y. We would like a strict error if this can be detected statically. Without the explicit syntax signalling PTC intent, the implementation will just do the conversion and accumulate stack space. Will QA find out in time? /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 22/01/2008, Jon Zeppieri <[EMAIL PROTECTED]> wrote: > Really, all of our back-and-forth since those messages has been pretty > much off topic. To bring this back to the topic. I do not think an explicit syntax for tail calls is useful for the following reasons: 1. It does not guarantee at the compile time that the call is in PTC position since the type checker is optional in the language. As such it can not be used as an universal static assert. 2. Given that ES4 does not specify a particular space bounds on most of runtime operations, the explicit syntax may mislead a reader about the execution complexity of the code. An implicit PCT at least does not emphasis itself syntactically and, as a consequence, the reader may consider all aspects of the code like GC pressure, operation complexity etc when reasoning about the space and time behavior. Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 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
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 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
> 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 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
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 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 12:35 PM, Brendan Eich wrote: > So the axes of disagreement seem to me to be: We need to agree on the primary purpose of proper tail calls. I say it is portability of code, and that all other concerns do not have enough weight to influence this proposal. > 1. explicit vs. implicit, Since PTC is about portability of code then what matters most is that implementations agree on what a tail call is. If the spec is unambiguous about what a tail call is, then implementations will have little trouble agreeing. Anyway, an explicit marking won't help. > 2. whether to have a tail annotation if implicit, Ditto. It won't aid in ensuring portability of code. > 3. statement vs. expression if explicit, and N/A > 4. whether explicit is required for debug-ability. PTC should not be for improving debug-ability. Jd ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 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 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 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 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 Jan 21, 2008, at 9:59 AM, Erik Arvidsson wrote: > I think we can all agree on that having explicit tail calls at compile > time enforces all runtimes to have proper tail calls? Yes, if we agree on explicit tail call syntax, and if you mean by "at compile time enforces" that explicit tail call syntax used in a non- tail position results in a compile-time error. Just to recap a bit: The standing proposal at http://wiki.ecmascript.org/doku.php? id=proposals:proper_tail_calls (which is not a spec, not bug-fixed against the rest of the proposed language, but still the accepted proposal of long standing) is for implicit proper tail calls. Many still favor this. The ticket at http://bugs.ecmascript.org/ticket/323 proposes explicit syntax, but it is not clear to me that this will be accepted. I think we want something like what Jon Zeppieri proposed in the ticket, an explicit "tail call here or error, please" assertion or annotation by the programmer, useful to readers as well. This is good no matter what the spec says about implicit vs. explicit PTC. In the explicit case of course this assertion is expressed directly by the PTC syntax -- no need for two ways to say the same thing, or for implicit tail calls to be asserted when the programmer could have been explicit in how the call itself was written. Another point of contention is statement vs. expression explicit syntax, but I think it would be wrong to have expression closures, but not to consider the calls to g and h as proper tail calls in: function f(a, b, c) a ? g(b) : h(c); With explicit syntax, we have to argue about the keyword. My enthusiasm for explicit syntax using a "goto" operator is not shared by folks who still see disdain and horror among their colleagues in reaction to this word. Dave Herman wrote me recently that it might as well be spelled "donttouchme" (I was going to guess something unprintable ;-). The concern waldemar raised about debugger-driver confusion due to implicit tail calls was thrashed in that lambda-the-ultimate thread I cited, and elsewhere. I personally don't think it is a decisive argument for explicit syntax, but it adds some weight. So the axes of disagreement seem to me to be: 1. explicit vs. implicit, 2. whether to have a tail annotation if implicit, 3. statement vs. expression if explicit, and 4. whether explicit is required for debug-ability. Your point that IF we agree on explicit syntax for PTCs, THEN conforming implementations must check at compile time is *probably* not controversial, provided the check is purely for tail call syntactic position. Conversions (implicit and hardcoded among the built-in types representing and wrapping primitives) that might defeat PTC may not be evident until runtime, where the result would be a TypeError or possibly a new Error subtype. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 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
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 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
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
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
On 21/01/2008, Jon Zeppieri <[EMAIL PROTECTED]> wrote:
> On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> wrote:
> > let f2;
> >
> > function f(a)
> > {
> > f2 = function() { return a; }
> > goto return g();
> > }
> >
> > function g() {f2 = null; ... }
...
>
> I don't understand your claim. You're claiming that the "frame of f"
> is "referenced through a global variable"? Clearly, f2 is the global
> variable, you're referring to. f2 may be bound to a function value
> that closes over a, which is part of f's activation frame -- or, more
> specifically, part of f's closure environment. But how would this
> prevent the call to g from being a tail call? Are you assuming that a
> would be on the stack? That is not a warranted assumption.
I am saying that even for calls in the tail position an implementation
may not eliminate the parent frame completely as it still may be
exposed via closures. As such the tail call optimization cannot
guarantee that the space complexity of the tail recursion is O(1).
>
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/21/08, Jon Zeppieri <[EMAIL PROTECTED]> wrote:
> On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> wrote:
> >
> > let f2;
> >
> > function f(a)
> > {
> > f2 = function() { return a; }
> > goto return g();
> > }
> >
> > function g() {f2 = null; ... }
To clarify, space is consumed by the evaluation of:
f2 = function() { return a; }
...which constructs (and binds) a closure.
goto return g();
...on the other hand, does not consume space. a is still live, but
it's live as part of f2's closure, not as part of f's activation
frame.
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 1/21/08, Igor Bukanov <[EMAIL PROTECTED]> wrote:
>
> let f2;
>
> function f(a)
> {
> f2 = function() { return a; }
> goto return g();
> }
>
> function g() {f2 = null; ... }
>
> Here in f "return g()" is in tail position yet the frame of f can not
> be eliminated completely since it is referenced through a global
> variable.
I don't understand your claim. You're saying that the "frame of f"
is "referenced through a global variable"? Clearly, f2 is the global
variable, you're referring to. f2 may be bound to a function value
that closes over a, which is part of f's activation frame -- or, more
specifically, part of f's closure environment. But how would this
prevent the call to g from being a tail call? Are you assuming that a
must be on the stack?
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Peter Michaux <[EMAIL PROTECTED]> wrote:
> On Jan 20, 2008 8:01 PM, Brendan Eich <[EMAIL PROTECTED]> wrote:
...
> > Proper tails calls are not an optimization; they certainly do change
> > semantics, insofar as you can't write certain programs without them
> > being guaranteed.
>
> I've been trying to find out how they are not an optimization.
I second that. Consider the following case:
let f2;
function f(a)
{
f2 = function() { return a; }
goto return g();
}
function g() {f2 = null; ... }
Here in f "return g()" is in tail position yet the frame of f can not
be eliminated completely since it is referenced through a global
variable. On the other hand a smart implementation may figure out
that, given the structure of g, there is no leak of the frame and it
can be eliminated completely.
So in reality due to this closure leakage there is no guarantees about
the space complexity unless one restricts the code that can present in
a function with a tail call. As such a tail call can be treated only
as an optimization hint as in general it is not possible to ensure
O(1) in space behavior for calls in the tail positions.
Regards, Igor
___
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008, at 9:08 AM, Peter Michaux wrote: >> Proper tails calls are not an optimization; they certainly do change >> semantics, insofar as you can't write certain programs without them >> being guaranteed. > > I've been trying to find out how they are not an optimization. I > haven't read anyone else that thinks they are not an optimization but > I have read other people refer to them as an optimization. Read more, then :-/. The Scheme and Pre-Scheme histories are interesting (in Pre-Scheme you used GOTO for a tail call -- explicit syntax I favor for ES4). See, for instance, Anton van Straaten's fine comment in the same LtU post I cited: http://lambda-the-ultimate.org/node/472#comment-3568 and especially: http://lambda-the-ultimate.org/node/472#comment-3549 Quote: "The ironic thing is that we're talking about a bug whose presence in the language implementation, and in people's minds, makes it difficult to detect that it is a bug. They don't think it's a bug, because they "know" recursion is unnatural and even dangerous — but the only reason they "know" that, is because their language implementation has a bug which makes it so. It's a recursive bug, which is particularly difficult to detect when one makes a habit of avoiding recursion..." > I think > that from an application programmers point of view they are an > optimization since the same program will run without proper tail calls > if the computer has infinite resources. And if my mother had wheels, she'd be a trolley-car. Meanwhile, back in reality, no computer has infinite resources, and as you pointed out to Igor, making "TCO" an option makes it useless on the web -- browsers have different, or no, stack quotas or redzoning. Semantics are not about the meanings of programs assuming infinite resources. > Following one of those links leads to a wiki and the wiki has the > following page which discusses proper tail calls as an optimization in > the language > > http://c2.com/cgi/wiki?TailCallOptimization Yes, it' s a common TLA but citing one use of it doesn't settle the debate. Please read more. /be ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Mon, Jan 21, 2008 at 8:57 AM, Peter Michaux <[EMAIL PROTECTED]> wrote: > I think Haskell and ES are in different situations as a developer > chooses a Haskel implementation for execution. ES4 code for the web is > almost certainly going to run on multiple ES4 implementations. If > there are no requirements for proper tail calls then they cannot be > depended upon and are useless. As long as all the implementations have the exact same call stack limitation then that holds true. However, I think it is unreasonable to enforce one call stack size fits all. I think we can all agree on that having explicit tail calls at compile time enforces all runtimes to have proper tail calls? -- erik ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 20, 2008 8:01 PM, Brendan Eich <[EMAIL PROTECTED]> wrote: > > On Jan 20, 2008, at 5:22 PM, Erik Arvidsson wrote: > > > My concern with E (or A for that matter) is that it requires > > additional syntax. I'd prefer if we could keep the syntax small. I > > don't think implicit PTC is an issue. It is an optimization that the > > interpreter/compiler should do. What are the problems with I? It > > does not change the semantics of the language. > > Proper tails calls are not an optimization; they certainly do change > semantics, insofar as you can't write certain programs without them > being guaranteed. I've been trying to find out how they are not an optimization. I haven't read anyone else that thinks they are not an optimization but I have read other people refer to them as an optimization. I think that from an application programmers point of view they are an optimization since the same program will run without proper tail calls if the computer has infinite resources. > I'll defer to Dave's 2005 LtU comment (he may have > newer ones he prefers), > > http://lambda-the-ultimate.org/node/472#comment-3511 He only mentions that transforming non tail-call application code into tail-call application code is "a standard optimization technique" in a language that has proper tail calls. He doesn't mention whether or not proper tail calls in the language are to be considered a optimization. > which has useful links. Following one of those links leads to a wiki and the wiki has the following page which discusses proper tail calls as an optimization in the language http://c2.com/cgi/wiki?TailCallOptimization Peter ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On Jan 21, 2008 5:34 AM, Igor Bukanov <[EMAIL PROTECTED]> wrote: > On 21/01/2008, Igor Bukanov <[EMAIL PROTECTED]> wrote: > > then I would prefer to make the tail calls an optional optimization in > > the same way as the type checker is optional. > > And if Haskell language specs can leave the issue of tail call > optimization up to implementations, then I do not see why ES4 can not > do the same. I think Haskell and ES are in different situations as a developer chooses a Haskel implementation for execution. ES4 code for the web is almost certainly going to run on multiple ES4 implementations. If there are no requirements for proper tail calls then they cannot be depended upon and are useless. Peter ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 21/01/2008, Igor Bukanov <[EMAIL PROTECTED]> wrote: > then I would prefer to make the tail calls an optional optimization in > the same way as the type checker is optional. And if Haskell language specs can leave the issue of tail call optimization up to implementations, then I do not see why ES4 can not do the same. >From http://www.haskell.org/onlinereport/intro.html : > This report defines the syntax for Haskell programs and an informal abstract > semantics for the meaning of such programs. We leave as implementation > dependent the ways in which Haskell programs are to be manipulated, > interpreted, compiled, etc. This includes such issues as the nature of > programming environments and the error messages returned for undefined > programs (i.e. programs that formally evaluate to _|_). Regards, Igor ___ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
Re: proper tail calls
On 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 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
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 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
