Lock

That's pretty much it. I've decided that there's little choice except to lock a regular unordered_map. The issue is that when you come to more than a couple parameters, it's way unfeasible to implement the whole thing atomically. So the result would look something like (ignoring immutability):

threadsafe type vector()(type t) {
    static unordered_map(type, type) cache;
    static lock l;
    scoped_lock sl(l);
    if (cache.find(t) != cache.end())
        return cache[t];
    type retval = struct {
        ...
    }
    return cache[t] = retval;
}


Not sure how the thread-safe specifiers are going to work quite yet. Static variables make me iffy, but they're definitely not part of the interface and they're still thread-safe, if I initialize them before making any calls, so I'm not feeling too bad about it. Of course, as this is all going to be transformed before anything happens, then it shouldn't be too hard to transform it into something else, like

struct vector {
    unordered_map<type, type> cache;
    lock l;
    threadsafe type operator()(type t) {
        scoped_lock sl(l);
        if (cache.find(t) != cache.end())
            return cache[t];
        type retval = struct {
            ...
        }
        return cache[t] = retval;
    }
};


It's thread-safe and referentially transparent. Now we'll just add a dose of immutability (don't want anyone to play with my vectors or break their rules).

threadsafe immutable_type vector()(immutable_type t) {
    static unordered_map(immutable_type, immutable_type) cache;
    static lock l;
    scoped_lock sl(l);
    if (cache.find(t) != cache.end())
        return cache[t];
    type retval = struct {
        ...
    }
    return cache[t] = retval;
}

Problem solved?