www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - purity and memory allocations/pointers

reply "monarch_dodra" <monarchdodra gmail.com> writes:
I'm a bit confused about where we draw the line with purity, and 
memory.

For example, take this "simple" function:

//----
char[] getMutableHello() pure
{
     return "hello".dup;
}
//----

This seems like it will *always* create the same result, yet at 
the same time, it calls the GC. "dup" could fail, amongst others, 
meaning there is failed purity.

Is this OK?

:::::::::::::::::::::::::::::::::::::::::

Where does purity mean when you are talking about 
slices/pointers? Simply that they *point*/*reference* the same 
payload? I mean:

void main()
{
     auto a = getMutableHello();
     auto b = getMutableHello();
     assert(a == b); //OK
     assert(a is b); //Derp :/
}

Did getMutableHello just violate its purity promise?

:::::::::::::::::::::::::::::::::::::::::

Another thing that bothers me, again, when interfacing with the 
GC, is "capacity". It is currently marked as pure, but I believe 
this is wrong: The GC can in-place extend the "useable" memory of 
a dynamic array. This means all referencing slices will be 
affected, yet un-modified. This means that calling "s.capacity" 
depends on the global state of the GC:

//----
     auto s1 = new ubyte[](12_000);
     auto bck = s1;
     size_t cap = s1.capacity;
     s1.reserve(13_000);
     assert(s1 is bck); //Apparently, s1 is not changed.
     assert(cap == s1.capacity); //This fails, yet capacity is 
pure?
//----

Again, is this OK?

:::::::::::::::::::::::::::::::::::::::::

One last question: Pointers.

int get(int* p) pure
{
     return *p;
}

void main()
{
     int i = 0;
     auto p = &i;
     get(p);
}

Here, get, to me, is obviously not pure, since it depends on the 
state of the global "i". *Where* did "get" go wrong? Did I simply 
"abusively" mark get as pure? Is the "pure" keyword's guarantee 
simply "weak"?

:::::::::::::::::::::::::::::::::::::::::

To sum up the question, regardless of how the *keyword* pure 
currently works, my question is "*How* should it behave"? We're 
currently marking things in Phobos as pure, and I'm worried the 
only reason we are doing it is that the keyword is lenient, and 
said functions *aren't* actually pure...
Aug 03 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/03/2013 05:59 PM, monarch_dodra wrote:
 I'm a bit confused about where we draw the line with purity, and memory.

 For example, take this "simple" function:

 //----
 char[] getMutableHello() pure
 {
      return "hello".dup;
 }
 //----

 This seems like it will *always* create the same result, yet at the same
 time, it calls the GC. "dup" could fail, amongst others, meaning there
 is failed purity.

 Is this OK?

Since a pure function call can overflow the stack, I don't really see this particular point as an issue. (D is Turing complete, unlike the machines it runs on.)
 :::::::::::::::::::::::::::::::::::::::::

 Where does purity mean when you are talking about slices/pointers?
 Simply that they *point*/*reference* the same payload? I mean:

 void main()
 {
      auto a = getMutableHello();
      auto b = getMutableHello();
      assert(a == b); //OK
      assert(a is b); //Derp :/
 }

 Did getMutableHello just violate its purity promise?
 ...

Well, no. It is by design. All purity really means is that the part of the existing store not reachable by following references in the arguments will not be mutated. What is unfortunate in a sense is that 'is' can be used on immutable references. This often precludes common subexpression elimination for pure function calls even though such an optimization would be valid otherwise.
 :::::::::::::::::::::::::::::::::::::::::

 Another thing that bothers me, again, when interfacing with the GC, is
 "capacity". It is currently marked as pure, but I believe this is wrong:
 The GC can in-place extend the "useable" memory of a dynamic array. This
 means all referencing slices will be affected, yet un-modified. This
 means that calling "s.capacity" depends on the global state of the GC:

 //----
      auto s1 = new ubyte[](12_000);
      auto bck = s1;
      size_t cap = s1.capacity;
      s1.reserve(13_000);
      assert(s1 is bck); //Apparently, s1 is not changed.
      assert(cap == s1.capacity); //This fails, yet capacity is pure?
 //----

 Again, is this OK?
 ...

Well, not really. IMO the issue here is that if D had a formal semantics, it would likely be indeterministic due to the GC interface. To make the execution of pure functions deterministic (which is not currently part of their guarantees), all operations that can witness indeterminism would need to be banned in pure functions (eg. ~=, ordering addresses, traversing hash tables etc.) It is not really possible to get rid of the non-determinism completely while keeping any kind of allocations, since allocations will return nondeterministic memory addresses. (Unless the formal semantics fully specifies the GC implementation. :o) ) Another stance that can be taken is that it is not really global state, since it is referenced by the slice. Then the above would be ok. (But semantically ugly.) Under that point of view, an issue is that capacity violates the transitivity of immutable.
 :::::::::::::::::::::::::::::::::::::::::

 One last question: Pointers.

 int get(int* p) pure
 {
      return *p;
 }

 void main()
 {
      int i = 0;
      auto p = &i;
      get(p);
 }

 Here, get, to me, is obviously not pure, since it depends on the state
 of the global "i". *Where* did "get" go wrong? Did I simply "abusively"
 mark get as pure? Is the "pure" keyword's guarantee simply "weak"?
 ...

Yes, it's weak.
 :::::::::::::::::::::::::::::::::::::::::

 To sum up the question, regardless of how the *keyword* pure currently
 works, my question is "*How* should it behave"? We're currently marking
 things in Phobos as pure, and I'm worried the only reason we are doing
 it is that the keyword is lenient, and said functions *aren't* actually
 pure...

I guess adding the requirement that a pure function cannot witness its own indeterminism is required to make the keyword legitimate.
Aug 03 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/03/2013 09:07 PM, Meta wrote:
 On Saturday, 3 August 2013 at 16:47:52 UTC, Timon Gehr wrote:
 On 08/03/2013 05:59 PM, monarch_dodra wrote:
 One last question: Pointers.

 int get(int* p) pure
 {
     return *p;
 }

 void main()
 {
     int i = 0;
     auto p = &i;
     get(p);
 }

 Here, get, to me, is obviously not pure, since it depends on the state
 of the global "i". *Where* did "get" go wrong? Did I simply "abusively"
 mark get as pure? Is the "pure" keyword's guarantee simply "weak"?
 ...

Yes, it's weak.

It depends on whether you think a pointer dereference is pure or not (I don't know the answer).

It is pure in D, but I guess you are not referring to that. What's your understanding of purity in this context?
 That aside, as long as get doesn't modify the
 value at *p or change what p points to, this is strongly pure

Modification and dereference within a Haskell expression: import Data.STRef import Control.Monad.ST x = runST $ do x <- newSTRef 0 writeSTRef x 1 v <- readSTRef x return v main = print x
 (i.e., the academic definition of purity).

I wouldn't go that far.
Aug 03 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/04/2013 02:50 AM, Meta wrote:
 On Saturday, 3 August 2013 at 23:04:14 UTC, Timon Gehr wrote:
 ...

 Modification and dereference within a Haskell expression:

 import Data.STRef
 import Control.Monad.ST

 x = runST $ do
   x <- newSTRef 0
   writeSTRef x 1
   v <- readSTRef x
   return v

 main = print x

I apologize, as I don't know how familiar you are with Haskell,

With the language, quite intimately.
 so forgive me if I'm telling you something you already know. That code is
 100% pure and side-effect free;

My point was basically that x is a pure expression of type Integer.
 no variables are being modified.

Which I didn't claim. A reference is dereferenced and the contents of the referenced slot are replaced. Then the reference is dereferenced again to read the modified value out.
 Haskell only simulates side-effects

What tells you that D does not 'simulate' mutable state?
 with monads,

What is done to main behind the scenes in order to execute the program is most definitely side-effecting.
 and do-notation

do notation is not central to my point.
 (syntwhat you
 use in this example) which is syntactic sugar.

 (i.e., the academic definition of purity).

I wouldn't go that far.

Perhaps that may go too far, as academics love to obfuscate topics with a bunch of extraneous cruft,

I take issue with this statement. I meant, I wouldn't assume 'the academic definition of purity' is a thing.
 but the fact remains that purity means:

 1. No modification of local or global state (side-effects)
 2. No dependence on global mutable state.

What does this statement quantify over? Eg, where is the abstraction boundary?
Aug 03 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 08/04/2013 06:37 AM, Meta wrote:
 On Sunday, 4 August 2013 at 02:05:55 UTC, Timon Gehr wrote:
 no variables are being modified.

Which I didn't claim. A reference is dereferenced and the contents of the referenced slot are replaced. Then the reference is dereferenced again to read the modified value out.

I'm confused about what your point is now. Are you trying to convince me that dereferencing p and modifying the value it points to are side-effect free? Of course you can do it in Haskell with some wizardry, but D doesn't do any of that. ...

Weak purity is actually superficially similar to state transformers in Haskell.
 Haskell only simulates side-effects

What tells you that D does not 'simulate' mutable state?

I see what you're getting at. I thought I had a good answer before I really thought about your question. I can't think of any way to prove that a language is not simply simulating mutable state off the top of my head. Do you actually have an answer to this question, or were you just making a point? ...

I think you cannot tell, and hence it is questionable whether simulated side effects are different from real side effects. Basically it is an implementation detail. The side effects occurring in that Haskell expression are as real as those occurring in D. (GHC actually implements this as updating a mutable memory location under the hood, but it does not really matter.)
 with monads,

What is done to main behind the scenes in order to execute the program is most definitely side-effecting.

I agree with you, but that is done by the runtime in a safe way and is mostly out of the user's hands. ...

I'd agree with 'mostly safe'. We don't/can't know how the real world works, and it has inherent limitations not shared by idealized programming languages. (and vice versa!)
 (i.e., the academic definition of purity).

I wouldn't go that far.

Perhaps that may go too far, as academics love to obfuscate topics with a bunch of extraneous cruft,

I take issue with this statement. I meant, I wouldn't assume 'the academic definition of purity' is a thing.

I don't know what you mean by this. By academic definition, I meant the definition of functional purity that is generally agreed-upon by the CS academia. ...

Me too. I just don't think there is a notion of functional purity applying equally well to all programming languages. Eg. in Spec# [Pure] precludes heap allocations IIRC, but pure functional languages can most definitely allocate heap storage when evaluating an expression.
 but the fact remains that purity means:

 1. No modification of local or global state (side-effects)
 2. No dependence on global mutable state.

What does this statement quantify over? Eg, where is the abstraction boundary?

Again, can you be more clear? My meaning was that for a function to be pure, in a functional programming sense, it must adhere to these rules.

At the lowest level of abstraction, no function call will adhere to these rules, since the machine changes its state. Then there is the memory allocator that carries around global state. The perception of whether or not this allocator is pure will likely depend on how much access to this global state is given to the user program. etc. How pure or impure a given operation is in a given language will sometimes depend on the entire language design. In order to resolve the topic, I guess it is useful to state which properties of 'pure' functions, we want to rely on. (Such properties are also easier to translate between programming languages, but this is still moot.)
Aug 03 2013
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 08/03/2013 06:47 PM, Timon Gehr wrote:
 Well, no. It is by design. All purity really means is that the part of
 the existing store not reachable by following references in the
 arguments will not be mutated.

s/mutated/accessed/
Aug 03 2013
prev sibling next sibling parent "anonymous" <anonymous example.com> writes:
On Saturday, 3 August 2013 at 15:59:22 UTC, monarch_dodra wrote:
 I'm a bit confused about where we draw the line with purity, 
 and memory.

 For example, take this "simple" function:

 //----
 char[] getMutableHello() pure
 {
     return "hello".dup;
 }
 //----

 This seems like it will *always* create the same result, yet at 
 the same time, it calls the GC. "dup" could fail, amongst 
 others, meaning there is failed purity.

 Is this OK?

When `dup` fails, some Exception/Error is thrown and the function won't return. So, purity is not affected, I think. There's also `nothrow` when you want to rule out exceptions.
 :::::::::::::::::::::::::::::::::::::::::

 Where does purity mean when you are talking about 
 slices/pointers? Simply that they *point*/*reference* the same 
 payload? I mean:

 void main()
 {
     auto a = getMutableHello();
     auto b = getMutableHello();
     assert(a == b); //OK
     assert(a is b); //Derp :/
 }

 Did getMutableHello just violate its purity promise?

I'd say `pure` doesn't promise equality of memory addresses. I imagine it would be rather annoying if you couldn't `new` in pure functions.
 :::::::::::::::::::::::::::::::::::::::::

 Another thing that bothers me, again, when interfacing with the 
 GC, is "capacity". It is currently marked as pure, but I 
 believe this is wrong: The GC can in-place extend the "useable" 
 memory of a dynamic array. This means all referencing slices 
 will be affected, yet un-modified. This means that calling 
 "s.capacity" depends on the global state of the GC:

 //----
     auto s1 = new ubyte[](12_000);
     auto bck = s1;
     size_t cap = s1.capacity;
     s1.reserve(13_000);
     assert(s1 is bck); //Apparently, s1 is not changed.
     assert(cap == s1.capacity); //This fails, yet capacity is 
 pure?
 //----

 Again, is this OK?

When you understand `capacity` as being referenced by the arrays, it's ok. Because then, of course `s1 is bck` even though its capacity changed. And `cap == s1.capacity` fails, because `cap` is a copy of an earlier state.
 :::::::::::::::::::::::::::::::::::::::::

 One last question: Pointers.

 int get(int* p) pure
 {
     return *p;
 }

 void main()
 {
     int i = 0;
     auto p = &i;
     get(p);
 }

 Here, get, to me, is obviously not pure, since it depends on 
 the state of the global "i". *Where* did "get" go wrong? Did I 
 simply "abusively" mark get as pure? Is the "pure" keyword's 
 guarantee simply "weak"?

By passing a pointer to `i`, you explicitly add it to the list of stuff, `get` may access (and alter). Indeed, `pure` by itself only guarantees "weak purity". That means, the function may alter its arguments (and everything reachable from them). To get "strong purity", mark all arguments as const.
 :::::::::::::::::::::::::::::::::::::::::

 To sum up the question, regardless of how the *keyword* pure 
 currently works, my question is "*How* should it behave"? We're 
 currently marking things in Phobos as pure, and I'm worried the 
 only reason we are doing it is that the keyword is lenient, and 
 said functions *aren't* actually pure...

I think all cases you showed work as expected. For `pure` to really shine (strong purity), you need to add some `const` into the mix. See also: http://dlang.org/function.html#pure-functions
Aug 03 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Saturday, 3 August 2013 at 16:47:52 UTC, Timon Gehr wrote:
 On 08/03/2013 05:59 PM, monarch_dodra wrote:
 One last question: Pointers.

 int get(int* p) pure
 {
     return *p;
 }

 void main()
 {
     int i = 0;
     auto p = &i;
     get(p);
 }

 Here, get, to me, is obviously not pure, since it depends on 
 the state
 of the global "i". *Where* did "get" go wrong? Did I simply 
 "abusively"
 mark get as pure? Is the "pure" keyword's guarantee simply 
 "weak"?
 ...

Yes, it's weak.

It depends on whether you think a pointer dereference is pure or not (I don't know the answer). That aside, as long as get doesn't modify the value at *p or change what p points to, this is strongly pure (i.e., the academic definition of purity).
Aug 03 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Saturday, 3 August 2013 at 19:07:49 UTC, Meta wrote:
 On Saturday, 3 August 2013 at 16:47:52 UTC, Timon Gehr wrote:
 On 08/03/2013 05:59 PM, monarch_dodra wrote:
 One last question: Pointers.

 int get(int* p) pure
 {
    return *p;
 }

 void main()
 {
    int i = 0;
    auto p = &i;
    get(p);
 }

 Here, get, to me, is obviously not pure, since it depends on 
 the state
 of the global "i". *Where* did "get" go wrong? Did I simply 
 "abusively"
 mark get as pure? Is the "pure" keyword's guarantee simply 
 "weak"?
 ...

Yes, it's weak.

It depends on whether you think a pointer dereference is pure or not (I don't know the answer). That aside, as long as get doesn't modify the value at *p or change what p points to, this is strongly pure (i.e., the academic definition of purity).

Thank the 3 of you for your answers. I think I had a wrong preconception of what pure is. I think this cleared most of it up.
Aug 03 2013
prev sibling next sibling parent "Lars T. Kyllingstad" <public kyllingen.net> writes:
On Saturday, 3 August 2013 at 21:19:35 UTC, monarch_dodra wrote:

 Thank the 3 of you for your answers. I think I had a wrong 
 preconception of what pure is. I think this cleared most of it 
 up.

You may also find this discussion interesting, if you haven't already seen it: http://forum.dlang.org/thread/i7bp8o$6po$1 digitalmars.com It basically led to our current definition of "pure".
Aug 03 2013
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Saturday, 3 August 2013 at 21:19:35 UTC, monarch_dodra wrote:
 On Saturday, 3 August 2013 at 19:07:49 UTC, Meta wrote:
 On Saturday, 3 August 2013 at 16:47:52 UTC, Timon Gehr wrote:
 On 08/03/2013 05:59 PM, monarch_dodra wrote:
 One last question: Pointers.

 int get(int* p) pure
 {
   return *p;
 }

 void main()
 {
   int i = 0;
   auto p = &i;
   get(p);
 }

 Here, get, to me, is obviously not pure, since it depends on 
 the state
 of the global "i". *Where* did "get" go wrong? Did I simply 
 "abusively"
 mark get as pure? Is the "pure" keyword's guarantee simply 
 "weak"?
 ...

Yes, it's weak.

It depends on whether you think a pointer dereference is pure or not (I don't know the answer). That aside, as long as get doesn't modify the value at *p or change what p points to, this is strongly pure (i.e., the academic definition of purity).

Thank the 3 of you for your answers. I think I had a wrong preconception of what pure is. I think this cleared most of it up.

Is there anywhere formal defining D's pure (weak vs strong etc.)? A page in the wiki perhaps? Imagine someone new coming to D and being confused by what our purity system is. It would suck to only be able to give an ad-hoc answer or link them to a previous discussion. I would offer but I don't really understand it myself.
Aug 03 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Saturday, 3 August 2013 at 23:04:14 UTC, Timon Gehr wrote:
 It depends on whether you think a pointer dereference is pure 
 or not  (I don't know the answer).

It is pure in D, but I guess you are not referring to that. What's your understanding of purity in this context?

I'm thinking of when a pointer points to an invalid location (0x00000000 or similar) and is dereferenced. I'm not sure if that would be considered impure or not, i.e., causes side effects.
 That aside, as long as get doesn't modify the
 value at *p or change what p points to, this is strongly pure

Modification and dereference within a Haskell expression: import Data.STRef import Control.Monad.ST x = runST $ do x <- newSTRef 0 writeSTRef x 1 v <- readSTRef x return v main = print x

I apologize, as I don't know how familiar you are with Haskell, so forgive me if I'm telling you something you already know. That code is 100% pure and side-effect free; no variables are being modified. Haskell only simulates side-effects with monads, and do-notation (syntwhat you use in this example) which is syntactic sugar.
 (i.e., the academic definition of purity).

I wouldn't go that far.

Perhaps that may go too far, as academics love to obfuscate topics with a bunch of extraneous cruft, but the fact remains that purity means: 1. No modification of local or global state (side-effects) 2. No dependence on global mutable state.
Aug 03 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Sunday, 4 August 2013 at 02:05:55 UTC, Timon Gehr wrote:
 no variables are being modified.

Which I didn't claim. A reference is dereferenced and the contents of the referenced slot are replaced. Then the reference is dereferenced again to read the modified value out.

I'm confused about what your point is now. Are you trying to convince me that dereferencing p and modifying the value it points to are side-effect free? Of course you can do it in Haskell with some wizardry, but D doesn't do any of that.
 Haskell only simulates side-effects

What tells you that D does not 'simulate' mutable state?

I see what you're getting at. I thought I had a good answer before I really thought about your question. I can't think of any way to prove that a language is not simply simulating mutable state off the top of my head. Do you actually have an answer to this question, or were you just making a point?
 with monads,

What is done to main behind the scenes in order to execute the program is most definitely side-effecting.

I agree with you, but that is done by the runtime in a safe way and is mostly out of the user's hands.
 (i.e., the academic definition of purity).

I wouldn't go that far.

Perhaps that may go too far, as academics love to obfuscate topics with a bunch of extraneous cruft,

I take issue with this statement. I meant, I wouldn't assume 'the academic definition of purity' is a thing.

I don't know what you mean by this. By academic definition, I meant the definition of functional purity that is generally agreed-upon by the CS academia.
 but the fact remains that purity means:

 1. No modification of local or global state (side-effects)
 2. No dependence on global mutable state.

What does this statement quantify over? Eg, where is the abstraction boundary?

Again, can you be more clear? My meaning was that for a function to be pure, in a functional programming sense, it must adhere to these rules.
Aug 03 2013
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Saturday, 3 August 2013 at 23:15:25 UTC, John Colvin wrote:
 On Saturday, 3 August 2013 at 21:19:35 UTC, monarch_dodra wrote:
 On Saturday, 3 August 2013 at 19:07:49 UTC, Meta wrote:
 On Saturday, 3 August 2013 at 16:47:52 UTC, Timon Gehr wrote:
 On 08/03/2013 05:59 PM, monarch_dodra wrote:
 One last question: Pointers.

 int get(int* p) pure
 {
  return *p;
 }

 void main()
 {
  int i = 0;
  auto p = &i;
  get(p);
 }

 Here, get, to me, is obviously not pure, since it depends 
 on the state
 of the global "i". *Where* did "get" go wrong? Did I simply 
 "abusively"
 mark get as pure? Is the "pure" keyword's guarantee simply 
 "weak"?
 ...

Yes, it's weak.

It depends on whether you think a pointer dereference is pure or not (I don't know the answer). That aside, as long as get doesn't modify the value at *p or change what p points to, this is strongly pure (i.e., the academic definition of purity).

Thank the 3 of you for your answers. I think I had a wrong preconception of what pure is. I think this cleared most of it up.

Is there anywhere formal defining D's pure (weak vs strong etc.)? A page in the wiki perhaps? Imagine someone new coming to D and being confused by what our purity system is. It would suck to only be able to give an ad-hoc answer or link them to a previous discussion. I would offer but I don't really understand it myself.

Woops, forgot about this: http://klickverbot.at/blog/2012/05/purity-in-d/ Is it still up-to-date?
Aug 04 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Aug 03, 2013 at 09:07:47PM +0200, Meta wrote:
 On Saturday, 3 August 2013 at 16:47:52 UTC, Timon Gehr wrote:
On 08/03/2013 05:59 PM, monarch_dodra wrote:
One last question: Pointers.

int get(int* p) pure
{
    return *p;
}

void main()
{
    int i = 0;
    auto p = &i;
    get(p);
}

Here, get, to me, is obviously not pure, since it depends on the
state of the global "i". *Where* did "get" go wrong? Did I simply
"abusively" mark get as pure? Is the "pure" keyword's guarantee
simply "weak"?
...

Yes, it's weak.

It depends on whether you think a pointer dereference is pure or not (I don't know the answer). That aside, as long as get doesn't modify the value at *p or change what p points to, this is strongly pure (i.e., the academic definition of purity).

I think a pointer dereference is weakly pure. Consider this: int func1(int x) pure { int scratch = x+1; func2(&scratch); return scratch; } void func2(int* x) pure { *x = 1; } Clearly, func1 can be strongly pure, because its input will never change based on any global state, in spite of the fact that func2 is dereferencing pointers. Therefore, func2 is (should be) weakly pure. Now consider this: void func2(int* x) pure { *x = 1; } int y = 2; void main() { func2(&y); } Can func2 still be said to be weakly pure? I say yes, because it cannot access global that that main() isn't already passing in! It is main that's impure, because it's the one that handed a reference to a global to func2. If we move the definition of y inside main, then main could be strongly pure. Which leads us to conclude that the reason main is impure is because it's referencing a non-local variable when it took the address of y. The act of taking addresses and dereferencing pointers does not make code impure; it merely makes them weakly pure as opposed to strongly pure. And weakly pure functions are callable from strongly pure functions, because any changes effected through pointers / references / whatever will never escape the scope of the strongly pure function (the strongly pure function isn't allowed to take an address of a non-local variable, so the weakly pure function will never be able to change anything outside). The outside world will never notice the difference. T -- Designer clothes: how to cover less by paying more.
Aug 03 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Aug 03, 2013 at 12:24:08PM -0700, H. S. Teoh wrote:
[...]
 I think a pointer dereference is weakly pure. Consider this:
 
 	int func1(int x) pure {
 		int scratch = x+1;
 		func2(&scratch);
 		return scratch;
 	}
 
 	void func2(int* x) pure {
 		*x = 1;
 	}
 
 Clearly, func1 can be strongly pure, because its input will never change

Gah, I meant its *output* will never change. T -- This sentence is false.
Aug 03 2013
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, August 03, 2013 23:19:33 monarch_dodra wrote:
 Thank the 3 of you for your answers. I think I had a wrong
 preconception of what pure is. I think this cleared most of it up.

_All_ that pure does by itself is guarantee that the function doesn't access any static or global variables which can be mutated after they're initialized. Where it becomes more entertaining is when the function becomes strongly pure (which at this point requires that all of the functions parameters be immutable or implicitly convertible to immutable - though it really should be when the _arguments_ are immutable or implicitly convertible to immutable and all of the parameters are either const or immutable or implicitly convertible to immutable). At that point, certain optimizations become possible, but what exactly those optimizations are is still something that's up for debate (e.g. when you can get away with converting the return value to a different level of mutability and when you can't). - Jonathan M Davis
Aug 03 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sun, Aug 04, 2013 at 01:15:24AM +0200, John Colvin wrote:
[...]
 Is there anywhere formal defining D's pure (weak vs strong etc.)? A
 page in the wiki perhaps?
 
 Imagine someone new coming to D and being confused by what our
 purity system is. It would suck to only be able to give an ad-hoc
 answer or link them to a previous discussion.
 
 I would offer but I don't really understand it myself.

It's really quite simple once you understand the motivation behind it. Pure (aka "strong" purity) means the return value of the function only depends on its arguments, not on any hidden state, not on any global state, and it has no side-effects. So no static variables, no globals, no side-effects. This is purity as generally understood in functional languages. Now, traditionally, (strong) purity is interpreted to mean that the function cannot use anything with side effects, like assignment statements and mutable variables, since easiest way to ensure that function as a whole has no side-effects is to build it out of primitives that also has no side-effects. The first insight in D, however, is that as long as the function's return value only ever depends on its arguments, and it cannot access any global variables (or cause side-effects like I/O), then it cannot be externally distinguished from a genuinely pure function (in the Haskell sense of pure). The fact that the function may be using mutable variables and assignment statements is invisible to the outside world, so for all intents and purposes, it might as well be Haskell-pure. This leads to the convenience in D that it's OK to use mutable variables and assignment statements, etc., that are traditionally prohibited in pure languages, inside a D pure function, as long as the outside world can't tell the difference. So we don't have to go full-blown functional programming inside the function; we can still use loops and arrays and stuff. This makes pure functions much more convenient to write, yet without sacrificing the advantages of true purity. The second insight in D, is that suppose you have a function, let's call it W, that (1) has no internal state, (2) doesn't directly access global variables, and (3) can affect the outside world but only through its arguments (e.g., a pointer, a reference to mutable variables, etc.). Now, clearly, being able to modify external state through its arguments violates the traditional sense of purity. But here's where the insight comes in: suppose we have a strongly pure function as described in the previous paragraph, let's call it F. It has no side-effects, no hidden state, no accessing of global variables, but does have some local variables it uses to calculate its return value. The question is, will F remain strongly pure if it calls W? So let's think about the ramifications of calling W. Since W is able to modify the outside world through its arguments, it seems that F can no longer be pure, since any side-effects caused by W will also implicate F. But if you think about it, the worst that F can do is to pass a reference to a local variable to W. It can't pass a reference to a global variable because it doesn't have any access to a global variable! So whatever side-effect W may have, that side-effect is confined inside the scope of F, and continues to be invisible to the world outside of F. We can therefore conclude that F is *still* strongly pure! Now, the story would be different if W could access global variables -- then its side-effects would be visible outside of F, and so F can no longer be pure. So W still has some restrictions on it, it's just that it's a little more lax than the restrictions on F. So here is where the idea of weak purity comes in. We say that W is "weakly pure", because it violates the traditional definition of purity (can't mutate outside state through reference arguments), but it is still restricted enough that when it's called from a strongly pure function, all of its side-effects are confined inside the local scope of the strongly pure function, and thereby are invisible to the world outside of the strongly pure function. IOW, a weakly pure function is a function that can be called by a strongly pure function without violating the strong purity of the latter. Finally, we make the observation that the distinction between a strongly-pure and weakly-pure function is completely determined by its argument types. A weakly-pure function is still not allowed to access global variables, for example; the only way it can mutate the outside world is if at least one of its arguments is mutable, or contains a reference to some outside state. If all of its arguments are immutable and contain no references, then the function can't actually have any side-effects on the outside world at all, and so it is, in fact, strongly pure. Thus, this allows us to use the "pure" keyword on *both* strongly-pure and weakly-pure functions: the weakly pure functions can be identified by the fact that one or more of their arguments may contain mutable references; the strongly pure functions are the ones whose arguments are immutable (or implicitly castable to immutable, like ints -- since modifying an int argument has no effect on the outside world). Thus, we arrive at our current definition of purity in D. To end, I'd like to mention the reason we want to go through all this tedium to define strongly pure vs. weakly pure: the key insight is that even though weakly pure functions are *not* pure in the traditional sense, they *can* be used as building blocks to build strongly pure functions! This greatly increases the implementation possibilities of strongly pure functions. Not only can we use local variables and assignments in imperative code inside a strongly pure function, we can also be assured that calling weakly-pure functions, which have side-effects, will still maintain our purity! The notion of weak purity assures us that none of the side-effects we use inside the strongly-pure function will ever "leak out" to the outside world. Therefore, we continue to enjoy the benefits of purity-based optimizations, like caching of return values, merging identical subexpressions, and many of the other optimizations that are traditionally restricted only to functional languages. T -- "640K ought to be enough" -- Bill G., 1984. "The Internet is not a primary goal for PC usage" -- Bill G., 1995. "Linux has no impact on Microsoft's strategy" -- Bill G., 1999.
Aug 03 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sun, Aug 04, 2013 at 02:35:38PM +0200, John Colvin wrote:
[...]
 Woops, forgot about this:
 http://klickverbot.at/blog/2012/05/purity-in-d/
 
 Is it still up-to-date?

AFAICT, yes. T -- The computer is only a tool. Unfortunately, so is the user. -- Armaphine, K5
Aug 04 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Saturday, 10 August 2013 at 18:28:07 UTC, H. S. Teoh wrote:
 It's really quite simple once you understand the motivation 
 behind it...

This seems like it would be a good topic for another article.
Aug 10 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Aug 10, 2013 at 08:44:06PM +0200, Meta wrote:
 On Saturday, 10 August 2013 at 18:28:07 UTC, H. S. Teoh wrote:
It's really quite simple once you understand the motivation behind
it...

This seems like it would be a good topic for another article.

:) But there's already one: http://klickverbot.at/blog/2012/05/purity-in-d/ T -- People say I'm arrogant, and so I am!!
Aug 10 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Saturday, 10 August 2013 at 20:23:38 UTC, H. S. Teoh wrote:
 But there's already one: 
 http://klickverbot.at/blog/2012/05/purity-in-d/

Humm, don't know how I missed that. I think somebody linked this a few days ago in a different thread, too.
Aug 10 2013
prev sibling parent "Meta" <jared771 gmail.com> writes:
On Sunday, 11 August 2013 at 00:31:30 UTC, Meta wrote:
 Humm, don't know how I missed that. I think somebody linked 
 this a few days ago in a different thread, too.

No, it was in this very thread and I just forgot about it.
Aug 10 2013