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.

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.

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.

> 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.

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 = new immutable(Object);
   return o;
}

And be just as valid (and more efficient).

-Steve

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.

On Mon, 19 May 2014 16:56:58 -0400, Ola Fosheim Grøstad <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ø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

Links?

> , 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.

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 all 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 same object. That's just what you should expect. Expecting something else is a BUG.

-Steve

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østad <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

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!

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.

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

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