Re: DIP: Tail call optimization
On Tuesday, 12 July 2016 at 10:46:01 UTC, Dmitry Olshansky wrote: On Sunday, 10 July 2016 at 05:03:46 UTC, Dietrich Daroch wrote: Hi everyone (= I've just added a new proposal to add a new attribute to ensure TCO is applied. [...] In contrast to what many folks expect, TCO is affecting program semantics in a way that changes stack overflow to normal execution. Therefore it's not an optimization but part of semantics, and there should be a way to mark a call as a tail-call in any optimization level. Yes, it's not a tiny detail that improves performance a bit, but it decides wheter the built binary works or not. Also, some people are against breakage, but having a correctly built binary that may surprise you with a stack overflow when ported is not something I would call real portability.
Re: DIP: Tail call optimization
On Tuesday, 12 July 2016 at 01:42:13 UTC, Andrew Godfrey wrote: On Monday, 11 July 2016 at 17:31:23 UTC, Dietrich Daroch wrote: On Monday, 11 July 2016 at 16:27:38 UTC, Andrew Godfrey wrote: [...] * It must not be ignorable by the compiler. * It must generate an error if that compiler would be unable to do the TCO. Otherwise, the compiler *may* (not "must") apply the TCO, unless compiled under (some optimization level, please specify), in which case it *must* apply TCO. One difficulty with this is the words "that compiler". I.e. other compilers are free to be unable to make the TCO. This means that by using this feature, you have made your code non-portable. I think that noticing problems while porting it it's better than having it crash unexpectedly as it would currently happen. Sure, non-portability that causes a guaranteed compiler error, is better than other kinds of non-portability. But it's still non-portable. That is distasteful enough that you probably need to make a more compelling case; factorial is a "toy" function that's not enough - on its own - to justify adding a feature. I personally feel like it is a neat idea, and it may enable some programming styles that I'm not familiar with so I can't say they definitively they have no value. The reason I'm not familiar with them could be that I've never had this feature in a language I've used a lot. So there could be something here, BUT I also think it would need to be a portable feature, which implies much more rigorous rules that all compilers would have to follow. (They could still do TCO for more complicated situations, but those wouldn't interact with this feature; to make use of this feature you'd have to conform to the more rigorous rules). I've thought about using pragmas and they would allow for an easier implementation if ignored pragmas raise warnings (and errors with strict flags) when a pragma was ignored. Under that setup, people who need the errors can enable the flags, while people who doesn't care about this can just ignore/disable the warnings and keep their programs without need for rewrite. Also, using pragmas requires no change on the grammar, nor adding new attributes that most people really dislike (I still don't get why, probably the text editors should take care to make them less distracting or even hiding them).
Re: DIP: Tail call optimization
On Monday, 11 July 2016 at 16:27:38 UTC, Andrew Godfrey wrote: [...] * It must not be ignorable by the compiler. * It must generate an error if that compiler would be unable to do the TCO. Otherwise, the compiler *may* (not "must") apply the TCO, unless compiled under (some optimization level, please specify), in which case it *must* apply TCO. One difficulty with this is the words "that compiler". I.e. other compilers are free to be unable to make the TCO. This means that by using this feature, you have made your code non-portable. I think that noticing problems while porting it it's better than having it crash unexpectedly as it would currently happen. P.S. You have proposed annotating the function with @tco - it seems more like it's the call site that needs to be annotated. I'm not sure about how to do annotations on the call site. Would a new keyword be required?
Re: DIP: Tail call optimization
On Monday, 11 July 2016 at 15:48:08 UTC, Ola Fosheim Grøstad wrote: On Monday, 11 July 2016 at 15:27:54 UTC, Dietrich Daroch wrote: I've been thinking about changing @tco for @boundedStack, as it'll really reflect guarantees on functions while implicitly asking for TCO on functions that require it. But the fact that most functions should be marked as @boundedStack is something that bothers me. Just keep in mind that a @tco constraint is much easier to implement than @boundedStack. I don't do tail calls much, but I think you have the right idea for a system level language: specify the constraints you want to hold rather than explicitly laying out everything manually. That's what I expect from a modern system level language. I have previously argued in favour of something similar like @boundedStack, but there is quite a bit of resistance against (and lack of interest in) solid static analysis in the D community. You probably will save yourself some trouble by reading one of the numerous threads touching on stack handling in D. Here is one: http://forum.dlang.org/post/logpgo$2k1d$1...@digitalmars.com Previous discussion seems to favour @unboundedStack as it can become a requirement to go beyond the stack-size-safe operations effectibly tracking where stack overflow may happen and encourage detailed review of those functions. Walter's concern is that a great amount of the D runtime library would make this unpractical. Maybe another attribute to promise bounded stack without a proof might be required to make the idea viable. I really think that this kinds of proofs are somewhat natural in D, as it follows ideas like contracts, and safe/trusted attributes.
Re: DIP: Tail call optimization
On Monday, 11 July 2016 at 14:36:22 UTC, Andrew Godfrey wrote: On Monday, 11 July 2016 at 10:25:36 UTC, Tofu Ninja wrote: On Sunday, 10 July 2016 at 13:15:38 UTC, Andrew Godfrey wrote: Btw here's a thread from 2014 that touches on the idea of a "tailrec" annotation. At the time, Walter viewed the optimization as the compiler's business and not something he'd elevate to a language feature: http://forum.dlang.org/post/lqp6pu$1kkv$1...@digitalmars.com I find it odd that something like tail recursions that actually makes certain things possible that wouldn't be otherwise is seen as only an optimization, when things like inlining which really is only an optimization is seen as important enough to have a pragma. I agree. Maybe Walter has reconsidered since then. He did also say, though, that he thinks D supports enough different programming styles already. Would you be satisfied with a pragma? I'd intuited (but could be wrong) that the focus of your proposal was to get a compiler error if someone makes a change to a recursive function, that causes the compiler to be unable to apply the TCO optimization. If that is your focus, it has heavy implications and the feature can't just be a pragma. Pragma does not seem enough, at least current pragmas can be ignored by the compilers (http://dlang.org/spec/pragma.html#predefined-pragmas), but if it's required for tco it can make it. I've been thinking about changing @tco for @boundedStack, as it'll really reflect guarantees on functions while implicitly asking for TCO on functions that require it. But the fact that most functions should be marked as @boundedStack is something that bothers me. The complement, @unboundedStack, might be better, as it would explicitly mark the functions that might cause stack overflows so they drag required attention and would also force the compiler to do TCO where required. Focusing on stack size, rather than directly on TCO might even allow to guarantee that many D programs do not crash due to a stack overflow, which is a nice guarantee that not many languages, allow to express. I'd like thoughts on this change of perspective. BTW, I'm glad that discussion has arised, as it can only make the propossal better.
Re: DIP: Tail call optimization
On Sunday, 10 July 2016 at 17:16:10 UTC, Ola Fosheim Grøstad wrote: On Sunday, 10 July 2016 at 17:10:32 UTC, Dietrich Daroch wrote: Annotating every callsite seems uncomfortable, being able to perform TCO is a property of the function and not something that might look call-site dependant. You only need to annotate the location where the function calls itself. The function might want some recursive calls to work without tail recursion restrictions and at the same time use tail recursion at the end. Or do you mean that this should prevent all kinds of recursion? That is a quite demanding analysis. For instance, the function could get itself passed in as a parameter... My bad, I misunderstood your point. Annotating recursive calls seems more flexible. Now the question is how should they be annotated? pragma is verbose, but avoids adding keywords. I think a constant stack size annotation would still make sense, but might not promise that stack overflows are not possible if a lot of local data is used and a big, but constant numbers of calls are made. It might be interesting to have proof that the stack is bounded (and won't overflow).
Re: DIP: Tail call optimization
On Sunday, 10 July 2016 at 16:52:09 UTC, Ola Fosheim Grøstad wrote: On Sunday, 10 July 2016 at 05:03:46 UTC, Dietrich Daroch wrote: Hi everyone (= I've just added a new proposal to add a new attribute to ensure TCO is applied. The proposal is really simple, but I'm clueless on how to implement it and also interested on getting feedback on it. Why should it be part of the function prototype? @nogc makes sense, because it is a guarantee for the caller. @tco does not bring any guarantees to the caller, so you might as well annotate the call-site with some compiler specific feature. Annotating every callsite seems uncomfortable, being able to perform TCO is a property of the function and not something that might look call-site dependant. Ok, I see as why it can be useless for the caller, maybe this should morph into a more general constant stack size growth annotation, but I don't see uses other than enforcing TCO.
Re: DIP: Tail call optimization
On Sunday, 10 July 2016 at 12:01:54 UTC, Andrew Godfrey wrote: On Sunday, 10 July 2016 at 05:03:46 UTC, Dietrich Daroch wrote: Hi everyone (= I've just added a new proposal to add a new attribute to ensure TCO is applied. The proposal is really simple, but I'm clueless on how to implement it and also interested on getting feedback on it. The proposal it's ready for merge on the new [DIPs repo](https://github.com/dlang/DIPs/pull/6) -- Dietrich I'll chime in to give a counterpoint to the ... I'll say "immature" discussion this generated. Just my opinion: Yes, an attribute to express something you expect the compiler to do, has value. (Clearly some people on here don't have experience with a codebase that is maintained by thousands of people). Even if compilers aren't required to implement TCO, it could work (compilers which didn't, would always give an error if you used the attribute). But it would then feel weird to me to use this attribute, knowing that some compilers would pass it and some would fail it. And compilers which always fail it, would feel pressure to do better. Whether this is good depends on your outlook. D does think of itself as "multi-paradigm", so maybe it should push on this. Personally I could see myself making use of this, but not being very sad if it didn't happen. I do prefer your more verbose proposals over "@tco" - a short abbreviation doesn't feel appropriate. If you look at it as trying to make the build fail, then it's definitely weird, but I think the point is to be able to state your expectations and get feedback from the compiler on those, the same as we already do with static typing. I feel the same about the multi-paradigm thing, D supports functional programming, so it definitely needs to ensure executions are efficient for people coming from functional languages. Probably recursion is more natural to them than manually unrolling to avoid a problem that did not existed in their previous language. I personally prefeer longer names, but I felt that @tco followed @nogc. We should consider what other languages have this kind of annotation to get a reasonable name for newcomers. Scala has @tailrec and it seeks the same goal as this DIP, finding wrong assumptions and seeking to ensure having a bounded call stack.
Re: DIP: Tail call optimization
On Sunday, 10 July 2016 at 06:59:21 UTC, ketmar wrote: On Sunday, 10 July 2016 at 06:44:22 UTC, Dietrich Daroch wrote: Yes, there is no cure for poor skills, but the point is to prevent the need to avoid recursion to ensure there are no stack overflows. It seems reasonable considering D targets systems programming. i see "system programmer" as someone who is able to understand when TCO is in effect without additional attribute noise. and for others it just doesn't matter -- as they probably is using a library written by "system programmer" anyway, and won't dive into code. ;-) sorry, it is really just a noise, like "@nogc". compiler does a fairly good work on TCO already, and adding another attribute will just make code messier. it is already @too @many @attributes @in @D. If attributes look messy, pragma can be used. It may look as an addition with little gain, but one of the reasons of compiling is to prevent runtime errors as early as possible and this seeks exactly that.
Re: DIP: Tail call optimization
On Sunday, 10 July 2016 at 06:17:08 UTC, ketmar wrote: On Sunday, 10 July 2016 at 05:55:50 UTC, Dietrich Daroch wrote: Yes, it probably does TCO. The problem is what if you think it does and it cannot do it because of a misunderstanding on when it can be applied or a bug? there can't be any "misunderstanding" from compiler side. either it is a leaf return, or not -- it is as easy as that. what your DIP is aimed for is brain-damaged coders who are not able to understand how programs work (and why "scope(exit)" may prevent TCO). it won't help anyone. sorry. Yes, there is no cure for poor skills, but the point is to prevent the need to avoid recursion to ensure there are no stack overflows. It seems reasonable considering D targets systems programming.
Re: DIP: Tail call optimization
On Sunday, 10 July 2016 at 06:18:41 UTC, Jack Stouffer wrote: On Sunday, 10 July 2016 at 05:55:50 UTC, Dietrich Daroch wrote: Yes, it probably does TCO. The problem is what if you think it does and it cannot do it because of a misunderstanding on when it can be applied or a bug? Then file a bug report? Not a bug on the compiler, but on the function you expect to be tail recursive.
Re: DIP: Tail call optimization
On Sunday, 10 July 2016 at 05:24:49 UTC, A.B wrote: On Sunday, 10 July 2016 at 05:03:46 UTC, Dietrich Daroch wrote: Hi everyone (= I've just added a new proposal to add a new attribute to ensure TCO is applied. The proposal is really simple, but I'm clueless on how to implement it and also interested on getting feedback on it. The proposal it's ready for merge on the new [DIPs repo](https://github.com/dlang/DIPs/pull/6) -- Dietrich That's crap...I disassemble DMD output some time to time. It already does TCO. Definitively a lol day... Yes, it probably does TCO. The problem is what if you think it does and it cannot do it because of a misunderstanding on when it can be applied or a bug?
DIP: Tail call optimization
Hi everyone (= I've just added a new proposal to add a new attribute to ensure TCO is applied. The proposal is really simple, but I'm clueless on how to implement it and also interested on getting feedback on it. The proposal it's ready for merge on the new [DIPs repo](https://github.com/dlang/DIPs/pull/6) -- Dietrich
