Struct-typing in Phobos

[Chris Williams]

I've been working on adding dcrypt to Phobos, which meant 
considering what to do in terms of taking it easy and simply 
pushing it in as-is, or converting all of the classes and 
interfaces into structs with type checkers (I'll be doing the 
latter). But it made me consider the pros and cons of the two 
options.

Basically, it seemed to come down to:

Pro-structs
1. Smaller, faster
2. Adds unique D-ish flavor to the standard library

Anti-structs
1. Difficult to read. E.g. a beginning programmer needs to be 
able to look at this and understand it before he can use the 
library:

size_t insertBack(Stuff)(Stuff stuff) if 
(isImplicitlyConvertible!(Stuff, T) || isInputRange!Stuff && 
isImplicitlyConvertible!(ElementType!Stuff, T));

And of course, even being able to read it, one would still need 
to track down isInputRange() and isImplicitlyConvertible() to 
know what they do.

2. When using classes and interfaces, type checking is as simple 
as writing the type to be passed in as a parameter. With 
struct-typing, people need to manually append a series of checks 
all over the place, which results in things like the following:

auto uniform(T, UniformRandomNumberGenerator)(ref 
UniformRandomNumberGenerator urng) if (!is(T == enum) && 
(isIntegral!T || isSomeChar!T));

Even though isUniformRNG() exists and is used on other 
implementations of uniform(), it isn't used here, because whoever 
developed the function forgot to include it on this particular 
function.

3. Non-extensible. To "extend" an SList or whatever, I would have 
to write a wrapper class with methods that forward to the SList 
methods, if I wanted my object to be able to interoperate with 
Phobos, or I would need to modify Phobos so that the body of 
SList was a template that could be mixed in (assuming I didn't 
want to override any methods, just add new ones).

4. Unclear how great an advantage the smaller/faster aspect 
actually gives us relative to the demerits of this style of 
coding. For example, using code from the below writeup (see 
below), I tested the performance of inserting 100,000 items then 
removing them all 100 times with both the interface/class and 
struct versions, for a total time of 1905±4ms / 1930±10ms (with a 
slightly smaller test the struct won, suggesting that there's no 
real difference). My suspicion is that the compiler/linker was 
detecting that there was only a single implemntation with no 
subclasses, hence it compiled out to something roughly equivalent 
with no vtable, so I split class implementation of HashSet into 
two, with an abstract base class that contained the "data" 
variable and nothing else, with all the methods declared in the 
subclass and that bumped the runtime to 1980±10ms. But still 
that's only a 2.5% difference in speed and only if one goes 
gung-ho with layering classes.

And for many objects - like random generators or HashSets - you 
aren't going to have masses of instances of the same type, just 
one top-level instance that internally contains basic data types 
(like structs), so there likely won't be much of a memory 
difference for most applications either.


Personally, I think that a better method of type-specialization 
needs to be added to the language (e.g. allowing isX!T statements 
to be used as types where we write types rather than preprocessor 
functions or allowing structs to implement interfaces) so that 
post-fixed "if" statements on function declarations are more of a 
last-ditch effort, rather than the norm. Though as pointed out, 
it might not be worth it unless someone can point out truly 
significant performance advantages.

But certainly for the moment, at least having an article about 
these things on the top site seems advisable, given how 
frequently we see them in the standard library. Plus, users and 
Phobos developers might want to have a quick tutorial to make 
their own.

So here's a quick write-up:

----

The core library of a language should be small, fast, powerful, 
and generic. This last item, however, causes a problem for 
library architects. Traditionally, the more generic something is, 
the larger and slower it is - with several layers of abstraction 
and indirection to allow many disparate implementations of a 
generic idea to all serve under the same interface. D supports 
all of the features that would allow one to write a library like 
this, but it also supports features that allow one to write a 
library which does not sacrifice performance for generality.

For example, here would be a standard declaration of a Set 
interface and a simple implementation as a class:

interface Set(T) {
     size_t length();
     size_t insert(T);
     T front();
     T back();
     void removeFront();
     void removeBack();
}

class HashSet(T) : Set!(T) {
private:
     void[0][T] data;

public:
     size_t length() {
         return data.length;
     }

     size_t insert(T value) {
         data[value] = [];
         return data.length;
     }

     T front() {
         foreach (k, v; data) {
             return k;
         }
         return T.init;
     }

     T back() {
         foreach_reverse (k, v; data) {
             return k;
         }
         return T.init;
     }

     void removeFront() {
         if (data.length == 0) return;

         T key;
         foreach (k, v; data) {
             key = k;
             break;
         }
         data.remove(key);
     }

     void removeBack() {
         if (data.length == 0) return;

         T key;
         foreach_reverse (k, v; data) {
             key = k;
             break;
         }
         data.remove(key);
     }
}

When we write a function which accepts a Set, we can write:

void foo(Set someSet) {
     someSet.insert(a);
     writeln(someSet.front);
}

This will accept and operate on any class which implements the 
Set interface (as you would expect).

To reduce overhead, in the D standard library, it is standard to 
try and implement this as a struct instead of as a class. But if 
we implement HashSet as a struct (which cannot implement an 
interface), then we would traditionally have no way to write 
functions which can accept generic types, like Sets.

This is solved firstly by use of the templating system. If I have 
a function which accepts a templated type, then so long as the 
code compiles once the type has been resolved, any arbitrary 
class or struct which implements the correct functions will 
compile and operate correctly.

void foo(Set)(Set someSet) { // "Set" is just a templated type 
name
     someSet.insert(a); // Only compiles if Set resolves to a type 
with insert and front defined
     writeln(someSet.front);
}

In a sense, this is a method for duck-typing in D, though not a 
very good one since if we look at the function declaration, it is 
not clear what types are or are not valid as parameters to foo(). 
We must look through the implementation of foo() to find useages 
of someSet to determine what is required. Likewise, there is 
nothing like "interface Set" which is mandating a standardized 
set of methods that all of our functions can expect and which 
developers of new implementations of Set types can know to 
implement.

This is corrected by use of compile-time duck-type checking 
templates. First we declare a template which implements a static 
test of compilability of the type for our chosen interface.

template isSet(Set) {
     enum bool isSet = is(typeof(
     (inout int = 0)
     {
         Set!int s = void; // can define an instance
         if (s.length == 0) {} // can test size
         s.insert(1); // can insert
         auto h = s.front; // can access front
         h = s.back; // can access back
         s.removeFront; // can remove front
         s.removeBack; // can remove back
     }));
}

Following this, we first want to validate that our implementation 
is compliant.

struct HashSet(T) {
     static assert( isSet!(HashSet!T) );
     ...
}

We can then upgrade foo() to also require only types which 
conform:

void foo(Set)(Set someSet) if (isSet!Set) {
     ...
}

While more verbose, this sort of duck-typing offers advantages 
beyond just speed. As it tests only 'compilability', options open 
up to allow flexibility in your definitions. One such example, 
the random number generators in std.random are defined so that 
they can be treated like InputRange types. Any InputRange is 
expected to return whether it is empty or not, but as a random 
number generator never becomes empty, in std.random the "empty" 
value is a constant (enum) attribute rather than a method.

Another similar benefit is the ability to allow undefined return 
types. For example, asymmetric cryptography algorithms should 
always generate Public and Private keys, but the values that 
comprise those keys is dependent on the algorithm used. 
RSAPublicKey and ElGamalPublicKey are basic data structures, not 
actionable classes. There is no reason to have a shared base 
class or common interface. With D's template-based duck-typing, 
one can validate the existence of public/private key accessors 
(using "auto" to hold the return values), without caring whether 
the return type for different implementations have the same or 
even interchangeable types.