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.

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

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.

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.

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

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.

On Mon, 19 May 2014 13:44:59 -0400, Ola Fosheim Grøstad <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 on 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. If your algorithm depends on running something twice and then comparing the 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 in 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 the argument is immutable.

-Steve

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.

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.

-Steve

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.

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