Implementing Pure Functions

[Andrei Alexandrescu]

On 6/17/11 8:39 AM, bearophile wrote:
> Andrei:
>
>> Automatic inference should not be slower than verification of
>> conditional purity. The work involved is the same.
>
>> No, it would work for all template functions and ran either
>> opportunistically or only as needed.
>
> The first thing you say goes against the second: if you run the
> verification algorithm even if the template is not tagged with pure,
> then you are doing more work than running it only on templates tagged
> as pure.

Well there are two sides of the coin. If you call e.g. a template 
function from within a pure function, you must do the verification 
anyway, or refuse to compile if the annotation is missing. Whether or 
not the annotation is present, the verification work done toward a 
successful compilation is the same. If anything, the time to a _failed_ 
compilation may be slower (but not arbitrarily so).

On the bright side, inference is great - no more need for the user to 
bother with annotations, the compiler takes care of it. Furthermore, the 
compiler may opportunistically infer function attributes (pure, nothrow 
etc.) if it wants to optimize a specific context.

> And even if it runs only on templates tagged with pure, I think the
> compiler is able to do a bit less work if you use pure(CTcond)
> instead, because the CTcond is chosen by the programmer to be quite
> discriminating.

The downside of that would be not only that the programmer must spend 
time figuring the right annotation, but also that the result will be 
suboptimal.

> I guess this can be solved adding some heuristics to
> the compiler: to test first the most probable places where something
> impure is (like the functions given as function or template
> arguments), to prune the impurity search graph faster.
>
> In the end I think your idea of automatic purity is better (if it
> works), because it's more handy for the programmer. But I suggest to
> add some pruning heuristics, and to run it only on templates tagged
> with pure.

It's Walter's. Templates should not be tagged with pure unless they are 
pure for all instantiations. Otherwise the annotation would lose any 
guarantee.


Thanks,

Andrei