Implementing Pure Functions

bearophile bearophileHUGS at lycos.com
Fri Jun 17 05:01:37 PDT 2011


Andrei:

> Right. I gave that example within the context of the discussion,

That Reddit page shows your last thoughts about conditional purity too:

>We do plan, however, to add purity inference for all template functions because the source code is by definition available. We believe that that is possible with a worklist approach. I haven't thought about it a lot, but it seems a fairly standard analysis. If you think it isn't, let us know before we look deeper into it! :o)<

>The algorithm would be quite powerful I think. It will be an optimistic analysis that starts with the assumption that a given template function is pure. Then for each function called by that function, put it in a worklist and iterate the worklist transitively replacing other functions with the functions they call, until either an impure function is found or the list is empty. If the list is empty, then the function is pure. So essentially the algorithm automatically annotates with "pure" (in the D sense) all template functions wherever possible. One neat thing is that for a given template function, some instantiations may be pure and some others may not.<

I presume this recursive algorithm is run only if the template is marked with "pure".

The older idea was to let the programmer control, and just add a condition to attributes, using something like @optional_tag or just adding the compile time condition beside the pure() attribute, an example:

template isPure(F) {
    enum bool isPure = functionAttributes!(F) & FunctionAttribute.PURE;
}

pure(isPure!F) int[] map(F)(F f, int[] data) {
    int[] res;
    foreach (x; data)
        res ~= f(x);
    return res;
}

We have to keep into account compilation time too. As more and more powerful features are added to the D type system, like this automatic purity, compilation time gets longer. Scala compilation is about ten times slower than Java code (even with the fast fsc compiler), and this makes programming in Scala a little worse in practice. Compilation time matters.

Is inferring purity automatically for templates as fast as a pure(CTcondition)? If the programmer uses something like pure(CTcondition) the compiler has to verify the purity of the template anyway, even if the condition is true, but the compiler doesn't need to verify that the template is pure if the CompileTime condition is false. Assuming most code is written correctly, I think this is able to shave away many tests, and save some time to the compiler, reducing compile time a bit.

Bye,
bearophile


More information about the Digitalmars-d mailing list