Mixing polymorphism and templates.

[elfprince13]

I'm working on a statically type-checked DSL. An expression node of type T has type Expr<T>, and definition of T itself (representing a literal) is something like class T : Expr<T>. There are a handful of Expr-subclasses that still have unbound type parameters (i.e. Let<U,T> binds variables of type U and returns a value of type T).

I would like to, at a minimum, be able to pattern match over bounded sets of possible U and T without resorting to (manual) copy-paste.

The annoying, but reasonably scalable for a small set of types, solution would be a copy-paste macro.

The nice and extensible solution would be some ability to pattern match based on a variance specification for template arguments: if A is a subtype of B, then being able to match an instance of Expr<A> in a pattern that specifies Expr<B> would be ideal (in Scala notation, the pattern would be for Expr<+B>).

I suspect I'm not the only person who would like to be able to do something like this, and I'm wondering what the obstacles are to implementation.

[elfprince13]

As a follow-up, I realize that C++ requires manual implementation of templates that support variance, so another solution would be an "is convertible-to" pattern or an "is constructible-from" pattern.

[solodon4]

Hi Thomas,

Thank you for suggestions. It would really help a lot if you could post some code in ideal syntax or in another language that would show what are you trying to achieve (applicable to both comments). This doesn't have to be what the library or C++ support today. Variance specification would require language support, but if I see the use-case, I might be able to provide you a reasonable solution within the library.

[elfprince13]

Assume we have a class hierarchy with inheritance that looks something like this:

class Node;
template<class T> class Expr : public Node;
class X : public Expr<X>;
class Y : public X, public Expr<Y>;
class Z : public Expr<Z>;
template<class T> class Let : public Expr<T>;
template<class T> class Symbol : public Expr<T>;
// Some other non-literal expression types

I would like to be able to do something like this:

template<typename T> bool nodeEvalsToT(Node n){
  Match(n) { 
    Case(C<Expr<T> >(children)) return true;
    Otherwise() return false;
   } EndMatch
}

And have nodeEvalsToT<X>(y) return true for Symbol<Y> y.

Alternatively, I might like to do something like this:

std::string toString(Node n){
  Match(n){
    Case(C<Let<_> >(bindings, result)) /* something there */
    Case(C<Symbol<_> >(boundTo, name)) return name;
    // Some other cases
  } EndMatch
}

Where the _ could match some (restricted) candidate set of types.

I've been thinking about this for a bit, and I think I could actually contort my inheritance hierarchy for this application to make everything work as-is with a bit of hackery:

class Node {};
struct AnyVal { typedef AnyVal Super; };
template<typename Super, template<typename D, typename B, typename ...O> class DNode, typename ...O>
using DeriveToBase = typename std::conditional<std::is_same<Super, AnyVal>::value, Node, DNode<Super, typename Super::Super, O...> >::type;
template<class D, typename _Super=AnyVal> class Expr : virtual public DeriveToBase<_Super, Expr> {
	typedef _Super Super;
};
template<class T> using _Expr = Expr<T, typename T::Super>;

But I haven't gotten to test it yet, and it definitely doesn't feel like a "clean" solution.