Thread by @ryanjfleury

One of the most powerful lessons I learned as a programmer was to use combinatoric spaces to my advantage, rather than allowing them to explode into—for example—handwritten source code. This required relaxing, for example, an obsession with static type checking.

https://twitter.com/scheminglunatic/status/1869304249039081677

Instead what I learned was to use static product types to form homogeneous building blocks for large combinatoric spaces, and to organize data transforms around forming those spaces. Choosing actual points in this space becomes a completely dynamic capability.

This is related to my comment the other day on sum types. The reason you won’t find many of them in my code is that I find that they leak combinatoric spaces into the source code itself, by forming one “axis” (1 of N types), which might be multiplied by another. That puts it in the path of non-temporal physical reality—physical code—which must either be handwritten or generated. This is either slow for the programmer, or for the computer.

Whereas if you keep the source code looser, with homogeneous types, you can allow defining points & transitioning between points in the combinatoric space to be much more natural & trivial of a computation. In practice this means you’ve turned an O(N*M*…) into an O(N+M+…), for either yourself or the compiler, or code generator (all three are good).

The fundamental reason for this is machine code, being representable by a transform from A -> B (where A and B are definitions of data formats, or types), must have a shape which expects/fits A as the input, and expects/fits B as the output. A|C -> B means you must have two paths: A -> B | C -> B. This suggests that, as the number of types grows, the number of codepaths must also grow. Or, put another way, the structure of types is reflected in the source code which uses those types.

You can often see this concretely in C - a discriminated `union` implies a `switch` (or some other branching mechanism on the tag). An array can imply a loop over the indices. A linked list can imply a loop over the links. And so on.

Thus, when someone attempts to take static type checking to the extreme, and maximally fit all potential data payloads into a format which only stores data which those payloads use (e.g. no unused fields in any case), they are not only exploding the number of types, they are also exploding the number of codepaths.

When confronted with this reality, one impulse is to force compilers or other generators to iterate the combinatoric space manually; this is perhaps preferable to doing it by hand, but what's preferable over both options is to simply avoid the combinatoric space being present in this domain at all.

This makes distinctions in combinatoric spaces a very trivial data problem, rather than an arbitrarily difficult code problem. It makes the code small, yet the set of possible effects from the code large.

One obvious place this shows up is that if you introduce a C, where you could've had a single A* (an expanded A), then all of your auxiliary codepaths - serialization is a good example - need to now account for C, whereas they could've simply accounted for a more homogeneous A* structure.

@LizardOrman (Also completely disagreed on the “zero cost” part)

@LizardOrman New languages have introduced features to automate sum type management, and prevent errors one could easily encounter with their implementations in C. What I’m saying is that sum types were a bad design to begin with—language features which paper over them don’t change that.

@cairnc1 Personally I have found I only very rarely want the switch. I instead want a single type at the bottom, which expands out into these large 2^N spaces, so that a great deal is possible via small changes in data.