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
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
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
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
