Implementing Pure Functions

[Timon Gehr]

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.
>
> 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. 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.
>
> Bye,
> bearophile

I think a template tagged with pure should be pure no matter what. Furthermore, I
think the additional work required is minimal. The compiler just has to store a
flag whether or not any function is pure and set it to false during semantic
analysis when it encounters an impure action within the function body. Also, I
assume that the bottleneck for compile time is parsing all the (Phobos) imports
(that is quite a lot even if you only import one function from one module!). But
hopefully local imports are going to improve that situation a lot. (I mean, why
exactly do I need to import Eg. std.regex when I do import std.stdio : writeln?)

A small problem I can see with the purity validation algorithm proposed by Andrei
relates to incremental builds (again):

module A;
int iampure(){
    return 5;
}

module B;
int puretemplate()(){ // inferred pure
    return iampure();
}

int main(){
    import std.stdio;
    writeln(puretemplate(), puretemplate()); // compiler caches result
}

$ dmd -c A
$ dmd -c B
$ dmd A.o B.o; ./A
55

Some funny guy decides to change A.iampure:
module A;
int iampure(){
    static int x;
    return ++x;
}

$ dmd -c A
$ dmd A.o B.o; ./A
11

Wrong! Should be 12.

Therefore, the compiler has to assume that functions defined in other modules are
not pure unless marked as such. (or issue a pure copy of each would-be-pure
function to the object file and call the pure version from inferred pure
templates. Then the problem would be detected at link time.)

I think the best way to handle it would be to make templates pure iff their body
would pass the standard purity validation. Less special casing.


Timon