Channels ▼

Walter Bright

Dr. Dobb's Bloggers

Voldemort Types In D

May 07, 2012

Now for the fun stuff.

First off, D allows for type inference for declarations, so I can write things like:


auto g = RandomNumberGenerator(seed);

and g will automatically be typed as RandomNumberGenerator. This is standard stuff. Pulling on this string a bit more, and we can infer the return types of functions:

  auto square(double d) {
    return d * d;
  }

  auto x = square(2.3);

and the compiler will set the return type of square to double, as that is the type of the return statement's expression. Of course, x will then also be typed as double. Now let's reorganize our generator function to look like this:


  module rnd;

  auto generator(uint seed) {

    struct RandomNumberGenerator {

    @property int front() {
        return ((seed / 0x10000) * seed) >> 16;
    }

    void popFront() {
        seed = seed * 1103515245 + 12345;
    }

    @property bool empty() { return false; }
    }

    RandomNumberGenerator g;
    g.popFront();    // get it going
    return g;
  }

Something fascinating has happened. RandomNumberGenerator becomes a type that is inside generator's scope. It is simply not visible outside of generator. It cannot be named — hence it's a Voldemort Type.

We can only get an instance of it via type inference:


  auto g = generator(5);

and then use g. I know what you're thinking — use typeof and declare another instance of RandomNumberGenerator:


  auto g = generator(4);
  typeof(g) h;

Sorry, that won't work, the compiler will not allow a Voldemort Type to be instantiated outside of its scope (the technical reason is it has no reference to the seed local variable).

There's one last detail that irks me. The loop:

    int count;
    foreach (n; generator(5)) {
        writeln(n);
        if (++count == 10)
        break;
    }

just looks so old-fashioned. With ranges, we can dispense with many loops, and instead use the range take to just grab the first 10 elements of the range:

  void main() {
    foreach (n; take(generator(5), 10))
    writeln(n);
  }

and then use writeln to get rid of the loop entirely:


  void main() {
    writeln(take(generator(5), 10));
  }

Are Voldemort Types Really Just Existential Types?

Given a type T, and a type U that can be extracted from T that has a defined relationship to T, then U is existential.

For example, if we are presented with a type T that is a pointer, we can derive the existential type U it points to with:

  import std.stdio;

  void extractU(T)(T t) {
    static if (is(T U : U*))
      writefln("type %s is a pointer to an %s", typeid(T), typeid(U));
    else
      writefln("type %s is not a pointer", typeid(T));
  }

  void main() {
    int* t;
    extractU(t);
    double d;
    extractU(d);
  }

which prints:

  type int* is a pointer to an int
  type double is not a pointer

While Voldemort types certainly hide their implementation, that does not make them existential types. Since Voldemort Types cannot be extracted from some über type, they are not existential.

Conclusion

Voldemort Types were a happy discovery in D, and enable a satisfying technique of encapsulating types in a way that they can be used, but not named.

Thanks to Andrei Alexandrescu, Bartosz Milewski, David Held and Jason House for their helpful comments and criticisms.

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