memoize

[Jonathan M Davis]

On Tuesday, January 04, 2011 06:15:16 Andrei Alexandrescu wrote:
> On 1/4/11 7:59 AM, Simen kjaeraas wrote:
> > Guilherme Vieira <n2.nitrogen at gmail.com> wrote:
> >> @Walter: would it be hard/impossible for the compiler to look at
> >> memoize and
> >> tell it exhibits pure behavior and is, thus, pure?
> > 
> > The simplest solution is this:
> > 
> > template memoize( alias fn ) {
> > static if ( isPure!fn ) {
> > pure auto memoize( ParameterTypeTuple!fn ) {
> > // Blah!
> > }
> > } else {
> > auto memoize( ParameterTypeTuple!fn ) {
> > // Blah!
> > }
> > 
> > }
> > }
> 
> I've been mulling over this for a while, maybe it's time to start
> discussing it.
> 
> Often you want to say "this entity is pure/const/immutable/safe... if
> this other entity is the same, or generally if this Boolean is true". So
> I was thinking of introducing e.g. a constrained pure:
> 
> template memoize( alias fn ) {
>      pure(isPure!fn) auto memoize( ParameterTypeTuple!fn ) {
>          ...
>      }
> }
> 
> So generally when you write "attribute(expression)" the attribute will
> be in effect if and only if the expression is true.
> 
> D has become very powerful at introspecting most of its own abstractions
> in the form of compile-time Booleans. This language extension would
> close the circle by allowing D to introduce attributes and qualifiers
> depending on compile-time Booleans.

We really do need something like this, and actually I was thinking of bringing 
it up again. The compiler should be able to determine if a template function is 
pure on its own, since it can look at all of the functions called and determine 
whether they're pure or not (the non-template functions will be obvious and the 
template ones would require the templates to be instantiated anyway, which would 
tell the compiler whether they were pure or not if the compiler were determining 
that, so determining whether a particular instantiation of template function can 
be pure shouldn't be all that hard) and then make the template function pure if 
they are and impure if they're not. Having a condition for purity as you suggest 
might be better. I don't know. It essentially requires the same thing though. 
It's just that the programmer is then making it explicit.

Regardless, we need _something_ like this or most template functions won't be 
able to be pure. And given how heavy templates are likely to be used in D - 
especially in Phobos - that seems like it would be unacceptable.

Also, nothrow and const have the same problem (and immutable too, I suppose, 
though I'm not sure that that's all that big a deal since it's likely going to 
be rare to mark a function as immutable). So, really, we need to find a way to do 
this for all such attributes and qualifiers, not just pure. Maybe pure(), 
const(), nothrow(), and immutable() should all be introduced as you're 
suggesting with pure. It might be nice though to have the compiler be able to do 
it for you rather than having to list every template function manually, since 
presumably, you're going to have to list them all anyway, though perhaps pure() 
and its compatriots would be useful with conditions other than function purity. 
So, maybe something like pure(auto) should be used, and then that would 
effectively lower to pure() with isPure!func for every template function called 
by that template function.

- Jonathan M Davis