Memory allocation purity

[Jonathan M Davis via Digitalmars-d]

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

> On Mon, 19 May 2014 12:35:26 -0400, Jonathan M Davis via
> Digitalmars-d <digitalmars-d at puremagic.com> wrote:
>
> > On Mon, 19 May 2014 09:42:31 -0400
> > Steven Schveighoffer via Digitalmars-d <digitalmars-d at puremagic.com>
> > wrote:
> >
> >> On Sun, 18 May 2014 09:58:25 -0400, H. S. Teoh via Digitalmars-d
> >> <digitalmars-d at 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 at 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