The Unanticipated Powers of Total Program Cardinality

Author: Rodolfo Hansen, Philips Software Competency Lead

Total Program Cardinality (TPC) remains a largely under-explored facet of software engineering, but it holds transformative potential. It is a static analysis measure, representing the complete range of ways a program can pass a type checker. It is inspired by the principles behind algebraic data types and presents an innovative approach to understanding and enhancing software quality, our ability to deliver fast, effectively and keeping patient safety as our top priority at Philips.

In this series of articles we will compare TPC as a quantitative metric for generally accepted software quality principles that would otherwise be purely qualitative, which we are using to extend our suite of open source roslyn analyzers at Philips.

Total Program Cardinality: An objective metric for the Constructive Programmer

In a previous article, we touched upon constructive programming, which is about removing non-deterministic elements from our code. The benefit? It provides a framework where we can mathematically prove a program’s correctness. At its core, constructive programming focuses on eliminating certain practices to narrow down the range of valid programs.

It’s about how we can get everything done without being Turing Complete!

These practices have parallels with Total Program Cardinality (TPC). On one hand constructive programming aims to make proving correctness easy, fast, and cheap. On the other, TPC is an objective metric which predicts the maintainability of a codebase. They both recommend restricting our coding practices to achieve their respective goals.

In fact, TPC also has parallels with existing industry best practices. We are able to categorize these practices in four key stages (ranking them by their impact in improving the TPC score) of program transformation that significantly impact a codebase’s Maintainability.

The Algebraic Insight

Unions, sealed traits, enums, std::variant are all ways to have a type whose number of potential values are the sum of another group of types. For example, an enum with the elements, Red, Green, and Blue has a cardinality of three. A sealed trait with this triplet plus a boolean holds only five elements:

⌊Red⌋, ⌊Green⌋, ⌊Blue⌋, ⌈true⌉, ⌈false⌉.

This is very different from having them both in a class.

In a class (or struct, or tuple), you would be able to build six potential values:

⟨Red,true⟩, ⟨Red,false⟩, ⟨Green,true⟩, ⟨Green,false⟩, ⟨Blue,true⟩, ⟨Blue,false⟩.

This foundational understanding is important. When languages advertise good support for this, they often use the term Algebraic Data Types, which reflects the essence of how different data types can interact and combine to form more complex structures.

TPC measures how many terms (values) can fit into a given type across the whole program. It extends the above example, where enums are additive and classes are multiplicative; with support for maps and functions (which are exponents), lists, trees, language features such as generics, etc.

Although the complexities of calculating TPC for a large codebase are beyond the scope of this article, the principal takeaway is straightforward: having no or just a few inappropriate terms accepted by your type definitions is dramatically advantageous. Making illegal values unrepresentable means:

• You can remove many runtime checks: less if statements and early returns means you can read your code faster.
• There are fewer ways you can write your functions: fewer possible states to consider means there’s less guesswork when writing your code.
• You can remove some unit tests: fewer system states means there are less places for bugs to hide, and unit tests for these simply cannot be written.
• Property based tests achieve much higher sampling coverage: means higher confidence and shorter wait times on your test suites, reducing the latency of the feature development feedback loop.

This is the starting point for constructing programs, which strive to keep the total number of potential illegal terms as close to zero as possible so that verification of mathematical correctness is either cheap or free.

From this position, the amount of syntax dedicated to ADTs in F# or Haskell is more than justified. The same principle that has taught us how null was a significant mistake shows how replacing a string or a class with an enum can yield improvements by factors in the hundreds of thousands or more.

Let’s now look at a very popular set of principles from this algebraic and quantitative perspective. Let’s, for example, use the S.O.L.I.D. principles which are themselves qualitative in nature. Do their suggestions of best practices yield a measurable quantitative result in terms of TPC?

S.O.L.I.D. principles and Cardinality

S.O.L.I.D. is a set of principles meant to make software design more understandable and maintainable. These principles, although they aren’t formulated from a constructive perspective, still present recommendations which reduce TPC. In other words TPC quantifies these principles:

• The Single-responsibility principle: “There should never be more than one reason for a class to change.” From a cardinality perspective, this translates to “keep less state alongside methods”. Or: have smaller return types (including the internal modifications to the class) which in calculating TPC references the following relation: aᵇ < (a+1)ᵇ.
• The Open–closed principle: “Software entities … should be open for extension, but closed for modification.” This asks us to avoid extending a method’s return value with a sum, or essentially: (aᶜ + bᶜ) < (a+b)ᶜ,
• The Liskov substitution principle: “Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it.” Very similar to the open-close principle, except it is now at the exponent. (aᵇ + aᶜ) < a^(b+c)
• The Interface segregation principle: “Clients should not be forced to depend upon interfaces that they do not use.” Depending on how we define client and interface, this is essentially a re-wording of one of the previous three principles.
• The Dependency inversion principle: “Depend upon abstractions, [not] concretions.” As far as the TPC calculation goes, this is equivalent to the Liskov substitution principle; basically, it is a fully separate initial concern that happens to have the same equation behind it.

Just like functional domain design in the previous stage, these principles all have a direct translation that helps keep the cardinality of our methods low by preventing us from sneaking in observable elaborations to our method’s behaviors.

It’s worth reminding that TPC provides a tangible metric for confirming whether applying a certain principle during refactoring will actually reduce a codebase’s complexity and by how much. That is to say, it is offering an objective measure behind many things that were subjective before.

This brings us to another relevant concept: YAGNI (You Aren’t Gonna Need It). YAGNI is often cited when following certain principles appears to complicate the code unnecessarily. YAGNI can itself be completely redelegated behind TPC as meaning “Keep TPC as low as possible”. TPC can help clarify such situations, showing, for example, when you might be tempted to choose a parameter that has more complexity (higher cardinality) than is actually required; or even the abstractions we choose can be shown to simply raise the overall TPC of a codebase and then deemed to be an unnecessary reification.

Further thoughts

This article introduces the Total Program Cardinality software quality metric and how it relates to existing software design principles. By being a quantitative metric, it really helps engineers at Philips reduce the amount of time we spend yak shaving when the above principles come into conflict.

In an following article, we will look at how TPC connects with programming language feature design. We’ll also revisit an exercise in actually counting TPC values and share several experiences where refactorings inspired by TPC lead to improvements in production code at Philips.

Curious about working in tech at Philips? Find out more here