Channels ▼

Walter Bright

Dr. Dobb's Bloggers

Inheriting Purity

February 22, 2012

In the D programming language, functions can be specified as 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:

  1. no reading or writing of global mutable data
  2. 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, don't they have to 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. 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:

  1. It turns out that quite a lot of functions are pure, even though they aren't marked as pure.

  2. Programmers tend to take the easy way, and just omit marking pure functions as pure.

  3. If you've got a complex inheritance hierarchy, and want to make some base functions pure, you're faced with editing the function signatures on all the overriding functions, even though they may already be pure.

  4. 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, yeah, 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.

Thanks to Andrei Alexandrescu for his helpful comments.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video