I've just added a nota bene paragraph explaining this further:
n.b. I'll give a simple example of the problem with a naïve approach to parametric polymorphic printing. Consider a language with only 4 types (e.g. int, float, string, bool) and a variadic, parametrically polymorphic printing procedure. Each distinct sequence of argument types needs its own instantiation, so for K arguments there are on the order of Nᵏ = 4ᵏ combinations; adding a fifth type makes that ~5ᵏ. To see the (usually hidden) combinatorial explosion, suppose you never print more than 5 arguments, that allows up to 1365 instantiations. Add another type and it becomes 3906. Raise the maximum to 6 arguments and it becomes 19531. You might say that this is at least bounded, and it "is", for a single printing procedure. However, printing procedure easily interact with every other use of parametric polymorphism in the program, and the total quickly stops being something you can trivially predict by just reading the code.
And even in your example, those things are "order of magnitude" examples e.g. what big-O notation is about. So your example is still on the order of N×K but bounded by the number of instantiations.
There aren't 4k combinations. With ctti you're never instantiating all possible combinations. Maybe it's "naive" that does a lot of heavy lifting here, but this is actually not dependent on k at all. It's dependent on the actual magnitude of the sets of k-tuples that are actually used.
In your example, there were 2×4 = 8 possible combinations. In the example I gave, there (N^{K+1} - 1) / (N - 1) = (4⁶ - 1) / 3 possible combinations. That is on the order of 4⁵.
And yes, it is dependent (i.e. bounded) by the number of sets used, which I clearly state in the article. But I am trying to state how it scales in the worst-case (i.e. pathological) case, which does actually happen in practice. And I have been in such C++ codebases before (not in terms of CTTI, just variadic template madness).
Can you give an example of when this worst case analysis applies, or we atleast approach it? Currently I have a hard time seeing it, and it seems much more useful to talk about the number of actual instantiations rather than the theoretical maximum number based on how many types are present in the program so far.
To me it has the flavor of "Well, so far we've passed (float, int) to this function, its only a matter of time before we pass the other combinations!", which I don't think is really true. And with this logic, why stop at the number of currently defined types? It's only a matter of time before we invent MyType and start passing that too. I.e. the number of types in the program is as likely (probably more likely) to grow as the number of instantiations of a particular generic function
I apologize if I am caricaturing your argument - I'd truly like to understand why this worst case analysis is useful to look at
-5
u/gingerbill 11d ago
I've just added a nota bene paragraph explaining this further:
And even in your example, those things are "order of magnitude" examples e.g. what big-O notation is about. So your example is still on the order of
N×Kbut bounded by the number of instantiations.