Purity (D2 standard libraries / object.d)

[Jason House]

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? ;)