On 6/17/11 7:01 AM, bearophile wrote:
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".
No, it would work for all template functions and ran either
opportunistically or only as needed.
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.
Automatic inference should not be slower than verification of
conditional purity. The work involved is the same.
We should do inference for pure, nothrow, const/immutable for any and
all template functions.
Andrei
