Maybe someone has already answered this question, but I don't remember it.

DMD 2.054 is able to infer if a template function is pure. Isn't it a good idea to use the same machinery to infer the unmarked functions too? A template may call a second function that's not annotated with 'pure' despite being pure. If the compiler is able to infer the purity of the second function, then both the template and the second function can be pure. This may offer optimization opportunities. Is doing this too much slow?

Bye and thank you,
bearophile

On Mon, 18 Jul 2011 16:01:08 -0400, bearophile <bearophileHUGS@lycos.com> wrote:

> Maybe someone has already answered this question, but I don't remember it.
>
> DMD 2.054 is able to infer if a template function is pure. Isn't it a good idea to use the same machinery to infer the unmarked functions too? A template may call a second function that's not annotated with 'pure' despite being pure. If the compiler is able to infer the purity of the second function, then both the template and the second function can be pure. This may offer optimization opportunities. Is doing this too much slow?

It might not be possible.  For example, if the target function has no public implementation.  This is not the case for templates -- the implementation must be available.

In theory, it's possible for the compiler to mark a function whose source is available as pure, and indeed, most could be.  It would be a nice solution to the issue we have now where so much is not pure.  At some point though, optional may not be what you want.  In fact, you may want the compiler to complain that a function you marked as pure isn't actually pure.  Relying on the compiler to determine purity has drawbacks...

-Steve

On 2011-07-18 13:32, Steven Schveighoffer wrote:
> On Mon, 18 Jul 2011 16:01:08 -0400, bearophile <bearophileHUGS@lycos.com>
> 
> wrote:
> > Maybe someone has already answered this question, but I don't remember it.
> > 
> > DMD 2.054 is able to infer if a template function is pure. Isn't it a good idea to use the same machinery to infer the unmarked functions too? A template may call a second function that's not annotated with 'pure' despite being pure. If the compiler is able to infer the purity of the second function, then both the template and the second function can be pure. This may offer optimization opportunities. Is doing this too much slow?
> 
> It might not be possible. For example, if the target function has no public implementation. This is not the case for templates -- the implementation must be available.
> 
> In theory, it's possible for the compiler to mark a function whose source is available as pure, and indeed, most could be. It would be a nice solution to the issue we have now where so much is not pure. At some point though, optional may not be what you want. In fact, you may want the compiler to complain that a function you marked as pure isn't actually pure. Relying on the compiler to determine purity has drawbacks...

We pretty much _have_ to rely on purity inference for templates, because the only other way is to have multiple versions of the template (one pure and one not), and not only is that highly undesirable, it becomes completely untenable once you add nothrow and @safe into the mix. Normal functions have none of these problems. And if pure were inferred for a function and then it became impure, that could break a _lot_ of code. And even if it didn't, and all of the functions in the chain just silently became impure, it could have negative effects on performance, and you wouldn't have a clue why.

Ideally, we wouldn't need purity inference at all. With templates, we don't have much choice, but it's not needed for normal functions.

- Jonathan M Davis

On Mon, 18 Jul 2011 16:52:41 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On 2011-07-18 13:32, Steven Schveighoffer wrote:
>> On Mon, 18 Jul 2011 16:01:08 -0400, bearophile <bearophileHUGS@lycos.com>
>>
>> wrote:
>> > Maybe someone has already answered this question, but I don't remember
>> > it.
>> >
>> > DMD 2.054 is able to infer if a template function is pure. Isn't it a
>> > good idea to use the same machinery to infer the unmarked functions  
>> too?
>> > A template may call a second function that's not annotated with 'pure'
>> > despite being pure. If the compiler is able to infer the purity of the
>> > second function, then both the template and the second function can be
>> > pure. This may offer optimization opportunities. Is doing this too  
>> much
>> > slow?
>>
>> It might not be possible. For example, if the target function has no
>> public implementation. This is not the case for templates -- the
>> implementation must be available.
>>
>> In theory, it's possible for the compiler to mark a function whose source
>> is available as pure, and indeed, most could be. It would be a nice
>> solution to the issue we have now where so much is not pure. At some
>> point though, optional may not be what you want. In fact, you may want
>> the compiler to complain that a function you marked as pure isn't actually
>> pure. Relying on the compiler to determine purity has drawbacks...
>
> We pretty much _have_ to rely on purity inference for templates, because the
> only other way is to have multiple versions of the template (one pure and one
> not), and not only is that highly undesirable, it becomes completely untenable
> once you add nothrow and @safe into the mix. Normal functions have none of
> these problems. And if pure were inferred for a function and then it became
> impure, that could break a _lot_ of code. And even if it didn't, and all of
> the functions in the chain just silently became impure, it could have negative
> effects on performance, and you wouldn't have a clue why.
>
> Ideally, we wouldn't need purity inference at all. With templates, we don't
> have much choice, but it's not needed for normal functions.

Well, with the relaxed purity rules, we are looking at a very large phobos codebase which could be vastly more pure than it is.  Not only does this mean pure attributes littered everywhere, but someone has to go through and mark 'em all.  And because pure functions cannot call impure functions, you can't just mark ones you *think* should be pure, you have to start at the bottom and move up from there.  It's not trivial work.

It's almost like shared, except we are forced to annotate for "unshared".

I'm not saying pure should be inferred everywhere, I'm just saying, it would be an attractive solution for the current situation.

-Steve

On 2011-07-18 14:01, Steven Schveighoffer wrote:
> On Mon, 18 Jul 2011 16:52:41 -0400, Jonathan M Davis <jmdavisProg@gmx.com>
> 
> wrote:
> > On 2011-07-18 13:32, Steven Schveighoffer wrote:
> >> On Mon, 18 Jul 2011 16:01:08 -0400, bearophile <bearophileHUGS@lycos.com>
> >> 
> >> wrote:
> >> > Maybe someone has already answered this question, but I don't remember it.
> >> > 
> >> > DMD 2.054 is able to infer if a template function is pure. Isn't it a good idea to use the same machinery to infer the unmarked functions
> >> 
> >> too?
> >> 
> >> > A template may call a second function that's not annotated with 'pure' despite being pure. If the compiler is able to infer the purity of the second function, then both the template and the second function can be pure. This may offer optimization opportunities. Is doing this too
> >> 
> >> much
> >> 
> >> > slow?
> >> 
> >> It might not be possible. For example, if the target function has no public implementation. This is not the case for templates -- the implementation must be available.
> >> 
> >> In theory, it's possible for the compiler to mark a function whose
> >> source
> >> is available as pure, and indeed, most could be. It would be a nice
> >> solution to the issue we have now where so much is not pure. At some
> >> point though, optional may not be what you want. In fact, you may want
> >> the compiler to complain that a function you marked as pure isn't
> >> actually
> >> pure. Relying on the compiler to determine purity has drawbacks...
> > 
> > We pretty much _have_ to rely on purity inference for templates, because
> > the
> > only other way is to have multiple versions of the template (one pure
> > and one
> > not), and not only is that highly undesirable, it becomes completely
> > untenable
> > once you add nothrow and @safe into the mix. Normal functions have none
> > of
> > these problems. And if pure were inferred for a function and then it
> > became
> > impure, that could break a _lot_ of code. And even if it didn't, and all
> > of
> > the functions in the chain just silently became impure, it could have
> > negative
> > effects on performance, and you wouldn't have a clue why.
> > 
> > Ideally, we wouldn't need purity inference at all. With templates, we
> > don't
> > have much choice, but it's not needed for normal functions.
> 
> Well, with the relaxed purity rules, we are looking at a very large phobos codebase which could be vastly more pure than it is. Not only does this mean pure attributes littered everywhere, but someone has to go through and mark 'em all. And because pure functions cannot call impure functions, you can't just mark ones you *think* should be pure, you have to start at the bottom and move up from there. It's not trivial work.
> 
> It's almost like shared, except we are forced to annotate for "unshared".
> 
> I'm not saying pure should be inferred everywhere, I'm just saying, it would be an attractive solution for the current situation.

Understandable, but I think that it the long run, it would definitely be a bad decision to infer purity for functions which aren't templated (be it because they themselves are templated or because they're inside of a larger template). It's bad enough that we need to do it with templates, but there's really no good way to do it otherwise.

- Jonathan M Davis

Jonathan M Davis:

> And if pure were inferred for a function and then it became impure, that could break a _lot_ of code.

OK. The restricted idea then is to infer only the purity of functions called by templates, to allow more templates to be pure, and such inferred purity is seen by function templates only.

Example: if a not pure function sqr is called by both a not pure template bar and by a pure function foo, the compiler raises an error in foo, because sqr is not pure, but compiles the pure main because sqr called by bar is seen as pure :-)


int sqr(in int x) {
    return x * x;
}
int foo(in int x) pure { // error, sqr is not tagged pure
    return sqr(x) + sqr(x);
}
int bar(T)(in T x) {
    return sqr(x) * sqr(x);
}
void main() pure {
    bar(1); // OK, sqr can be inferred as pure
}


It looks a bit complex :-)

Bye,
bearophile

On 7/18/2011 7:00 PM, bearophile wrote:
> Jonathan M Davis:
>
>> And if pure were inferred for a function and then it became
>> impure, that could break a _lot_ of code.
>
> OK. The restricted idea then is to infer only the purity of functions called by templates, to allow more templates to be pure, and such inferred purity is seen by function templates only.
>
> Example: if a not pure function sqr is called by both a not pure template bar and by a pure function foo, the compiler raises an error in foo, because sqr is not pure, but compiles the pure main because sqr called by bar is seen as pure :-)
>
>
> int sqr(in int x) {
>      return x * x;
> }
> int foo(in int x) pure { // error, sqr is not tagged pure
>      return sqr(x) + sqr(x);
> }
> int bar(T)(in T x) {
>      return sqr(x) * sqr(x);
> }
> void main() pure {
>      bar(1); // OK, sqr can be inferred as pure
> }
>
>
> It looks a bit complex :-)
>
> Bye,
> bearophile

I thought purity inference only worked one level deep. It would look at each of the functions it calls. If they are all explicitly marked pure, then its pure. I don't believe it analyzes the body of sqr to mark it as pure. You'd still have to mark sqr as pure.

On 2011-07-18 16:02, Johann MacDonagh wrote:
> On 7/18/2011 7:00 PM, bearophile wrote:
> > Jonathan M Davis:
> >> And if pure were inferred for a function and then it became impure, that could break a _lot_ of code.
> > 
> > OK. The restricted idea then is to infer only the purity of functions called by templates, to allow more templates to be pure, and such inferred purity is seen by function templates only.
> > 
> > Example: if a not pure function sqr is called by both a not pure template bar and by a pure function foo, the compiler raises an error in foo, because sqr is not pure, but compiles the pure main because sqr called by bar is seen as pure :-)
> > 
> > 
> > int sqr(in int x) {
> > 
> > return x * x;
> > 
> > }
> > int foo(in int x) pure { // error, sqr is not tagged pure
> > 
> > return sqr(x) + sqr(x);
> > 
> > }
> > int bar(T)(in T x) {
> > 
> > return sqr(x) * sqr(x);
> > 
> > }
> > void main() pure {
> > 
> > bar(1); // OK, sqr can be inferred as pure
> > 
> > }
> > 
> > 
> > It looks a bit complex :-)
> > 
> > Bye,
> > bearophile
> 
> I thought purity inference only worked one level deep. It would look at each of the functions it calls. If they are all explicitly marked pure, then its pure. I don't believe it analyzes the body of sqr to mark it as pure. You'd still have to mark sqr as pure.

I'm not sure how deep it currnently goes, but it definitely _should_ go as deep as the templates go. If it calls an templated functions, then those functions have to be generated before it can use them anyway - let alone know whether they're pure or not. So, if you have 10 levels of 10 template function calls with a normal pure function at the bottom (or a template function at the bottom which doesn't call any other functions and doesn't do anything that a pure function can't do), then all 10 levels should be pure. Whether that works at the moment, I don't know. But if it's only one level, then purity inference doesn't gain us much given how often templated functions call other templated functions.

- Jonathan M Davis

On 7/18/2011 7:43 PM, Jonathan M Davis wrote:
> On 2011-07-18 16:02, Johann MacDonagh wrote:
>> On 7/18/2011 7:00 PM, bearophile wrote:
>>> Jonathan M Davis:
>>>> And if pure were inferred for a function and then it became
>>>> impure, that could break a _lot_ of code.
>>>
>>> OK. The restricted idea then is to infer only the purity of functions
>>> called by templates, to allow more templates to be pure, and such
>>> inferred purity is seen by function templates only.
>>>
>>> Example: if a not pure function sqr is called by both a not pure template
>>> bar and by a pure function foo, the compiler raises an error in foo,
>>> because sqr is not pure, but compiles the pure main because sqr called
>>> by bar is seen as pure :-)
>>>
>>>
>>> int sqr(in int x) {
>>>
>>> return x * x;
>>>
>>> }
>>> int foo(in int x) pure { // error, sqr is not tagged pure
>>>
>>> return sqr(x) + sqr(x);
>>>
>>> }
>>> int bar(T)(in T x) {
>>>
>>> return sqr(x) * sqr(x);
>>>
>>> }
>>> void main() pure {
>>>
>>> bar(1); // OK, sqr can be inferred as pure
>>>
>>> }
>>>
>>>
>>> It looks a bit complex :-)
>>>
>>> Bye,
>>> bearophile
>>
>> I thought purity inference only worked one level deep. It would look at
>> each of the functions it calls. If they are all explicitly marked pure,
>> then its pure. I don't believe it analyzes the body of sqr to mark it as
>> pure. You'd still have to mark sqr as pure.
>
> I'm not sure how deep it currnently goes, but it definitely _should_ go as
> deep as the templates go. If it calls an templated functions, then those
> functions have to be generated before it can use them anyway - let alone know
> whether they're pure or not. So, if you have 10 levels of 10 template function
> calls with a normal pure function at the bottom (or a template function at the
> bottom which doesn't call any other functions and doesn't do anything that a
> pure function can't do), then all 10 levels should be pure. Whether that works
> at the moment, I don't know. But if it's only one level, then purity inference
> doesn't gain us much given how often templated functions call other templated
> functions.
>
> - Jonathan M Davis

Right, I'm saying if you have this:

void something(S)(S s)
{
    somethingElse!S(s);
    callSomething();
}

In this case inference would take a look at everything it calls. When it hits the somethingElse template it must generate that before moving on. That generated template will have inferred purity. The template will then check callSomething and explicitly check its purity. If the generated somethingElse template and callSomething are both pure, then the generated something template is pure in this case.