== Quote from Walter Bright (newshound1@digitalmars.com)'s article
> dsimcha wrote:
> > In this case, foo.myInvariantArray goes out of scope when foo() returns.  When bar() allocates an array, it's entirely possible that the GC will give bar.myArray the same memory address as foo.myArray had.  In this case, if you're only using stack bits to handle memoization, you're screwed.
> That's the beauty of a garbage collector <g>. The bits will include a reference to the immutable data, which the gc will see, and so the gc will not reclaim that data.

Good point, the bits in the internal memoization AA will contain a reference.  I forgot about that.  This leads to another problem, though:  Wouldn't this cause a lot of soft memory leaks, since you're holding references to stuff that's otherwise no longer needed?

dsimcha wrote:
> == Quote from Walter Bright (newshound1@digitalmars.com)'s article
>> dsimcha wrote:
>>> In this case, foo.myInvariantArray goes out of scope when foo() returns.  When
>>> bar() allocates an array, it's entirely possible that the GC will give bar.myArray
>>> the same memory address as foo.myArray had.  In this case, if you're only using
>>> stack bits to handle memoization, you're screwed.
>> That's the beauty of a garbage collector <g>. The bits will include a
>> reference to the immutable data, which the gc will see, and so the gc
>> will not reclaim that data.
> 
> Good point, the bits in the internal memoization AA will contain a reference.  I
> forgot about that.  This leads to another problem, though:  Wouldn't this cause a
> lot of soft memory leaks, since you're holding references to stuff that's
> otherwise no longer needed?

The job of managing those kind of design tradeoffs is something that the programmer should handle.

Andrei Alexandrescu wrote:

>> That's way beyond the ability of a compiler to do automatically. The compiler would have to understand that the pure function produces continuous results.
> 
> You're replying to the wrong guy. I'm saying: the compiler shouldn't have to do so, but it should allow functions to do it.

Here's the simplest memoization example I could come up with.  Maybe we should try to figure out how to get this to work and then expand to other cases?

/** Fibonocci number generator based on
 * http://en.wikipedia.org/wiki/Fibonacci_number **/
pure int fibonocci(int n)
in { assert( i>=0 && i<10 ); }
out(result) { assert( result>0 ); }
body{
  static __thread int[10] cache = [0,1,-1,-1,-1,-1,-1,-1,-1,-1];
  if (cache[n] >= 0)
    return i;
  else return fibonacci(n-1)+fibonacci(n-2);
}

unittest{
  assert(fibonocci(4) == 3);
  assert(fibonocci(9) == 34);
}

Note the thread-local static variable.  That's guaranteed to be thread safe and is easy to prove that it has no side effects outside of the fibonocci function.

Inevitably, I've embarrassed myself by not actually passing what I thought was simple code through a compiler...


> Lately it looks like a lot of the problems discussed here inevitably lead to a built-in feature. We want properties, let's have a property thingy. We want memoization, let's have a memoize thingy. We want optimally aligned structures, let's have an optimal align thingy. I'm holding my breath for a request for the kitchen sink thingy.

That kitchen sink thingy sounds useful.  What does it do? ;)

Walter Bright wrote:
> Christopher Wright wrote:
>> Stewart Gordon wrote:
>>> Stewart Gordon wrote:
>>> <snip>
>>>> Walter, before you go and implement any of this, I must point out that it's spelt "memorization" and "memorize".  (Or "memorisation" and "memorise" if you're British, but that's an aside.)
>>>
>>> Or maybe not...
>>> http://en.wikipedia.org/wiki/Memoization
>>>
>>> Still, I'm confused....
>>>
>>> Stewart.
>>
>> I thought you were joking. What's confusing you?
> 
> I forgot.

Walter Bright is the new Stewart Gordon!

Bill Baxter wrote:
> But the call for a memoization thingy I just don't get.  No way that
> should be a compiler feature, just far too many ways to memoize with
> too many different tradeoffs.  And a memoizing wrapper function
> basically loses nothing in terms of expressiveness.
> 
> --bb

The ability for you to memoize a pure function and get a pure function as a result. Your pure functions can't use the memoized version of the pure function.

This means you might have to use a lot more memoization wrappers.

Jason House wrote:
> Andrei Alexandrescu wrote:
> 
>>> That's way beyond the ability of a compiler to do automatically.  The compiler would have to understand that the pure function produces continuous results.
>> You're replying to the wrong guy. I'm saying: the compiler shouldn't have to do so, but it should allow functions to do it.

So effectiely, the compiler could just trust pure functions to be actually pure, with UB for any that isn't?

> Here's the simplest memoization example I could come up with.

You mean the simplest example beyond just remembering a single property value?

> Maybe we should try to figure out how to get this to work and then
> expand to other cases?
<snip>
> Note the thread-local static variable.  That's guaranteed to be
> thread safe and is easy to prove that it has no side effects outside
> of the fibonocci function.
> 
> Inevitably, I've embarrassed myself by not actually passing what I
> thought was simple code through a compiler...
<snip>

Indeed.

Stewart.

On Sun, Jan 11, 2009 at 11:43 PM, Christopher Wright <dhasenan@gmail.com> wrote:
> Bill Baxter wrote:
>>
>> But the call for a memoization thingy I just don't get.  No way that should be a compiler feature, just far too many ways to memoize with too many different tradeoffs.  And a memoizing wrapper function basically loses nothing in terms of expressiveness.
>>
>> --bb
>
> The ability for you to memoize a pure function and get a pure function as a result. Your pure functions can't use the memoized version of the pure function.
>
> This means you might have to use a lot more memoization wrappers.

Isn't this the same old "logically const" vs "const" argument we went through ages ago?

--bb

Walter Bright wrote:
> dsimcha wrote:
>> Good point, the bits in the internal memoization AA will contain a reference.  I
>> forgot about that.  This leads to another problem, though:  Wouldn't this cause a
>> lot of soft memory leaks, since you're holding references to stuff that's
>> otherwise no longer needed?
> 
> The job of managing those kind of design tradeoffs is something that the programmer should handle.

*cough* And with weak pointer/reference types we could handle it quite nicely. *cough* ;)

"Walter Bright" wrote
> Andrei Alexandrescu wrote:
>> Walter Bright wrote:
>>> Michel Fortin wrote:
>>>> Hum, could the compiler be trusted to add the memoization code to pure functions so they can stay pure?
>>>
>>> If the compiler does general memoization on pure functions, all it has to do is use the bits of the arguments passed on the stack to the function as an index into an associative array of the return values.
>>
>> Not the bits, the full objects if they have indirection. (Pure functions should accept const parameters!)
>
> You're right, the "just the bits on the stack" is if the arguments are immutable. Const arguments would have to include whatever was indirectly referenced, which I argue is impractical for the runtime to handle automatically.

Bits on the stack also do not work for immutable reference arguments. Imagine two immutable strings that are exactly the same data, but have different pointers.  You wouldn't want to memoize only on the pointer values (or you'd lose

I think bits on the stack only work for non-reference arguments.  It sounds like memoization is a non-automatic feature in any case.  Which is a shame because I thought it was a common pure-function optimization by the way it was discussed in the past.

-Steve