www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - DIP: Tail call optimization

reply Dietrich Daroch <dietr1ch acm.org> writes:
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
Jul 09 2016
next sibling parent reply A.B <A.B aaaabbbb.sdf.vr> writes:
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...
Jul 09 2016
parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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?
Jul 09 2016
next sibling parent reply ketmar <ketmar ketmar.no-ip.org> writes:
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.
Jul 09 2016
next sibling parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 09 2016
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
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.
Jul 09 2016
parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 10 2016
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 07:30:32 UTC, Dietrich Daroch wrote:
 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.
then TCO should be added to language spec too. for now, compiler is not obliged to implement it. also, many implementations only implement TCO for functions with exactly same args -- is this something that should be speced, or not? we already has one optimization case speced -- NRVO. and it is BAD. adding another implementation detail to the spec will only worsen the situation, i believe.
Jul 10 2016
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Sunday, 10 July 2016 at 07:43:14 UTC, ketmar wrote:
 we already has one optimization case speced -- NRVO. and it is 
 BAD. adding another implementation detail to the spec will only 
 worsen the situation, i believe.
We have other cases cases where optimization is expected but it is poorly speced. However I like the fact that the spec does demand some optimizations because it ensures the quality of a conforming implementation. Yet, TCO in particular it not applicable directly in many cases, and usually needs many transformations before it can be applied. There nothing wrong with guaranteeing that it will be applied in trivial cases. (This should be done by adding a sentence to the spec, not by adding a pargma) However for more complex cases it heavily depends on the optimizer and on the backend! In general you don't want to relay in such optimizations. When in doubt avoid recursion.
Jul 10 2016
prev sibling parent ixid <adamsibson gmail.com> writes:
On Sunday, 10 July 2016 at 06:17:08 UTC, ketmar wrote:
 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.
This is really unacceptablely rude. Step away from the computer and cool off.
Jul 10 2016
prev sibling next sibling parent reply A.B <A.B aaaabbbb.sdf.vr> writes:
On Sunday, 10 July 2016 at 05:55:50 UTC, Dietrich Daroch wrote:
 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?
When the tought is not clear the sentences are messy.
Jul 09 2016
parent reply Seb <seb wilzba.ch> writes:
On Sunday, 10 July 2016 at 06:17:17 UTC, A.B wrote:
 On Sunday, 10 July 2016 at 05:55:50 UTC, Dietrich Daroch wrote:
 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:
 [...]
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?
When the tought is not clear the sentences are messy.
- "That's crap" - "brain-damaged coders" ... guys, please stay friendly, constructive and polite! I thought we are all grown-ups here!
Jul 09 2016
next sibling parent reply A.B <A.B aaaabbbb.sdf.vr> writes:
On Sunday, 10 July 2016 at 06:20:59 UTC, Seb wrote:
 On Sunday, 10 July 2016 at 06:17:17 UTC, A.B wrote:
 On Sunday, 10 July 2016 at 05:55:50 UTC, Dietrich Daroch wrote:
 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:
 [...]
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?
When the tought is not clear the sentences are messy.
- "That's crap" - "brain-damaged coders" ... guys, please stay friendly, constructive and polite! I thought we are all grown-ups here!
Get fucked by yourself asshole ! Your penance is that you'll have to review all the crappy DIPs that will come on GH until your death, now that anyone can post his fantastic idea easily. Hahahahaha.
Jul 09 2016
parent reply Jack Stouffer <jack jackstouffer.com> writes:
On Sunday, 10 July 2016 at 06:29:43 UTC, A.B wrote:
 Get fucked by yourself asshole ! Your penance is that you'll 
 have to review all the crappy DIPs that will come on GH until 
 your death, now that anyone can post his fantastic idea easily.

 Hahahahaha.
Go back to >>>/g/
Jul 09 2016
parent A.B <A.B aaaabbbb.sdf.vr> writes:
On Sunday, 10 July 2016 at 06:47:47 UTC, Jack Stouffer wrote:
 On Sunday, 10 July 2016 at 06:29:43 UTC, A.B wrote:
 Get fucked by yourself asshole ! Your penance is that you'll 
 have to review all the crappy DIPs that will come on GH until 
 your death, now that anyone can post his fantastic idea easily.

 Hahahahaha.
Go back to >>>/g/
what does that (>>>/g/) mean ?
Jul 10 2016
prev sibling parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 06:20:59 UTC, Seb wrote:
 ... guys, please stay friendly, constructive and polite! I 
 thought we are all grown-ups here!
i do. someone who is not able to understand when and how TCO works is clearly brain-damaged. if he isn't, why did he become programmer in the first place? it is clear that he is not able to program.
Jul 09 2016
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 06:37:18 UTC, ketmar wrote:
 On Sunday, 10 July 2016 at 06:20:59 UTC, Seb wrote:
 ... guys, please stay friendly, constructive and polite! I 
 thought we are all grown-ups here!
i do. someone who is not able to understand when and how TCO works is clearly brain-damaged. if he isn't, why did he become programmer in the first place? it is clear that he is not able to program.
note that i didn't said this about OP, in no way. so no personal attacks here.
Jul 09 2016
next sibling parent reply Tofu Ninja <joeyemmons yahoo.com> writes:
On Sunday, 10 July 2016 at 06:39:06 UTC, ketmar wrote:
 On Sunday, 10 July 2016 at 06:37:18 UTC, ketmar wrote:
 On Sunday, 10 July 2016 at 06:20:59 UTC, Seb wrote:
 ... guys, please stay friendly, constructive and polite! I 
 thought we are all grown-ups here!
i do. someone who is not able to understand when and how TCO works is clearly brain-damaged. if he isn't, why did he become programmer in the first place? it is clear that he is not able to program.
note that i didn't said this about OP, in no way. so no personal attacks here.
Your joking right? No personal attacks?
Jul 10 2016
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 09:05:46 UTC, Tofu Ninja wrote:
 Your joking right? No personal attacks?
where do you see personal attack in my words? i'm not saying that OP is dumb, and i'm not saying that his proposal is dumb. but it is *aimed* to dumb people (which doesn't automatically makes it dumb, you know). and i got tired of being "polite", from now on when i'll see dumb people, i'll say that i see dumb people, not "different" or "mentally impaired". as for the topic, i *tried* to explain why i see no value in the proposal. and part of the explanation included referring to "brain-damaged coders". but yeah, this (again) reminded me why i once resigned from NG. i'd probably should do it again, IRC is enough.
Jul 10 2016
parent reply "Smoke" Adams <SA2432 gmail.com> writes:
On Sunday, 10 July 2016 at 09:20:07 UTC, ketmar wrote:
 On Sunday, 10 July 2016 at 09:05:46 UTC, Tofu Ninja wrote:
 Your joking right? No personal attacks?
where do you see personal attack in my words? i'm not saying that OP is dumb, and i'm not saying that his proposal is dumb. but it is *aimed* to dumb people (which doesn't automatically makes it dumb, you know). and i got tired of being "polite", from now on when i'll see dumb people, i'll say that i see dumb people, not "different" or "mentally impaired". as for the topic, i *tried* to explain why i see no value in the proposal. and part of the explanation included referring to "brain-damaged coders". but yeah, this (again) reminded me why i once resigned from NG. i'd probably should do it again, IRC is enough.
Seems like your pretty dumb. You don't capitalize I, which is a basic grammatical rule in the English language. I'm sure you have your dumb logic for it though. Your real problem is that you are an arrogant prick that seems to think the world revolves around your tiny little pathetic uninteresting life. You are not god, not the end all be all, not the shit, not even popular or important. Stop trying to pretend you are and actually try to get along with other people, and accept that not every is as smart as you think you are. Maybe not everyone in the world is a bad ass leet coder as you are, maybe they are a bad ass Tennis player that does coding for fun on the side to expand their understanding of life. What do you do besides code? Are you actually any good at coding BTW? I doubt as good as you think you are. People like you have a very tiny understanding of reality and it shows. Please grow up, quickly. Your life and everyone around you will benefit. It's not about how big you think your balls are, how big they actually are, or if there tennis balls... Grow up, act your age(if your not 12, which you probably are, so act like your 30 then), get with the program, and try to help make everyone's life a bit more enjoyable. If you get your panties in a ruff because someone says something that you think is "dumb", enlighten them nicely... after all, you might just be the one needing enlightenment.
Jul 10 2016
parent ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 10:50:20 UTC, "Smoke" Adams wrote:
 You are not
i am.
Jul 10 2016
prev sibling parent reply ag0aep6g <anonymous example.com> writes:
On 07/10/2016 08:39 AM, ketmar wrote:
 note that i didn't said this about OP, in no way. so no personal attacks
 here.
It's no stretch to assume that the one who proposes the feature would make use of it. You called those who would use it "brain-damaged".
Jul 10 2016
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 09:24:58 UTC, ag0aep6g wrote:
 On 07/10/2016 08:39 AM, ketmar wrote:
 note that i didn't said this about OP, in no way. so no 
 personal attacks
 here.
It's no stretch to assume that the one who proposes the feature would make use of it. You called those who would use it "brain-damaged".
i am not responsible for people's assumptions.
Jul 10 2016
parent reply ag0aep6g <anonymous example.com> writes:
On 07/10/2016 11:30 AM, ketmar wrote:
 On Sunday, 10 July 2016 at 09:24:58 UTC, ag0aep6g wrote:
[...]
 It's no stretch to assume that the one who proposes the feature would
 make use of it. You called those who would use it "brain-damaged".
i am not responsible for people's assumptions.
So when one makes a post here saying that "D is aimed at brain-dead people", we shouldn't take that for an insult. Because, hey, they couldn't have known that we use it, and there's clearly no reason for them to assume so.
Jul 10 2016
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 09:46:24 UTC, ag0aep6g wrote:
 So when one makes a post here saying that "D is aimed at 
 brain-dead people", we shouldn't take that for an insult.
absolutely. but "D is crap" is whole different story.
Jul 10 2016
parent reply ag0aep6g <anonymous example.com> writes:
On 07/10/2016 12:21 PM, ketmar wrote:
 On Sunday, 10 July 2016 at 09:46:24 UTC, ag0aep6g wrote:
 So when one makes a post here saying that "D is aimed at brain-dead
 people", we shouldn't take that for an insult.
absolutely. but "D is crap" is whole different story.
Your quote leaves out the "because" part, which is the interesting part.
Jul 10 2016
parent ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 11:17:17 UTC, ag0aep6g wrote:
 Your quote leaves out the "because" part, which is the 
 interesting part.
because it is irrelevant.
Jul 10 2016
prev sibling parent reply Jack Stouffer <jack jackstouffer.com> writes:
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?
Jul 09 2016
parent Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 09 2016
prev sibling next sibling parent reply Andrew Godfrey <X y.com> writes:
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.
Jul 10 2016
next sibling parent reply Andrew Godfrey <X y.com> writes:
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
Jul 10 2016
parent reply Tofu Ninja <joeyemmons yahoo.com> writes:
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.
Jul 11 2016
parent reply Andrew Godfrey <X y.com> writes:
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.
Jul 11 2016
parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 11 2016
next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
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
Jul 11 2016
parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 11 2016
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Monday, 11 July 2016 at 16:18:47 UTC, Dietrich Daroch wrote:
 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.
I would favour it, but I am not a DMD developer ;-)
 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.
Yes. Although keep in mind that DMD does not have a shared intermediate representation, so each backend probably might have to implement it over a low level SSA which may or may not be suitable. So, if they have to implement 3 different versions of it for DMD, LDC and GDC what are then the chances that this will pass? Contrast this to a language like Whiley which has an intermediate representation geared towards theorem-proving. Would D benefit from a shared intermediate representation suitable for static analysis? Sure. But you probably need more than a single feature-request to get there.
Jul 11 2016
prev sibling parent reply Andrew Godfrey <X y.com> writes:
On Monday, 11 July 2016 at 15:27:54 UTC, Dietrich Daroch wrote:
 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.
Ola addressed the "bounded stack" idea. TCO is hard enough, I'll stick to that: When people say "it should be a pragma", I think they particularly are saying, "it should be ignorable by the compiler". That is a different feature. I think you need to lay out *exactly* what you want it to do - because doing so will raise the questions that need to be answered. I'll take a stab, but this may not be the direction you're pushing in. This is a straw man to illustrate the difficulties I see: * 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. If you additionally want to make it portable, then you need to specify the conditions under which *any valid compiler* must be able to apply the TCO. Also, you need to make the feature generate a compiler error if it is used under other conditions. This all seems rather difficult; at any rate, I don't see any hints in the current proposal about what these rules would be. (Even a rule as simple as "the call must be to the same function" could be tricky.) P.S. You have proposed annotating the function with tco - it seems more like it's the call site that needs to be annotated.
Jul 11 2016
parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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?
Jul 11 2016
parent reply Andrew Godfrey <X y.com> writes:
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).
 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?
I don't know this. (E.g. Are attributes allowed at the beginning of a statement?)
Jul 11 2016
parent Dietrich Daroch <dietr1ch acm.org> writes:
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).
Jul 11 2016
prev sibling parent Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 10 2016
prev sibling next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
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.
Jul 10 2016
next sibling parent ketmar <ketmar ketmar.no-ip.org> writes:
On Sunday, 10 July 2016 at 16:52:09 UTC, Ola Fosheim Grøstad 
wrote:
  tco does not bring any guarantees to the caller, so you might 
 as well annotate the call-site with some compiler specific 
 feature.
actually, annotating the call itself seems to have alot more sense judging from described OP inspiration for the feature.
Jul 10 2016
prev sibling parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 10 2016
next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
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...
Jul 10 2016
parent reply Dietrich Daroch <dietr1ch acm.org> writes:
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).
Jul 10 2016
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 10 July 2016 at 17:32:32 UTC, Dietrich Daroch wrote:
 It might be interesting to have proof that the stack is bounded 
 (and won't overflow).
Yes, a stack depth guarantee would be useful for D fibers.
Jul 10 2016
prev sibling parent qznc <qznc web.de> writes:
On Sunday, 10 July 2016 at 17:10:32 UTC, Dietrich Daroch wrote:
 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.
You are thinking about recursive functions only, but actually a "tail call" has nothing to do with recursion. Example: int foo() { return 42; } int bar() { return foo(); } There is no recursion, but a tail call in bar and you may want the the compiler to optimize it. If you want to turn recursive functions into loops, then you should change to name imho. Maybe stackbounded. It could be a function property, if you want recursions of more than one function to be bounded wrt stack space. You could then require that tco functions can only call other tco functions. Example: tco int foo(int x) { if (x < 42) return x; else return bar(x-1); } tco int bar(int x) { if (x < 41) return x; else return foo(x-5); } Also, you might want to compiler switch to disable to optimization for debugging. TCO may be confusing, when you run your in a debugger. Overall, this DIP is not as trivial as it looks. I would like to see a more convincing use case/example as a justification.
Jul 11 2016
prev sibling next sibling parent reply Dicebot <public dicebot.lv> writes:
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
In the future I'd recommend to delay announcing DIP until it get to the point of being merged into the queue (I'd do it myself at that point). Right now there are quite some boring technical details to be fleshed out before it becomes a complete proposal - asking for community feedback is likely to be time-inefficient. And sorry for some of the inadequate responses you got here. D language authors don't want to enforce any code of conduct or moderation in the newsgroup which means certain personas have to be simply ignored. In the end only thing that should matter is a good technical document to be merged into the queue.
Jul 11 2016
parent ixid <adamsibson hotmail.com> writes:
On Monday, 11 July 2016 at 11:19:59 UTC, Dicebot wrote:
 D language authors don't want to enforce any code of conduct or 
 moderation in the newsgroup which means certain personas have 
 to be simply ignored.
This is not a policy that will scale well. Ketmar's behaviour was badly out of line. People need to save the scathing pseudo-Linus stuff for the inner-circle rather than new comers.
Jul 12 2016
prev sibling next sibling parent reply Basile B. <b2.temp gmx.com> writes:
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
Oh no, another consequence of the wilzaback. He has announced everywhere that it's possible to make DIPs on github...what a surpise to see that. So...Dietrich, do you use D a bit at least ? Or do you come because you read r/programming or hackernews ?
Jul 11 2016
parent Seb <seb wilzba.ch> writes:
On Monday, 11 July 2016 at 12:29:33 UTC, Basile 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
Oh no, another consequence of the wilzaback. He has announced everywhere that it's possible to make DIPs on github...what a surpise to see that.
I am happy to learn why posting the announcement to reddit was a mistake. The reception was entirely positive and as Dicebot pointed out, having a formal process about language changes is a must-have criteria for many companies and thus a blocker for further adaption of D. On the contrary I think it was a wake-up call for people being frustrated with some deficits of D. Moreover I am not sure why you keep misspelling my lastname. If eight letter are to difficult to memorize for you, you might want to stop complaining about deficit's of other people.
 So...Dietrich, do you use D a bit at least ? Or do you come 
 because you read r/programming or hackernews ?
Did you take the time to look at the DIP before making your offenses? Dietrich has already published D modules on Github which you would have seen if you be generally interested and not trolling. As other people already have stated the DIP is not trivial and the only thing that was sub-optimal was it's announcement in News before being fleshed out, but to be fair Dietrich just followed the new DIP process protocol, which still needs fine-tuning in its details. However without motivated alpha warriors like Dietrich such fine-tuning can't happen, so you should be more thankful to him. Dietrich: Don't let yourself distract by trolls. Keep on improving your DIP and making it great & convincing!
Jul 11 2016
prev sibling next sibling parent bachmeier <no spam.net> writes:
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
Would something like Clojure's recur and trampoline do what you want? http://www.clojure.org/about/functional_programming#_recursive_looping A number of Common Lisp programmers like to use those functions because TCO is then guaranteed, and unlike Common Lisp where you don't know for sure what will happen, it is explicit.
Jul 11 2016
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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.
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. It was a big road block for me when I tried to implement threaded-code interpreter, because it will stack overflow in debug mode.
 The proposal it's ready for merge on the new [DIPs 
 repo](https://github.com/dlang/DIPs/pull/6)

 --
 Dietrich
Jul 12 2016
parent Dietrich Daroch <dietr1ch acm.org> writes:
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.
Jul 13 2016