www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Infer purity of functions too?

reply bearophile <bearophileHUGS lycos.com> writes:
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
Jul 18 2011
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Jul 18 2011
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Jul 18 2011
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Jul 18 2011
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Jul 18 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Jul 18 2011
parent reply Johann MacDonagh <johann.macdonagh.no spam.gmail.com> writes:
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.
Jul 18 2011
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Jul 18 2011
parent Johann MacDonagh <johann.macdonagh.no spam.gmail.com> writes:
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.
Jul 18 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
 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
:-)


This seems quite useful for delegates given to higher order functions:

int spam(in int x) pure { return x * 3; }
auto squares = map!((int x){ return spam(x) * x; })(iota(10));

With this idea squares is usable in a pure function too, because the map
template infers the given delegate as pure.

Otherwise you need to write:

int spam(in int x) pure { return x * 3; }
auto squares = map!((int x) pure { return spam(x) * x; })(iota(10));

Bye,
bearophile
Jul 18 2011
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On 2011-07-18 16:07, bearophile wrote:

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


 
 This seems quite useful for delegates given to higher order functions:
 
 int spam(in int x) pure { return x * 3; }
 auto squares = map!((int x){ return spam(x) * x; })(iota(10));
 
 With this idea squares is usable in a pure function too, because the map
 template infers the given delegate as pure.
 
 Otherwise you need to write:
 
 int spam(in int x) pure { return x * 3; }
 auto squares = map!((int x) pure { return spam(x) * x; })(iota(10));


I believe that there is some level of purity inference with delegates, but I 
don't know what the situation with that is exactly.

- Jonathan M Davis
Jul 18 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 I believe that there is some level of purity inference with delegates, but I 
 don't know what the situation with that is exactly.


I didn't know/remember this, but it seems you are right, delegates too seem to
receive purity inference. This has one downside too, this innocent-looking
program doesn't compile:


import std.math;
void main() {
    auto funcs = [(int x){return x; },
                  (int x){return abs(x); }];
}


The error, DMD 2.054:

test.d(4): Error: incompatible types for ((__dgliteral1) ? (__dgliteral2)):
'int delegate(int x) pure nothrow' and 'int delegate(int x) nothrow'

How to solve this specific problem: I think abs() can be pure.

An example of a bit more general class of problems:

import std.math;
void main() {
    auto funcs = [&sin, &tan];
}


test.d(3): Error: incompatible types for ((& sin) ? (& tan)): 'real
function(real x) pure nothrow  safe' and 'real function(real x) pure nothrow
 trusted'

To solve this more generic class of problems the compiler has to give to the
funcs array a common type (where possible), here int delegate(int x) pure
nothrow[] is able to contain both kinds of delegates, and cast all the array
delegates to the common type (I have a bug report about this in Bugzilla).

Bye,
bearophile
Jul 20 2011
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On 2011-07-20 17:01, bearophile wrote:

 Jonathan M Davis:

 I believe that there is some level of purity inference with delegates,
 but I don't know what the situation with that is exactly.




I only know because when Walter initially made the purity inference changes, 
the commit mentioned delegates, and I had to ask whether it included templated 
functions. There's every possibility though that it needs some ironing out (or 
that other language features need some ironing) out for it to work in some 
cases though (as you appear to be running into).

- Jonathan M Davis
Jul 20 2011
prev sibling parent Mafi <mafi example.org> writes:
Am 21.07.2011 02:01, schrieb bearophile:

 Jonathan M Davis:


 I believe that there is some level of purity inference with delegates, but I
 don't know what the situation with that is exactly.


 I didn't know/remember this, but it seems you are right, delegates too seem to
receive purity inference. This has one downside too, this innocent-looking
program doesn't compile:


 import std.math;
 void main() {
      auto funcs = [(int x){return x; },
                    (int x){return abs(x); }];
 }


 The error, DMD 2.054:

 test.d(4): Error: incompatible types for ((__dgliteral1) ? (__dgliteral2)):
'int delegate(int x) pure nothrow' and 'int delegate(int x) nothrow'

 How to solve this specific problem: I think abs() can be pure.

 An example of a bit more general class of problems:

 import std.math;
 void main() {
      auto funcs = [&sin,&tan];
 }


 test.d(3): Error: incompatible types for ((&  sin) ? (&  tan)): 'real
function(real x) pure nothrow  safe' and 'real function(real x) pure nothrow
 trusted'

 To solve this more generic class of problems the compiler has to give to the
funcs array a common type (where possible), here int delegate(int x) pure
nothrow[] is able to contain both kinds of delegates, and cast all the array
delegates to the common type (I have a bug report about this in Bugzilla).

 Bye,
 bearophile


I would say the common type is int delegate(int) pure nothrow  trustd .
Jul 21 2011