Inheriting Purity

written by Walter Bright

February 22, 2012

In the D programming language, functions can be specified to be pure with an attribute:

pure int foo() { ... }

and the compiler will check that, indeed, the body of the function foo() does not do anything that violates purity:

no reading or writing of global mutable data
no calling impure functions

In other words, the return value of a pure function will be the same if its arguments are the same. Pure functions are an essential characteristic of functional programming, and their value is widely recognized. So far, so good.

Now, consider a class B that derives from class A and overrides one of its functions:

class A {
    int foo(int i) { ... }
}
class B : A {
    override pure int foo(int i) { ... }
}

It overrides an impure function A.foo with a pure function B.foo. But wait a moment! Mustn't they be the same type, i.e. either both pure or both impure?

In fact, that's not the case; the signature of the overriding method does not have to be exactly the same as the corresponding method in the base class. It has long been known that derived class methods are covariant in the return type and contravariant in the parameter types. Simply put, the overriding method may accept base parameter types and return a derived type. And even that is not the whole story. The Contract Programming discipline argues that generally an overriding method could require less and provide more without that affecting the soundness of the program. And purity does require less and provide more, so it fits the bill quite well.

This is because A.foo sets the requirements for the virtual function foo, and overrides of it must either meet the requirements or do better. Purity is an additional requirement on B.foo, but that doesn't affect the virtual caller. This is standard polymorphism.

So what happens with this?

class A {
    pure int foo(int i) { ... }
}
class B : A {
    override int foo(int i) { ... }
}

Impure B.foo overrides pure function A.foo. This can't work, because A.foo's virtual caller is expecting purity. It isn't covariant. And, indeed, the compiler catches it:

test.d(5): Error: function test.B.foo of type int(int i) overrides but is
not covariant with test.A.foo of type pure int(int i)

which is the current state of affairs with the D compiler. But it kind of bugged me:

It turns out that quite a lot of functions are pure, even though they aren't marked as pure.
Programmers tend to take the easy way, and just omit marking pure functions as pure.
If you've got a complex inheritance hierarchy, and want to make some base functions pure, you're faced with a bunch of editing of the function signatures on all the overriding functions, even though they may already be pure.
Darn it, it's looking like the compiler is giving a spurious error.

Although D is a statically typed language, it does a lot of type inference and type deduction. It even does purity inference for all function templates and lambdas. That has been a great success, particularly because it's the kind that simply makes things work better, removes unnecessary limitations, and requires no work from the programmer.

D also does inheritance of in and out contracts. Couldn't purity be inherited? Can this work?

It turns out it can work! In cases where the compiler previously emitted the aforementioned covariance error, if the covariance was simply a missing pure annotation, add in the annotation. Voila! Of course, then the compiler has to also check that the newly minted pure function really is pure by looking at its body. The idea is completely semantically sound, and does not break any existing code. It's also robust from a code maintenance standpoint — the maintenance programmer can also add a pure qualifier to the base class functions without risk of silently breaking anything.

Can we take this idea further? Turns out, yay, we can! It also works for const, nothrow, and @safe attributes. Stay tuned!

Conclusion

pure, const, nothrow and @safe all have well-known ‘viral’ effects, meaning that once you start using it it tends to need to pervade the code. Like a chocolate bar, you can't just take a single bite of it. Inheritance and inference of these attributes (along with the rest of D's type inference and deduction abilities) helps a lot with reducing the tedium of the viral effect of refactoring code to take advantage of them. This capability is in the development version of D now, and will go out in the next release.

Acknowledgements

Thanks to Andrei Alexandrescu for his helpful comments.

Articles

Inheriting Purity

Conclusion

Acknowledgements