Writing a compiler: how to get simple templates to work?

Question

I have a language with a very C++-like syntax. The lexer and parser are in place and produce the correct AST. For the largest part the backend is also done.

The basic system the compiler uses to create types is very simple: all types are considered built-in and all instances are global. So there's just a simple map which matches a types name to a method that creates a Variable which is basically a generic type like boost::any. Another map with the variable's name as key and the Variable as value serves as the global scope:

std::map< std::string, std::function< Variable() > typeList;

  //register some types
typeList[ "X" ] = Variable::Create<X>;
typeList[ "Y" ] = CreateInstanceOfY;
....

When the compiler gets the AST node for an initialization like X myVar; it basically does

std::map< std::string, Variable > globalScope;
globalScope[ "myVar" ] = typeList[ "X" ]();

When myVar is used later on it can be accessed by simple type dispatching like

X& x = myVar.GetReference<X>();

Now I would like to extend this a bit and use simple templates. Suppose there is a type "array" which is implemented using a vector. I could register everything like

typeList[ "array<X>" ] = Variable::Create< std::vector< X > >;

but that is not quite managable as it would have to be repeated for all combinations. Ideally I'd need functionality allowing to write something like this:

typeList.CreateTemplateVariable( "array", "X" )

which would then create a Variable instance which internally holds an std::vector< X >. I tried hard but cannot figure out how to do this. Maybe I just started the wrong way with the simple type mapping and is that the reason I cannot get my head around it.

So the question is simple: is it possible to do this? And how?

Answer 1

I am not sure I got your problem right, but if you have M parametric types (vector<>, list<>, ...) and N simple types (int, double, ...), you would need M*N actual implementations if you want to support all combinations. All these implementations have to be known at compile time (or in principle you might invoke C++ compiler on-the-fly). Do you actually want this?

A workaround could be to use non-typed containers instead. For example, vector<Object*> storing pointers that can be subsequently converted to the required type, for example with a dynamic_cast. This way you would only need M implementations for parametric types, and can resolve "array" to vector, and "X" to X independently.

Answer 2

Generally the way you do template-like types is as you describe, but instead of creating all possible combinations ahead of time, you create them on demand. So you might have a getType routine like:

std::function< Variable() > getType(std::string name) {
    auto rv = typeList[name];
    if (rv) return rv;
    auto template_start = name.find('<');
    if (template_start != string::npos) {
        auto template_end = name.rfind('>');
        std::string arg = name.substr(template_start+1, template_end);
        std::string base = name.substr(0, template_start);
        typeList[name] = rv = InstantiateTemplate(base, arg);
        return rv; }
    throw UnknownTypeError(name);
}

This gets called for any type referred to in the program, creating the needed template instantiations on demand.