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 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
next 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 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 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 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 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
prev sibling 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 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 next sibling parent "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
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
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 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 "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 =?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 next sibling parent "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
prev sibling next sibling 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
prev sibling next 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 "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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