Jason House wrote:
> I chose nearly dead keywords for a reason ;) If I got Walter to think
> about how to implement "pure" memoizers for an extra half hour, I
> will consider myself highly successful. I must leave the fishing
> discussion up to the two of you in a coffee shop! (I'd love to sit in
> and participate with that discussion, but online forums make the
> conversation far too difficult)

Coffee shop discussions are certainly the best.

dsimcha wrote:
> == Quote from Walter Bright (newshound1@digitalmars.com)'s article
>> 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.
>> The problem is identifying if this would be faster than recomputing the
>> return value.
> 
> Wouldn't this also cause threading issues?  The obvious solution would be to use
> TLS, but his requires duplicating the cache across threads.  Also, using AAs
> internally like this would lead to very deeply hidden memory allocations, and
> therefore possibly more frequent GC, etc.

Immutable data doesn't have threading issues, which is the beauty of them.

Andrei Alexandrescu wrote:
> Michel Fortin wrote:
>> On 2009-01-10 00:10:11 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:
>>
>>>> The problem is identifying if this would be faster than recomputing the return value.
>>>
>>> I used memoizers for exp and log (the most called functions in some code I wrote) and it made the original version feel like it was driving in reverse.
>>
>> That's only true because, in your specific context, those functions were called often with the same input. In a program that rarely use the same inputs, your memoizing functions will just waste time and memory.
> 
> No, because I use interpolation.

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.

== Quote from Walter Bright (newshound1@digitalmars.com)'s article
> 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.

Even if the bits are immutable, I can't see how this could work.  What if something is GC'd and then that memory location gets overwritten?  For example:

import std.contracts, std.stdio;

enum N = 100;

void main() {
    foo();
    bar();
}

uint pureFun(invariant uint[] data) pure {
    // Do stuff.
    return someUint;
}

void foo() {
    uint[] myArray = new uint[N];
    // Fill in myArray;
    invariant uint[] myInvariantArray = assumeUnique(myArray);
    writeln(pureFun(myInvariantArray));
}

void bar() {
    // Same as foo().
}

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.

== Quote from Walter Bright (newshound1@digitalmars.com)'s article
> dsimcha wrote:
> > == Quote from Walter Bright (newshound1@digitalmars.com)'s article
> >> 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. The problem is identifying if this would be faster than recomputing the return value.
> >
> > Wouldn't this also cause threading issues?  The obvious solution would be to use TLS, but his requires duplicating the cache across threads.  Also, using AAs internally like this would lead to very deeply hidden memory allocations, and therefore possibly more frequent GC, etc.
> Immutable data doesn't have threading issues, which is the beauty of them.

You misunderstood the question.  I mean, at the implementation level, even though it wouldn't be visible to the programmer, the AA that did the memoization would have to be mutable so it could be modified when a new value was to be memoized. This is where the threading issues would come in.  What I was saying is that synchronizing on this would be bad for obvious reasons, and TLS would still not be great because you wouldn't be able to share memoized values across threads.

On Sun, Jan 11, 2009 at 4:31 AM, Stewart Gordon <smjg_1998@yahoo.com> 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.
>

Heh heh.  Yeh, I remember I thought I'd found a major typo in the CLR algorithms tome when I first ran across that.  But it's not a typo. It's "memo-ization" as in writing down a memo for yourself to remind you of the answer later.

--bb

dsimcha wrote:
> You misunderstood the question.  I mean, at the implementation level, even though
> it wouldn't be visible to the programmer, the AA that did the memoization would
> have to be mutable so it could be modified when a new value was to be memoized.
> This is where the threading issues would come in.  What I was saying is that
> synchronizing on this would be bad for obvious reasons, and TLS would still not be
> great because you wouldn't be able to share memoized values across threads.

You're right, I hadn't thought of that. But you could do a per-thread memoization using thread local storage. No sync problems.

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.

Walter Bright wrote:
> Andrei Alexandrescu wrote:
>> Michel Fortin wrote:
>>> On 2009-01-10 00:10:11 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:
>>>
>>>>> The problem is identifying if this would be faster than recomputing the return value.
>>>>
>>>> I used memoizers for exp and log (the most called functions in some code I wrote) and it made the original version feel like it was driving in reverse.
>>>
>>> That's only true because, in your specific context, those functions were called often with the same input. In a program that rarely use the same inputs, your memoizing functions will just waste time and memory.
>>
>> No, because I use interpolation.
> 
> 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.

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.


Andrei

On Sun, Jan 11, 2009 at 8:51 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Walter Bright wrote:
>>
>> Andrei Alexandrescu wrote:
>>>
>>> Michel Fortin wrote:
>>>>
>>>> On 2009-01-10 00:10:11 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:
>>>>
>>>>>> The problem is identifying if this would be faster than recomputing the return value.
>>>>>
>>>>> I used memoizers for exp and log (the most called functions in some
>>>>> code I wrote) and it made the original version feel like it was driving in
>>>>> reverse.
>>>>
>>>> That's only true because, in your specific context, those functions were called often with the same input. In a program that rarely use the same inputs, your memoizing functions will just waste time and memory.
>>>
>>> No, because I use interpolation.
>>
>> 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.
>
> 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.

Just get Walter to implement AST macros and it should stop.  :-) Until then the library solutions are often unpalatable.  Like using string mixins to implement properties.  Ick.

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