Voldemort Types In D

written by Walter Bright

Sometimes, the confluence of existing features can yield unexpected surprises. While I'd like to think that we designed Voldemort Types into the D programming language, the reality is that they were discovered by Andrei Alexandrescu. What are Voldemort Types? Read on.

First, a bit of background.

An InputRange in D is a type with the following members:

Member	Description
`front`	get the first element of the range
`popFront`	remove the first element of the range
`empty`	are there more elements in the range?

which form the basis of iteration. Just for fun, let's design an InputRange which will return a sequence of random numbers, forever. (We can also call this a generator.)

It can look like this (not a very good random number generator, but it'll do for the moment):

module rnd;

struct RandomNumberGenerator {

    this(uint seed) {
        next = seed;
	popFront();   // get it going
    }

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

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

    @property bool empty() { return false; }

  private:
    uint next;
}

and a function that'll return it:

RandomNumberGenerator generator(uint seed) {
    return RandomNumberGenerator(seed);
}

and a lovely program that will print out 10 such numbers:

import std.stdio;
import rnd;

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

and the result is:

That's where one would normally stop. But there's just something annoying about it. All I really care about is the rnd.generator function, but yet there's this type RandomNumberGenerator sitting out there by itself. It just looks like a failure of encapsulation, as it is leaking outside of my generator abstraction.

I could mark it with the private attribute and modules other than rnd won't be able to access it. But it's still there, outside the scope of where it belongs, and other module members can still access it, private or not (in D, private declarations are not hidden from other declarations within the same module). Besides, I want it to be so clean it squeaks.

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.

Acknowledgements

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

Articles

Voldemort Types In D

Are Voldemort Types Really Just Existential Types?

Conclusion

Acknowledgements