Sometimes I get stuck and look for a way to think about a problem a different way. There are some problems that you can view in the form of a matrix/table. The structure looks like this:

A B C D E
1 A1 B1 C1 D1 E1
2 A2 B2 C2 D2 E2
3 A3 B3 C3 D3 E3
4 A4 B4 C4 D4 E4
5 A5 B5 C5 D5 E5

There are rows and columns, and I'm trying to work on the cells. Let's try an example from a simple game:

Attack Defend Special
Fighter sword armor slam
Mage fireball reflect freeze
Thief dagger dodge disarm

The rows are the character classes: Fighter, Mage, Thief.

The columns are the types of actions: Attack, Defend, Special.

The matrix contains all the code to handle each of these types of actions for each of the types of characters.

What does the code look like? The usual thing to do is to organize this into three modules:

  1. Fighter will contain code to handle sword attacks, damage reduction from armor, and slam special attacks.
  2. Mage will contain code to handle fireballs, damage reflect, and freeze special attacks.
  3. Thief will contain code to handle dagger attacks, damage avoidance from dodge, and disarm special attacks.

Sometimes it's useful to transpose the matrix. I can organize along the other axis:

Fighter Mage Thief
Attack sword fireball dagger
Defend armor reflect dodge
Special slam freeze disarm
  1. Attack will contain code to handle sword attacks, fireball attacks, and dagger attacks.
  2. Defend will contain code to handle damage reduction, damage reflect, and damage avoidance.
  3. Special will contain code to handle slam, freeze, and disarm.

I was taught that the one style is "good" and the other style is "bad". But it's not obvious why this should be so. The reason is that there is an assumption that we will often add more character classes (nouns) but rarely add more types of actions (verbs). That way I can add more code with a new module, without touching all the existing ones. It may or may not be true for this game. By looking at the transpose, it makes me aware of the assumption, and I can question it. I'll then think about what kind of flexibility I want, then decide on the code structure.

Let's consider another example.

In programming language implementations, there are different types of nodes corresponding to the primitives: constants, operators, loops, branches, functions, types, etc. I need to generate code for each of these.

Generate Code
Constant
Operator
Loop
Branch
Function
Type

Great! I can have one class for each type of node, and they can all derive from a superclass Node. But this is based on the assumption that I will often add more rows and rarely add more columns. What happens in an optimizing compiler? We add more optimization passes. Each one is another column.

Generate Code Data flow Constant folding Loop fusion
Constant
Operator
Loop
Branch
Function
Type

If I want to add a new optimization pass, I would need to add a new method to each class, and all the code for an optimization pass is spread out all over the place. This is the situation I was trying to avoid! So some systems will add another layer on top of this. Using "visitors" I can keep all the loop fusion code in one module instead of splitting it up among lots of files.

If I look at the transpose of the matrix, it reveals another approach:

Constant Operator Loop Branch Function Type
Generate code
Data flow
Constant folding
SSA
Loop fusion

Now instead of classes with methods, I can use tagged unions with pattern matching (not all languages support this). This keeps all the code for each optimization pass together without requiring the indirection of visitors.

It's often useful to look a a problem in terms of a matrix. Applied to the object-oriented structure that everyone thinks about, it might lead me to use something different, such as an entity-component-systems, relational databases, or reactive programming.

It's not just for code. Here's an example of applying the idea to products. Let's suppose there are people with various interests:

Nick Feng Sayid Alice
cars X X
politics X X
math X X
travel X X

If I were designing a social web site, I might let people follow other people. Nick might follow Alice because they're both interested in cars and Feng because they're both interested in travel. But Nick would also get Alice's math posts and Feng's politics posts. If I consider the transpose of this matrix, I might let people follow topics. Nick might join a cars group and also a travel group. Facebook and Reddit started around the same time, but they're transposes of each other. Facebook lets you follow people; Reddit lets you follow topics.

When I get stuck, or when I'm wanting to consider alternatives, I look at the problem to see if there are multiple axes of organization. Sometimes approaching the problem from a different direction can yield a better approach.

Labels: ,

3 comments:

Jan wrote at March 25, 2019 12:39 AM

Hey Amit,

This reminds me a lot of the expression problem where you want to have an extensible object tree.

On the one hand you want to add logic, and on the other hand types.

There's some interesting solutions out there to solve this, but most of the time you'll need a programming language that supports multiple dispatch.

Wouter Lievens wrote at March 25, 2019 7:18 AM

You run into a similar problem when you think about software implementations of boardgames. A logical design choice at first would be to create classes around all the game objects (cards, pawns, the board, ...) and put the logic in them where it belongs. Then you get to the nitty gritty details of the game rules and notice you're modifying code all over the place all of the time, and you realize it makes much more sense to treat the game rules as first-class entities (e.g. Classes), and keep the cards and pawns and all that basically as pretty dumb objects.

Amit wrote at March 26, 2019 9:05 AM

@Jan: YES, I first learned about this in the context of programming languages (I was at Rice at the time with the people mentioned on the wikipedia page, and spent some of my phd years on that problem). I found that for most problems though, I don't actually need multiple dispatch; I only need to pick one of the two as the primary extension axis. I started noticing similar things in other contexts too. In games, for example, entity-component-systems, and in databases, the object-relational mapping.

@Wouter: ah, interesting! I wonder if it's also in part because physical board games had cards and pawns etc as dumb objects, and game rules were being "executed" in the human brain.