Ross Esmond

Code, Prose, and Mathematics.

portrait of myself, Ross Esmond
Written — Last Updated

Expression Problem.

The Expression Problem is a software engineering dilema where the more implementations an abstract data type has, the harder it is to add new behaviors, and vice versa. Take a shape, for instance. If a program has distinct implmentations for a circle, { center, radius }, and a square, { center, dimension }, then any new function which operates on shapes must know how to operate on both circles and squares, as they use different properties to define themselves. A function which detects if a point is inside or outside a shape would need to check euclidean distance to the center of a circle, but check taxi cab distance to the center of a square. Each combination of implementation $I$ and behavior $B$ requires custom code, $C = I\times B$.

There is no solution to the expression problem. The only way to mitigate the combinatorial explosion of code complexity is to either be conservative with implementations or with functions, though introducing multiple levels of abstraction can adjust the equation.

Encapsulated vs Exhibited.

Object Oriented Programming follows the convention of encapsulation of state. State may only be accessed by select methods which are listed on the abstract data type. Any new implementation is also required to define its own implementations of these behaviors, though they are allowed to adopt defaults when applicable. Extending an object with new methods creates a requirement that a new implementation of that method be added to every single concrete object which implements that abstract type, which may be impossible if any of the concrete types are outside of the programmers control. Adding a new concrete implementation of an abstract type, conversely, may always be performed, even if it may require all new methods. The conventions and design of OOP languages are engineered toward facilitating new permutations of state to satisfy data types, but not new behaviors of those data types.

Functional Programming on the other hand, follows the convention of exhibition of state. Data types are represented by primitive values, such that the state therein may be access by any function with access to the data type. New behaviors of that data type are then as simple as writing a new function of that value which implements the behavior. A programmer is never restricted from making these new functions, even if the creation of the values is outside the programmers control. Creating a new variant of the state for the same data type, conversely, may be very difficult, as every function throughout the system that expects the value to exist in its current form would need to be edited to have two distinct, branching code paths. This might not be possible if some of the functions are outside of the programmers control. The conventions and design of FP languages are engineered toward facilitating new functions on existing data types, but not new permutations of state on existing data types.

The UNIX solution

UNIX philosophy says that every program should accept and return text. A UNIX spreadsheet program wouldn’t open as a GUI and save a CSV file; it would use terminal parameters and return rows and columns of text, possibly in csv format. This uniformity allows programs to operate on more variants of data. On Windows, Excel, Word, and Powerpoint all require their own search box, but UNIX can get by with just grep for everything.

This same philosophy can be applied to the Expression Problem, just without it necessarily being text-based. The Expression Problem says that the amount of function implementations you require is the cross product of the number of distinct data structures $I$ times the number of functions you require $B$. You can then reduce code by reducing $I$. You do this by agressively normalizing data variants into one universal data structure—whatever is the most general structure.

For shapes, a collection of lines and curves may be the most general data structure. To reduce function implementations, one could attempt to construct all data variants using only a collection of lines. Instead of a square constructor that creates a Square data structure, a createSquare function would create a collection of four lines in the shape of a square. If we then implement a new function that measures the perimeter of a shape, we would only have to implement it once, as all shapes use the same internal structure.

This approach may not even be more work. Quite often we require this general data structure anyways, though we may build it late into development. If this general shape is required, than any other implementation of a shape that could have been represented as an arbitrary shape is wasted code. This approach also boostes flexibility by solving for problems that we have not yet anticipated. Our original requirements may have never mentioned the need for a Rombus class, but if all of our shapes are only Shapes to begin with, than we practically already have the Rombus class before we even require it. All we need is one rombus function to help in their creation, and we’re there.