www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Memory allocation purity

reply "Brian Schott" <briancschott gmail.com> writes:
What is the plan for the "pure"-ity of memory management?

Right now the "new" operator is considered to be pure even though 
it is not, but related functinos like malloc, GC.addRange, 
GC.removeRange, and others are not.

This prevents large portions of std.allocator from being pure. 
This then prevents any containers library built on std.allocator 
from being pure, which does the same for any funcions and data 
structures written using those containers.

If malloc can never be considered pure, even when hidden behind 
an allocator, why can it be considered pure when hidden behind 
the GC?
May 14 2014
next sibling parent "w0rp" <devw0rp gmail.com> writes:
On Wednesday, 14 May 2014 at 22:42:47 UTC, Brian Schott wrote:
 What is the plan for the "pure"-ity of memory management?

 Right now the "new" operator is considered to be pure even 
 though it is not, but related functinos like malloc, 
 GC.addRange, GC.removeRange, and others are not.

 This prevents large portions of std.allocator from being pure. 
 This then prevents any containers library built on 
 std.allocator from being pure, which does the same for any 
 funcions and data structures written using those containers.

 If malloc can never be considered pure, even when hidden behind 
 an allocator, why can it be considered pure when hidden behind 
 the GC?

I think even C malloc should be considered pure. True, it affects global state by allocating memory, but it never changes existing values, it just allows for new values. free is pure because it isn't side-effecting, it deallocates what you give it. That's just my perspective on it though, others might have other views on it.
May 14 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 14 May 2014 22:42:46 +0000
Brian Schott via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 What is the plan for the "pure"-ity of memory management?

 Right now the "new" operator is considered to be pure even though
 it is not, but related functinos like malloc, GC.addRange,
 GC.removeRange, and others are not.

 This prevents large portions of std.allocator from being pure.
 This then prevents any containers library built on std.allocator
 from being pure, which does the same for any funcions and data
 structures written using those containers.

 If malloc can never be considered pure, even when hidden behind
 an allocator, why can it be considered pure when hidden behind
 the GC?

I think malloc should definitely be considered pure for the same reasons that new is considered pure. I don't know about the other memory management functions though. I'd really have to think through their side effects to have an opinion on them. If we can make them pure though, that would certainly help with ensuring that allocators can be pure. - Jonathan M Davis
May 14 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 3:42 PM, Brian Schott wrote:
 If malloc can never be considered pure, even when hidden behind an allocator,

It cannot be pure as long as it can fail.
 why can it be considered pure when hidden behind the GC?

Because GC failures are not recoverable, so the pure allocation cannot fail.
May 14 2014
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 5:44 PM, Brian Schott wrote:
 Can we say that Mallocator failures are not recoverable?

malloc itself does not have that property. But you could design a wrapper for it that did.
May 14 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/14, 6:11 PM, Brian Schott wrote:
 On Thursday, 15 May 2014 at 00:48:52 UTC, Walter Bright wrote:
 On 5/14/2014 5:44 PM, Brian Schott wrote:
 Can we say that Mallocator failures are not recoverable?

malloc itself does not have that property. But you could design a wrapper for it that did.

I'm concerned specifically with this wrapper: https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L773 We need to make these functions pure if they are going to be usable. Removing the stdlib import and adding private extern (C) { void* malloc(size_t) pure nothrow trusted; void free(void*) pure nothrow trusted; void* realloc(void*, size_t) pure nothrow trusted; } as well as a throwing OutOfMemoryError if they fail should be sufficient, correct?

I think so. A more cautious solution would be to define PureMallocator in addition to Mallocator. Andrei
May 14 2014
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/14, 5:44 PM, Brian Schott wrote:
 On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:
 On 5/14/2014 3:42 PM, Brian Schott wrote:
 If malloc can never be considered pure, even when hidden behind an
 allocator,

It cannot be pure as long as it can fail.
 why can it be considered pure when hidden behind the GC?

Because GC failures are not recoverable, so the pure allocation cannot fail.

Can we say that Mallocator failures are not recoverable?

FWIW std.allocator allows constructing a bunch of small-business allocators for which failure to allocate is entirely legit. The methods of such allocator may be weakly pure. An allocator that ultimately falls back to GCAllocator and "never fails" should be pure - better yet, inferred as such. Andrei
May 14 2014
prev sibling next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 14 May 2014 at 22:42:47 UTC, Brian Schott wrote:
 What is the plan for the "pure"-ity of memory management?

 Right now the "new" operator is considered to be pure even 
 though it is not, but related functinos like malloc, 
 GC.addRange, GC.removeRange, and others are not.

 This prevents large portions of std.allocator from being pure. 
 This then prevents any containers library built on 
 std.allocator from being pure, which does the same for any 
 funcions and data structures written using those containers.

 If malloc can never be considered pure, even when hidden behind 
 an allocator, why can it be considered pure when hidden behind 
 the GC?

Allocating memory through new and malloc should always be pure, I think, because failure either returns null in malloc's case, or throws an error in new's case. As for GC.addRange, GC.removeRange, etc... it's hard to say. These functions definitely alter the state of the GC, but it's all wrapped up in the GC's black box, guaranteed to never escape (I think? I don't know exactly how they're implemented). In the general case, as long as side-effects can be guaranteed to never affect anything outside of a function/class/struct, I think it can probably be pure (D's notion of purity, anyway).
May 14 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I think,
because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.
 or throws an error in new's case.

A non-recoverable error. ^^^^^^^^^^^^^^^
May 14 2014
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 5:56 PM, Meta wrote:
 On Thursday, 15 May 2014 at 00:50:06 UTC, Walter Bright wrote:
 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I think,
because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.
 or throws an error in new's case.

A non-recoverable error. ^^^^^^^^^^^^^^^

If we pretend that there's infinite memory, then malloc will never return null.

And what happens when malloc returns null?
May 14 2014
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/15/14, 6:02 AM, Steven Schveighoffer wrote:
 On Wed, 14 May 2014 20:50:08 -0400, Walter Bright
 <newshound2 digitalmars.com> wrote:

 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I
 think, because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.

Basically, you are saying that malloc must return the same block whenever it's called with the same parameters. This is simply nonsense. null is not special, it's just another block. I'm not saying malloc should be pure based on this, but the possibility that it returns null does not disqualify it.

Null is special - it's a singularity. It can't be subsequently used for constructing a proper object. That makes it different even after we discount for comparing pointers. Andrei
May 15 2014
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:
 On 5/14/2014 3:42 PM, Brian Schott wrote:
 If malloc can never be considered pure, even when hidden 
 behind an allocator,

It cannot be pure as long as it can fail.
 why can it be considered pure when hidden behind the GC?

Because GC failures are not recoverable, so the pure allocation cannot fail.

Malloc is a tricky case. The results it returns are theoretically always unique, and it is referentially transparent if we pretend that we have infinite memory.
May 14 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:
 On 5/14/2014 3:42 PM, Brian Schott wrote:
 If malloc can never be considered pure, even when hidden 
 behind an allocator,

It cannot be pure as long as it can fail.
 why can it be considered pure when hidden behind the GC?

Because GC failures are not recoverable, so the pure allocation cannot fail.

Can we say that Mallocator failures are not recoverable?
May 14 2014
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 15 May 2014 at 00:50:06 UTC, Walter Bright wrote:
 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be 
 pure, I think, because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.
 or throws an error in new's case.

A non-recoverable error. ^^^^^^^^^^^^^^^

If we pretend that there's infinite memory, then malloc will never return null.
May 14 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
On Thursday, 15 May 2014 at 00:48:52 UTC, Walter Bright wrote:
 On 5/14/2014 5:44 PM, Brian Schott wrote:
 Can we say that Mallocator failures are not recoverable?

malloc itself does not have that property. But you could design a wrapper for it that did.

I'm concerned specifically with this wrapper: https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L773 We need to make these functions pure if they are going to be usable. Removing the stdlib import and adding private extern (C) { void* malloc(size_t) pure nothrow trusted; void free(void*) pure nothrow trusted; void* realloc(void*, size_t) pure nothrow trusted; } as well as a throwing OutOfMemoryError if they fail should be sufficient, correct?
May 14 2014
prev sibling next sibling parent "Kapps" <opantm2+spam gmail.com> writes:
On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:
 Because GC failures are not recoverable, so the pure allocation 
 cannot fail.

Is this intentionally the case? I always thought you could handle it with onOutOfMemoryError if you knew that your program could handle running out of memory and free some memory (i.e., cached data) to recover. I've never actually had a use for it myself, so I'm just basing this off of newsgroup discussions I remember (possibly incorrectly) reading.
May 14 2014
prev sibling next sibling parent "Idan Arye" <GenericNPC gmail.com> writes:
On Wednesday, 14 May 2014 at 22:50:10 UTC, w0rp wrote:
 I think even C malloc should be considered pure. True, it 
 affects global state by allocating memory, but it never changes 
 existing values, it just allows for new values. free is pure 
 because it isn't side-effecting, it deallocates what you give 
 it. That's just my perspective on it though, others might have 
 other views on it.

`free` is not pure, because if you have a reference to that memory that reference is no longer valid.
May 14 2014
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 15 May 2014 at 01:33:36 UTC, Idan Arye wrote:
 On Wednesday, 14 May 2014 at 22:50:10 UTC, w0rp wrote:
 I think even C malloc should be considered pure. True, it 
 affects global state by allocating memory, but it never 
 changes existing values, it just allows for new values. free 
 is pure because it isn't side-effecting, it deallocates what 
 you give it. That's just my perspective on it though, others 
 might have other views on it.

`free` is not pure, because if you have a reference to that memory that reference is no longer valid.

It is weakly pure, i.e., it can only affect the world through the parameters given to it (and the state of the computer's memory... but we should ignore that).
May 14 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 14 May 2014 17:00:39 -0700
Walter Bright via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On 5/14/2014 3:42 PM, Brian Schott wrote:
 If malloc can never be considered pure, even when hidden behind an
 allocator,

It cannot be pure as long as it can fail.
 why can it be considered pure when hidden behind the GC?

Because GC failures are not recoverable, so the pure allocation cannot fail.

Then we should create a wrapper for malloc which throws a MemoryError when malloc fails. Then malloc failures would be the same as GC failures. - Jonathan M Davis
May 14 2014
prev sibling next sibling parent reply Adam Sakareassen via Digitalmars-d <digitalmars-d puremagic.com> writes:
For my 2 cents,

The more D allows 'pure' functions to diverge from functional purity the 
less relevant the flag is for compiler optimisations.

I think purity should be defined by what the compiler is allowed to do 
to a function.  The results of all pure functions should be cacheable. 
If the compiler can prove that the arguments to a pure function are 
constant then the function can be run at compile time to get the result.

A more advanced compiler should be able to do a lot of optimisation 
based on the fact that a function is marked pure.  A compiler can often 
prove arguments are constant when a human can't show the same easily. 
Other optimisation parses often expose constants that may be arguments 
to pure functions.

For example, a foreach loop over a small array could be unwound to 
remove the overhead of branching.  The iterator then becomes a constant 
in each segment of the former loop.  If the iterator is the argument to 
a pure function, the entire function call could be eliminated and 
replaced with the result.

By the same reasoning cacheability is important.  A pure function might 
be called within a loop with a parameter that is not altered during the 
loop.  If the compiler knows the function is pure, it can perform the 
calculation before the loop and simply reuse the cached result for each 
iteration.

New and malloc are not really pure.  They return a different result each 
call, and the state of the PC is changed.   However, if the programmer 
knows his function behaves in a pure way, it would be nice if a 
programmer could tell the compiler to go ahead and optimise away the 
function call anyway.  Some kind of “trusted pure” tag would be required 
I guess.

A 'trusted pure' function would be free to allocate memory as it wishes, 
providing it is freed (or left for collection), and the pointer does not 
escape the function.  From the point of view of the calling software the 
function is functionally pure.

My point is that if we are going to allow relaxed purity in D, then the 
definition should be angled towards a performance advantage.  Naturally 
there are quite a number of other advantages of creating pure functions 
besides performance.  If we define what compiler is allowed to do to a 
pure function we make reasoning about pure functions simple.  It even 
opens the idea of 'trusted pure' functions that compiler can't prove are 
pure, because they may do something like call a C routine.  From a 
compilers point of view they could be considered pure because the 
programmer says the compiler is free to eliminate the function call if 
it knows the result.


On 15/05/2014 8:42 AM, Brian Schott via Digitalmars-d wrote:
 What is the plan for the "pure"-ity of memory management?

 Right now the "new" operator is considered to be pure even though it is
 not, but related functinos like malloc, GC.addRange, GC.removeRange, and
 others are not.

 This prevents large portions of std.allocator from being pure. This then
 prevents any containers library built on std.allocator from being pure,
 which does the same for any funcions and data structures written using
 those containers.

 If malloc can never be considered pure, even when hidden behind an
 allocator, why can it be considered pure when hidden behind the GC?

May 14 2014
next sibling parent reply luka8088 <luka8088 owave.net> writes:
On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 05:51:14 +0000
 via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 
 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)" The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence. Even other sources are consistent on this matter, and this is what purity by definition is.
May 15 2014
next sibling parent luka8088 <luka8088 owave.net> writes:
On 15.5.2014. 11:35, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 10:14:48 +0200
 luka8088 via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 
 On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 05:51:14 +0000
 via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)" The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence. Even other sources are consistent on this matter, and this is what purity by definition is.

The reread the paragraph at the top of the section of the documentation that you linked to: "Pure functions are functions which cannot access global or static, mutable state save through their arguments. This can enable optimizations based on the fact that a pure function is guaranteed to mutate nothing which isn't passed to it, and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)." That outright says that pure only _can_ enable functional purity - in particular when the compiler is able to guarantee that the function cannot mutate its arguments. pure itself however means nothing of the sort. The fact that pure functions cannot access global state _is_ the basis for functional purity when combined with parameters that arguments cannot be mutated.

I am aware of weak/strong purity. I am only talking about strong purity now. To quote bearophile: bool randomBit() pure nothrow safe { return (new int[1].ptr) > (new int[1].ptr); } void main() {} "Pure functions are functions which cannot access global or static, mutable state save through their arguments." - no objections here "This can enable optimizations based on the fact that a pure function is guaranteed to mutate nothing which isn't passed to it, and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)." - no arguments where passed to the function, it should always return the same result
 
 If you get hung up on what the concept of functional purity is or what
 you thought pure was before using D, then you're going to have a hard
 time understanding what pure means in D. And yes, it's a bit weird, but
 it comes from the practical standpoint of how to make functional purity
 possible without being too restrictive to be useful. So, it really
 doesn't matter what other sources say about what purity means. That's
 not what D's pure means. D's pure is just a building block for what
 purity normally means. It makes it so that the compiler can detect
 functional purity and then optimize based on it, but it doesn't in and
 of itself have anything to do with functional purity.
 
 If the documentation isn't getting that across, then I guess that it
 isn't clear enough. But I would have thought that the part that said
 "and in cases where the compiler can guarantee that a pure function
 cannot alter its arguments, it can enable full, functional purity"
 would have made it clear that D's pure is _not_ functionally pure by
 itself. The first part of the paragraph says what pure really means:
 "Pure functions are functions which cannot access global or static,
 mutable state save through their arguments." Everything else with
 regards to functional purity is derived from there, but in and of
 itself, that's _all_ that the pure attribute in D means.
 
 See also: http://klickverbot.at/blog/2012/05/purity-in-d/
 
 - Jonathan M Davis
 

Yeah, it does not seem to be clear enough. It comes down to two simple questions: - should you be able to make a strong pure rand() function i D? - if not, why? My answer would be: no, because the result should always be the same. Of course I could be wrong, but my understanding of it fits with what the docs say. I think that answering this questions would clarify a lot!
May 15 2014
prev sibling next sibling parent reply luka8088 <luka8088 owave.net> writes:
On 15.5.2014. 11:45, Don wrote:
 On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
 On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 05:51:14 +0000
 via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)" The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence. Even other sources are consistent on this matter, and this is what purity by definition is.

Please note: D's 'pure' annotation does *not* mean that the function is pure. It means that it is statically verified to be OK to call it from a pure function. The compiler determines if a function is pure, the programmer never does. There are two things going on here, and they are quite distinct. (1) Really the keyword should be something like ' noglobal', rather than 'pure'. It's called pure for historical reasons. To reduce confusion I'll call D's pure ' noglobal' and the functional languages pure ' memoizable'. But it turns out that memoizable isn't actually an interesting property, whereas ' noglobal' is. "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from noglobal. Suppose you have function f(), which calls function g(). If f does not depend on global state, then g must not depend on global state. BUT if f() can be memoizable even if g() is not memoizable. This approach used by D enormously increases the number of functions which can be statically proven to be pure. The nomenclature can create confusion though. (2) Allowing GC activity inside a noglobal function does indeed weaken our ability to memoize. The compiler can still perform memoizing operations on most functions that return GC-allocated memory, but it's more difficult. We don't yet have data on how much of a problem this is. An interesting side-effect of the recent addition of nogc to the language, is that we get this ability back.

Yeah, I read all about weak/string purity and I do understand the background. I was talking about strong purity, maybe I should pointed that out. So, to correct myself: As I understood strong purity implies memoization. Am I correct?
May 15 2014
next sibling parent luka8088 <luka8088 owave.net> writes:
On 15.5.2014. 12:48, Don wrote:
 On Thursday, 15 May 2014 at 10:31:47 UTC, luka8088 wrote:
 On 15.5.2014. 11:45, Don wrote:
 On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
 On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 05:51:14 +0000
 via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)" The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence. Even other sources are consistent on this matter, and this is what purity by definition is.

Please note: D's 'pure' annotation does *not* mean that the function is pure. It means that it is statically verified to be OK to call it from a pure function. The compiler determines if a function is pure, the programmer never does. There are two things going on here, and they are quite distinct. (1) Really the keyword should be something like ' noglobal', rather than 'pure'. It's called pure for historical reasons. To reduce confusion I'll call D's pure ' noglobal' and the functional languages pure ' memoizable'. But it turns out that memoizable isn't actually an interesting property, whereas ' noglobal' is. "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from noglobal. Suppose you have function f(), which calls function g(). If f does not depend on global state, then g must not depend on global state. BUT if f() can be memoizable even if g() is not memoizable. This approach used by D enormously increases the number of functions which can be statically proven to be pure. The nomenclature can create confusion though. (2) Allowing GC activity inside a noglobal function does indeed weaken our ability to memoize. The compiler can still perform memoizing operations on most functions that return GC-allocated memory, but it's more difficult. We don't yet have data on how much of a problem this is. An interesting side-effect of the recent addition of nogc to the language, is that we get this ability back.

Yeah, I read all about weak/string purity and I do understand the background. I was talking about strong purity, maybe I should pointed that out. So, to correct myself: As I understood strong purity implies memoization. Am I correct?

Yes. 'strong pure' means pure in the way that the functional language crowd means 'pure'. 'weak pure' just means doesn't use globals. But note that "strong purity" isn't an official concept, it was just the terminology I used when explain to Walter what I meant. I don't like the term because it's rather misleading -- in reality you could define a whole range of purity strengths (more than just two). The stronger the purity, the more optimizations you can apply.

Ok. Now it is much clearer, thanks.
May 15 2014
prev sibling next sibling parent luka8088 <luka8088 owave.net> writes:
On 15.5.2014. 13:04, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 10:48:07 +0000
 Don via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 
 Yes. 'strong pure' means pure in the way that the functional
 language crowd means 'pure'.
 'weak pure' just means doesn't use globals.

 But note that "strong purity" isn't an official concept, it was
 just the terminology I used when explain to Walter what I meant.
 I don't like the term because it's rather misleading
 -- in reality you could define a whole range of purity strengths
 (more than just two).
 The stronger the purity, the more optimizations you can apply.

Yeah, I agree. The problem is that it always seems necessary to use the terms weak pure to describe the distinction - or maybe I just suck at coming up with a better way to describe it than you did initially. Your recent post in this thread talking about noglobal seems to be a pretty good alternate way to explain it though. Certainly, the term pure throws everyone off at first. - Jonathan M Davis

Yeah, +1. Or isolated, as in "isolated from outer scopes".
May 15 2014
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/15/14, 3:31 AM, luka8088 wrote:
 Yeah, I read all about weak/string purity and I do understand the
 background. I was talking about strong purity, maybe I should pointed
 that out.

 So, to correct myself: As I understood strong purity implies
 memoization. Am I correct?

Yes, as long as you don't rely on distinguishing objects by address. Purity of allocation is frequently assumed by functional languages because without it it would be difficult to get much work done. Then, most functional languages make it difficult or impossible to distinguish values by their address. In D that's easy. A D programmer needs to be aware of that, and I think that's fine. Andrei
May 15 2014
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/15/2014 05:24 PM, Andrei Alexandrescu wrote:
 On 5/15/14, 3:31 AM, luka8088 wrote:
 Yeah, I read all about weak/string purity and I do understand the
 background. I was talking about strong purity, maybe I should pointed
 that out.

 So, to correct myself: As I understood strong purity implies
 memoization. Am I correct?

Yes, as long as you don't rely on distinguishing objects by address. Purity of allocation is frequently assumed by functional languages

Examples?
 because without it it would be difficult to get much work done.

Why?
 Then,
 most functional languages make it difficult or impossible to distinguish
 values by their address.

If it's not impossible because of lack of the concept it's not a pure functional language.
 In D that's easy. A D programmer needs to be
 aware of that, and I think that's fine.


 Andrei

It's not fine: The spec claims that this problem does not exist. http://dlang.org/function.html "... and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)"
May 15 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/15/14, 9:03 AM, Timon Gehr wrote:
 On 05/15/2014 05:24 PM, Andrei Alexandrescu wrote:
 On 5/15/14, 3:31 AM, luka8088 wrote:
 Yeah, I read all about weak/string purity and I do understand the
 background. I was talking about strong purity, maybe I should pointed
 that out.

 So, to correct myself: As I understood strong purity implies
 memoization. Am I correct?

Yes, as long as you don't rely on distinguishing objects by address. Purity of allocation is frequently assumed by functional languages

Examples?

cons 1 2 is equal to cons 1 2
 because without it it would be difficult to get much work done.

Why?

It's rather obvious. You've got to have the ability to create new values in a pure functional programming language.
 Then,
 most functional languages make it difficult or impossible to distinguish
 values by their address.

If it's not impossible because of lack of the concept it's not a pure functional language.

Agreed.
 In D that's easy. A D programmer needs to be
 aware of that, and I think that's fine.


 Andrei

It's not fine: The spec claims that this problem does not exist.

We must fix the spec. Please submit a pull request, thanks. Andrei
May 15 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/15/2014 08:03 PM, Andrei Alexandrescu wrote:
 Purity of allocation is frequently assumed by functional languages

Examples?

cons 1 2 is equal to cons 1 2 ...

I don't see anything whose specification would need to mention 'allocation'.
 because without it it would be difficult to get much work done.

Why?

It's rather obvious. You've got to have the ability to create new values in a pure functional programming language.

This kind of operational reasoning is not essential. Of course, in practice you want to evaluate expressions, but the resulting programs are of the same kind as those of a non-pure language, and can do the same kind of operations. There is not really a distinction to be made at that level of abstraction.
May 15 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/15/14, 2:52 PM, Timon Gehr wrote:
 On 05/15/2014 08:03 PM, Andrei Alexandrescu wrote:
 Purity of allocation is frequently assumed by functional languages

Examples?

cons 1 2 is equal to cons 1 2 ...

I don't see anything whose specification would need to mention 'allocation'.

That's the point. There's no specification of allocation - the evaluator may create two lists or reuse the same, and it's all transparent.
 because without it it would be difficult to get much work done.

Why?

It's rather obvious. You've got to have the ability to create new values in a pure functional programming language.

This kind of operational reasoning is not essential. Of course, in practice you want to evaluate expressions, but the resulting programs are of the same kind as those of a non-pure language, and can do the same kind of operations. There is not really a distinction to be made at that level of abstraction.

I'm afraid I got lost here. Andrei
May 15 2014
prev sibling parent luka8088 <luka8088 owave.net> writes:
On 15.5.2014. 17:24, Andrei Alexandrescu wrote:
 On 5/15/14, 3:31 AM, luka8088 wrote:
 Yeah, I read all about weak/string purity and I do understand the
 background. I was talking about strong purity, maybe I should pointed
 that out.

 So, to correct myself: As I understood strong purity implies
 memoization. Am I correct?

Yes, as long as you don't rely on distinguishing objects by address. Purity of allocation is frequently assumed by functional languages because without it it would be difficult to get much work done. Then, most functional languages make it difficult or impossible to distinguish values by their address. In D that's easy. A D programmer needs to be aware of that, and I think that's fine. Andrei

Hm, this does not seem right. safe prevents you from taking the address of of a value, as stated in http://dlang.org/function.html#safe-functions , shouldn't pure do the same? Reading again through the safe docs it seems to me that purity (both strong and weak) should imply safe. I have seen many claims that in D pure means something else from what it means in functional languages and I think that it is too bad if there is not going to be functional language alike purity in D. I have not seen any example of something that can't be forbidden by the compiler if such support would considered.
May 15 2014
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/15/2014 11:45 AM, Don wrote:
 "No global state" is a deep, transitive property of a function.
 "Memoizable" is a superficial supersetextra

Why? A memoizable function is still memoizable if it is changed internally to memoize values in global memory, for example.
 property which the compiler
 can trivially determine from  noglobal.

May 15 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/15/2014 9:07 AM, Timon Gehr wrote:
 Why? A memoizable function is still memoizable if it is changed internally to
 memoize values in global memory, for example.

I doubt a compiler could prove it was pure.
May 15 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/15/2014 11:33 PM, Walter Bright wrote:
 On 5/15/2014 9:07 AM, Timon Gehr wrote:
 Why? A memoizable function is still memoizable if it is changed
 internally to
 memoize values in global memory, for example.

I doubt a compiler could prove it was pure.

Yes, that was actually my point. Memoizable is actually a non-trivial property. (But note that while a compiler cannot in general discover a proof, it could just _check_ a supplied proof.)
May 15 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/15/2014 2:41 PM, Timon Gehr wrote:
 On 05/15/2014 11:33 PM, Walter Bright wrote:
 On 5/15/2014 9:07 AM, Timon Gehr wrote:
 Why? A memoizable function is still memoizable if it is changed
 internally to
 memoize values in global memory, for example.

I doubt a compiler could prove it was pure.

Yes, that was actually my point. Memoizable is actually a non-trivial property. (But note that while a compiler cannot in general discover a proof, it could just _check_ a supplied proof.)

If the compiler cannot mechanically verify purity, the notion of purity is rather useless, since as this thread shows it is incredibly easy for humans to be mistaken about it.
May 15 2014
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/15/2014 4:00 PM, H. S. Teoh via Digitalmars-d wrote:
 What if the language allowed the user to supply a proof of purity, which
 can be mechanically checked?

I think those sorts of things are PhD research topics. It's a bit beyond the scope of what we're trying to do with D.
May 15 2014
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/15/2014 5:20 PM, bearophile wrote:
 Walter Bright:

 I think those sorts of things are PhD research topics. It's a bit beyond the
 scope of what we're trying to do with D.

Perhaps yes. Yet, the Whiley language is not PhD-level, and it's inspiring :) Things like value range propagation show that even rather small amounts of statically known information can give back plenty of value to D!

Yes, the VRP has been a nice win for D. No other language does it.
May 15 2014
parent Walter Bright <newshound2 digitalmars.com> writes:
On 5/16/2014 1:54 AM, Araq wrote:
 Yes, the VRP has been a nice win for D. No other language does it.

I don't know why you keep saying things like that, you don't know all the languages out there. Nimrod does it too fwiw...

I having trouble finding it in the spec: http://nimrod-lang.org/manual.html Can you please point me to it?
May 16 2014
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 05/16/2014 01:56 AM, Walter Bright wrote:
 On 5/15/2014 4:00 PM, H. S. Teoh via Digitalmars-d wrote:
 What if the language allowed the user to supply a proof of purity, which
 can be mechanically checked?

I think those sorts of things are PhD research topics.

Well, feasibility has long ago been demonstrated and I hope those ideas will eventually see general adoption.
 It's a bit beyond the scope of what we're trying to do with D.

Sure, but it still makes sense to be aware of and think about what would be possible. (Otherwise it is too tempting to get fully sold on inferior technology, based on the mistaken assumption that there is no way to do significantly better.)
May 16 2014
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/16/2014 01:00 AM, H. S. Teoh via Digitalmars-d wrote:
 On Thu, May 15, 2014 at 03:22:25PM -0700, Walter Bright via Digitalmars-d
wrote:
 On 5/15/2014 2:41 PM, Timon Gehr wrote:
 On 05/15/2014 11:33 PM, Walter Bright wrote:
 On 5/15/2014 9:07 AM, Timon Gehr wrote:
 Why? A memoizable function is still memoizable if it is changed
 internally to memoize values in global memory, for example.

I doubt a compiler could prove it was pure.

Yes, that was actually my point. Memoizable is actually a non-trivial property. (But note that while a compiler cannot in general discover a proof, it could just _check_ a supplied proof.)

If the compiler cannot mechanically verify purity, the notion of purity is rather useless, since as this thread shows it is incredibly easy for humans to be mistaken about it.

What if the language allowed the user to supply a proof of purity, which can be mechanically checked? Just rephrasing what Timon said, though -- I've no idea how such a thing might be implemented. You'd need some kind of metalanguage for writing the proof in, perhaps inside a proof block attached to the function declaration, that can be mechanically verified to be correct.

Yes, either that or one could even just implement it in the existing language by introducing types for evidence, and basic termination checking. eg. http://dpaste.dzfl.pl/33018edab028 (This is a really basic example. Templates or more language features could be used to simplify some of the more tedious steps, but I think it illustrates well the basic ideas. Maybe there are some small mistakes because I didn't find the time to actually implement the checker.)
 Alternatively, if only one or two statements are causing trouble, the
 proof can provide mechanically checkable evidence just for those
 specific statements.

 The metalanguage must be mechanically checkable, of course. But this may
 be more plausible than it sounds -- for example, solutions to certain
 NP-complete problems are verifiable within a far shorter time than it
 would take to actually solve said problem.

Indeed checking whether there is a proof of some fact up to some specific length N for a powerful enough logic is an NP-complete problem. (If N is encoded in unary.)
 This suggests that perhaps,
 while the purity of an arbitrary piece of code is, in general,
 infeasible for the compiler to mechanically prove, it may be possible in
 some cases that the compiler can mechanically verify a user-supplied
 proof, and thus provide the same guarantees as it would for
 directly-provable code.


 T

In fact, this would cover most cases. Usually there is some checkable reason why a piece of code is correct (because otherwise it would not have been invented in the first place.)
May 16 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/16/14, 4:53 AM, Timon Gehr wrote:
 On 05/16/2014 01:00 AM, H. S. Teoh via Digitalmars-d wrote:
 On Thu, May 15, 2014 at 03:22:25PM -0700, Walter Bright via
 Digitalmars-d wrote:
 On 5/15/2014 2:41 PM, Timon Gehr wrote:
 On 05/15/2014 11:33 PM, Walter Bright wrote:
 On 5/15/2014 9:07 AM, Timon Gehr wrote:
 Why? A memoizable function is still memoizable if it is changed
 internally to memoize values in global memory, for example.

I doubt a compiler could prove it was pure.

Yes, that was actually my point. Memoizable is actually a non-trivial property. (But note that while a compiler cannot in general discover a proof, it could just _check_ a supplied proof.)

If the compiler cannot mechanically verify purity, the notion of purity is rather useless, since as this thread shows it is incredibly easy for humans to be mistaken about it.

What if the language allowed the user to supply a proof of purity, which can be mechanically checked? Just rephrasing what Timon said, though -- I've no idea how such a thing might be implemented. You'd need some kind of metalanguage for writing the proof in, perhaps inside a proof block attached to the function declaration, that can be mechanically verified to be correct.

Yes, either that or one could even just implement it in the existing language by introducing types for evidence, and basic termination checking. eg. http://dpaste.dzfl.pl/33018edab028

Typo: int_leibiz_equality :o). -- Andrei
May 16 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/16/2014 07:41 PM, Andrei Alexandrescu wrote:
 On 5/16/14, 4:53 AM, Timon Gehr wrote:
 ...

 Yes, either that or one could even just implement it in the existing
 language by introducing types for evidence, and basic termination
 checking.

 eg. http://dpaste.dzfl.pl/33018edab028


 On 5/16/14, 4:53 AM, Timon Gehr wrote:
 (This is a really basic example. Templates or more language features
 could be used to simplify some of the more tedious steps, but I think
 it illustrates well the basic ideas. Maybe there are some small mistakes
 because I didn't find the time to actually implement the checker.)

 Typo: int_leibiz_equality :o). -- Andrei

If that is everything, then I am in good shape! :o)
May 17 2014
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 05/17/2014 09:29 PM, Timon Gehr wrote:

 Typo: int_leibiz_equality :o). -- Andrei

If that is everything, then I am in good shape! :o)

It could be argued though, that this axiom was not too aptly named in the first place, because it describes the indiscernibility of identicals instead of the identity of indiscernibles.
May 17 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/15/2014 2:45 AM, Don wrote:
 An interesting side-effect of the recent addition of  nogc to the language, is
 that we get this ability back.

I hadn't thought of that. Pretty cool!
May 15 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/15/14, 11:03 AM, Walter Bright wrote:
 On 5/15/2014 2:45 AM, Don wrote:
 An interesting side-effect of the recent addition of  nogc to the
 language, is
 that we get this ability back.

I hadn't thought of that. Pretty cool!

Yah, that's unexpected in a nice way. -- Andrei
May 15 2014
parent Walter Bright <newshound2 digitalmars.com> writes:
On 5/15/2014 4:32 PM, Andrei Alexandrescu wrote:
 On 5/15/14, 11:03 AM, Walter Bright wrote:
 On 5/15/2014 2:45 AM, Don wrote:
 An interesting side-effect of the recent addition of  nogc to the
 language, is
 that we get this ability back.

I hadn't thought of that. Pretty cool!

Yah, that's unexpected in a nice way. -- Andrei

Nice to have a positive surprise!
May 15 2014
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 05/15/2014 03:06 PM, "Ola Fosheim Grøstad" 
<ola.fosheim.grostad+dlang gmail.com>" wrote:
 On Thursday, 15 May 2014 at 12:37:22 UTC, w0rp wrote:
 To consider the design of pure, you must first consider that you
 cannot add functional purity to an imperative language.

Of course you can. Functional languages execute in an "imperative context". That's why you need monads. ...

Strictly speaking you don't "need" monads, they are sometimes just an adequate way of structuring a program.
 The term "pure function" is only needed in a non-functional language.
 Applicative/functional languages only have mathematical functions, no
 need for the term "pure" there.

In discussions about e.g. Haskell, it is often used to denote an expression of a specific form inside a `stateful' DSL. E.g. if "η" is the unit of some monad, then (η v) is sometimes called a "pure value", while values of other forms are not called pure.
May 15 2014
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/15/2014 02:57 PM, Steven Schveighoffer wrote:
 On Thu, 15 May 2014 02:50:05 -0400, Ola Fosheim Grøstad
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
 A little example of D purity (this compiles):

 bool randomBit() pure nothrow  safe {
     return (new int[1].ptr) > (new int[1].ptr);
 }

Yes, and then you may as well allow a random generator with private globals. Because memoing is no longer sound anyway.

This has nothing to do with allocators being pure. They must be pure as a matter of practicality. The issue that allows the above anomaly is using the address of something. There is a reason functional languages do not allow these types of things. But in functional languages, allocating is allowed. ...

Not really, allocation is just an implementation detail. The computational language is meaningful independent of how you might achieve evaluation of expressions. I can in principle evaluate an expression of such a language on paper without managing a separate store, even though this usually will help efficiency. Functional programming languages are not about taking away features from a procedural core language. They are based on the idea that the fundamental operation is substitution of terms.
 To be honest, code that would exploit such an anomaly is only ever used
 in "proof" exercises, and never in real code.

Hashtables are quite real.
 I don't think it's an issue.

 -Steve

This is the issue: On Thu, 15 May 2014 10:48:07 +0000 Don via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 Yes. 'strong pure' means pure in the way that the functional
 language crowd means 'pure'.
 'weak pure' just means doesn't use globals.


There is no way to make that claim precise in an adequate way such that it is correct.
May 15 2014
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 05/15/2014 07:41 PM, Steven Schveighoffer wrote:
 Not really, allocation is just an implementation detail. The
 computational language is meaningful independent of how you might
 achieve evaluation of expressions. I can in principle evaluate an
 expression of such a language on paper without managing a separate
 store, even though this usually will help efficiency.

 Functional programming languages are not about taking away features
 from a procedural core language. They are based on the idea that the
 fundamental operation is substitution of terms.

But they do not deal in explicit pointers.

(Well, http://hackage.haskell.org/package/base-4.7.0.0/docs/Foreign-Marshal Alloc.html#v:malloc )
 Otherwise, that's a can of
 worms that would weaken the guarantees, similar to how D's guarantees
 are weakened.
 ...

The concept of a 'pointer' to some primitive value does not have a meaning in such languages. Every value is an "rvalue".
 We have no choice in D, we must accept that explicit pointers are used.
 ...

We could e.g. ban comparing immutable references for identity / in-memory order.
 To be honest, code that would exploit such an anomaly is only ever used
 in "proof" exercises, and never in real code.

Hashtables are quite real.

Pretend I'm ignorant, what does this imply? ...

E.g. order of iteration may be dependent on in-memory order of keys and the 'same' keys might occur multiple times.
 This is the issue:

 On Thu, 15 May 2014 10:48:07 +0000
 Don via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 Yes. 'strong pure' means pure in the way that the functional
 language crowd means 'pure'.
 'weak pure' just means doesn't use globals.


There is no way to make that claim precise in an adequate way such that it is correct.

This doesn't help, I'm lost with this statement. -Steve

The issue is that there are apparently different expectations about what the keyword is supposed to do.
May 15 2014
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever automatically
 memoize strongly pure function results by compiler. A very practical
 concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei
May 15 2014
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 05/19/2014 09:03 PM, Dicebot wrote:
 immutable(Object*) alloc() pure
 {
      return new Object();
 }

 bool oops() pure
 {
      auto a = alloc();
      auto b = alloc();
      return a is b;
 }

 This is a snippet that will always return `true` if memoization is at
 work and `false` if strongly pure function will get actually called
 twice. If changing result of your program because of silently enabled
 compiler optimization does not indicate a broken compiler I don't know
 what does.

Furthermore, it may not at all be obvious that this is happening: After all, purity can be inferred for template-heavy code, and comparing addresses will not prevent purity inference.
May 19 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 01:33:34 +0000
Idan Arye via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Wednesday, 14 May 2014 at 22:50:10 UTC, w0rp wrote:
 I think even C malloc should be considered pure. True, it
 affects global state by allocating memory, but it never changes
 existing values, it just allows for new values. free is pure
 because it isn't side-effecting, it deallocates what you give
 it. That's just my perspective on it though, others might have
 other views on it.

`free` is not pure, because if you have a reference to that memory that reference is no longer valid.

But does that really matter from the perspective of pure? That's really more of an safety issue. There might be some way that that violates purtiy, but I can't think of one at the moment. free can't be strongly pure, because it's arguments couldn't be immutable (or even const) without violating the type system, but I _think_ that it's fine for free to be weakly pure. It's quite possible that I'm missing something though. - Jonathan M Davis
May 14 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 01:25:52 +0000
Kapps via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:
 Because GC failures are not recoverable, so the pure allocation
 cannot fail.

Is this intentionally the case? I always thought you could handle it with onOutOfMemoryError if you knew that your program could handle running out of memory and free some memory (i.e., cached data) to recover. I've never actually had a use for it myself, so I'm just basing this off of newsgroup discussions I remember (possibly incorrectly) reading.

It's intended that all Errors be considered unrecoverable. You can catch them when necessary to try and do cleanup, but that's fairly risky, and you should probably only do it when you're very sure of what's going on (which generally means that the Error was thrown very close to where you're catching it). There's no guarantee that automatic cleanup occurs when Errors are thrown (unlike with Exceptions), so when an Error is thrown, the program tends to be in a weird state on top of the weird state that caused the Error to be thrown in the first place. In theory, you could catch an OutOfMemoryError very close to where it was thrown and deal with it, but that's really not what was intended. - Jonathan M Davis
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 02:49:28 UTC, Adam Sakareassen via 
Digitalmars-d wrote:
 The more D allows 'pure' functions to diverge from functional 
 purity the less relevant the flag is for compiler optimisations.

 By the same reasoning cacheability is important.  A pure 
 function might be called within a loop with a parameter that is 
 not altered during the loop.  If the compiler knows the 
 function is pure, it can perform the calculation before the 
 loop and simply reuse the cached result for each iteration.

Yep, purity implies memoing. Malloc and new are not pure because they return objects that can be differentiated by address. Malloc and new are random generators in that sense. So to make them pure you will have to put a ban on taking address, comparing address etc on the objects... However mmap to a fixed address is pure if it throws an exception on failure because the exception bypass the call site of the pure function (pure functions should not catch side effect exceptions). Returning null does not make a function impure. Pure functions may return bottom (like division by zero). Pure in D seems pointless to me.
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 05:51:16 UTC, Ola Fosheim Grøstad 
wrote:
 However mmap to a fixed address is pure if it throws an 
 exception on failure because the exception bypass the call site 
 of the pure function (pure functions should not catch side 
 effect exceptions).

This of course presumes a transactional view, that the transaction is the context of purity and that flaws in purity unwinds all changes and thus abort the transaction (the try block). If the result of a series of pure function calls can be used to flip a coin within a transaction, then those functions cannot be considered pure in any meaningful sense.
May 14 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Ola Fosheim Grøstad:

 Pure in D seems pointless to me.

If you start using pure in D you see it's like const: it allows you to remove certain kinds of your mistakes from the code, and it makes it more easy to reason about the code. You can use mutability inside a strongly pure function. This is a very good. Bye, bearophile
May 14 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Ola Fosheim Grøstad:

 If the result of a series of pure function calls can be used to 
 flip a coin within a transaction, then those functions cannot 
 be considered pure in any meaningful sense.

A little example of D purity (this compiles): bool randomBit() pure nothrow safe { return (new int[1].ptr) > (new int[1].ptr); } void main() {} Bye, bearophile
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 06:24:30 UTC, bearophile wrote:
 If you start using pure in D you see it's like const: it allows 
 you to remove certain kinds of your mistakes from the code, and 
 it makes it more easy to reason about the code.

As lint like functionality, yes.
 You can use mutability inside a strongly pure function. This is 
 a very good.

Local mutability does not affect purity, it is the pre and post conditions at the call site that matters.
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
 A little example of D purity (this compiles):

 bool randomBit() pure nothrow  safe {
     return (new int[1].ptr) > (new int[1].ptr);
 }

Yes, and then you may as well allow a random generator with private globals. Because memoing is no longer sound anyway.
May 14 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 05:51:14 +0000
via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 06:59:08 UTC, Jonathan M Davis via 
Digitalmars-d wrote:
 And it _definitely_ has nothing to do with functional purity.

Which makes it pointless and misleading.
 Now, combined with other information, you _can_ get functional 
 purity out it -
 e.g. if all the parameters to a function are immutable, then it 
 _is_
 functionally pure, and optimizations requiring functional 
 purity can be done
 with that function.

No, you can't say it is functionally pure if you can flip a coin with a pure function. To do that you would need a distinction between "prove pure" and "assume pure" as well as having immutable reference types that ban identity comparison.
 So, no, purity does _not_ imply memoization.

It should, or use a different name.
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
And mutating through parameters does not affect functional purity 
in the theoretical sense if the function holds the only reference 
to it. It is comparable to taking one value and returning a new 
version of it.

Rigor is important in language design. If you cannot say ALWAYS, 
then the compiler will have to assume NEVER.
May 15 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 07:22:02 +0000
via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Thursday, 15 May 2014 at 06:59:08 UTC, Jonathan M Davis via
 Digitalmars-d wrote:
 And it _definitely_ has nothing to do with functional purity.

Which makes it pointless and misleading.
 Now, combined with other information, you _can_ get functional
 purity out it -
 e.g. if all the parameters to a function are immutable, then it
 _is_
 functionally pure, and optimizations requiring functional
 purity can be done
 with that function.

No, you can't say it is functionally pure if you can flip a coin with a pure function. To do that you would need a distinction between "prove pure" and "assume pure" as well as having immutable reference types that ban identity comparison.
 So, no, purity does _not_ imply memoization.

It should, or use a different name.

Originally, pure required that the function parameters be pure in addition to disallowing the function from accessing global or static variables or calling functions that weren't pure. It allowed for mutation within the function, and it allowed for allocation via new, but from the outside, the function _was_ functionally pure. The problem was that it was almost useless. You just couldn't do anything in a pure function that mattered most of the time. You couldn't call any other functions from the pure function unless they were pure, which meant that the arguments to them had to be immutable, which just didn't work, because while the arguments to the first function were immutable, what it had to do internally often involved operating on other variables which were created within the function which were not immutable and didn't need to be immutable, but you couldn't use them with any functions unless they were immutable thanks to the fact that all pure functions had to have immutable parameters, and pure functions could only call pure functions. It just didn't work. So, Don introduced the idea of "weak" purity. What it comes down to is that it's an extension of the concept that mutation within a pure function is fine just so long as its arguments aren't mutated. We made it so that pure functions _didn't_ have to have immutable parameters. They just couldn't access anything that wasn't passed to them as arguments. This meant that they could only mutate what they were given and thus they didn't violate the "strong" purity of the original pure function which had immutable parameters. e.g. string strongFunc(immutable string foo, int i) pure { auto foo = str ~ " hello world "; weak(str, i); return str; } void weakFunc(ref string str, int i) pure { foreach(j; 0 .. i) str ~= to!(j); } The strong guarantees that strongFunc has which make it functionally pure are not violated by the fact that weakFunc is _not_ functionally pure. But by marking it pure, it guarantees that it can safely be called from a strongly pure function without violating the guarantees of that strongly pure function. To do that, _all_ we need to guarantee is that the weakly pure function cannot access anything save for what's passed into it (since if it could access global variables, that would violate the guarantees of any other pure functions that called it), but we do need that guarantee. The result is that the pure attribute doesn't in and of itself mean functional purity anymore, but it _can_ be used to build a function which is functionally pure. You could argue that a different attribute should be used other than pure to mark "weakly" pure functions, but that would just complicate things. The compiler is capable of figuring out the difference between a "weakly" pure and "strongly" pure function on its own from just the function signature just so long as "weak" purity is detectable from the function signature. So, we only need one attribute - one to mark the fact that the function can't access global, mutable state and can't call any functions that can. And we were already marking strongly pure functions with pure, so it made perfect sense to use it on weakly pure functions as well. At that point, it was just up to the compiler to detect whether the function was strongly pure or not and thus was functionally pure and could be used in optimizations. So, sorry that it offends your sensibilities that pure by itself does not indicate functional purity, but it's a building block for functional purity, and the evolution of things made it make perfect sense to use the pure attribute for this. And even if pure _didn't_ enable functional purity, it would still be highly useful just from the fact that a pure function (be it weak or strong) cannot access global variables, and that makes it _much_ easier to reason about code, because you know that it isn't accessing anything that wasn't passed to it. I recommend that you read this article by David Nadlinger: http://klickverbot.at/blog/2012/05/purity-in-d/ - Jonathan M Davis
May 15 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 10:14:48 +0200
luka8088 via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 05:51:14 +0000
 via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)" The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence. Even other sources are consistent on this matter, and this is what purity by definition is.

The reread the paragraph at the top of the section of the documentation that you linked to: "Pure functions are functions which cannot access global or static, mutable state save through their arguments. This can enable optimizations based on the fact that a pure function is guaranteed to mutate nothing which isn't passed to it, and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)." That outright says that pure only _can_ enable functional purity - in particular when the compiler is able to guarantee that the function cannot mutate its arguments. pure itself however means nothing of the sort. The fact that pure functions cannot access global state _is_ the basis for functional purity when combined with parameters that arguments cannot be mutated. If you get hung up on what the concept of functional purity is or what you thought pure was before using D, then you're going to have a hard time understanding what pure means in D. And yes, it's a bit weird, but it comes from the practical standpoint of how to make functional purity possible without being too restrictive to be useful. So, it really doesn't matter what other sources say about what purity means. That's not what D's pure means. D's pure is just a building block for what purity normally means. It makes it so that the compiler can detect functional purity and then optimize based on it, but it doesn't in and of itself have anything to do with functional purity. If the documentation isn't getting that across, then I guess that it isn't clear enough. But I would have thought that the part that said "and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity" would have made it clear that D's pure is _not_ functionally pure by itself. The first part of the paragraph says what pure really means: "Pure functions are functions which cannot access global or static, mutable state save through their arguments." Everything else with regards to functional purity is derived from there, but in and of itself, that's _all_ that the pure attribute in D means. See also: http://klickverbot.at/blog/2012/05/purity-in-d/ - Jonathan M Davis
May 15 2014
prev sibling next sibling parent "Don" <x nospam.com> writes:
On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
 On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 05:51:14 +0000
 via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 
 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)" The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence. Even other sources are consistent on this matter, and this is what purity by definition is.

Please note: D's 'pure' annotation does *not* mean that the function is pure. It means that it is statically verified to be OK to call it from a pure function. The compiler determines if a function is pure, the programmer never does. There are two things going on here, and they are quite distinct. (1) Really the keyword should be something like ' noglobal', rather than 'pure'. It's called pure for historical reasons. To reduce confusion I'll call D's pure ' noglobal' and the functional languages pure ' memoizable'. But it turns out that memoizable isn't actually an interesting property, whereas ' noglobal' is. "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from noglobal. Suppose you have function f(), which calls function g(). If f does not depend on global state, then g must not depend on global state. BUT if f() can be memoizable even if g() is not memoizable. This approach used by D enormously increases the number of functions which can be statically proven to be pure. The nomenclature can create confusion though. (2) Allowing GC activity inside a noglobal function does indeed weaken our ability to memoize. The compiler can still perform memoizing operations on most functions that return GC-allocated memory, but it's more difficult. We don't yet have data on how much of a problem this is. An interesting side-effect of the recent addition of nogc to the language, is that we get this ability back.
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 09:23:00 UTC, Jonathan M Davis via 
Digitalmars-d wrote:
 functions that weren't pure. It allowed for mutation within the 
 function, and
 it allowed for allocation via new, but from the outside, the 
 function _was_
 functionally pure.

If it didn't return the memory allocated with new and if the call to new resulted in an exception, yes.
 It just didn't work.

That I question. A pure function ( http://en.wikipedia.org/wiki/Pure_function ) depends on the values of the parameters, and only that. That is most useful. Those value can be very complex. You could have a pure member function look up values in a cache. Then the configuration of entire cache is the value. You need to think about this in terms of pre/post conditions in Hoare Logic (which I am not very good at btw).
 So, Don introduced the idea of "weak" purity. What it comes 
 down to is that
 it's an extension of the concept that mutation within a pure 
 function is fine
 just so long as its arguments aren't mutated. We made it so 
 that pure
 functions _didn't_ have to have immutable parameters. They just 
 couldn't
 access anything that wasn't passed to them as arguments. This 
 meant that they
 could only mutate what they were given and thus they didn't 
 violate the
 "strong" purity of the original pure function which had 
 immutable parameters.

And that's fine as long as nobody else is holding a reference to those mutable parameters. That means that you are taking version N of the mutable and returning version N+1. That's similar to x=1 a =f(x) x=x+1 b = f(x) which can be rewritten as: x0 =1 a = f(x0) x1 = x0+1 b = f(x1) If you think in terms of a context for purity such as a transaction then you can even allow access to globals as long as they remain constant until the transaction is committed (or you leave the context where purity is desired). Meaning, you can memoize within that context.
 functions that called it), but we do need that guarantee. The 
 result is that
 the pure attribute doesn't in and of itself mean functional 
 purity anymore,
 but it _can_ be used to build a function which is functionally 
 pure.

But, that can be deduced by the compiler, so what is the point of having "pure" for "weakly pure"? Clearly you only need to specify "strongly pure"?
 So, sorry that it offends your sensibilities that pure by 
 itself does not
 indicate functional purity, but it's a building block for 
 functional purity,

It doesn't offend me, but it is a source of confusion and not sticking to definitions makes the language design look random. The same thing goes for lazy parameters. Why pick Call-By-Name (Algol style) over Call-By-Need (memoing)? Call-By-Name is known to be error prone. Actually, lazy parameters should be restricted to pure expressions… if correctness and safety is the goal.
 attribute for this. And even if pure _didn't_ enable functional 
 purity, it
 would still be highly useful just from the fact that a pure 
 function (be it
 weak or strong) cannot access global variables, and that makes 
 it _much_
 easier to reason about code, because you know that it isn't 
 accessing anything
 that wasn't passed to it.

Ok, but maybe the opposite would be better. Marking functions that access globals with global or something. After all, most functions don't access globals.
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 09:45:52 UTC, Don wrote:
 But it turns out that  memoizable isn't actually an interesting 
 property, whereas ' noglobal' is.

 "No global state" is a deep, transitive property of a function. 
 "Memoizable" is a superficial supersetextra property which the 
 compiler can trivially determine from  noglobal.

Uhm. That is a pretty strong assumption. "memoizable" is very useful property when you do multihreading, transactions or anything that requires locking. And you can still access globals, you just need a guarantee that globals don't change until you are done. Considering that > 90% of the functions I write don't do IO or globals I'd rather specify the opposite. "io", "global" whatever. That is also easy to enforce, i.e. you don't get to access IO/globals if you don't annotate the function.
May 15 2014
prev sibling next sibling parent "Don" <x nospam.com> writes:
On Thursday, 15 May 2014 at 10:31:47 UTC, luka8088 wrote:
 On 15.5.2014. 11:45, Don wrote:
 On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
 On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
 On Thu, 15 May 2014 05:51:14 +0000
 via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Yep, purity implies memoing.

No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity. Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort. So, no, purity does _not_ imply memoization. - Jonathan M Davis

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)" The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence. Even other sources are consistent on this matter, and this is what purity by definition is.

Please note: D's 'pure' annotation does *not* mean that the function is pure. It means that it is statically verified to be OK to call it from a pure function. The compiler determines if a function is pure, the programmer never does. There are two things going on here, and they are quite distinct. (1) Really the keyword should be something like ' noglobal', rather than 'pure'. It's called pure for historical reasons. To reduce confusion I'll call D's pure ' noglobal' and the functional languages pure ' memoizable'. But it turns out that memoizable isn't actually an interesting property, whereas ' noglobal' is. "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from noglobal. Suppose you have function f(), which calls function g(). If f does not depend on global state, then g must not depend on global state. BUT if f() can be memoizable even if g() is not memoizable. This approach used by D enormously increases the number of functions which can be statically proven to be pure. The nomenclature can create confusion though. (2) Allowing GC activity inside a noglobal function does indeed weaken our ability to memoize. The compiler can still perform memoizing operations on most functions that return GC-allocated memory, but it's more difficult. We don't yet have data on how much of a problem this is. An interesting side-effect of the recent addition of nogc to the language, is that we get this ability back.

Yeah, I read all about weak/string purity and I do understand the background. I was talking about strong purity, maybe I should pointed that out. So, to correct myself: As I understood strong purity implies memoization. Am I correct?

Yes. 'strong pure' means pure in the way that the functional language crowd means 'pure'. 'weak pure' just means doesn't use globals. But note that "strong purity" isn't an official concept, it was just the terminology I used when explain to Walter what I meant. I don't like the term because it's rather misleading -- in reality you could define a whole range of purity strengths (more than just two). The stronger the purity, the more optimizations you can apply.
May 15 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 10:10:57 +0000
via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Thursday, 15 May 2014 at 09:23:00 UTC, Jonathan M Davis via
 Digitalmars-d wrote:
 functions that weren't pure. It allowed for mutation within the
 function, and
 it allowed for allocation via new, but from the outside, the
 function _was_
 functionally pure.

If it didn't return the memory allocated with new and if the call to new resulted in an exception, yes.
 It just didn't work.

That I question. A pure function ( http://en.wikipedia.org/wiki/Pure_function ) depends on the values of the parameters, and only that. That is most useful. Those value can be very complex. You could have a pure member function look up values in a cache. Then the configuration of entire cache is the value. You need to think about this in terms of pre/post conditions in Hoare Logic (which I am not very good at btw).
 So, Don introduced the idea of "weak" purity. What it comes
 down to is that
 it's an extension of the concept that mutation within a pure
 function is fine
 just so long as its arguments aren't mutated. We made it so
 that pure
 functions _didn't_ have to have immutable parameters. They just
 couldn't
 access anything that wasn't passed to them as arguments. This
 meant that they
 could only mutate what they were given and thus they didn't
 violate the
 "strong" purity of the original pure function which had
 immutable parameters.

And that's fine as long as nobody else is holding a reference to those mutable parameters.

That would only matter if the compiler were trying to optimize based on pure functions with mutable parameters. It doesn't. And it would actually be very difficult for it to do so without doing full program optimization, which really doesn't work with the C linking model that D uses. The fact that we have thread-local by default helps, but it's not enough for more than very simple cases. The compiler doesn't care about optimizing weakly pure functions. The whole purpose of weakly pure functions is to have functions which aren't functionally pure but can still be used in functions that _are_ functionally pure.
 If you think in terms of a context for purity such as a
 transaction then you can even allow access to globals as long as
 they remain constant until the transaction is committed (or you
 leave the context where purity is desired). Meaning, you can
 memoize within that context.

That doesn't work with D's model, because it doesn't have any concept of transactions like that. It also doesn't really have any concept of memoization either. The most that it does that is anything like memoizaton is optimize away multiple calls to a function within a single expression (or maybe within a statement - I don't remember which). So, auto y = sqrt(x) * sqrt(x); might become something more like auto temp = sqrt(x); y = x * x; but after that, the result of sqrt(x) is forgotten. So, in reality, the optimization gains from strongly pure functions are pretty minimal (almost non-existent really). If we were willing to do code flow analysis, we could probably make more optimizations (assuming that the exact same function call was made several times within a single function, which isn't all that common anyway), but Walter is generally against doing code flow analysis in the compiler due to the complications that it adds. We have some, but not a lot. The two main gains for purity are 1. being able to know for sure that a function doesn't access any global variables, which makes it easier to reason about the code. 2. being able to implicitly convert types to and from mutable, const, and immutable based on the knowledge that a particular value has to be unique. I'd say that functional purity was really the original goal of adding pure to the language, but it's really those two effects which have given us the most benefit. #2 in particular was unexpected, and the compiler devs keep finding new places that they can take advantage of it, which makes dealing with immutable a lot more pleasant - particularly when it comes to creating immutable objects that require mutation in order to be initialized properly.
 functions that called it), but we do need that guarantee. The
 result is that
 the pure attribute doesn't in and of itself mean functional
 purity anymore,
 but it _can_ be used to build a function which is functionally
 pure.

But, that can be deduced by the compiler, so what is the point of having "pure" for "weakly pure"? Clearly you only need to specify "strongly pure"?

It can't be deduced from the signature, and the compiler has to be able to know based only on the signature, because it doesn't necessarily have the source code for the function available. The only functions for which the compiler ever deduces anything from their bodies are templated functions, because it always has their bodies, and if it didn't do the attribute inference for you, you'd be forced to either restrict the function by marking it (or not marking it) with a particular set of attributes, or you'd have to duplicate the function for each combination of attributes that you wanted. So, when you mark a function as pure, the compiler verifies that it's pure based on its body, but when other functions use it, all they know or care about is the signature of the function. So, it's up to the programmer to tell the compiler that a function is supposed to be pure, and it's up to the compiler to verify that, and then use that knowledge to infer other things based purely on the signature (like functional purity or the ability to implicitly convert a type to the same type but with different mutability).
 Ok, but maybe the opposite would be better. Marking functions
 that access globals with  global or something. After all, most
 functions don't access globals.

I agree that that would be great if we were starting over - just like it would be great if safe were the default, but it's too late now. We have to make do with what we have. We can make backwards-compatible changes, but we're very much trying to minimize breaking changes at this point. We'll still make them if we really think that they're needed, but we really want to avoid it. And as nice as changing some of the attributes around would be nice, it's too big a breaking change for too little gain. - Jonathan M Davis
May 15 2014
prev sibling next sibling parent "Don" <x nospam.com> writes:
On Thursday, 15 May 2014 at 10:46:21 UTC, Ola Fosheim Grøstad 
wrote:
 On Thursday, 15 May 2014 at 09:45:52 UTC, Don wrote:
 But it turns out that  memoizable isn't actually an 
 interesting property, whereas ' noglobal' is.

 "No global state" is a deep, transitive property of a 
 function. "Memoizable" is a superficial supersetextra property 
 which the compiler can trivially determine from  noglobal.

Uhm. That is a pretty strong assumption. "memoizable" is very useful property when you do multihreading, transactions or anything that requires locking.

It's useful, but it's not a deep property, and importantly, it isn't transient. The compiler can trivially work it out if it knows the function is noglobal.
 And you can still access globals, you just need a guarantee 
 that globals don't change until you are done.

Sure, but how can the compiler statically check that? It's a tough problem. (That's not a rhetorical question, BTW. If you have a solution, that would be awesome).
 Considering that > 90% of the functions I write don't do IO or 
 globals I'd rather specify the opposite. "io", "global" 
 whatever. That is also easy to enforce, i.e. you don't get to 
 access IO/globals if you don't annotate the function.

I agree, I'd personally like to have an annotation ' global', and put 'pure:' at the top of every module.
May 15 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Don:

 I'd personally like to have an annotation ' global', and put 
 'pure:' at the top of every module.

I suggested a little more powerful outer: https://d.puremagic.com/issues/show_bug.cgi?id=5007 Bye, bearophile
May 15 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 10:48:07 +0000
Don via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Yes. 'strong pure' means pure in the way that the functional
 language crowd means 'pure'.
 'weak pure' just means doesn't use globals.

 But note that "strong purity" isn't an official concept, it was
 just the terminology I used when explain to Walter what I meant.
 I don't like the term because it's rather misleading
 -- in reality you could define a whole range of purity strengths
 (more than just two).
 The stronger the purity, the more optimizations you can apply.

Yeah, I agree. The problem is that it always seems necessary to use the terms weak pure to describe the distinction - or maybe I just suck at coming up with a better way to describe it than you did initially. Your recent post in this thread talking about noglobal seems to be a pretty good alternate way to explain it though. Certainly, the term pure throws everyone off at first. - Jonathan M Davis
May 15 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 15 May 2014 at 05:51:16 UTC, Ola Fosheim Grøstad 
wrote:
 On Thursday, 15 May 2014 at 02:49:28 UTC, Adam Sakareassen via 
 Digitalmars-d wrote:
 The more D allows 'pure' functions to diverge from functional 
 purity the less relevant the flag is for compiler 
 optimisations.

 By the same reasoning cacheability is important.  A pure 
 function might be called within a loop with a parameter that 
 is not altered during the loop.  If the compiler knows the 
 function is pure, it can perform the calculation before the 
 loop and simply reuse the cached result for each iteration.

Yep, purity implies memoing. Malloc and new are not pure because they return objects that can be differentiated by address.

There's an important difference between malloc and new: malloc returns a pointer, but new returns a typed object. This is crucial IMO, because the returned objects are equal to each other. They aren't identical, but then different int variables with the same value aren't identical either, and a function returning int is still considered pure. So it's not identity (~ address) that matters.
 Pure in D seems pointless to me.

Not at all: Don't think of it in terms of low-level optimization opportunities, but in terms of semantics. For example, you get the concept of uniqueness. And the optimizations can still be done, because strongly pure functions can be recognized by their signatures.
May 15 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Marc Schütz:

 And the optimizations can still be done, because strongly pure 
 functions can be recognized by their signatures.

What optimizations do you think GDC compiler is doing (or will do) on pure functions? Bye, bearophile
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 11:03:35 UTC, Don wrote:
 And you can still access globals, you just need a guarantee 
 that globals don't change until you are done.

Sure, but how can the compiler statically check that? It's a tough problem. (That's not a rhetorical question, BTW. If you have a solution, that would be awesome).

What you need is some way to formally specify what a lock covers or rather register what globals can be accessed in a transaction. So you basically need some sort of whole program analysis. With transactional memory you only take the lock if the transaction fails, so it is ok if locking is slow or to take multiple locks. The CPU reverts to regular mutex based locking and clears the cache if another thread touch the memory that has been used in the transaction. At least that is how I read the Haswell documentation.
 I agree, I'd personally like to have an annotation ' global', 
 and put 'pure:' at the top of every module.

It makes a lot of sense to put the annotation burden on the things you want less of, yes. "Do I really need to make this global? Maybe I should do it some other way…"
May 15 2014
prev sibling next sibling parent Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 15 May 2014 10:50, Walter Bright via Digitalmars-d
<digitalmars-d puremagic.com> wrote:
 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I think,
 because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.

Even if it doesn't fail, malloc called with identical arguments still returns a different result every time. You can't factor malloc outside a loop and cache the result because it's being called repeatedly with the same argument like you're supposed to be able to do with any other pure function. You shouldn't be able to do that with gcalloc either... how can gcalloc be pure?
May 15 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 15 May 2014 at 11:35:46 UTC, bearophile wrote:
 Marc Schütz:

 And the optimizations can still be done, because strongly pure 
 functions can be recognized by their signatures.

What optimizations do you think GDC compiler is doing (or will do) on pure functions?

I don't know whether it does or will do any. It is a theoretical option ("can be done"). It's the kind of optimizations Ole talked about that apply only to functionally pure functions. But the important point is that `new` can be pure, if you consider pure to be about equality, not identity. This applies only to typed allocators, not malloc.
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 11:31:34 UTC, Marc Schütz wrote:
 There's an important difference between malloc and new: malloc 
 returns a pointer, but new returns a typed object. This is 
 crucial IMO, because the returned objects are equal to each 
 other.

I most code, but not all, so how does the compiler know if you don't have a reference type that explicitly bans identity comparison? If one requires value semantics it should also cover the reference. (Some programs allocate empty objects as "enums".)
 optimization opportunities, but in terms of semantics. For 
 example, you get the concept of uniqueness. And the

I agree that uniqueness is an important property. I think Rust is onto something when they now want to rename "mut" to "uniq" or "only". But in this case uniqueness is the problem with "weakly pure", a problem that "pure functions" don't have.
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 May 2014 21:11:30 -0400, Brian Schott <briancschott gmail.com>  
wrote:

 On Thursday, 15 May 2014 at 00:48:52 UTC, Walter Bright wrote:
 On 5/14/2014 5:44 PM, Brian Schott wrote:
 Can we say that Mallocator failures are not recoverable?

malloc itself does not have that property. But you could design a wrapper for it that did.

I'm concerned specifically with this wrapper: https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L773 We need to make these functions pure if they are going to be usable. Removing the stdlib import and adding private extern (C) { void* malloc(size_t) pure nothrow trusted; void free(void*) pure nothrow trusted; void* realloc(void*, size_t) pure nothrow trusted; }

Be careful. The above is all correct, but as has been discussed, the minute you start making returns immutable or parameters immutable, they become strong-pure, which has undesirable properties for allocators. If you wrap the above with calls to typed data, then strong-pure might be inferred. The compiler can specially designate things like idup to make sure they always are considered weak-pure. But library code has to be more cautious. -Steve
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 07:52:20 -0400, Manu via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On 15 May 2014 10:50, Walter Bright via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I  
 think,
 because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.

Even if it doesn't fail, malloc called with identical arguments still returns a different result every time. You can't factor malloc outside a loop and cache the result because it's being called repeatedly with the same argument like you're supposed to be able to do with any other pure function. You shouldn't be able to do that with gcalloc either... how can gcalloc be pure?

That only applies to strong-pure functions. malloc would be weak-pure, since it returns a mutable pointer. -Steve
May 15 2014
prev sibling next sibling parent "w0rp" <devw0rp gmail.com> writes:
Ola, you do not understand 'pure.'

To consider the design of pure, you must first consider that you 
cannot add functional purity to an imperative language. It cannot 
be done. What you can do instead is what D offers with a 'weak 
purity' guarantee. That global state is not modified indirectly, 
that side-effects do not occur in a function, except through the 
function's parameters, except for memory allocation. D allows you 
to come pretty close to strong purity when a function is marked 
pure, does not allocate memory inside it or through its 
arguments, and has only const or immutable arguments. The only 
way you can get a better purity guarantee than that is to use a 
functional programming language like Haskell.
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 11:01:38 UTC, Jonathan M Davis via 
Digitalmars-d wrote:
 functions with mutable parameters. It doesn't. And it would 
 actually be very
 difficult for it to do so without doing full program 
 optimization, which
 really doesn't work with the C linking model that D uses.

I think this C linking excuse is used too much :-). Clearly one can specify properties of C functions when writing the bindings. (Or; should be able to). Besides, not all call trees are full of C calls.
 functions. The whole
 purpose of weakly pure functions is to have functions which 
 aren't
 functionally pure but can still be used in functions that _are_ 
 functionally pure.

I take it you mean "expressions" and not necessarily defined functions. So the compiler memoize values derived from weakly pure functions?
 source code for the function available. The only functions for 
 which the
 compiler ever deduces anything from their bodies are templated 
 functions,

But with the amount of templates in phobos… maybe it is time to move beyond fully separate compilation units?
 about is the signature of the function. So, it's up to the 
 programmer to tell
 the compiler that a function is supposed to be pure, and it's 
 up to the
 compiler to verify that, and then use that knowledge to infer

Ok, but based on bearophile's example it doesn't verify purity properly. So it is essentially part verified ("verify noglob") and part programmer guarantee ("this is pure"). I don't mind programmers being able to set guarantees. For instance for a C function or machine language routines it might be useful to specify that this is pure and avoid recomputation.
 I agree that that would be great if we were starting over - 
 just like it would
 be great if  safe were the default, but it's too late now. We 
 have to make do with what we have.

Yes, many changes over time is not good. Maybe it would be a good idea to collect all those syntax improvements and apply them all at once once the semantics are frozen.
 avoid it. And as
 nice as changing some of the attributes around would be nice, 
 it's too big a
 breaking change for too little gain.

It doesn't have to break anything. You could add " global" and " pure" (strong pure) and keep "pure" (weakly pure) as a deprecated feature.
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 02:50:05 -0400, Ola Fosheim Gr=C3=B8stad  =

<ola.fosheim.grostad+dlang gmail.com> wrote:

 On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
 A little example of D purity (this compiles):

 bool randomBit() pure nothrow  safe {
     return (new int[1].ptr) > (new int[1].ptr);
 }

Yes, and then you may as well allow a random generator with private =

 globals. Because memoing is no longer sound anyway.

This has nothing to do with allocators being pure. They must be pure as = a = matter of practicality. The issue that allows the above anomaly is using the address of somethin= g. = There is a reason functional languages do not allow these types of thing= s. = But in functional languages, allocating is allowed. To be honest, code that would exploit such an anomaly is only ever used = in = "proof" exercises, and never in real code. I don't think it's an issue. -Steve
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 May 2014 20:50:08 -0400, Walter Bright  
<newshound2 digitalmars.com> wrote:

 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I  
 think, because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.

Basically, you are saying that malloc must return the same block whenever it's called with the same parameters. This is simply nonsense. null is not special, it's just another block. I'm not saying malloc should be pure based on this, but the possibility that it returns null does not disqualify it. -Steve
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 12:37:22 UTC, w0rp wrote:
 To consider the design of pure, you must first consider that 
 you cannot add functional purity to an imperative language.

Of course you can. Functional languages execute in an "imperative context". That's why you need monads. The term "pure function" is only needed in a non-functional language. Applicative/functional languages only have mathematical functions, no need for the term "pure" there.
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 12:57:43 UTC, Steven Schveighoffer 
wrote:
 To be honest, code that would exploit such an anomaly is only 
 ever used in "proof" exercises, and never in real code. I don't 
 think it's an issue.

That's the wrong attitude to take when it comes to the compiler and runtime. If it verifies, it should verify. Not mostly, but fully, otherwise "weakly pure" becomes a programmer guarantee. Which is ok too, but either the one or the other. How can you prove that such issues don't arise in real code?
May 15 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Thursday, 15 May 2014 at 12:57:43 UTC, Steven Schveighoffer 
wrote:
 On Thu, 15 May 2014 02:50:05 -0400, Ola Fosheim Grøstad 
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
 A little example of D purity (this compiles):

 bool randomBit() pure nothrow  safe {
    return (new int[1].ptr) > (new int[1].ptr);
 }

Yes, and then you may as well allow a random generator with private globals. Because memoing is no longer sound anyway.

This has nothing to do with allocators being pure. They must be pure as a matter of practicality. The issue that allows the above anomaly is using the address of something. There is a reason functional languages do not allow these types of things. But in functional languages, allocating is allowed.

Which is what makes D pure lint-like helper and not effective optimization enabler. This part of type system was under-designed initially, it should have been much more restrictive. I am ok with current state though, it is just sad that it creates lot of false expectations from those familiar with pure functional languages.
 To be honest, code that would exploit such an anomaly is only 
 ever used in "proof" exercises, and never in real code. I don't 
 think it's an issue.

This is not true. Because of such code you can't ever automatically memoize strongly pure function results by compiler. A very practical concern.
May 15 2014
prev sibling next sibling parent Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 15 May 2014 22:30, Steven Schveighoffer via Digitalmars-d
<digitalmars-d puremagic.com> wrote:
 On Thu, 15 May 2014 07:52:20 -0400, Manu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 15 May 2014 10:50, Walter Bright via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I think,
 because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.

Even if it doesn't fail, malloc called with identical arguments still returns a different result every time. You can't factor malloc outside a loop and cache the result because it's being called repeatedly with the same argument like you're supposed to be able to do with any other pure function. You shouldn't be able to do that with gcalloc either... how can gcalloc be pure?

That only applies to strong-pure functions. malloc would be weak-pure, since it returns a mutable pointer.

Why should returning a mutable pointer imply weak purity?
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 09:24:54 -0400, Ola Fosheim Gr=C3=B8stad  =

<ola.fosheim.grostad+dlang gmail.com> wrote:

 On Thursday, 15 May 2014 at 12:57:43 UTC, Steven Schveighoffer wrote:
 To be honest, code that would exploit such an anomaly is only ever us=


 in "proof" exercises, and never in real code. I don't think it's an  =


 issue.

That's the wrong attitude to take when it comes to the compiler and =

 runtime.

There are always ways around the guarantees. This one isn't as detectabl= e, = since there is no "red-flag" cast or attribute. But I see no utility in = = such code.
 If it verifies, it should verify. Not mostly, but fully, otherwise  =

 "weakly pure" becomes a programmer guarantee. Which is ok too, but  =

 either the one or the other.

Memory allocation is an exception to purity that is widely considered OK= , = because of the practical need for allocating memory from a heap to do = work. In general, it's the block of data that is important, not it's = address. Where it comes from is of no consequence.
 How can you prove that such issues don't arise in real code?

Of course I can't prove it doesn't arise, but I can't think of any use = cases to do something significant based on the address of heap data in = relation to another unrelated heap block. Perhaps you can show a use case for it? The other thing to think about is that such code won't serve the purpose= = for which it was written! randomBit won't be random because it will like= ly = be memoized. In any case, the alternative is to have D pure functions avoid using = pointers. It's as drastic as that. -Steve
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 09:40:03 -0400, Manu via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On 15 May 2014 22:30, Steven Schveighoffer via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 On Thu, 15 May 2014 07:52:20 -0400, Manu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 15 May 2014 10:50, Walter Bright via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I  
 think,
 because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.

Even if it doesn't fail, malloc called with identical arguments still returns a different result every time. You can't factor malloc outside a loop and cache the result because it's being called repeatedly with the same argument like you're supposed to be able to do with any other pure function. You shouldn't be able to do that with gcalloc either... how can gcalloc be pure?

That only applies to strong-pure functions. malloc would be weak-pure, since it returns a mutable pointer.

Why should returning a mutable pointer imply weak purity?

Because if it were strong-pure, the compiler could optimize two sequential calls as returning the same exact thing. Imagine if a constructor to a mutable object always returned the same object because the constructor's parameters were immutable. It would be useless. -Steve
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 09:28:57 -0400, Dicebot <public dicebot.lv> wrote:

 On Thursday, 15 May 2014 at 12:57:43 UTC, Steven Schveighoffer wrote:
 On Thu, 15 May 2014 02:50:05 -0400, Ola Fosheim Gr=C3=B8stad  =


 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
 A little example of D purity (this compiles):

 bool randomBit() pure nothrow  safe {
    return (new int[1].ptr) > (new int[1].ptr);
 }

Yes, and then you may as well allow a random generator with private =



 globals. Because memoing is no longer sound anyway.

This has nothing to do with allocators being pure. They must be pure =


 a matter of practicality.

 The issue that allows the above anomaly is using the address of  =


 something. There is a reason functional languages do not allow these =


 types of things. But in functional languages, allocating is allowed.

Which is what makes D pure lint-like helper and not effective =

 optimization enabler. This part of type system was under-designed  =

 initially, it should have been much more restrictive.

It's easy to say this, but the restrictions to apply would be draconian.= I = think it would be nearly impossible to prevent such abuses in a language= = with explicit references.
 To be honest, code that would exploit such an anomaly is only ever us=


 in "proof" exercises, and never in real code. I don't think it's an  =


 issue.

This is not true. Because of such code you can't ever automatically =

 memoize strongly pure function results by compiler. A very practical  =

 concern.

I think you can still memoize these cases. There is no reason for the = language to support a pure RNG. -Steve
May 15 2014
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 15 May 2014 at 06:50:06 UTC, Ola Fosheim Grøstad 
wrote:
 On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
 A little example of D purity (this compiles):

 bool randomBit() pure nothrow  safe {
    return (new int[1].ptr) > (new int[1].ptr);
 }

Yes, and then you may as well allow a random generator with private globals. Because memoing is no longer sound anyway.

No, this particular example appears to be invalid code. Under the C memory model [1], the result of comparing two pointers to distinct objects (allocations) is undefined/unspecified behavior (I think it is undefined in C and unspecified in C++, but I don't remember the details). Of course, you could rescue the example by casting the pointers to size_t or something along the lines, but this is something that could be disallowed in pure code. David [1] Which typically applies to D, unless defined otherwise. Our language specification is woefully incomplete in this regard, though.
May 15 2014
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 15 May 2014 at 13:40:16 UTC, Manu via Digitalmars-d 
wrote:
 Why should returning a mutable pointer imply weak purity?

The argument here is that a valid mutable pointer returned from a pure function could always point to a new allocation, as new is allowed in pure code. More precisely, the only way to return a valid mutable pointer from a parameterless function is to make it point to a new allocation, so allowing memory allocations does not even preclude the inference of stronger guarantees here. David
May 15 2014
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 15 May 2014 at 13:42:58 UTC, Steven Schveighoffer 
wrote:
 On Thu, 15 May 2014 09:24:54 -0400, Ola Fosheim Grøstad 
 <ola.fosheim.grostad+dlang gmail.com> wrote:
 That's the wrong attitude to take when it comes to the 
 compiler and runtime.

There are always ways around the guarantees. This one isn't as detectable, since there is no "red-flag" cast or attribute. But I see no utility in such code.

I have to agree with Ola here. If you write a piece of pure, safe code, there should be no way for compiler optimizations to make your code behave differently. This is not only because implicitly allowing unsafe code would be against the design philosophy behind D, but also as attribute inference might tag functions as pure without the programmer explicitly specifying so.
 In any case, the alternative is to have D pure functions avoid 
 using pointers. It's as drastic as that.

I'd suspect that it is enough to disallow using the content of pointers explicitly, i.e. as a sequence of bytes instead of just a handle to an object. David
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 10:42:00 -0400, David Nadlinger <code klickverbot.at=
  =

wrote:
 On Thursday, 15 May 2014 at 13:42:58 UTC, Steven Schveighoffer wrote:
 On Thu, 15 May 2014 09:24:54 -0400, Ola Fosheim Gr=C3=B8stad  =


 <ola.fosheim.grostad+dlang gmail.com> wrote:
 That's the wrong attitude to take when it comes to the compiler and =



 runtime.

There are always ways around the guarantees. This one isn't as =


 detectable, since there is no "red-flag" cast or attribute. But I see=


 no utility in such code.

I have to agree with Ola here. If you write a piece of pure, safe cod=

 there should be no way for compiler optimizations to make your code  =

 behave differently.

In general, I would say any code that performs differently after = optimization is not preferable. But in this case, you have ignored the = rules, and the result is not exactly incorrect or unsafe. In fact, you = can't really argue that it's invalid (randomBit could legitimately alway= s = return true or false, even in a non-optimized program). The question here is, can we come up with a static rule that is effectiv= e, = but not cripplingly prohibitive?
 This is not only because implicitly allowing unsafe code would be  =

 against the design philosophy behind D, but also as attribute inferenc=

 might tag functions as pure without the programmer explicitly specifyi=

 so.

So far, I haven't seen code that's unsafe only if optimized. Have an = example?
 In any case, the alternative is to have D pure functions avoid using =


 pointers. It's as drastic as that.

I'd suspect that it is enough to disallow using the content of pointer=

 explicitly, i.e. as a sequence of bytes instead of just a handle to an=

 object.

This means format("%x", ptr) isn't allowed to be pure? What about calculating index offsets? Note that pointer math between two= = pointers on the same block of memory is perfectly legitimate. I would expect that someone could be able to write a type equivalent to = a = slice, and it should be allowed to be pure. -Steve
May 15 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
David Nadlinger:

 I'd suspect that it is enough to disallow using the content of 
 pointers explicitly, i.e. as a sequence of bytes instead of 
 just a handle to an object.

Yes, if you allow only a referentially pure view of pointers, then you have a strong purity. Bye, bearophile
May 15 2014
prev sibling next sibling parent Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 15 May 2014 23:47, Steven Schveighoffer via Digitalmars-d
<digitalmars-d puremagic.com> wrote:
 On Thu, 15 May 2014 09:40:03 -0400, Manu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 15 May 2014 22:30, Steven Schveighoffer via Digitalmars-d

 <digitalmars-d puremagic.com> wrote:
 On Thu, 15 May 2014 07:52:20 -0400, Manu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 15 May 2014 10:50, Walter Bright via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 On 5/14/2014 5:03 PM, Meta wrote:
 Allocating memory through new and malloc should always be pure, I
 think,
 because
 failure either returns null in malloc's case,

malloc cannot be pure if, with the same arguments, it returns null sometimes and not other times.

Even if it doesn't fail, malloc called with identical arguments still returns a different result every time. You can't factor malloc outside a loop and cache the result because it's being called repeatedly with the same argument like you're supposed to be able to do with any other pure function. You shouldn't be able to do that with gcalloc either... how can gcalloc be pure?

That only applies to strong-pure functions. malloc would be weak-pure, since it returns a mutable pointer.

Why should returning a mutable pointer imply weak purity?

Because if it were strong-pure, the compiler could optimize two sequential calls as returning the same exact thing. Imagine if a constructor to a mutable object always returned the same object because the constructor's parameters were immutable. It would be useless. -Steve

I don't follow. Forget that it's a pointer... it's just a number. A strong pure function simply doesn't modify it's inputs (which we can guarantee with const/immutable args), and returns the same output. It shouldn't matter if the output is mutable or not, it just has to be the same. Whether it's the number 10, or a pointer. I guess it logically follows that the output must be const or immutable, because it can only possibly be returning a pointer to, or to a member of, one of it's args... and 'turtles all the way down'. But that leads me back to where I started... how can it possibly be that an allocator of any sort can be pure? If you can allocate a new pointer, you can return it as a const or immutable pointer if you like, and then the function looks awfully like a strong pure function even though it returns a new pointer every time. That's not pure at all.
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 12:01:35 -0400, Manu via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On 15 May 2014 23:47, Steven Schveighoffer via Digitalmars-d

 Because if it were strong-pure, the compiler could optimize two  
 sequential
 calls as returning the same exact thing. Imagine if a constructor to a
 mutable object always returned the same object because the constructor's
 parameters were immutable. It would be useless.

I don't follow. Forget that it's a pointer... it's just a number.

But that doesn't make sense. What you are returning is not the pointer value, but the pointed-at object. When you return an allocated object, you aren't returning the pointer, just a way to get to the object.
 A
 strong pure function simply doesn't modify it's inputs (which we can
 guarantee with const/immutable args), and returns the same output.
 It shouldn't matter if the output is mutable or not, it just has to be
 the same. Whether it's the number 10, or a pointer.

define "the same"? char[] foo(int x) pure {return to!(char[])(x);} would you argue that foo(5) always returns "5"? Or would you argue that it returns {length:1, ptr:0xee532000}? A memoization would mean it's always returning the same exact object, not the same value.
 I guess it logically follows that the output must be const or
 immutable, because it can only possibly be returning a pointer to, or
 to a member of, one of it's args... and 'turtles all the way down'.

You are thinking of uniqueness of the result. That does not require strong purity.
 But that leads me back to where I started... how can it possibly be
 that an allocator of any sort can be pure? If you can allocate a new
 pointer, you can return it as a const or immutable pointer if you
 like, and then the function looks awfully like a strong pure function
 even though it returns a new pointer every time. That's not pure at
 all.

Strong pure is not required for implicit casting, uniqueness is. You can establish uniqueness based on comparing the return types to the parameters. But a "strong pure" (and like Don says, this is really a bad description) as I understand it means pure in the functional purity sense -- all immutable parameters, all immutable returns, no global access. These can be optimized similarly to all functional languages (memoization of results, reordering or factoring of calls, dispatching calls to multiple threads, etc.). -Steve
May 15 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 11:42:00 -0400, Timon Gehr <timon.gehr gmx.ch> wrote=
:

 On 05/15/2014 02:57 PM, Steven Schveighoffer wrote:
 On Thu, 15 May 2014 02:50:05 -0400, Ola Fosheim Gr=C3=B8stad
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
 A little example of D purity (this compiles):

 bool randomBit() pure nothrow  safe {
     return (new int[1].ptr) > (new int[1].ptr);
 }

Yes, and then you may as well allow a random generator with private globals. Because memoing is no longer sound anyway.

This has nothing to do with allocators being pure. They must be pure =


 a matter of practicality.

 The issue that allows the above anomaly is using the address of
 something. There is a reason functional languages do not allow these
 types of things. But in functional languages, allocating is allowed.
 ...

Not really, allocation is just an implementation detail. The =

 computational language is meaningful independent of how you might  =

 achieve evaluation of expressions. I can in principle evaluate an  =

 expression of such a language on paper without managing a separate  =

 store, even though this usually will help efficiency.

 Functional programming languages are not about taking away features fr=

 a procedural core language. They are based on the idea that the  =

 fundamental operation is substitution of terms.

But they do not deal in explicit pointers. Otherwise, that's a can of = worms that would weaken the guarantees, similar to how D's guarantees ar= e = weakened. We have no choice in D, we must accept that explicit pointers are used.
 To be honest, code that would exploit such an anomaly is only ever us=


 in "proof" exercises, and never in real code.

Hashtables are quite real.

Pretend I'm ignorant, what does this imply?
 This is the issue:

 On Thu, 15 May 2014 10:48:07 +0000
 Don via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 Yes. 'strong pure' means pure in the way that the functional
 language crowd means 'pure'.
 'weak pure' just means doesn't use globals.


There is no way to make that claim precise in an adequate way such tha=

 it is correct.

This doesn't help, I'm lost with this statement. -Steve
May 15 2014
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 15 May 2014 at 15:09:32 UTC, Steven Schveighoffer 
wrote:
 But in this case, you have ignored the rules, […]

Which rules exactly? My point is mainly that this area of the language is underspecified.
 This means format("%x", ptr) isn't allowed to be pure?

The short answer would be: Yes. The alternatives seem to be: - Disallowing memory allocations in pure code (not workable) - Bidding farewell to the idea that pure + no mutable indirections means FP-sense purity.
 What about calculating index offsets? Note that pointer math 
 between two pointers on the same block of memory is perfectly 
 legitimate.

Taking offsets within the same block are fine. Even in the light of GC allocations being pure, this doesn't lead to any non-determinism, as there isn't any mechanism for the relative offset between whatever you are considering to change without any outside input.
 I would expect that someone could be able to write a type 
 equivalent to a slice, and it should be allowed to be pure.

Yes. David
May 15 2014
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, May 15, 2014 at 03:22:25PM -0700, Walter Bright via Digitalmars-d wrote:
 On 5/15/2014 2:41 PM, Timon Gehr wrote:
On 05/15/2014 11:33 PM, Walter Bright wrote:
On 5/15/2014 9:07 AM, Timon Gehr wrote:
Why? A memoizable function is still memoizable if it is changed
internally to memoize values in global memory, for example.

I doubt a compiler could prove it was pure.

Yes, that was actually my point. Memoizable is actually a non-trivial property. (But note that while a compiler cannot in general discover a proof, it could just _check_ a supplied proof.)

If the compiler cannot mechanically verify purity, the notion of purity is rather useless, since as this thread shows it is incredibly easy for humans to be mistaken about it.

What if the language allowed the user to supply a proof of purity, which can be mechanically checked? Just rephrasing what Timon said, though -- I've no idea how such a thing might be implemented. You'd need some kind of metalanguage for writing the proof in, perhaps inside a proof block attached to the function declaration, that can be mechanically verified to be correct. Alternatively, if only one or two statements are causing trouble, the proof can provide mechanically checkable evidence just for those specific statements. The metalanguage must be mechanically checkable, of course. But this may be more plausible than it sounds -- for example, solutions to certain NP-complete problems are verifiable within a far shorter time than it would take to actually solve said problem. This suggests that perhaps, while the purity of an arbitrary piece of code is, in general, infeasible for the compiler to mechanically prove, it may be possible in some cases that the compiler can mechanically verify a user-supplied proof, and thus provide the same guarantees as it would for directly-provable code. T -- When solving a problem, take care that you do not become part of the problem.
May 15 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:

 it may be possible in some cases that the compiler can 
 mechanically
 verify a user-supplied proof, and thus provide the same 
 guarantees
 as it would for directly-provable code.

Yes, this is common enough. As an example the Whiley (http://whiley.org/ ) is not able to find the proof for various invariants and contracts, but the programmer can write them down and Whiley verifies them to be correct during the compilation. Inventing a proof is harder, but verifying it is often much easier. The first way D can introduce such things (simple proof) is in the static verify of some contracts. Verifying memoizable or reflexive/ symmetric/ transitive (for functions with two arguments) is perhaps a bit too much ambitious for D compilers. But it surely goes well with the idea of a language that tries to both avoid bugs and generate efficient binaries :-) (And perhaps someday C++ Axioms of Concepts will be handled by a C++ compiler able to verify a function to be symmetric). Bye, bearophile
May 15 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Walter Bright:

 I think those sorts of things are PhD research topics. It's a 
 bit beyond the scope of what we're trying to do with D.

Perhaps yes. Yet, the Whiley language is not PhD-level, and it's inspiring :) Things like value range propagation show that even rather small amounts of statically known information can give back plenty of value to D! Bye, bearophile
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 13:42:58 UTC, Steven Schveighoffer 
wrote:
 In any case, the alternative is to have D pure functions avoid 
 using pointers. It's as drastic as that.

You need: 1. references with value semantics. 2. "non pure exceptions" that cannot be caught within a pure chain, but can be caught outside Besides that I think programmer provided guarantees for referential transparency are valuable for C/ASM and for non-pure to pure conversion using the exception in point 2.
May 15 2014
prev sibling next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Friday, 16 May 2014 at 00:27:34 UTC, Andrei Alexandrescu wrote:
 On 5/15/14, 2:52 PM, Timon Gehr wrote:
 On 05/15/2014 08:03 PM, Andrei Alexandrescu wrote:
 Purity of allocation is frequently assumed by functional 
 languages

Examples?

cons 1 2 is equal to cons 1 2 ...

I don't see anything whose specification would need to mention 'allocation'.

That's the point. There's no specification of allocation - the evaluator may create two lists or reuse the same, and it's all transparent.
 because without it it would be difficult to get much work 
 done.

Why?

It's rather obvious. You've got to have the ability to create new values in a pure functional programming language.

This kind of operational reasoning is not essential. Of course, in practice you want to evaluate expressions, but the resulting programs are of the same kind as those of a non-pure language, and can do the same kind of operations. There is not really a distinction to be made at that level of abstraction.

I'm afraid I got lost here.

I believe Timon's point is that allocation is an implementation detail, just like the existence of registers, memory caches, and the stack. Those things need not exist to perform the computation and as a result there is no need to assume anything about their purity (as far as the language is concerned, they don't exist). D dropped the ball (perhaps) by making memory allocation real. If 'new' was just defined to create a new object without specifying (directly or indirectly) that it lived in memory and had an address that could be compared then the allocation of memory would be an implementation detail invisible to the language, and that would allow "true" purity, and the optimisation opportunities that come with it.
May 16 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 21:48:16 UTC, Timon Gehr wrote:
 The term "pure function" is only needed in a non-functional 
 language.
 Applicative/functional languages only have mathematical 
 functions, no
 need for the term "pure" there.

In discussions about e.g. Haskell, it is often used to denote an expression of a specific form inside a `stateful' DSL. E.g. if "η" is the unit of some monad, then (η v) is sometimes called a "pure value", while values of other forms are not called pure.

Yes, from haskell.org: <<While programs may describe impure effects and actions outside Haskell, they can still be combined and processed ("assembled") purely, inside Haskell, creating a pure Haskell value - a computation action description that describes an impure calculation. That is how Monads in Haskell separate between the pure and the impure.>> So, I think my statement holds.
May 16 2014
prev sibling next sibling parent "Araq" <rumpf_a web.de> writes:
 Yes, the VRP has been a nice win for D. No other language does 
 it.

I don't know why you keep saying things like that, you don't know all the languages out there. Nimrod does it too fwiw...
May 16 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Walter Bright:

 Yes, the VRP has been a nice win for D.

There are ways to improve it in very useful ways, that increase static safety and cut down the number of useless casts required. Some currently refused examples: --------------- int[100] array; void main() { foreach (immutable idx, const x; array) ubyte y = idx; } --------------- void foo(immutable uint x) in { assert(x <= ubyte.max); } body { ubyte y = x; } void main() {} https://issues.dlang.org/show_bug.cgi?id=10751 More on contracts: uint foo() in { } out(result) { assert(result < 100); } body { return 20; } void bar(immutable ubyte x) {} void main() { bar(foo()); } --------------- D immutability is under-utilized, it avoids the need for flow analysis: void main(in string[] args) { immutable ushort x = args.length % 5; immutable ubyte y = x; } uint x; void main() { immutable uint y = x; if (y <= ubyte.max) { ubyte z = y; } } uint x; void main() { immutable uint y = x; assert(y <= ubyte.max); ubyte z = y; } https://issues.dlang.org/show_bug.cgi?id=10594 --------------- More: https://issues.dlang.org/show_bug.cgi?id=10615 https://issues.dlang.org/show_bug.cgi?id=12753 Bye, bearophile
May 16 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 18:30:55 -0400, David Nadlinger <code klickverbot.at=
  =

wrote:
 On Thursday, 15 May 2014 at 15:09:32 UTC, Steven Schveighoffer wrote:
 But in this case, you have ignored the rules, [=E2=80=A6]

Which rules exactly? My point is mainly that this area of the language=

 is underspecified.

The rules that we have been discussing, you cannot make significant = decisions based on the addresses of 2 unrelated pointers.
 This means format("%x", ptr) isn't allowed to be pure?

The short answer would be: Yes. The alternatives seem to be: - Disallowing memory allocations in pure code (not workable) - Bidding farewell to the idea that pure + no mutable indirections =

 means FP-sense purity.

There is a 3rd option: - FP purity, working fine as long as you don't do stupid things based on= = addresses. And even possibly working fine if you do stupid things based = on = addresses. In other words, still assume FP purity, and if you expect randomness bas= ed = on heap addresses to work, it just won't. Keep in mind, nothing discusse= d = so far can cause invalid results. It just will be less random than = expected. I really don't see a problem with this. You are changing non-deterministic behavior to different, but still = non-deterministic behavior. How do you even measure the impact?
 What about calculating index offsets? Note that pointer math between =


 two pointers on the same block of memory is perfectly legitimate.

Taking offsets within the same block are fine. Even in the light of GC=

 allocations being pure, this doesn't lead to any non-determinism, as  =

 there isn't any mechanism for the relative offset between whatever you=

 are considering to change without any outside input.

I think it is impossible to statically prevent address comparison betwee= n = 2 unrelated pointers, but statically allow address comparison between 2 = = related ones. The compiler does not have the information to determine = whether 2 pointers are related at compile time. In fact, it may do BOTH! bool foo(int *x, int *y) pure { return x < y; } bool bar() pure { if(foo(new int, new int)) // bad { int[10] x; return foo(x.ptr, x.ptr + 5); // ok } return false; } In the interest of nailing down what the rules SHOULD be (and I agree th= ey = need to be in the spec), here is a strawman to discuss: You cannot do comparisons between two unrelated heap pointers that were = = allocated from the heap inside the same pure call. This only applies to = = the pointer values themselves, not the data pointed at (as long as that = = data is not a similar pointer). I will define the "same pure call" as the function call into a pure = function from a non-pure function. Note, this is not a rule to implement as a static enforcement, it's one = = the programmer must not do. Like 'undefined behavior'. I don't think we = = can enforce it, as I mentioned above. A lint tool may be able to catch it, and we can also possibly catch it a= t = runtime, as long as the allocator can determine whether you're inside a = = pure function. -Steve
May 16 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 08:43:11 -0700
Andrei Alexandrescu via Digitalmars-d <digitalmars-d puremagic.com>
wrote:

 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever automatically
 memoize strongly pure function results by compiler. A very practical
 concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it. However, that should have no effect on pure functions that return value types - even if the function took pointers or references as arguments or allocated memory internally. They should but perfectly memoizable. - Jonathan M Davis
May 17 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 11:03:13 -0700
Walter Bright via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On 5/15/2014 2:45 AM, Don wrote:
 An interesting side-effect of the recent addition of  nogc to the
 language, is that we get this ability back.

I hadn't thought of that. Pretty cool!

Definitely, but we also need to be careful with it. If nogc just restricts allocations by the GC and not allocations in general, and if we make it so that malloc is pure (even if it's only when wrapped by a function which throws an Error when malloc returns null), then I don't think that we quite get it back, because while the GC may not have allocated any objects, malloc could still have be used to allocate them. We'd need to be able to either say that _nothing_ allocated within the function, which isn't quite what nogc does as I understand it (though admittedly, I haven't paid much attention to the discussions on it, much as I would have liked to). So, maybe we need to find a way to make it so that a wrapped malloc can be pure but isn't nogc? Though if we go that route, that implies that nogc should have been noalloc. Regardless, I think that making malloc pure definitely affects the issue of whether a nogc function can be assumed to not return newly allocated memory. - Jonathan M Davis
May 17 2014
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via Digitalmars-d
wrote:
 On Thu, 15 May 2014 08:43:11 -0700
 Andrei Alexandrescu via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:
 
 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever
 automatically memoize strongly pure function results by compiler.
 A very practical concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it. However, that should have no effect on pure functions that return value types - even if the function took pointers or references as arguments or allocated memory internally. They should but perfectly memoizable.

bool func(int x) /* pure? */ { int[] a, b; a = new int[x]; b = new int[x]; return (a.ptr < b.ptr); } Where do you draw the line? T -- Tech-savvy: euphemism for nerdy.
May 18 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sun, 18 May 2014 06:58:25 -0700
"H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> wrote:

 On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via
 Digitalmars-d wrote:
 On Thu, 15 May 2014 08:43:11 -0700
 Andrei Alexandrescu via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever
 automatically memoize strongly pure function results by
 compiler. A very practical concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it. However, that should have no effect on pure functions that return value types - even if the function took pointers or references as arguments or allocated memory internally. They should but perfectly memoizable.

bool func(int x) /* pure? */ { int[] a, b; a = new int[x]; b = new int[x]; return (a.ptr < b.ptr); } Where do you draw the line?

Hmmmm. I think that it was pointed out somewhere else in this thread that that sort of comparison is already undefined in C (and thus probably D) - certainly it's not something that's really valid to do normally. However, there are other things that we currently do "normally" which have similar problems (e.g. toHash on Object hashing the reference). Maybe if we could come up with a set of operations which weren't valid in a pure function because they'd behave differently depending on which memory block was given to new, then we could make it work. But we may simply need to say that memoization of pure functions just isn't going to work if we allow allocations to take place in pure functions. That wouldn't be ideal, but I'm also not convinced that it matters much. It's already so rare that memoization of a function call can occur, that I'm pretty much convinced that memoization is useless as an optimization - at least as long as the compiler is doing it. After all, how often does a function get called with same the arguments within a single function let alone a single expression (and as I understand it, memoization only ever occurs at this point within either a single expression or statement - I don't remember which - but regardless, it's not even within a whole function)? And since there's no way that the compiler is going to memoize alls to a function across functions or even across calls to the same function which is calling the function which is being memoized, unless it's very common to call a function with the same result within a single function (and I really don't think that it is), then memoization by the compiler is really of minimal benefit, much as it would be nice to have it where we can. Regardless, we should error on the side of not memoizing in order to avoid undefined behavior due to memory allocations causing the pure function to act slightly differently across function calls (even when it's given the same arguments). - Jonathan M Davis
May 18 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 01:19:29 UTC, Jonathan M Davis via 
Digitalmars-d wrote:
 It's already so rare that memoization of a function call can 
 occur, that I'm
 pretty much convinced that memoization is useless as an 
 optimization - at
 least as long as the compiler is doing it. After all, how often 
 does a
 function get called with same the arguments within a single 
 function let alone
 a single expression (and as I understand it, memoization only 
 ever occurs at
 this point within either a single expression or statement - I 
 don't remember
 which - but regardless, it's not even within a whole function)?

Memoization is valid throughout the program. Opportunities occur frequently with generic programming and inlining.
 Regardless, we should error on the side of not memoizing in 
 order to avoid

Then you don't need strict pure functions.
May 18 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 19 May 2014 05:16:13 +0000
via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Monday, 19 May 2014 at 01:19:29 UTC, Jonathan M Davis via
 Digitalmars-d wrote:
 It's already so rare that memoization of a function call can
 occur, that I'm
 pretty much convinced that memoization is useless as an
 optimization - at
 least as long as the compiler is doing it. After all, how often
 does a
 function get called with same the arguments within a single
 function let alone
 a single expression (and as I understand it, memoization only
 ever occurs at
 this point within either a single expression or statement - I
 don't remember
 which - but regardless, it's not even within a whole function)?

Memoization is valid throughout the program. Opportunities occur frequently with generic programming and inlining.

I seriously question that assertion. How often do you really call the same function with the same arguments? And given that for the memoization to be done by the compiler without saving the result somewhere (which could actually _harm_ efficiency in many cases and certainly isn't something that the compiler does right now), the most that it could possibly memoize would be within a single function, that makes it all the less likely that it could memoize any calls. And given that the most it currently memoizes would be within a single expression (or possibly a single statement - I can't remember which), that makes it so that about the only time that it can memoize function calls is when you do something like foo(2) * foo(2), and how often does _that_ happen? Sure, it happens from time to time, but in my experience, it's very rare to make the same function call with the same arguments within a single expression or statement.
 Regardless, we should error on the side of not memoizing in
 order to avoid

Then you don't need strict pure functions.

As far as I'm concerned the two big gains from pure are 1. it makes it easier to reason about code, because it guarantees that the function didn't access any global or static variables. 2. it allows us to implicitly convert to different levels of mutability for the return type of pure functions where the compiler can guarantee that the return value was allocated within the function. Any other benefits we get from pure are great, but they're incidental in comparison. And in particular, in my experience, memoization opportunities are so rare that there's really no point in worrying about them. They're just a nice bonus when they do happen. - Jonathan M Davis
May 18 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 05:39:49 UTC, Jonathan M Davis via 
Digitalmars-d wrote:
 1. it makes it easier to reason about code, because it 
 guarantees that the
 function didn't access any global or static variables.

It can, through the parameters, like an array of pointers. And avoiding IO is not sufficient to mark 90% of my code as weakly pure.
 2. it allows us to implicitly convert to different levels of 
 mutability for
 the return type of pure functions where the compiler can 
 guarantee that the
 return value was allocated within the function.

But if you can have a struct/pointer as a parameter then you can clearly return objects not allocated in the function?
May 18 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 19 May 2014 06:05:26 +0000
via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Monday, 19 May 2014 at 05:39:49 UTC, Jonathan M Davis via
 Digitalmars-d wrote:
 1. it makes it easier to reason about code, because it
 guarantees that the
 function didn't access any global or static variables.

It can, through the parameters, like an array of pointers. And avoiding IO is not sufficient to mark 90% of my code as weakly pure.

Except that if most of your code is marked pure, then there aren't very many points where it could access a global or static variable. And regardless of that, the fact that the only way to access a global or static variable in a pure function is through one of its arguments still guarantees that the function isn't messing with anything that wasn't passed to it, so that still helps a lot with being able to reason about code. Sure, it could still be passed an argument that points to a global variable (directly or indirectly), but then you only have to worry about globals being accessed if they were passed in (directly or indirectly). Sure, it's not as big a gain as when a function is strongly pure, but it's good enough for most cases.
 2. it allows us to implicitly convert to different levels of
 mutability for
 the return type of pure functions where the compiler can
 guarantee that the
 return value was allocated within the function.

But if you can have a struct/pointer as a parameter then you can clearly return objects not allocated in the function?

The compiler is smart enough in many cases to determine whether the return value could have been passed in or not (though it wouldn't surprise me if it could be made smarter in that regard). With a function like string foo(string bar) pure {...} it can't assume that the return type is unique, because it could have been passed in via the parameter, but with string foo(char[] bar) pure {..} or int* foo(string bar) pure {..} it could, because it's impossible for the parameter to be returned from the function (unless casting that breaks the type system is used anyway - and the compiler is free to assume that that isn't done). So, it varies quite a bit as to whether a pure function is guaranteed to be returning newly allocated memory or not, but the compiler often can determine that, and when it can, it makes dealing with immutable far, far more pleasant. It's particularly useful when you need to allocate an immutable object but also need to mutate it as part of initializing it. If you do it in a pure function where the compiler knows that the object couldn't have been passed in, then the return type can be freely converted to various levels of mutability - including immutable - without having to use immutable within the function. - Jonathan M Davis
May 18 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 06:30:46 UTC, Jonathan M Davis via 
Digitalmars-d wrote:
 makes dealing with immutable far, far more pleasant. It's 
 particularly useful
 when you need to allocate an immutable object but also need to 
 mutate it as
 part of initializing it. If you do it in a pure function where 
 the compiler
 knows that the object couldn't have been passed in, then the 
 return type can
 be freely converted to various levels of mutability - including 
 immutable -
 without having to use immutable within the function.

It does not appear as a clean design that functions should have different semantics than a block. What matters is that the object reference is unique. Confusing this with pure seems like a bad idea.
May 19 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 19 May 2014 07:37:55 +0000
via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Monday, 19 May 2014 at 06:30:46 UTC, Jonathan M Davis via
 Digitalmars-d wrote:
 makes dealing with immutable far, far more pleasant. It's
 particularly useful
 when you need to allocate an immutable object but also need to
 mutate it as
 part of initializing it. If you do it in a pure function where
 the compiler
 knows that the object couldn't have been passed in, then the
 return type can
 be freely converted to various levels of mutability - including
 immutable -
 without having to use immutable within the function.

It does not appear as a clean design that functions should have different semantics than a block. What matters is that the object reference is unique. Confusing this with pure seems like a bad idea.

I don't follow you. The fact that D's pure helps the compiler determine cases where it knows that the return value of a function is unique is a key feature of pure and has proven to be a great idea. Perhaps you're hung up on the fact that the term "pure" is being used, and you're thinking about functional purity? If so, forget about pure in the functional sense if you want to discuss D purity. You need to think of it as something more like noglobal. That combined with other information in the function signature allows the compiler to determine cases where it knows that the returned value is unique. It also can lead to the compiler determining that a function in functionally pure and thus memoizable, but at this point, that's pretty incidental to what pure is and does. It's part of it, but it's not the primary feature of what D's pure is or is for. It's unfortunate that the language's evolution lead us to using the term pure for what it's currently used for, but we're pretty much stuck with it at this point. Regardless, the fact that D's pure allows us to determine when the return value of a function has to be unique is fantastic and has proven very helpful. - Jonathan M Davis
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 18 May 2014 09:58:25 -0400, H. S. Teoh via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via  
 Digitalmars-d wrote:
 On Thu, 15 May 2014 08:43:11 -0700
 Andrei Alexandrescu via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever
 automatically memoize strongly pure function results by compiler.
 A very practical concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it.


Memoizing reference returns that are immutable should be fine.
 However, that should have no effect on pure functions that return
 value types - even if the function took pointers or references as
 arguments or allocated memory internally. They should but perfectly
 memoizable.

bool func(int x) /* pure? */ { int[] a, b; a = new int[x]; b = new int[x]; return (a.ptr < b.ptr); } Where do you draw the line?

Definitely this is fine being pure, and can be memoized. It just won't do what you thought it would. So? :) This is what Andrei meant as being "penalized." -Steve
May 19 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 19 May 2014 09:42:31 -0400
Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
wrote:

 On Sun, 18 May 2014 09:58:25 -0400, H. S. Teoh via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via
 Digitalmars-d wrote:
 On Thu, 15 May 2014 08:43:11 -0700
 Andrei Alexandrescu via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever
 automatically memoize strongly pure function results by
 compiler. A very practical concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it.


Memoizing reference returns that are immutable should be fine.

Only if you consider it okay for the behavior of the function to change upon memoization - or at least don't consider that the behaviors changed due to the fact that the objects are equal but not the same object (which can matter for reference types) is something that matters. It has less of an impact when you're dealing with immutable objects, because changing the value of one won't change the value of another, but it can still change the behavior of the program due to the fact that they're not actually the same object. So, I'd be inclined to argue that no functions which return memory should be memoizable. And given that the compiler can only memoize functions within a single expression (or maybe statement - I can't remember which) - I don't think that that restriction even costs us much. - Jonathan M Davis
May 19 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 08:51:11 UTC, Jonathan M Davis via 
Digitalmars-d wrote:
 Perhaps you're hung up on the fact
 that the term "pure" is being used, and you're thinking about 
 functional
 purity?

No, I just don't think it makes much sense the way "pure" is defined in D. Since it doesn't actually mean anything specific unless you also do analysis of the parameters and return type. If you put a restriction on a function then that restriction should be well defined, clear and useful for a specific purpose.
 stuck with it at this point. Regardless, the fact that D's pure 
 allows us to
 determine when the return value of a function has to be unique

But it doesn't declare a return value to be unique… It just states that there are no side effects except through the arguments, and except for object identity. I am also not sure if it makes much sense to make it mandatory to define a function in order to initialize an immutable value in an imperative language. I don't like the orthogonal aspect of blocks and functions. Imperative functions and procedures are essentially named blocks of statements. Pure functions are essentially expressions.
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 12:35:26 -0400, Jonathan M Davis via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On Mon, 19 May 2014 09:42:31 -0400
 Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On Sun, 18 May 2014 09:58:25 -0400, H. S. Teoh via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via
 Digitalmars-d wrote:
 On Thu, 15 May 2014 08:43:11 -0700
 Andrei Alexandrescu via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever
 automatically memoize strongly pure function results by
 compiler. A very practical concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it.


Memoizing reference returns that are immutable should be fine.

Only if you consider it okay for the behavior of the function to change upon memoization - or at least don't consider that the behaviors changed due to the fact that the objects are equal but not the same object (which can matter for reference types)

It shouldn't matter. Something that returns immutable references, can return that same thing again if asked the same way. Nobody should be looking at the address in any meaningful way.
 is something that matters. It has less of an impact when
 you're dealing with immutable objects, because changing the value of one  
 won't
 change the value of another, but it can still change the behavior of the
 program due to the fact that they're not actually the same object.

Such a program is incorrectly written.
 And given that the compiler can only memoize functions within a single
 expression (or maybe statement - I can't remember which) - I don't think  
 that
 that restriction even costs us much.

It can make a huge difference, and it doesn't have to be memoized within the same expression, it could be memoized globally with a hashtable, or within the same function. -Steve
May 19 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer 
wrote:
 It shouldn't matter. Something that returns immutable 
 references, can return that same thing again if asked the same 
 way. Nobody should be looking at the address in any meaningful 
 way.

I think this is at odds with generic programming. What you are saying is that if you plug a pure function into an algorithm then you have to test for "pure" in the algorithm if it is affected by object identity. Otherwise, goodbye plug-n-play.
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Gr=C3=B8stad  =

<ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer wrote:
 It shouldn't matter. Something that returns immutable references, can=


 return that same thing again if asked the same way. Nobody should be =


 looking at the address in any meaningful way.

I think this is at odds with generic programming. What you are saying =

 that if you plug a pure function into an algorithm then you have to te=

 for "pure" in the algorithm if it is affected by object identity.  =

 Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for certain = = reasons is OK, Object identity being one of them. But some of the tricks being detailed here as "proof" that we cannot = memoize are not really valid code. Returning the same immutable object, when called with the same immutable= = parameters, should never cause a break in code, pure or not. -Steve
May 19 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer 
wrote:
 Returning the same immutable object, when called with the same 
 immutable parameters, should never cause a break in code, pure 
 or not.

This isn't at all obvious to me. Also I think the "coin flip trick" represent a class of algorithms that depend on imposing a sort order on objects. I can easily see an algorithm break if you sometimes receive the same object and sometimes receive a new object with the same values as parameters. That's how an optimizer works, sometimes it optimizes, sometimes not. If your algorithm depends on running something twice and then comparing the two results then it could easily break. In order to prevent this you would need to "box it as a value" and let the type system forbid object identity comparison.
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 13:44:59 -0400, Ola Fosheim Gr=C3=B8stad  =

<ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer wrote:
 Returning the same immutable object, when called with the same  =


 immutable parameters, should never cause a break in code, pure or not=


 This isn't at all obvious to me. Also I think the "coin flip trick"  =

 represent a class of algorithms that depend on imposing a sort order o=

 objects.

Anything that uses the order of unrelated addresses is incorrect outside= = of the heap code itself.
 I can easily see an algorithm break if you sometimes receive the same =

 object and sometimes receive a new object with the same values as  =

 parameters.

Then you should have no problem producing an example, right?
 That's how an optimizer works, sometimes it optimizes, sometimes not. =

 your algorithm depends on running something twice and then comparing t=

 two results then it could easily break.

The whole POINT of pure functions is that it will return the same thing.= = The fact that it lives in a different piece of memory or not is not = important. We have to accept that. Any code that DEPENDS on that being i= n = a different address is broken. For instance, I would consider it fully possible and reasonable, and to = = only break already-broken code (except for testing implementation, which= = would have to change anyway), to make idup just return the argument if t= he = argument is immutable. -Steve
May 19 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 18:33:55 UTC, Steven Schveighoffer 
wrote:
 Anything that uses the order of unrelated addresses is 
 incorrect outside of the heap code itself.

Nah, not on modern archiectures without GC compaction.
 Then you should have no problem producing an example, right?

I did. Besides, I think language constructs should be proven sound a priori, not post mortem...
 The whole POINT of pure functions is that it will return the 
 same thing. The fact that it lives in a different piece of 
 memory or not is not important. We have to accept that. Any 
 code that DEPENDS on that being in a different address is 
 broken.

Which neans you cannot safely plug a pure function into a generic algorithm unless it testsfor purity.
 For instance, I would consider it fully possible and 
 reasonable, and to only break already-broken code (except for 
 testing implementation, which would have to change anyway), to 
 make idup just return the argument if the argument is immutable.

That could easily break sound code that need guards with different identities.
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 14:49:41 -0400, Ola Fosheim Gr=C3=B8stad  =

<ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 18:33:55 UTC, Steven Schveighoffer wrote:

 Then you should have no problem producing an example, right?

I did. Besides, I think language constructs should be proven sound a =

 priori, not post mortem...

Let me cut to the chase here. I haven't seen it. Let's not go any furthe= r = until you can produce it. -Steve
May 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer 
wrote:
 On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Grøstad 
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer 
 wrote:
 It shouldn't matter. Something that returns immutable 
 references, can return that same thing again if asked the 
 same way. Nobody should be looking at the address in any 
 meaningful way.

I think this is at odds with generic programming. What you are saying is that if you plug a pure function into an algorithm then you have to test for "pure" in the algorithm if it is affected by object identity. Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for certain reasons is OK, Object identity being one of them.

immutable(Object*) alloc() pure { return new Object(); } bool oops() pure { auto a = alloc(); auto b = alloc(); return a is b; } This is a snippet that will always return `true` if memoization is at work and `false` if strongly pure function will get actually called twice. If changing result of your program because of silently enabled compiler optimization does not indicate a broken compiler I don't know what does.
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 15:03:55 -0400, Dicebot <public dicebot.lv> wrote:

 On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer wrote:
 On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Gr=C3=B8stad  =


 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer wrote:
 It shouldn't matter. Something that returns immutable references, c=




 return that same thing again if asked the same way. Nobody should b=




 looking at the address in any meaningful way.

I think this is at odds with generic programming. What you are sayin=



 is that if you plug a pure function into an algorithm then you have =



 test for "pure" in the algorithm if it is affected by object identit=



 Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for certa=


 reasons is OK, Object identity being one of them.

immutable(Object*) alloc() pure { return new Object(); } bool oops() pure { auto a =3D alloc(); auto b =3D alloc(); return a is b; } This is a snippet that will always return `true` if memoization is at =

 work and `false` if strongly pure function will get actually called  =

 twice. If changing result of your program because of silently enabled =

 compiler optimization does not indicate a broken compiler I don't know=

 what does.

The code is incorrectly implemented, let me fix it: bool oops() pure { return false; } -Steve
May 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Monday, 19 May 2014 at 19:20:46 UTC, Steven Schveighoffer 
wrote:
 On Mon, 19 May 2014 15:03:55 -0400, Dicebot <public dicebot.lv> 
 wrote:

 On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer 
 wrote:
 On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Grøstad 
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer 
 wrote:
 It shouldn't matter. Something that returns immutable 
 references, can return that same thing again if asked the 
 same way. Nobody should be looking at the address in any 
 meaningful way.

I think this is at odds with generic programming. What you are saying is that if you plug a pure function into an algorithm then you have to test for "pure" in the algorithm if it is affected by object identity. Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for certain reasons is OK, Object identity being one of them.

immutable(Object*) alloc() pure { return new Object(); } bool oops() pure { auto a = alloc(); auto b = alloc(); return a is b; } This is a snippet that will always return `true` if memoization is at work and `false` if strongly pure function will get actually called twice. If changing result of your program because of silently enabled compiler optimization does not indicate a broken compiler I don't know what does.

The code is incorrectly implemented, let me fix it: bool oops() pure { return false; } -Steve

Oh, and are probably eager to show me links to specs which indicate what part of my snippet breaks the type system? Is it allocation that is forbidden in reasonable code? Or object identity? Please stop this "write proper code" absurdism. This code is safe, doesn't use casts or pointer forging or any other dirty low level tricks. If compiler can't reject it as invalid and goes into funny mode instead, compiler is fucked. There can be no excuse for it. Your statement is essentially no different from "yeah this language supports addition but please never add 3 and 6, it is incorrect and will always return random results". Language spec is demanded for a reason.
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 16:23:34 -0400, Dicebot <public dicebot.lv> wrote:

 On Monday, 19 May 2014 at 19:20:46 UTC, Steven Schveighoffer wrote:
 On Mon, 19 May 2014 15:03:55 -0400, Dicebot <public dicebot.lv> wrote=


 On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer wrote:
 On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Gr=C3=B8stad  =




 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer wrote=





 It shouldn't matter. Something that returns immutable references,=






 can return that same thing again if asked the same way. Nobody  =






 should be looking at the address in any meaningful way.

I think this is at odds with generic programming. What you are =





 saying is that if you plug a pure function into an algorithm then =





 you have to test for "pure" in the algorithm if it is affected by =





 object identity. Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for =




 certain reasons is OK, Object identity being one of them.

immutable(Object*) alloc() pure { return new Object(); } bool oops() pure { auto a =3D alloc(); auto b =3D alloc(); return a is b; } This is a snippet that will always return `true` if memoization is a=



 work and `false` if strongly pure function will get actually called =



 twice. If changing result of your program because of silently enable=



 compiler optimization does not indicate a broken compiler I don't kn=



 what does.

The code is incorrectly implemented, let me fix it: bool oops() pure { return false; } -Steve

Oh, and are probably eager to show me links to specs which indicate wh=

 part of my snippet breaks the type system? Is it allocation that is  =

 forbidden in reasonable code? Or object identity?

None is forbidden, and the combination above is a BUG. Bugs happen, = compilers actually compile them. pure !=3D bug-free.
 Please stop this "write proper code" absurdism. This code is safe,  =

 doesn't use casts or pointer forging or any other dirty low level  =

 tricks. If compiler can't reject it as invalid and goes into funny mod=

 instead, compiler is fucked. There can be no excuse for it.

The code above relies on implementation details of the allocator to do = it's work. It's invalid to do so. Please show me the code that goes into "funny land" because of an = incorrect result of oops. I suppose it looks like this: if(oops()) { system("rm -rf /"); } The example is meaningless, because it uses a ridiculous method to = calculate false. Honestly, the above code COULD be written like this: immutable(Object) alloc() pure { static immutable o =3D new immutable(Object); return o; } And be just as valid (and more efficient). -Steve
May 19 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 18:55:57 UTC, Steven Schveighoffer 
wrote:
 On Mon, 19 May 2014 14:49:41 -0400, Ola Fosheim Grøstad 
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 18:33:55 UTC, Steven Schveighoffer 
 wrote:

 Then you should have no problem producing an example, right?

I did. Besides, I think language constructs should be proven sound a priori, not post mortem...

Let me cut to the chase here. I haven't seen it. Let's not go any further until you can produce it.

I've given several examples, but I oppose the general attitude. Language constructs should be formally proven correct. Proving a program to be correct is usually not worth it, but for individual language construct it is indeed possible and necessary, optimization depends on it. This is also why you should strive for a small set of primitives and build high level constructs by lowering them to the minimal language. You can then limit your proof to the primitives. The basic idea in generic programming is that you can implement the full blown generic algorithm, plug in the parts that can vary and let the optimizing compiler boil it down into an optimized tight machine language construct. The programmer should not be required to "deduce" what will happen when he plugs stuff into the generic algorithm. If optimization change semantics you will risk efficient algorithm implementations either going wrong or into an infinite loop. Not at all suitable for a programming language that aims for system level efficiency and generic programming.
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 16:56:58 -0400, Ola Fosheim Gr=C3=B8stad  =

<ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 18:55:57 UTC, Steven Schveighoffer wrote:
 On Mon, 19 May 2014 14:49:41 -0400, Ola Fosheim Gr=C3=B8stad  =


 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 18:33:55 UTC, Steven Schveighoffer wrote:

 Then you should have no problem producing an example, right?

I did. Besides, I think language constructs should be proven sound a=



 priori, not post mortem...

Let me cut to the chase here. I haven't seen it. Let's not go any =


 further until you can produce it.

I've given several examples

Links?
 , but I oppose the general attitude. Language constructs should be  =

 formally proven correct. Proving a program to be correct is usually no=

 worth it, but for individual language construct it is indeed possible =

 and necessary, optimization depends on it.

I think it is correct. How is it not? Proving correct is very difficult,= = proving incorrect is not difficult. Just a counter example is needed. So= = far, the examples have not disproven the point.
 If optimization change semantics you will risk efficient algorithm  =

 implementations either going wrong or into an infinite loop. Not at al=

 suitable for a programming language that aims for system level  =

 efficiency and generic programming.

It's not incorrect, just a bug to depend on an allocator allocating two = = different addresses, or allocating in a certain order. In other words, inside a pure function, an allocator of an immutable = object is to be treated as if it may or may not choose to return the sam= e = object. That's just what you should expect. Expecting something else is = a = BUG. -Steve
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 17:14:44 -0400, Steven Schveighoffer  =

<schveiguy yahoo.com> wrote:

 On Mon, 19 May 2014 16:56:58 -0400, Ola Fosheim Gr=C3=B8stad  =

 <ola.fosheim.grostad+dlang gmail.com> wrote:

 I've given several examples

Links?

BTW, you probably shouldn't expect any response from me, I'm about to go= = into travel-prep mode, and I likely will not be checking forums. If you = = are at dconf, perhaps we can continue the discussion in person :) -Steve
May 19 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 19 May 2014 at 21:16:19 UTC, Steven Schveighoffer 
wrote:
 BTW, you probably shouldn't expect any response from me, I'm 
 about to go into travel-prep mode, and I likely will not be 
 checking forums. If you are at dconf, perhaps we can continue 
 the discussion in person :)

I am not going to be there, but I guess this topic could easily fit in on the back side of paper napkin (or a dozen). Have a nice trip!
May 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Monday, 19 May 2014 at 20:51:22 UTC, Steven Schveighoffer 
wrote:
 On Mon, 19 May 2014 16:23:34 -0400, Dicebot <public dicebot.lv> 
 wrote:

 On Monday, 19 May 2014 at 19:20:46 UTC, Steven Schveighoffer 
 wrote:
 On Mon, 19 May 2014 15:03:55 -0400, Dicebot 
 <public dicebot.lv> wrote:

 On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer 
 wrote:
 On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Grøstad 
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven 
 Schveighoffer wrote:
 It shouldn't matter. Something that returns immutable 
 references, can return that same thing again if asked the 
 same way. Nobody should be looking at the address in any 
 meaningful way.

I think this is at odds with generic programming. What you are saying is that if you plug a pure function into an algorithm then you have to test for "pure" in the algorithm if it is affected by object identity. Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for certain reasons is OK, Object identity being one of them.

immutable(Object*) alloc() pure { return new Object(); } bool oops() pure { auto a = alloc(); auto b = alloc(); return a is b; } This is a snippet that will always return `true` if memoization is at work and `false` if strongly pure function will get actually called twice. If changing result of your program because of silently enabled compiler optimization does not indicate a broken compiler I don't know what does.

The code is incorrectly implemented, let me fix it: bool oops() pure { return false; } -Steve

Oh, and are probably eager to show me links to specs which indicate what part of my snippet breaks the type system? Is it allocation that is forbidden in reasonable code? Or object identity?

None is forbidden, and the combination above is a BUG. Bugs happen, compilers actually compile them. pure != bug-free.

No it is not. It is semantically valid code which does exactly what it was expected to do. Unless compiler optimization happens which will actually introduce a bug silently. It is optimization that is broken, not code itself. And this is not some sort of imaginary code. `alloc` implementation may be located in some other static library and not available to compiler. It is likely to be not a plain `alloc` in real code but some utility function that creates and returns object internally. In the end result is the same. You can't allow even object identity operator if memoization is to happen reliably.
 Please stop this "write proper code" absurdism. This code is 
 safe, doesn't use casts or pointer forging or any other dirty 
 low level tricks. If compiler can't reject it as invalid and 
 goes into funny mode instead, compiler is fucked. There can be 
 no excuse for it.

The code above relies on implementation details of the allocator to do it's work. It's invalid to do so.

Wrong again. It does not rely upon anything. It simply checks if two objects returned by two functions calls are identical. With zero assumptions about it.
 Please show me the code that goes into "funny land" because of 
 an incorrect result of oops.

What the hell are you speaking about? Getting two different results for a function depending on -O flag is not weird enough for you? - Hey, this program produces a wrong output! - But it doesn't wipe your system. You will be fine. At this point it is hard to believe you are serious and not trolling.
May 19 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 19 May 2014 13:11:43 -0400
Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
wrote:

 On Mon, 19 May 2014 12:35:26 -0400, Jonathan M Davis via
 Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Mon, 19 May 2014 09:42:31 -0400
 Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On Sun, 18 May 2014 09:58:25 -0400, H. S. Teoh via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via
 Digitalmars-d wrote:
 On Thu, 15 May 2014 08:43:11 -0700
 Andrei Alexandrescu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever
 automatically memoize strongly pure function results by
 compiler. A very practical concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it.


Memoizing reference returns that are immutable should be fine.

Only if you consider it okay for the behavior of the function to change upon memoization - or at least don't consider that the behaviors changed due to the fact that the objects are equal but not the same object (which can matter for reference types)

It shouldn't matter. Something that returns immutable references, can return that same thing again if asked the same way.

Except that a pure function _can't_ return the same object by definition - not unless it was passed in via an argument. And unless the compiler can guarantee that the object being return _isn't_ newly allocated, then it has to assume that it could have been, in which case, it can't assume that two calls to the same pure function return the same object. It may return _equal_ objects - but not the same object. And since we're talking about reference types, the fact that they're not the same object can definitely have an impact on the behavior of the program.
 Nobody should be looking at the address in any meaningful way.

Maybe they shouldn't be, but there's nothing stopping them. It's perfectly legal to write code which depends on the value of the address of an object. So, memoizing the result of a pure function which returns a reference type _will_ have an impact on the behavior of some programs.
 is something that matters. It has less of an impact when
 you're dealing with immutable objects, because changing the value
 of one won't
 change the value of another, but it can still change the behavior
 of the program due to the fact that they're not actually the same
 object.

Such a program is incorrectly written.

Well, then Object.toHash is incorrectly written.
 And given that the compiler can only memoize functions within a
 single expression (or maybe statement - I can't remember which) - I
 don't think that
 that restriction even costs us much.

It can make a huge difference, and it doesn't have to be memoized within the same expression, it could be memoized globally with a hashtable, or within the same function.

Not by the compiler. All it ever does with regards to memoization is optimize out multiple calls to the same function with the same argument within a single expression. It doesn't even make that optimization elsewhere within a function. Sure, a programmer could choose to explicitly memoize the result, but then it's up to them to not memoize it when it shouldn't be memoized. - Jonathan M Davis
May 19 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 19 May 2014 14:33:55 -0400
Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
wrote:

 The whole POINT of pure functions is that it will return the same
 thing. The fact that it lives in a different piece of memory or not
 is not important. We have to accept that. Any code that DEPENDS on
 that being in a different address is broken.

Except that if you're talking about reference types, and the reference points to two different objects, then they're _equal_ rather than being the same object. That's the whole point of the is operator - to check whether two objects are in fact the same object. I agree that relying on things like whether one address in memory is larger or smaller than another address in unrelated memory is just plane broken, but it's perfectly legitimate for code to depend on whether a particular object is the same object as another rather than equal. And memoizing the result of a function - be it pure or otherwise - will therefore have an effect on the semantics of perfectly valid programs. And honestly, even if equality were all that mattered for memoization, the fact that the compiler only does it on a very, very restrictive basis (since it never saves the result, only optimizes out extraneous calls) makes it so that memoization is kind of useless from the standpoint of the compiler. It's only really useful when the programmer does it, and they can decide whether it's okay to memoize a function based on the requirements of their program (e.g. whether reference equality matters or just object equality). - Jonathan M Davis
May 19 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 19 May 2014 15:20:46 -0400
Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
wrote:

 On Mon, 19 May 2014 15:03:55 -0400, Dicebot <public dicebot.lv> wrote:

 On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer wrote:
 On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Grøstad
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer
 wrote:
 It shouldn't matter. Something that returns immutable
 references, can return that same thing again if asked the same
 way. Nobody should be looking at the address in any meaningful
 way.

I think this is at odds with generic programming. What you are saying is that if you plug a pure function into an algorithm then you have to test for "pure" in the algorithm if it is affected by object identity. Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for certain reasons is OK, Object identity being one of them.

immutable(Object*) alloc() pure { return new Object(); } bool oops() pure { auto a = alloc(); auto b = alloc(); return a is b; } This is a snippet that will always return `true` if memoization is at work and `false` if strongly pure function will get actually called twice. If changing result of your program because of silently enabled compiler optimization does not indicate a broken compiler I don't know what does.

The code is incorrectly implemented, let me fix it: bool oops() pure { return false; }

Sure, that particular example may be contrived, but there's plenty of code out there that checks for whether two objects are the same object. A classic example would be for skipping equality checks if the two objects are the same object, but it could be used in far more complex situations that don't involve doing equality checks when two objects aren't the same. The reality of the matter is that regardless of whether you think that checking two objects to see whether they're the same object is a valid operation or not, it's perfectly legal to do so and _will_ happen in code, so if the compiler makes optimizations which will change whether two objects are the same object (e.g. optimizing out a second call to a pure function within an expression so that the result is reused in spite of the fact that the function returns a new object each time it's called), then the result is that the semantics of the program have changed due to an optimization. And that is most definitely a bad thing. IMHO, if the compiler cannot guarantee that a pure function returns the same object every time if it returns a reference type, then the compiler should never optimize out multiple calls to that function. To do otherwise would make it so that the semantics of the program change due to an optimization. - Jonathan M Davis
May 19 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 18:46:22 -0400, Dicebot <public dicebot.lv> wrote:

 On Monday, 19 May 2014 at 20:51:22 UTC, Steven Schveighoffer wrote:
 On Mon, 19 May 2014 16:23:34 -0400, Dicebot <public dicebot.lv> wrote:


 Oh, and are probably eager to show me links to specs which indicate  
 what part of my snippet breaks the type system? Is it allocation that  
 is forbidden in reasonable code? Or object identity?

None is forbidden, and the combination above is a BUG. Bugs happen, compilers actually compile them. pure != bug-free.

No it is not. It is semantically valid code which does exactly what it was expected to do. Unless compiler optimization happens which will actually introduce a bug silently. It is optimization that is broken, not code itself.

Again, the bug is to break if a function that allocates an immutable object for some reason re-uses the immutable object (perfectly legitimate optimization, whether done by the compiler or intentionally). I still have not seen the code that somehow can't handle this.
 And this is not some sort of imaginary code. `alloc` implementation may  
 be located in some other static library and not available to compiler.  
 It is likely to be not a plain `alloc` in real code but some utility  
 function that creates and returns object internally.

alloc isn't the problem. oops is incorrectly implemented to depend on implementation details of the allocator.
 Please stop this "write proper code" absurdism. This code is safe,  
 doesn't use casts or pointer forging or any other dirty low level  
 tricks. If compiler can't reject it as invalid and goes into funny  
 mode instead, compiler is fucked. There can be no excuse for it.

The code above relies on implementation details of the allocator to do it's work. It's invalid to do so.

Wrong again. It does not rely upon anything. It simply checks if two objects returned by two functions calls are identical. With zero assumptions about it.

Then why is oops returning true a failure case?
 Please show me the code that goes into "funny land" because of an  
 incorrect result of oops.

What the hell are you speaking about? Getting two different results for a function depending on -O flag is not weird enough for you?

It's not unheard of. When you violate language assumptions, it happens. I've seen code that breaks when -O is passed, vs. when it's not.
 - Hey, this program produces a wrong output!
 - But it doesn't wipe your system. You will be fine.

This is a superficial reading of my statement ;)
 At this point it is hard to believe you are serious and not trolling.

Yeah, it was kind of trolling, but I keep asking questions and have been given the same irrelevant answers. Sorry. -Steve
May 20 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 23:33:30 -0400, Jonathan M Davis via Digitalmars-d  =

<digitalmars-d puremagic.com> wrote:

 On Mon, 19 May 2014 15:20:46 -0400
 Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On Mon, 19 May 2014 15:03:55 -0400, Dicebot <public dicebot.lv> wrote=


 On Monday, 19 May 2014 at 17:35:34 UTC, Steven Schveighoffer wrote:=



 On Mon, 19 May 2014 13:31:08 -0400, Ola Fosheim Gr=C3=B8stad
 <ola.fosheim.grostad+dlang gmail.com> wrote:

 On Monday, 19 May 2014 at 17:11:43 UTC, Steven Schveighoffer
 wrote:
 It shouldn't matter. Something that returns immutable
 references, can return that same thing again if asked the same
 way. Nobody should be looking at the address in any meaningful
 way.

I think this is at odds with generic programming. What you are saying is that if you plug a pure function into an algorithm then=





 you have to test for "pure" in the algorithm if it is affected by=





 object identity. Otherwise, goodbye plug-n-play.

I think I misstated this, of course, looking at the address for certain reasons is OK, Object identity being one of them.

immutable(Object*) alloc() pure { return new Object(); } bool oops() pure { auto a =3D alloc(); auto b =3D alloc(); return a is b; } This is a snippet that will always return `true` if memoization is at work and `false` if strongly pure function will get actually called twice. If changing result of your program because of silently enabled compiler optimization does not indicate a broken compiler I don't know what does.

The code is incorrectly implemented, let me fix it: bool oops() pure { return false; }

Sure, that particular example may be contrived, but there's plenty of =

 code out
 there that checks for whether two objects are the same object. A class=

 example would be for skipping equality checks if the two objects are t=

 same
 object

If anything, the optimization will make this more efficient.
 , but it could be used in far more complex situations that don't invol=

 doing equality checks when two objects aren't the same.

This is hand-waving. I need a real example to understand.
 The reality of the matter is that regardless of whether you think that=

 checking two objects to see whether they're the same object is a valid=

 operation or not, it's perfectly legal to do so and _will_ happen in  =

 code, so
 if the compiler makes optimizations which will change whether two  =

 objects are
 the same object (e.g. optimizing out a second call to a pure function =

 within
 an expression so that the result is reused in spite of the fact that t=

 function returns a new object each time it's called), then the result =

 that
 the semantics of the program have changed due to an optimization. And =

 that is
 most definitely a bad thing.

How so? What exactly happens when two identical, but immutable objects, = = are optimized into being the same object?
 IMHO, if the compiler cannot guarantee that a pure function returns th=

 same
 object every time if it returns a reference type, then the compiler  =

 should
 never optimize out multiple calls to that function. To do otherwise wo=

 make it so that the semantics of the program change due to an  =

 optimization.

General reference type, yes. Immutable reference type, no. -Steve
May 20 2014
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 May 2014 23:14:03 -0400, Jonathan M Davis via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On Mon, 19 May 2014 13:11:43 -0400
 Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On Mon, 19 May 2014 12:35:26 -0400, Jonathan M Davis via
 Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Mon, 19 May 2014 09:42:31 -0400
 Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 On Sun, 18 May 2014 09:58:25 -0400, H. S. Teoh via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via
 Digitalmars-d wrote:
 On Thu, 15 May 2014 08:43:11 -0700
 Andrei Alexandrescu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 5/15/14, 6:28 AM, Dicebot wrote:
 This is not true. Because of such code you can't ever
 automatically memoize strongly pure function results by
 compiler. A very practical concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

Agreed. The fact that a pure function can return newly allocated memory pretty much kills the idea of being able to memoize pure functions that return pointers or references, because the program's behavior would change if it were to memoize the result and reuse it.


Memoizing reference returns that are immutable should be fine.

Only if you consider it okay for the behavior of the function to change upon memoization - or at least don't consider that the behaviors changed due to the fact that the objects are equal but not the same object (which can matter for reference types)

It shouldn't matter. Something that returns immutable references, can return that same thing again if asked the same way.

Except that a pure function _can't_ return the same object by definition - not unless it was passed in via an argument.

Compiles today (2.065): immutable(Object) alloc() pure { static immutable o = new immutable(Object); return o; }
 Such a program is incorrectly written.

Well, then Object.toHash is incorrectly written.

It might actually be, yes. toHash really should examine the object contents, not the address. -Steve
May 20 2014