www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - GC.malloc is pure - wat

reply "anonymous" <anonymous example.com> writes:
GC.malloc is marked pure. But it isn't, is it?

This should hold for a pure function:
     assert(f(x) == f(x));
This fails with GC.malloc, of course.

Or consider this:
     auto v = f(x);
     auto w = f(x);
When f is pure, a compiler should be free to reuse the value of v 
for w. That's no good with GC.malloc, obviously.
Apr 24 2015
next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
string toLower(string s);

Should that be pure? Repeated calls to it, given the same input, 
will return the same output, but they will also most likely be 
separately allocated.

GC.malloc might be cheating to be pure, but it does enable a lot 
of more logically pure stuff on top of it...
Apr 24 2015
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 11:05 AM, anonymous wrote:
 GC.malloc is marked pure. But it isn't, is it?

 This should hold for a pure function:
      assert(f(x) == f(x));
All functional make this concession -- allocating is pure as long as you don't look at the address. You a language that doesn't allow allocating memory is quite useless.
 This fails with GC.malloc, of course.

 Or consider this:
      auto v = f(x);
      auto w = f(x);
 When f is pure, a compiler should be free to reuse the value of v for w.
 That's no good with GC.malloc, obviously.
This is OK as long as f is *strong* pure. D pure is not the same as the traditional definition. And GC.malloc is not strong pure, as it returns mutable data. However, this should be strong pure: immutable(int)* foo(int x) pure { return new int(x); } Any call to foo could be cached and avoided. This is allowed by the compiler (but I'm not sure if the optimization is implemented). But *inside* foo, you are allowed to call "weak" pure functions. Those calls cannot be cached. Note that calls to foo *could* be cached, but are not *required* to be cached, as you hinted in your question. -Steve
Apr 24 2015
next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 11:21 AM, Steven Schveighoffer wrote:

 All functional make this concession -- allocating is pure as long as you
 don't look at the address. You a language that doesn't allow allocating
 memory is quite useless.
All functional *languages* make this concession... -Steve
Apr 24 2015
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Friday, 24 April 2015 at 15:21:43 UTC, Steven Schveighoffer 
wrote:
 Any call to foo could be cached and avoided. This is allowed by 
 the compiler (but I'm not sure if the optimization is 
 implemented).
It does, but only in the same expression, i.e. auto a = sin(x) * sin(x); // sin() is called only once but: auto a = sin(x); auto b = sin(x); // sin() is called again here
Apr 24 2015
parent reply "anonymous" <anonymous example.com> writes:
On Friday, 24 April 2015 at 15:29:59 UTC, Marc Schütz wrote:
 auto a = sin(x) * sin(x);    // sin() is called only once
Could you give a complete example of when this is done? Two calls here (ldc2 -c -O): real grepme(real x) pure { import std.math; auto a = sin(x) * sin(x); return a; } 0000000000000000 <_D4test6grepmeFNaeZe>: 0: 48 83 ec 28 sub rsp,0x28 4: db 6c 24 30 fld TBYTE PTR [rsp+0x30] 8: d9 c0 fld st(0) a: db 7c 24 10 fstp TBYTE PTR [rsp+0x10] e: db 3c 24 fstp TBYTE PTR [rsp] 11: e8 00 00 00 00 call 16 <_D4test6grepmeFNaeZe+0x16> 16: db 7c 24 1c fstp TBYTE PTR [rsp+0x1c] 1a: db 6c 24 10 fld TBYTE PTR [rsp+0x10] 1e: db 3c 24 fstp TBYTE PTR [rsp] 21: e8 00 00 00 00 call 26 <_D4test6grepmeFNaeZe+0x26> 26: db 6c 24 1c fld TBYTE PTR [rsp+0x1c] 2a: de c9 fmulp st(1),st 2c: 48 83 c4 28 add rsp,0x28 30: c3 ret
Apr 24 2015
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Friday, 24 April 2015 at 16:34:09 UTC, anonymous wrote:
 On Friday, 24 April 2015 at 15:29:59 UTC, Marc Schütz wrote:
 auto a = sin(x) * sin(x);    // sin() is called only once
Could you give a complete example of when this is done? Two calls here (ldc2 -c -O): real grepme(real x) pure { import std.math; auto a = sin(x) * sin(x); return a; } 0000000000000000 <_D4test6grepmeFNaeZe>: 0: 48 83 ec 28 sub rsp,0x28 4: db 6c 24 30 fld TBYTE PTR [rsp+0x30] 8: d9 c0 fld st(0) a: db 7c 24 10 fstp TBYTE PTR [rsp+0x10] e: db 3c 24 fstp TBYTE PTR [rsp] 11: e8 00 00 00 00 call 16 <_D4test6grepmeFNaeZe+0x16> 16: db 7c 24 1c fstp TBYTE PTR [rsp+0x1c] 1a: db 6c 24 10 fld TBYTE PTR [rsp+0x10] 1e: db 3c 24 fstp TBYTE PTR [rsp] 21: e8 00 00 00 00 call 26 <_D4test6grepmeFNaeZe+0x26> 26: db 6c 24 1c fld TBYTE PTR [rsp+0x1c] 2a: de c9 fmulp st(1),st 2c: 48 83 c4 28 add rsp,0x28 30: c3 ret
Hmm... strange. I was convinced it worked that way. I used `sin()` specifically because I remember I've seen an example with it. But now I can't get it do work anymore, not even with `int` or a user-defined pure function.
Apr 24 2015
prev sibling parent reply "anonymous" <anonymous example.com> writes:
On Friday, 24 April 2015 at 15:21:43 UTC, Steven Schveighoffer 
wrote:
 This is OK as long as f is *strong* pure. D pure is not the 
 same as the traditional definition.

 And GC.malloc is not strong pure, as it returns mutable data.
Ah, this is the piece I was missing. I was aware of weak/strong pure, but I didn't know the return type plays a role in that. Could core.stdc.stdlib.malloc and friends also be marked pure then?
Apr 24 2015
next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 11:43 AM, anonymous wrote:
 On Friday, 24 April 2015 at 15:21:43 UTC, Steven Schveighoffer wrote:
 This is OK as long as f is *strong* pure. D pure is not the same as
 the traditional definition.

 And GC.malloc is not strong pure, as it returns mutable data.
Ah, this is the piece I was missing. I was aware of weak/strong pure, but I didn't know the return type plays a role in that. Could core.stdc.stdlib.malloc and friends also be marked pure then?
IMO, yes. But not everyone agrees with that. Definitely, free has issues with being pure. And if free cannot be pure, there's not much point in making malloc pure. But I could see something like RefCounted that uses malloc being pure. -Steve
Apr 24 2015
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 24 April 2015 at 15:43:17 UTC, anonymous wrote:
 On Friday, 24 April 2015 at 15:21:43 UTC, Steven Schveighoffer 
 wrote:
 This is OK as long as f is *strong* pure. D pure is not the 
 same as the traditional definition.

 And GC.malloc is not strong pure, as it returns mutable data.
Ah, this is the piece I was missing. I was aware of weak/strong pure, but I didn't know the return type plays a role in that. Could core.stdc.stdlib.malloc and friends also be marked pure then?
No. Allocating on the GC is "stateless" as the GC will handle the state by itself, from the program perspective, there is no state to maintain. malloc require free, and the state management is pushed on the application rather than the runtime. It is not pure.
Apr 24 2015
parent reply "anonymous" <anonymous example.com> writes:
On Friday, 24 April 2015 at 17:07:20 UTC, deadalnix wrote:
 On Friday, 24 April 2015 at 15:43:17 UTC, anonymous wrote:
[...]
 Could core.stdc.stdlib.malloc and friends also be marked pure 
 then?
No. Allocating on the GC is "stateless" as the GC will handle the state by itself, from the program perspective, there is no state to maintain. malloc require free, and the state management is pushed on the application rather than the runtime. It is not pure.
There's also GC.free, which is also marked pure. I can't see how GC.malloc followed by GC.free is more pure than stdlib malloc followed by stdlib free.
Apr 24 2015
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 24 April 2015 at 17:45:57 UTC, anonymous wrote:
 On Friday, 24 April 2015 at 17:07:20 UTC, deadalnix wrote:
 On Friday, 24 April 2015 at 15:43:17 UTC, anonymous wrote:
[...]
 Could core.stdc.stdlib.malloc and friends also be marked pure 
 then?
No. Allocating on the GC is "stateless" as the GC will handle the state by itself, from the program perspective, there is no state to maintain. malloc require free, and the state management is pushed on the application rather than the runtime. It is not pure.
There's also GC.free, which is also marked pure. I can't see how GC.malloc followed by GC.free is more pure than stdlib malloc followed by stdlib free.
GC.free should probably not be pure, but that is also not at all what you talk about in previous posts, which led me to think you are essentially doing a stunt as to not admit you were wrong.
Apr 24 2015
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 1:57 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 17:45:57 UTC, anonymous wrote:
 On Friday, 24 April 2015 at 17:07:20 UTC, deadalnix wrote:
 On Friday, 24 April 2015 at 15:43:17 UTC, anonymous wrote:
[...]
 Could core.stdc.stdlib.malloc and friends also be marked pure then?
No. Allocating on the GC is "stateless" as the GC will handle the state by itself, from the program perspective, there is no state to maintain. malloc require free, and the state management is pushed on the application rather than the runtime. It is not pure.
There's also GC.free, which is also marked pure. I can't see how GC.malloc followed by GC.free is more pure than stdlib malloc followed by stdlib free.
GC.free should probably not be pure, but that is also not at all what you talk about in previous posts, which led me to think you are essentially doing a stunt as to not admit you were wrong.
I think you are thinking of safe-ty. malloc and free can be pure, but must be contained properly. purity when it comes to mutable data is a tricky thing. -Steve
Apr 24 2015
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 24 April 2015 at 18:48:43 UTC, Steven Schveighoffer 
wrote:
 I think you are thinking of  safe-ty. malloc and free can be 
 pure, but must be contained properly.

 purity when it comes to mutable data is a tricky thing.

 -Steve
No, it should not be pure because it alter global state in a manner visible to the program.
Apr 24 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 3:12 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 18:48:43 UTC, Steven Schveighoffer wrote:
 I think you are thinking of  safe-ty. malloc and free can be pure, but
 must be contained properly.

 purity when it comes to mutable data is a tricky thing.
No, it should not be pure because it alter global state in a manner visible to the program.
But so does GC.malloc. In any case, it's already been stated by Walter/Andrei that they are not interested in making C malloc/free pure. So it's a moot issue to argue over. This likely will come up again when std.allocator is completed, and we can re-examine it then. -Steve
Apr 24 2015
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 24 April 2015 at 19:41:21 UTC, Steven Schveighoffer 
wrote:
 On 4/24/15 3:12 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 18:48:43 UTC, Steven Schveighoffer 
 wrote:
 I think you are thinking of  safe-ty. malloc and free can be 
 pure, but
 must be contained properly.

 purity when it comes to mutable data is a tricky thing.
No, it should not be pure because it alter global state in a manner visible to the program.
But so does GC.malloc.
No, that's the whole point of using a GC. You ask it for a chunk of memory, it gives you a chunk of memory. This does not affect any other part of your program as it is a NEW chunk of memory, so you are not messing with your program state. When you free, you potentially alter references anywhere outside your "pure" function. It must not be pure. Obviously, there is state involved inside the GC, but the whole point is that it is isolated from the program (granted the GC is not buggy).
Apr 24 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 4:42 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 19:41:21 UTC, Steven Schveighoffer wrote:
 On 4/24/15 3:12 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 18:48:43 UTC, Steven Schveighoffer wrote:
 I think you are thinking of  safe-ty. malloc and free can be pure, but
 must be contained properly.

 purity when it comes to mutable data is a tricky thing.
No, it should not be pure because it alter global state in a manner visible to the program.
But so does GC.malloc.
No, that's the whole point of using a GC. You ask it for a chunk of memory, it gives you a chunk of memory. This does not affect any other part of your program as it is a NEW chunk of memory, so you are not messing with your program state.
But I can check memory usage size and see global state has been altered.
 When you free, you potentially alter references anywhere outside your
 "pure" function. It must not be pure.
When you do ANYTHING to mutable data, you potentially alter references outside your pure function. This is not a disqualifier. It's accessing global sate directly that wasn't passed to you that is a disqualifier. -Steve
Apr 24 2015
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 24 April 2015 at 20:55:02 UTC, Steven Schveighoffer 
wrote:
 But I can check memory usage size and see global state has been 
 altered.
OK, if you want to play that game, don't access memory ever, that is global state. I mean, even if the memory is read only you may end up affecting the MMU, so that is definitively a no go. Also, you'd better have only a one instruction loop in your program as otherwise you'll affect the program counter, a definitively visible state from the user.
 When you free, you potentially alter references anywhere 
 outside your
 "pure" function. It must not be pure.
When you do ANYTHING to mutable data, you potentially alter references outside your pure function. This is not a disqualifier. It's accessing global sate directly that wasn't passed to you that is a disqualifier. -Steve
pure function can access global immutable state that wasn't passed to it, so you may want to revise your definition.
Apr 24 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 5:07 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 20:55:02 UTC, Steven Schveighoffer wrote:
 But I can check memory usage size and see global state has been altered.
OK, if you want to play that game, don't access memory ever, that is global state. I mean, even if the memory is read only you may end up affecting the MMU, so that is definitively a no go. Also, you'd better have only a one instruction loop in your program as otherwise you'll affect the program counter, a definitively visible state from the user.
All I'm saying is that GC.malloc alters global state. I agree that it's OK to pretend that it doesn't because as long as you agree not to base things on this knowledge, you are fine calling pure functions that use GC. It's possible to do things like this, to make pure functions "unpure": bool foo() pure { return new int(0) < new int(0); } We just agree to ignore that aspect. And I'm OK with it. As I'm OK with ignoring the bad things you can do with C malloc or C free that make things impure.
 When you free, you potentially alter references anywhere outside your
 "pure" function. It must not be pure.
When you do ANYTHING to mutable data, you potentially alter references outside your pure function. This is not a disqualifier. It's accessing global sate directly that wasn't passed to you that is a disqualifier.
pure function can access global immutable state that wasn't passed to it, so you may want to revise your definition.
Sure: s/accessing/altering, my mistake. -Steve
Apr 24 2015
next sibling parent reply "weaselcat" <weaselcat gmail.com> writes:
On Friday, 24 April 2015 at 23:27:36 UTC, Steven Schveighoffer 
wrote:
 All I'm saying is that GC.malloc alters global state. I agree 
 that it's OK to pretend that it doesn't because as long as you 
 agree not to base things on this knowledge, you are fine 
 calling pure functions that use GC.
A lie that is universally agreed upon is virtually indistinguishable from the truth. the reasons against making malloc/free pure are very... thin. Walter himself attempted to make them pure only last week(!) https://github.com/D-Programming-Language/druntime/pull/1221
Apr 24 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/24/15 8:30 PM, weaselcat wrote:
 On Friday, 24 April 2015 at 23:27:36 UTC, Steven Schveighoffer wrote:
 All I'm saying is that GC.malloc alters global state. I agree that
 it's OK to pretend that it doesn't because as long as you agree not to
 base things on this knowledge, you are fine calling pure functions
 that use GC.
A lie that is universally agreed upon is virtually indistinguishable from the truth. the reasons against making malloc/free pure are very... thin. Walter himself attempted to make them pure only last week(!) https://github.com/D-Programming-Language/druntime/pull/1221
I hadn't noticed that. And linked from there is the reason I was shown that free cannot be pure (from a while ago): void freeIt(immutable(int)* x) pure { free(cast(int *)x); } A compiler could legally just not even call this function. It's a pretty compelling reason. I have a feeling that we can't make free generally pure. When needed, it will have to be hacked somehow in a controlled way. Or we could make some rule that you should never cast immutable pointers to mutable in order to free them. Doesn't sound very enforceable... -Steve
Apr 24 2015
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 24 April 2015 at 23:27:36 UTC, Steven Schveighoffer 
wrote:
 pure function can access global immutable state that wasn't 
 passed to
 it, so you may want to revise your definition.
Sure: s/accessing/altering, my mistake. -Steve
That is the whole point. See it as follow: GC.malloc create new state. As long as this new state doesn't escape the pure function, it is as if that state was local.
Apr 25 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/25/15 11:06 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 23:27:36 UTC, Steven Schveighoffer wrote:
 pure function can access global immutable state that wasn't passed to
 it, so you may want to revise your definition.
Sure: s/accessing/altering, my mistake.
That is the whole point. See it as follow: GC.malloc create new state. As long as this new state doesn't escape the pure function, it is as if that state was local.
I get that, you can apply the same thing for free. No reason this can't be a pure function: void foo() { int *x = cast(int *)malloc(sizeof(int)); *x = 0; scope(exit) free(x); } But there are other problems, as I pointed out in another post. -Steve
Apr 27 2015
parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 27 April 2015 at 10:50:12 UTC, Steven Schveighoffer 
wrote:
 On 4/25/15 11:06 PM, deadalnix wrote:
 On Friday, 24 April 2015 at 23:27:36 UTC, Steven Schveighoffer 
 wrote:
 pure function can access global immutable state that wasn't 
 passed to
 it, so you may want to revise your definition.
Sure: s/accessing/altering, my mistake.
That is the whole point. See it as follow: GC.malloc create new state. As long as this new state doesn't escape the pure function, it is as if that state was local.
I get that, you can apply the same thing for free. No reason this can't be a pure function:
With malloc, you have 2 new thing is userland: - A new state, which, as for the GC case could be considered pure. - A global state that you have to maintain (the fact that you allocated and must free) and this should not be pure.
 void foo()
 {
    int *x = cast(int *)malloc(sizeof(int));
    *x = 0;
    scope(exit) free(x);
 }

 But there are other problems, as I pointed out in another post.

 -Steve
In that specific use case, I think this is fair to consider that code pure, or at least pretend it is. D being a system programming language, you can pretend this is pure.
Apr 27 2015
prev sibling parent "anonymous" <anonymous example.com> writes:
On Friday, 24 April 2015 at 17:57:12 UTC, deadalnix wrote:
 On Friday, 24 April 2015 at 17:45:57 UTC, anonymous wrote:
[...]
 I can't see how GC.malloc followed by GC.free is more pure 
 than stdlib malloc followed by stdlib free.
GC.free should probably not be pure,
Ok, fair enough. Right now, I'd lean the other way and make stdlib free pure, too. Both free variants essentially invalidate their void* arguments. (Weakly) pure functions may tinker with their arguments, so that could be fine. I'm probably missing something, though. Feel free to enlighten me.
 but that is also not at all what you talk about in previous 
 posts, which led me to think you are essentially doing a stunt 
 as to not admit you were wrong.
Huh? I had missed that GC.malloc isn't strongly pure but weakly pure because the return type. I don't mean to deny that or distract from it. If it helps: I was wrong. My shame is great. Please forgive my ignorance.
Apr 24 2015
prev sibling parent reply "David Nadlinger" <code klickverbot.at> writes:
On Friday, 24 April 2015 at 15:05:15 UTC, anonymous wrote:
     auto v = f(x);
     auto w = f(x);
 When f is pure, a compiler should be free to reuse the value of 
 v for w. That's no good with GC.malloc, obviously.
In case there is further confusion about purity in D, let me do a shameless plug for an article I wrote a couple of years back: http://klickverbot.at/blog/2012/05/purity-in-d/ — David
Apr 24 2015
parent "anonymous" <anonymous example.com> writes:
On Friday, 24 April 2015 at 18:03:50 UTC, David Nadlinger wrote:
 In case there is further confusion about purity in D, let me do 
 a shameless plug for an article I wrote a couple of years back: 
 http://klickverbot.at/blog/2012/05/purity-in-d/

  — David
I'm pretty sure that I've read that. But I had completely forgotten about the "Indirections in the Return Type?" part which covers exactly the scenario I was worried about. So, yeah, good article. Sorry for the noise.
Apr 24 2015