What does Combinatoric Interface mean?

Question

I am watching this talk by Sean Parent. He notes that:

Choosing the same syntax for the same semantics enables code reuse and avoids combinatoric interfaces

What does "combinatoric interface" mean?
Could you explain with an example?

P.S. Thinking more about this my guess is that if we have n types and m operations with common semantics on the types (they do the same thing on the types), instead of writing m x n functions (i.e. the possible combinations of types and operations), we only write m generic operations. Is that what it means?

Answer 1

The speaker's terminology is unfortunate and ambiguous, since he mentions combinatorial interfaces (soundtrack of the video) but wrote combinatoric interface (the slides in the video).

The speaker is in reality referring to interface combinatorics and more precisely combinatorial explosion, i.e. the rapid growth of code caused by the m x n combinations compared to the m possibilities that you very rightly spotted in your post-scriptum. So you got it right :-)

Since the speaker mentions C++ and the standard library, we can mention how the use of templates (the C++ way for generics) in libraries such as <algorithm> and <iterator> allows the programmer to write a single piece of code, using a single interface and the same syntax, that can be reused for 12 different kind of containers, using forward or backward iteration. Of course, all this because fortunately, the library authors ensured that the same syntax offered the same semantic. If the same semantic would be achieved for different containers with a different interface or syntax , the same programmer would have to write 24 variations of his/her code. So obviously, the reuse would not be facilitated.

I didn't watch the full presentation, but the speaker mentions immediately the necessity to respect the semantics associated with a syntax, such as for example the copy constructor. I do not have his example at hand, but there are plenty of StackOverflow examples where people misuse operator overloading to associate a well known operator syntax with behavior that does not comply with the expected semantic. My favourite example is the (mis)use of operator+ for doing a side effect and change an objet which is not supposed to be changed by the + operation. This results in a+b no longer being the same as b+a, not to speak about a+b+c.

May be worth to mention, but the combination of a semantic with a given syntax is at the origin of language idioms. So misusing the relation between syntax and semantic might not only create a combinatorial explosion (interface effect), but it might also generate a lot of misunderstanding and bugs (wrong expectations).

Answer 2

It means nothing, it is a poor choice of words. Combinatoricallity is not a measurable property. In fact, the word combinatoric does not exist.

The word combinatorial does exist:

relating to the selection of a given number of elements from a larger number without regard to their arrangement.

So what he means (judged by the example he gives) is that we should do with established semantic concepts rather than make up our own.

We could create a property named NumberOfElements for our collection but this would violate POLA (the Principle Of Least Astonishment). There is prior art, we should use it.

We could implement a property Count on our collection that gives us the number of times the collection was accessed. This would be bad for the same reason.

Answer 3

Combinatorics is, to put it simply, making combinations.

For example, let's say we combine a color with a piece of clothing:

* Red, green, blue
* Hat, shirt, pants

There are 6 options in total (3 colors + 3 clothing types) but there is a total of 9 combinations. This disparity grows as the number of options grows. The amount of combinations that exist (color_count * clothing_type_count) quickly outgrows the amount of options (color_count + clothing_type_count).

Suppose we want to test all of these things. It would be better if we write separate tests for the features themselves:

* Test for red
* Test for green
* Test for blue
* Test for hat
* Test for shirt
* Test for pants

Because that requires 6 total tests, compared to testing the 9 combinations themselves:

* Test for blue hat
* Test for blue shirt
* Test for blue pants
* Test for green hat
* Test for green shirt
* Test for green pants
* Test for red hat
* Test for red shirt
* Test for red pants

Further compounding the issue, suppose we add a new color (yellow). If we are testing the features separately, that requires us to write one new test:

* Test for yellow

But if we had been writing tests for the combinations themselves, then we would've have three times as much work:

* Test for yellow hat
* Test for yellow shirt
* Test for yellow pants

If you let the example grow, you'll see that the problem with testing combinations gets worse. If there were 100 clothing types, adding a new color would take 100x more work if we were testing every combination instead of the features themselves.

Choosing the same syntax for the same semantics enables code reuse and avoids combinatoric interfaces

"Red shirt" is an example of a combinatoric interface, as opposed to the separated "red" and "shirt" features.