This repository is an experiment with defining a rather complete typeclass system inside the C++ language.

The nearing of the C++20 standard has led me to revise this repository.

Following changes have been made:

• a few erroneus statements on SFINAE fixed
• a concept Instance introduced (see tc_concept.hpp)
• some new examples devised

Typical uses of typeclasses are following:

1. a solution to the “expression problem” (concerned with extending a datatype both with new operations and new variants without touching existing code)
2. a rich interface (an interface with a small set of required methods and a great supply of default methods defined in terms of the required ones or in terms of each another)
3. a compiler-checked logical constraint on a type or a tuple of types
4. a dynamic-dispatch mechanism (e.g. existential types in Haskell or dynamic traits in Rust)
5. function overloading (using type inference to determine a corresponding typeclass instance)

Typeclasses in the mainstream languages are rare (despite their general usefulness): the only two languages with builtin support for typeclasses seem to be Haskell and Rust (and some aspects of typeclasses can be emulated in several other languages).

It appears that typeclasses (at least with respect to all the usecases above) can be easily described by C++ templates. Futhermore a typeclass system supporting all the points above can be implemented using only Standard C++98. Our implementation consists of the tc.hpp header-only library and some usage examples in the samples directory.

The full C++98 implementation is very short: it consists of a struct declaration and three one-line variadic macros.

The C++11 implementation has in addition a single type alias (which can be used in place of one of the previously mentioned C++98 macros), a single short struct definition and a single one-line macro for forcing compile-time constraints.

This is a (very likely incomplete) list of C++ typeclass implementations which can be easily googled.

E.g. http://www.nauths.fr/en/2015/04/26/cpp-typeclasses.html or http://blog.shaynefletcher.org/2016/10/haskell-type-classes-in-ocaml-and-c.html.

A typeclass is modelled by a simple templated struct:

template<class T>
struct Monoid {
    static T empty();
    static T append(T, T);
};

A typeclass instance is defined by the template specialization:

template<>
struct Monoid<int> {
    static int empty() { return 0; }
    static int append(int x, int y) { return x+y; }
};

The main drawback is that no part of the definition of template<class T> struct Monoid is present in any of its specializations. So all the code in that definition describes only how the types for which the typeclass is not implemented behave.

The problem is that we have no simple way of defining default method implementations or enforcing logical constraints like “all instances of the typeclass A must also be instances of the typeclass B”.

Because the general typeclass template definition is concerned with the case of “type T is not an instance of the typeclass”, a much better version of the typeclass definition would be simply

template<class T> struct Monoid;

This line of thought gets us to the following.

A blogpost https://functionalcpp.wordpress.com/2013/08/16/type-classes/ has a little more elaborate definition using an explicit static boolean to distinguish between the types which implement the typeclass and the types which do not.

The problem with the inability to define default method implementations still persists.

Sometimes it is said that C++ concepts have lots in common with typeclasses. Unfortunately it's only partially true: of the five usecases listed in the introduction the C++ concepts provide only the third one: they group types into semantic categories so that a semantic category membership can be compile-time checked.

Some of the other typeclass features were present in a previous iteration of the concept system (so called “C++0x concepts”) but currently we have only a sort of “Concepts Lite”.

It may be interesting to compare concepts and typeclasses w.r.t. their logical strength.

Typeclasses support recursion, but can use only a conjunctive part of logic (i.e. one can say “type T belongs to a class X if T belongs to Y and to Z”, but cannot say “type T belongs to a class X if T belongs to at least one of Y and Z”).

Concepts do not support recursion, but can use the logical disjunction (with concepts there is no such a thing as a conflict of implementations).

Also concepts are an “if-and-only-if” condition as opposed to typeclasses, which allow to express separate implications in both directions.

Nevertheless, the introduction of concepts allows one to replace a rather clunky TC_REQUIRE macro with a simple constraint Instance (see tc_concept.hpp).

This constraint allows, for example, dispatching on the fact of some type not being an instance of some typeclass (see concept.cpp and show_concept.cpp). For a workaround not using concepts see show_unshowable.cpp.

Our implementation solves the issue that the template specializations override the original definition by never specializing the definition of a typeclass. Instead all typeclass instances are stored as specializations of a separate type (this type is same for all instances of all typeclasses). This allows us to define the default methods of a typeclass with a CRTP-like pattern.

Below we describe the structure and the workings of the tc.hpp header.

To define a typeclass one uses a templated struct with some static methods:

template<class T>
struct Foo {
    static void foo() = delete;
};

Default implementations (even mutually dependent) can be used:

template<class T>
struct Foo {
    // default typeclass methods are a sort of CRTP

    static int foo(int x) {
        TC_IMPL(Foo<T>) FooT; // this syntax is described below
        return FooT::bar(x) + 1;
    }

    static int bar(int x) {
        TC_IMPL(Foo<T>) FooT; 
        return FooT::foo(x) - 1;
    }
};

For more info on default methods see default.cpp.

All typeclass instances are tracked by a single type _tc_impl_. It's defined as

template<class T> struct _tc_impl_;

Adding a type Bar to the typeclass Foo is as simple as

template<>
struct _tc_impl_< Foo<Bar> > {
    typedef struct: Foo<Bar> { /* method implementations */ } type;
};

To facilitate such definitions a macro is introduced:

#define TC_INSTANCE(tc, body...) \
    struct _tc_impl_< tc > { typedef struct: tc body type; };

If the tc parameter has commas (e.g. Show< pair<int,int> > or Foo<Bar, Baz>) a small helper variadic macro can be used to wrap the parameter:

#define TC(x...) x

It should be noted that even in the case variadic macros are not supported a helpful set of macros can be defined:

#define TC_INSTANCE_BEGIN(tc) \
    struct _tc_impl_< tc > { typedef struct: tc
#define TC_INSTANCE_END type; };
#define COMMA ,

And now instead of

template<>
TC_INSTANCE(TC(Foo<Bar,Baz>), { 
    static void foo() { /* definition */ } 
})

we must write

template<>
TC_INSTANCE_BEGIN(Foo<Bar COMMA Baz>) {
    static void foo() { /* definition */ } 
} TC_INSTANCE_END

The tc.hpp provides two ways of calling methods of a typeclass.

The first way is to use the TC_IMPL macro defined as

#define TC_IMPL(tc...) typedef typename _tc_impl_< tc >::type

For example:

TC_IMPL(Foo<Bar,Baz>) FBB;

FBB::foo();

The second (less verbose) way is to use a C++11-only templated type alias

template<class T> using tc_impl_t = typename _tc_impl_<T>::type;

It is used as follows:

tc_impl_t<Foo<Bar,Baz>>::foo();

It can be used in conjunction with decltype to get a sort of poor man's type inference.

Fortunately, typeclasses play rather well with template overloads (see show.cpp where a templated overload of operator<< is used to infer a correct typeclass instance) so in some cases one doesn't need to specify any types at all.

The mechanism of C++ template instantiation provides an automatic checking of typeclass instance “real” dependencies (required by typeclass method implementations). E.g. with the following definition

template<class T>
TC_INSTANCE(Foo<Bar<T>>, {
    void foo() {
        tc_impl_t<Foo<T>>::foo();
    }
})

an attempt to use tc_impl_t<Foo<Bar<Baz>>>::foo() will fail if Baz doesn't implement the Foo typeclass.

But sometimes typeclasses are used as a sort of marker (e.g. Rust marker traits like Clone): a fact that some relation holds between some types. Frequently such typeclasses have no methods so the mechanism described above is useless.

We use a rather dumb solution: a static_assert checking if a static type field is present on the specific _tc_impl_ specialization.

template<class T> struct _tc_dummy_ { static bool const value = true; T t; };
#define TC_REQUIRE(tc...) \
    static_assert( _tc_dummy_<tc_impl_t<tc>>::value, "unreachable" );

It's very likely that a more beautiful solution exists.

Now there definitely exists a more beautiful solution: beginning from C++20, a requirement can be placed between template<...> and the corresponding class or instance definition:

template<class T> requires Instance<Foo<T>> // constraint on a class
struct Bar { ... };
// Rust:    trait Bar: Foo { ... }
// Haskell: class (Foo x) => Bar x where { ... }

template<class T> requires Instance<Good<T>> // constraint on an instance
TC_INSTANCE(Good<Foo<T>>, { ... });
// Rust:    impl<T: Good> Good for Foo<T> { ... }
// Haskell: instance (Good x) => Good (Foo x)

template<class T> requires Instance<Foo<T>> // constraint on an overload
void foo(T t) { ... }
// Rust:    fn foo<T: Foo>(t: T) { ... }
// Haskell: foo :: (Foo x) => x -> IO ()
//
// Note: this analogy is not precise. C++ allows to define the second 
// "fallback" overload, which is selected for types NOT implementing Foo:
template<class T> void foo(T t) { ... }

Also note that such a constraint can be placed using C++98-only constructs:

// a constrained typeclass instance
TC_INSTANCE(Foo<Bar<T>>, {
    TC_IMPL(Foo<T>) FooBar; 
    // instead of TC_REQUIRE(Foo<T>)

    /* some methods */
})

// a constrained function
void foo() {
    TC_IMPL(Foo<Baz>) FooBaz;
    FooBaz();
    // two lines instead of a single one: TC_REQUIRE(Foo<Baz>)

    /* some code */
}

For an example see the constrained.cpp file.

Existential types are a way of describing dynamic dispatch in terms of a typeclass system. Simply stated, if we have a (one-parametric, for the sake of simplicity) typeclass C then we have a type (exists a. C a => a) which is a supertype of any instance of the typeclass C. We'll use a shorter (Rust-like) notation dyn C below.

To describe such a type we must define two utility types. Suppose we have a typeclass

template<class T> 
struct Foo {
    // we can dispatch only through a reference or a pointer
    static void foo(T const &x, int y) = delete;
};

Now we define an abstract type corresponding to an existential dyn Foo

struct DynFoo {
    // now the first argument becomes "this"
    virtual void foo_self(int y) const = 0;
    virtual ~DynFoo() {}
};

template<>
TC_INSTANCE(Foo<DynFoo>, {
    static void foo(DynFoo const &x, int y) {
        x.foo_self(y);
    }
})

and a generic type to wrap objects of different types

template<class T>
struct DynFooWrapper: DynFoo {
    T self;

    void foo_self(int y) const {
        tc_impl_t<Foo<T>>::foo(self, y);
    }

    DynFooWrapper(T x): self(x) {}
};

The final step is to transform DynFooWrapper<T> values into an instances of DynFoo. This can be done by the means of boxing:

template<T>
std::unique_ptr<DynFoo> to_foo(T x) {
    return std::make_unique<DynFooWrapper<T>>(x);
}

Finally, it's convenient to define a Foo instance for boxed values:

template<T>
TC_INSTANCE(Foo<std::unique_ptr<T>>, {
    static void foo(std::unique_ptr<T> const &x, int y) {
        tc_impl_t<Foo<T>>::foo(*x, y);
    }
})

This last step is the only step which must be explicitly done in Rust (and all these steps are done implicitly in Haskell). So consider this only as a proof-of-concept demonstration that it is possible (albeit a little cumbersome) to adapt C++ inheritance-based dispatching to a typeclass system.

An example of existential types can be seen in the show.cpp file.

At the cost of slightly complicating the macros the “naive” version described above could be endowed with the same features as the tc.hpp implementation.

See the tc_alt.hpp header and the alt_samples directory. Significant differences in the usage are marked by a // DIFFERENCE comment.