www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Most basic nothrow, pure, safe functions?

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
In a recent (well, recently pulled anyway) pull request that Monarch Dodra  
brought up, we debated what should be considered nothrow in the depths of  
druntime.

I think we all agree that there are some things that the compiler simply  
cannot prove are nothrow, but to be able to write useful nothrow code, we  
have to paste nothrow on there anyway.

It got me thinking, we really should determine exactly at what level  
nothrow, pure, and  safe should be "overridden" inside druntime, and apply  
those low-level attributes. Then everything above them can be checked by  
the compiler.

In the case of the recent pull,  
https://github.com/D-Programming-Language/druntime/pull/553,  
assumeSafeAppend was the culprit. The function uses the heap's metadata to  
determine the exact block that a slice points at, and adjusts the "used"  
field stored as part of that appendable block. However, it calls some  
monitor enter and monitor exit functions that are not marked nothrow, due  
to synchronizing on a lock.

We all agreed that nothing that assumeSafeAppend did should really throw,  
and so the pull just used c linkage to "add" nothrow to an otherwise  
unmarked function. But that solution isn't very good. At some point, the  
function *could* throw (I hope not), and then the forced nothrow will  
create silent bugs.

It would be better if we could mark the lowest level functions possible  
nothrow, and figure out which ones we had to "force". Same goes for pure  
and  safe.

This is not exactly a proposal, but an idea that we should consider at  
some point to do this analysis. I don't think it will be very difficult,  
but probably tedious.

-Steve
Mar 18 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Steven Schveighoffer:


 But that solution isn't very good. At some point, the function 
 *could* throw (I hope not), and then the forced nothrow will 
 create silent bugs.


Walter has recently proposed optimizations for nothrow functions 
(like this: https://d.puremagic.com/issues/show_bug.cgi?id=12384 
). If nothrow is circumvented and the function throws, the 
program goes into undefined behavour at best. So I agree that 
those annotations should start from the ground up.

Bye,
bearophile
Mar 18 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/18/2014 4:20 PM, Steven Schveighoffer wrote:

 In a recent (well, recently pulled anyway) pull request that Monarch Dodra
 brought up, we debated what should be considered nothrow in the depths of
druntime.


There's a lot of low hanging nothrow fruit in druntime that doesn't need 
analysis, it just needs to get done:

https://d.puremagic.com/issues/show_bug.cgi?id=12389
Mar 18 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 18 Mar 2014 19:48:45 -0400, Walter Bright  
<newshound2 digitalmars.com> wrote:


 On 3/18/2014 4:20 PM, Steven Schveighoffer wrote:

 In a recent (well, recently pulled anyway) pull request that Monarch  
 Dodra
 brought up, we debated what should be considered nothrow in the depths  
 of druntime.


 There's a lot of low hanging nothrow fruit in druntime that doesn't need  
 analysis, it just needs to get done:

 https://d.puremagic.com/issues/show_bug.cgi?id=12389


Can we mark _d_monitorenter and _d_monitorexit nothrow and have the  
compiler see that when using synchronized? This was the hurdle we couldn't  
overcome in the referenced pull request.

Should those be marked nothrow? What about pure and  safe?

-Steve
Mar 18 2014
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/18/2014 4:56 PM, Steven Schveighoffer wrote:

 Can we mark _d_monitorenter and _d_monitorexit nothrow and have the compiler
see
 that when using synchronized? This was the hurdle we couldn't overcome in the
 referenced pull request.

 Should those be marked nothrow? What about pure and  safe?


Good question. I don't have an answer at the moment.
Mar 18 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/18/2014 5:49 PM, Walter Bright wrote:

 On 3/18/2014 4:56 PM, Steven Schveighoffer wrote:

 Can we mark _d_monitorenter and _d_monitorexit nothrow and have the compiler
see
 that when using synchronized? This was the hurdle we couldn't overcome in the
 referenced pull request.

 Should those be marked nothrow? What about pure and  safe?


 Good question. I don't have an answer at the moment.


I'm pretty sure they can't be pure. After all, monitors affect global state,
can 
result in deadlocks, etc.
Mar 20 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 20 Mar 2014 17:32:01 -0400, Walter Bright  
<newshound2 digitalmars.com> wrote:


 On 3/18/2014 5:49 PM, Walter Bright wrote:

 On 3/18/2014 4:56 PM, Steven Schveighoffer wrote:

 Can we mark _d_monitorenter and _d_monitorexit nothrow and have the  
 compiler see
 that when using synchronized? This was the hurdle we couldn't overcome  
 in the
 referenced pull request.

 Should those be marked nothrow? What about pure and  safe?


 Good question. I don't have an answer at the moment.


 I'm pretty sure they can't be pure. After all, monitors affect global  
 state, can result in deadlocks, etc.


How do they affect global state?

Resulting in deadlocks does not make them impure. This is also a pure  
function:

pure int foo()
{
    while(1) {}
    return 0;
}

Pure doesn't mean "bug free".

-Steve
Mar 20 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Steven Schveighoffer:


 This is also a pure function:

 pure int foo()
 {
    while(1) {}
    return 0;
 }

 Pure doesn't mean "bug free".


Thankfully the D compiler catches the bug :-)

test.d(3,4): Warning: statement is not reachable

Bye,
bearophile
Mar 20 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 20 Mar 2014 21:44:38 -0400, bearophile <bearophileHUGS lycos.com>  
wrote:


 Steven Schveighoffer:


 This is also a pure function:

 pure int foo()
 {
    while(1) {}
    return 0;
 }

 Pure doesn't mean "bug free".


 Thankfully the D compiler catches the bug :-)

 test.d(3,4): Warning: statement is not reachable


I can make it not catch that error, but that is not the bug. The bug is  
that it never returns, effectively deadlocking. The sample is  
intentionally short to demonstrate my point, I (obviously) didn't try to  
compile it.

-Steve
Mar 20 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/20/14, 6:52 PM, Steven Schveighoffer wrote:

 On Thu, 20 Mar 2014 21:44:38 -0400, bearophile
 <bearophileHUGS lycos.com> wrote:


 Steven Schveighoffer:


 This is also a pure function:

 pure int foo()
 {
    while(1) {}
    return 0;
 }

 Pure doesn't mean "bug free".


 Thankfully the D compiler catches the bug :-)

 test.d(3,4): Warning: statement is not reachable


 I can make it not catch that error, but that is not the bug. The bug is
 that it never returns, effectively deadlocking. The sample is
 intentionally short to demonstrate my point, I (obviously) didn't try to
 compile it.

 -Steve


My dream: pure  safe functions never cause deadlock.

Andrei
Mar 20 2014
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/20/2014 6:40 PM, Steven Schveighoffer wrote:

 How do they affect global state?


Mutexes implicitly share state. It's the reason they exist. They can't be pure, 
because pure functions don't share state.
Mar 20 2014
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 21 March 2014 at 02:00:11 UTC, Walter Bright wrote:

 On 3/20/2014 6:40 PM, Steven Schveighoffer wrote:

 How do they affect global state?


 Mutexes implicitly share state. It's the reason they exist. 
 They can't be pure, because pure functions don't share state.


If you got that road, you can't allow memory allocators to be
used in pure code. That isn't a good argument.
Mar 20 2014
parent Walter Bright <newshound2 digitalmars.com> writes:
On 3/20/2014 7:02 PM, deadalnix wrote:

 On Friday, 21 March 2014 at 02:00:11 UTC, Walter Bright wrote:

 Mutexes implicitly share state. It's the reason they exist. They can't be
 pure, because pure functions don't share state.


 If you got that road, you can't allow memory allocators to be
 used in pure code. That isn't a good argument.


The analogy doesn't apply. Operator new is regarded as supplying memory from an 
infinite reservoir. There is no implicit global state.

The whole point of a mutex is to change state and share it. It's utterly
different.
Mar 21 2014
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 20 Mar 2014 22:00:15 -0400, Walter Bright  
<newshound2 digitalmars.com> wrote:


 On 3/20/2014 6:40 PM, Steven Schveighoffer wrote:

 How do they affect global state?


 Mutexes implicitly share state. It's the reason they exist. They can't  
 be pure, because pure functions don't share state.


I view it differently. I feel like locking and unlocking a mutex is pure.  
After calling lock, the same thing *always* happens. After unlocking, the  
same thing *always* happens. It's a weird thing -- when you lock a mutex,  
you own it after it's locked. It's no longer shared. It can be thought of  
as pulling memory out of the heap to temporarily own, and then putting it  
back, just like memory allocation (which is considered pure).

This is quite different from actual global state, which is accessed via  
globals.

trylock I don't think should be pure. I'm not sure about read/write locks.

-Steve
Mar 20 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 20 Mar 2014 22:14:59 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Thu, 20 Mar 2014 22:00:15 -0400, Walter Bright  
 <newshound2 digitalmars.com> wrote:


 On 3/20/2014 6:40 PM, Steven Schveighoffer wrote:

 How do they affect global state?


 Mutexes implicitly share state. It's the reason they exist. They can't  
 be pure, because pure functions don't share state.


 I view it differently. I feel like locking and unlocking a mutex is  
 pure. After calling lock, the same thing *always* happens. After  
 unlocking, the same thing *always* happens. It's a weird thing -- when  
 you lock a mutex, you own it after it's locked. It's no longer shared.  
 It can be thought of as pulling memory out of the heap to temporarily  
 own, and then putting it back, just like memory allocation (which is  
 considered pure).


Thinking about it some more, I see what you mean -- an unshared mutex is  
useless.

But at the same time, some "logically" pure functions cannot be so without  
mutexes. E.g. memory allocation.

-Steve
Mar 20 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 21 March 2014 at 03:04:36 UTC, Steven Schveighoffer 
wrote:

 Thinking about it some more, I see what you mean -- an unshared 
 mutex is useless.

 But at the same time, some "logically" pure functions cannot be 
 so without mutexes. E.g. memory allocation.


Since when does "shared" => "impure" ?

If the function takes a pointer to shared data, then you are 
explicitly saying "this function depends on this shared data". 
But as long is it isn't referencing some *other* global directly, 
it is perfectly pure.

For example:

//----
int i = 5;

void foo(int* p) pure
{++p;}

void main() pure
{
     foo(&p);
}
//----

This is "textbook" of a pure function changing global state.

----------------

So the way I see it: shared => pinter to mutex => touching it is 
fair game => can be legit pure (IMO).
Mar 21 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/21/2014 12:03 AM, monarch_dodra wrote:

 On Friday, 21 March 2014 at 03:04:36 UTC, Steven Schveighoffer wrote:

 Thinking about it some more, I see what you mean -- an unshared mutex is
useless.

 But at the same time, some "logically" pure functions cannot be so without
 mutexes. E.g. memory allocation.


 Since when does "shared" => "impure" ?

 If the function takes a pointer to shared data, then you are explicitly saying
 "this function depends on this shared data". But as long is it isn't
referencing
 some *other* global directly, it is perfectly pure.


We've been using 'shared' here to mean shared with another piece of code that 
looks at the state, not 'shared' as in data shared amongst multiple threads.
Mar 21 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 21 March 2014 at 07:14:47 UTC, Walter Bright wrote:

 On 3/21/2014 12:03 AM, monarch_dodra wrote:

 On Friday, 21 March 2014 at 03:04:36 UTC, Steven Schveighoffer 
 wrote:

 Thinking about it some more, I see what you mean -- an 
 unshared mutex is useless.

 But at the same time, some "logically" pure functions cannot 
 be so without
 mutexes. E.g. memory allocation.


 Since when does "shared" => "impure" ?

 If the function takes a pointer to shared data, then you are 
 explicitly saying
 "this function depends on this shared data". But as long is it 
 isn't referencing
 some *other* global directly, it is perfectly pure.


 We've been using 'shared' here to mean shared with another 
 piece of code that looks at the state, not 'shared' as in data 
 shared amongst multiple threads.


Ok. That's a fair point. So in that case, our function is 
pointing at "data", and is allowed to mutate it, and observe its 
state.

Now, if *another* piece of code is doing the same thing at the 
same time (potentially mutating "data", does that still violate 
purity?

As long a the function doesn't access/mutate something via direct 
global state, it's pure, isn't it?

I think... it's tough to wrap your head around the issue.
Mar 21 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/21/2014 12:59 AM, monarch_dodra wrote:

 Ok. That's a fair point. So in that case, our function is pointing at "data",
 and is allowed to mutate it, and observe its state.

 Now, if *another* piece of code is doing the same thing at the same time
 (potentially mutating "data", does that still violate purity?


A mutex essentially reads and writes a global flag, which other functions can 
also read and write.

That makes it NOT pure.
Mar 21 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 21 Mar 2014 14:18:05 -0400, Walter Bright  
<newshound2 digitalmars.com> wrote:


 On 3/21/2014 12:59 AM, monarch_dodra wrote:

 Ok. That's a fair point. So in that case, our function is pointing at  
 "data",
 and is allowed to mutate it, and observe its state.

 Now, if *another* piece of code is doing the same thing at the same time
 (potentially mutating "data", does that still violate purity?


 A mutex essentially reads and writes a global flag, which other  
 functions can also read and write.

 That makes it NOT pure.


No, that's not the case. A mutex does not write a global flag, it writes a  
shared flag. And the flag is passed into it.

I still think straight locking and unlocking of mutexes should be pure,  
because of the exclusive nature of the data protected by them.

-Steve
Mar 21 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/21/2014 11:23 AM, Steven Schveighoffer wrote:

 On Fri, 21 Mar 2014 14:18:05 -0400, Walter Bright <newshound2 digitalmars.com>
 wrote:


 On 3/21/2014 12:59 AM, monarch_dodra wrote:

 Ok. That's a fair point. So in that case, our function is pointing at "data",
 and is allowed to mutate it, and observe its state.

 Now, if *another* piece of code is doing the same thing at the same time
 (potentially mutating "data", does that still violate purity?


 A mutex essentially reads and writes a global flag, which other functions can
 also read and write.

 That makes it NOT pure.


 No, that's not the case. A mutex does not write a global flag, it writes a
 shared flag. And the flag is passed into it.


Here's a litmus test you can use for purity. Consider:

     int foo() pure;
     {
	auto a = foo();
     }

Now, since 'a' is never used, we can delete the assignment, and since foo is 
pure, we can delete foo():

     {
     }

Is this program distinguishable from the former? If not, then foo() is not pure.
Mar 21 2014
parent "Meta" <jared771 gmail.com> writes:
On Friday, 21 March 2014 at 19:19:06 UTC, Walter Bright wrote:

 Here's a litmus test you can use for purity. Consider:

     int foo() pure;
     {
 	auto a = foo();
     }

 Now, since 'a' is never used, we can delete the assignment, and 
 since foo is pure, we can delete foo():

     {
     }

 Is this program distinguishable from the former? If not, then 
 foo() is not pure.


Consider this:

int foo(int* pa) pure
{
     if (pa)
     {
         *pa = foo();
     }
}

This is also pure according to D's type system, but it fails your 
litmus test. This, however, passes:

int foo(immutable(int)* pa) pure
{
     pa = pfoo();
}

I think the case of a monitor is closer to the first example.
Mar 21 2014
prev sibling parent reply "Sean Kelly" <sean invisibleduck.org> writes:
On Friday, 21 March 2014 at 02:00:11 UTC, Walter Bright wrote:

 On 3/20/2014 6:40 PM, Steven Schveighoffer wrote:

 How do they affect global state?


 Mutexes implicitly share state. It's the reason they exist. 
 They can't be pure, because pure functions don't share state.


Locking a monitor is also a mutating operation and yet I believe 
you can have const synchronized methods.  They live somewhat 
outside the normal type system.  I don't see any point in having 
pure class methods, but what about:

pure int add(T)(const(T) a, const(T) b) {
     return a + b;
}

Where the variables above are instances of a synchronized class?  
The operation would implicitly lock their monitors to perform the 
addition.
Mar 21 2014
parent Walter Bright <newshound2 digitalmars.com> writes:
On 3/21/2014 9:28 AM, Sean Kelly wrote:

 On Friday, 21 March 2014 at 02:00:11 UTC, Walter Bright wrote:

 On 3/20/2014 6:40 PM, Steven Schveighoffer wrote:

 How do they affect global state?


 Mutexes implicitly share state. It's the reason they exist. They can't be
 pure, because pure functions don't share state.


 Locking a monitor is also a mutating operation and yet I believe you can have
 const synchronized methods.  They live somewhat outside the normal type system.
 I don't see any point in having pure class methods, but what about:

 pure int add(T)(const(T) a, const(T) b) {
      return a + b;
 }

 Where the variables above are instances of a synchronized class? The operation
 would implicitly lock their monitors to perform the addition.


Yes, I think the pairing of lock/unlock of a mutex can be pure, but just a lock 
or just an unlock cannot be.
Mar 21 2014
prev sibling parent "Sean Kelly" <sean invisibleduck.org> writes:
On Tuesday, 18 March 2014 at 23:56:15 UTC, Steven Schveighoffer 
wrote:

 On Tue, 18 Mar 2014 19:48:45 -0400, Walter Bright 
 <newshound2 digitalmars.com> wrote:


 On 3/18/2014 4:20 PM, Steven Schveighoffer wrote:

 In a recent (well, recently pulled anyway) pull request that 
 Monarch Dodra
 brought up, we debated what should be considered nothrow in 
 the depths of druntime.


 There's a lot of low hanging nothrow fruit in druntime that 
 doesn't need analysis, it just needs to get done:

 https://d.puremagic.com/issues/show_bug.cgi?id=12389


 Can we mark _d_monitorenter and _d_monitorexit nothrow and have 
 the compiler see that when using synchronized? This was the 
 hurdle we couldn't overcome in the referenced pull request.

 Should those be marked nothrow? What about pure and  safe?


I'd be inclined to say yes.  Although monitors use lazy 
initialization, I think the failure to initialize a monitor 
should probably be considered an Error.
Mar 20 2014
prev sibling next sibling parent reply Mike Parker <aldacron gmail.com> writes:
On 3/19/2014 8:20 AM, Steven Schveighoffer wrote:


 We all agreed that nothing that assumeSafeAppend did should really
 throw, and so the pull just used c linkage to "add" nothrow to an
 otherwise unmarked function.


Does this mean that extern(C) functions are automatically considered 
nothrow? That is not my current understanding.
Mar 18 2014
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 3/18/2014 6:56 PM, Mike Parker wrote:

 Does this mean that extern(C) functions are automatically considered nothrow?


No.
Mar 18 2014
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 18 Mar 2014 21:56:54 -0400, Mike Parker <aldacron gmail.com> wrote:


 On 3/19/2014 8:20 AM, Steven Schveighoffer wrote:


 We all agreed that nothing that assumeSafeAppend did should really
 throw, and so the pull just used c linkage to "add" nothrow to an
 otherwise unmarked function.


 Does this mean that extern(C) functions are automatically considered  
 nothrow? That is not my current understanding.


No, but extern C functions are not mangled. Therefore, the declaration can  
be nothrow, but the implementation not have that attribute, and linking  
still works. It's a way to work around the compiler checks.

-Steve
Mar 19 2014
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 19/03/14 00:20, Steven Schveighoffer wrote:

 I think we all agree that there are some things that the compiler simply cannot
 prove are nothrow, but to be able to write useful nothrow code, we have to
paste
 nothrow on there anyway.


Just to clarify my understanding here: exactly how much compiler checking _is_ 
done of nothrow?  Is it simply to confirm that whatever is called by the 
function contains no "throw" statements (hopefully all the way down ...), or is 
there more ... ?

What I'm wondering is whether just as we have  safe and  trusted for the 
situations where the compiler can verify and where the programmer has verified, 
is there a case for complementing nothrow with another attribute ("wontthrow"?) 
that's a programmer assurance rather than a compiler-checked guarantee?

I imagine if that was worthwhile someone would already have done it, but I'm 
curious.
Mar 19 2014
prev sibling next sibling parent =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-19 08:59, Joseph Rushton Wakeling wrote:

 On 19/03/14 00:20, Steven Schveighoffer wrote:

 I think we all agree that there are some things that the compiler
 simply cannot
 prove are nothrow, but to be able to write useful nothrow code, we
 have to paste
 nothrow on there anyway.


 Just to clarify my understanding here: exactly how much compiler
 checking _is_ done of nothrow?  Is it simply to confirm that whatever is
 called by the function contains no "throw" statements (hopefully all the
 way down ...), or is there more ... ?


It checks that any exceptions thrown in the function body are caught in 
a try/catch, and that any functions not marked nothrow are similarly 
handled in a try/catch. I believe that is all.

For templated functions, the compiler does the same to figure out if the 
instantiation is nothrow. Thus a function can call a templated function 
that's not marked nothrow if its body can be compiled as such.

--
   Simen
Mar 20 2014
prev sibling parent reply "w0rp" <devw0rp gmail.com> writes:
I'd just like to toss one in there. .dup and .idup for slices and 
associative arrays. I've seen a few cases where these functions 
are not nothrow when they could be. (Because OutOfMemoryError is 
an Error, not an Exception.)
Mar 20 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 20 March 2014 at 12:51:35 UTC, w0rp wrote:

 I'd just like to toss one in there. .dup and .idup for slices 
 and associative arrays. I've seen a few cases where these 
 functions are not nothrow when they could be. (Because 
 OutOfMemoryError is an Error, not an Exception.)


The reasons it's not nothrow is because because dup causes 
postblit, and postblit could throw.

Of course, by that same token, postblit could be unsafe and 
impure. It's terribly inconsistent.

Which is another big problem of druntime: Mostly everything in it 
is done at run-time using typeid, so there is no static inference.
Mar 20 2014