About The Transformation Priority Premise

A couple weekends ago a friend and I dedicated one of our study sessions to the discussion of The Transformation Priority Premise (TPP). Both of us already had a general idea of the concept and the reasoning behind it, but neither could come up with a real world example where it would be clearly useful.

TPP was first proposed by Uncle bob which, on his article, suggests a list of transformations, simple operations that change the behavior of code, along with the idea that we should favour tests and implementations that employ the ones on the top of the list (higher priority) rather than the ones on the bottom (lower priority).

1. ({}–>nil) no code at all->code that employs nil
2. (nil->constant)
3. (constant->constant+) a simple constant to a more complex constant
4. (constant->scalar) replacing a constant with a variable or an argument
5. (statement->statements) adding more unconditional statements.
6. (unconditional->if) splitting the execution path
7. (scalar->array)
8. (array->container)
9. (statement->recursion)
10. (if->while)
11. (expression->function) replacing an expression with a function or algorithm
12. (variable->assignment) replacing the value of a variable.

To demonstrate the usefulness of this premise the article explains how, by applying it, it would help to solve the impasse faced by Alphonse while doing the Word Wrap kata.

In order to come up with our own conclusions and understand how useful could this premise be during the development process, we decided to also try this kata, analyse our steps in more detail and compare them to the approach taken in both these articles.

Exploring The Word Wrap Kata

You write a class called Wrapper, that has a single static function named wrap that takes two arguments, a string, and a column number. The function returns the string, but with line breaks inserted at just the right places to make sure that no line is longer than the column number. You try to break lines at word boundaries.

This kata starts very simple and, up until the third test, there is not much to discuss. We write a simple test and the obvious implementation follows, we start by returning null, just to test failure, then "" and finally the input text itself. After three iterations this is what we end up with.

public static String wrap(String text, int columnSize) {
  if (isNull(text)) return "";
  return text;
}

The first couple steps are pretty simple and intuitive, but at this point we reach a fork in our testing path and we have two different ways to proceed. We have to choose between

• wrap("word word", 6) == "word\nword" that tests breaking between words that don’t fit one line
• wrap("longword", 4) == "long\nword" that tests breaking within a single word that doesn’t fit one line

Which should we chose? What should we base our decision on?

It does not seem to be one obvious choice here. However, both articles suggest that making the right choice at this point is decisive to the kata’s outcome, completely changing the implementation experience down the road as one of the paths leads to an impasse that forces a complete rewrite of the all implementation while the other allows the algorithm to be written in a more stepwise fashion.

The first path - Breaking at space first

This first path starts by breaking on the space, separating two words that don’t fit in one line together. This can be solved by applying a 11.(expression->function) transformation to our current state by changing the return text; statement.

// wrap("word word", 6) == "word\nword"
return text.replaceAll(" ", "\n");

After this, both articles choose to pose the same test, wrapping three words that don’t fit one line after the second space.

// wrap("word word word", 11) == "word word\nword"

This is the test where, in the original article, Alphonse gets stuck in what is presented as an inevitable big leap that leads to a complete rewrite of the algorithm. He did not seem to find a simple implementation to make the test pass as quickly and went down the rabbit hole, started coding blindly, which lead to a lot of simultaneous changes that in the end didn’t even pass the original test. All this changes felt overwhelming and, after some reflection, the conclusion was that he was trying to pass the “wrong” test.

If we analyse his implementation against the TPP list of transformations we can see that it used multiple low priority transformations on a single step

• 6.(unconditional->if)
• 9.(statement->recursion)
• 11.(expression->function)
• 12.(variable->assignment)

This situation of trying to make this specific test pass is presented in Uncle Bob’s article as The Impasse Problem.

[…] where there is no way to get the next test to pass without rewriting the whole algorithm. […] The current solution does not appear to be easily transformable into something that will pass the new test.

Stating that there is no simpler test nor a simpler obvious implementation that makes the test pass, neither of the articles go further down this path and decide to backtrack, opting to follow the second path instead.

We can’t deny that this specific implementation added too much logic, too much complexity in a single step and is not a natural progression, however, we argue that there is a simpler implementation for this test and even an intermediary test that could be used as a stepping stone to make a more incremental progression, keeping us on track down this path. But lets stop here… for now, and check how the second path unrolls.

The second path - Breaking long words first

When the article starts Breaking the Impasse it sidetracks for a bit to show that, if we followed TPP rigidly, we should first implement the invalid input case as it could be solved with a higher priority transformation. We can safely step over this step as it could be implemented at any point with no interference with the rest of the algorithm.

We found ourselves again at the fork in the testing path but this time we choose to start by breaking a single word that does not fit in a column, a longword. Here the article can come across as slightly biased, when it compares the 11.(expression->function) , replaceAll(), used to solve the test in the first path, with a single 6.(unconditional->if) that is used to solve this test. In reality it does, but just in a first instance, by returning a constant which then needs to be generalized by posing a follow up test that also requires a 11.(expression->function) transformation.

// wrap("longword", 4) == "long\nword"
public static String wrap(String text, int columnSize) {
  if (isNull(text)) return "";
  if (text.length() <= columnSize) return text;

  return text.substring(0, columnSize) + "\n" + text.substring(columnSize); // return "long\nword";
}

The next step is testing multiple breaks in a single word that is longer than twice the column size which is passed with 9.(statement->recursion).

// wrap("longerword", 6) == "longer\nword"
return text.substring(0, columnSize) + "\n" + wrap(text.substring(columnSize), columnSize);

Here, the article points that it is possible to pass this test with 10.(if->while) but defends that recursion is simpler than iteration. Is this always the case, that recursion is simpler than iteration, or is it situational?

We are finished with the problem of breaking long words and we can now start solving the breaking at word boundaries problem. For this we are back to our initial test on the first path twoWordsLongerThanLimitShouldWrap. As above, the two step process is used again, splitting the execution pathways first by adding an if and returning a constant and then generalizing. We again merge them into a single step for brevity.

// wrap("word word", 6) == "word\nword"
public static String wrap(String text, int columnSize) {
  if (isNull(text)) return "";
  if (text.length() <= columnSize) return text;
  
  int space = text.indexOf(" ");
  if (space >= 0)
    return text.substring(0, space) + "\n" + text.substring(space+1);
  
  return text.substring(0, columnSize) + "\n" + wrap(text.substring(columnSize), columnSize);
}

Note that on this step the article just lists two transformations, one 6.(unconditional->if) and one 11.(expression->function), leaving out the text.indexOf(" “) instruction.

Next test is threeWordsEachLongerThanLimitShouldWrap which is solved with another simple 9.(statement->recursion) transformation followed by some refactoring that we decide to postpone for later.

Finally, the test that originated the impasse is presented again, but this time instead of the big leap it is presented as having an obvious solution. The test is passed in two steps, first replacing indexOf() by lastIndexOf() which makes the test pass but breaks the previous one, and then instead of looking for the last space’s index in the all text, text.lastIndexOf(" "), it looks only in the substring that can be contained in one column

text.substring(0, columnSize).lastIndexOf(" ")

The final test fixes the edge case of a break occurring right after the end of a word, at the space character position, which is solved by adding a simple +1 to the column size. With this iteration we are finished with the implementation.

public static String wrap(String text, int columnSize) {
  if (isNull(text)) return "";
  if (text.length() <= columnSize) return text;
  
  int space = text.substring(0, columnSize + 1).lastIndexOf(" ");
  if (space >= 0) 
    return text.substring(0, space) + "\n" + wrap(text.substring(space+1), columnSize);

  return text.substring(0, columnSize) + "\n" + wrap(text.substring(columnSize), columnSize);
}

A new perspective on the first path - Solving the impasse

When we left this path we were stuck in a really intricate solution in what felt like a big leap and both articles decided to stop and follow a different approach.

// wrap("word word", 6) == "word\nword"
public static String wrap(String text, int columnSize) {
  if (isNull(text)) return "";
  return text.replaceAll(" ", "\n");
}

Although it seems that by following the new test path we were able to reach a solution in an iterative fashion that we could not attain by following the first approach, we believe that it happened not because of the testing path per se but mainly because we took small steps and opted for a recursive solution. We believe that, in the original article, Alphonse got stuck because he was trying to solve problems that were beyond the scope of the actual test, trying to generalize ahead of time and unfortunately also choosing an iterative approach to do it which, at least in this case, seems to lead to a more complex solution.

Lets have another look at the test and try taking a smaller step, one that just put the code in a green state.

// wrap("word word word", 11) == "word word\nword"

Actually, in his article, Uncle Bob mentions a simple way to solve this test, by simply using a function like replaceLast(" ", "\n"), and that is kind of what we did. Although we don’t think it is really necessary as the implementation of replaceLast seems simple enough, we can come up with a simpler test that could be written before to make the algorithm evolve in smaller steps.

@Test
public void twoWordsShorterThanTheLimitDoNotWrap() {
    assertEquals("word word", wrap("word word", 11));
}

This test can be solved with 6.(unconditional->if), a relatively high priority transformation.

if (text.length() <= columnSize) return text;
return text.replaceAll(" ", "\n");

And then we can go ahead with the replaceLast suggestion and solve the impasse situation. Not adding more than we need.

// wrap("word word word", 11) == "word word\nword"
public static String wrap(String text, int columnSize) {
  if (isNull(text)) return "";
  if (text.length() <= columnSize) return text;
  
  // replaceLast(" ", "\n")
  int lastSpace = text.lastIndexOf(' ');
  return text.substring(0, lastSpace) + "\n" + text.substring(lastSpace + 1);
}

This change undeniably solves the impasse avoiding a full rewrite of the algorithm. We just changed the replaceAll call by an implementation of replaceLast and were able do it with a single 11.(expression->function) (disregarding lastIndexOf() similarly to what was done with indexOf() on path two). Note that the changes guided by the two last tests together have exactly the same complexity as the ones used on path 2 to solve the first test after the fork.

We can proceed with the next test that is also the follow up test suggested by Uncle Bob

// wrap("word word word word", 11) == "word word\nword word"
String columnText = text.substring(0, columnSize);
int lastSpace = columnText.lastIndexOf(' ');

The change is pretty straightforward, and we already saw it at the end of path 2. A simple 11.(expression->function) to find the last space within the text’s initial substring that fits in one column instead of using the all text.

Next we can go for the generalization and, following the TPP priority table where mutation is over iteration, use 9.(statement->recursion) which requires a simple change on the last return statement.

// wrap("word word word", 6) == "word\nword\nword"
return text.substring(0, lastSpace) + "\n" + wrap(text.substring(lastSpace + 1), columnSize);

Finally we can add the +1 on the columnText calculation to solve the edge case bug and wrap up the problem of breaking text on spaces.

public static String wrap(String text, int columnSize) {
  if (isNull(text)) return "";
  if (text.length() <= columnSize) return text;

  String columnText = text.substring(0, columnSize + 1);
  int space = columnText.lastIndexOf(' ');
  
  return text.substring(0, space) + "\n" + wrap(text.substring(space + 1), columnSize);
}

Now we can start breaking long words. These final steps are not too relevant as they are all in all similar to the first steps we saw in path 2. However, for completion sake, we can start with wordLongerThanLengthBreaksAtLength that we easily solve with 6.(unconditional->if) and 11.(expression->function) and finally wordLongerThanTwiceLengthShouldBreakTwice that requires applying 9.(statement->recursion) one more time but now on the long text flow of execution, which was just created on the previous step. With these changes, we end up with a similar solution to the one we obtained following the other testing path.

Conclusions and questions

This kata can be boiled down to solving two separate problems or flows (as the titles are hinting), which means we have 2 broad ways to approach its resolution: solving space breaks first or solving long words first. We think that both paths lead to similar implementations without any of them inherently leading to an unavoidable impasse or a less iterative progression as hinted by the articles.

My premise is that if you choose the tests and implementations that employ transformations that are higher on the list, you will avoid the impasse.

When we are stuck, we don’t know what test to write or how to pass it and probably we also don’t have a good estimate on the implementation complexity, which makes it hard to choose the test with higher priority next. Besides, this example shows that TPP was not decisive when choosing the testing path as, in the end, we reached the same outcome with similar complexity transformations and following two different paths.

When trying to make a failing test pass there are a lot of unknowns and possibilities for its resolution, the use of replaceAll can throw you off the correct path or maybe a quick and apparently harmless google search for a replaceLast implementation points you in the wrong direction. We can cater the idea that by following a certain path this is avoidable but that is at least debatable. Can it be generalized for other situations?

With this we do not mean to completely dismiss TPP, we can consider its usefulness when looking for a simpler implementation. It can be a way to evaluate our solution and rethink if we could achieve the same result but with simpler transformations. In the case portrait in the original article the writer got overwhelmed and started, even though unconsciously, solving more than what was needed. A way to help focus his efforts on the simplest way to pass the test could have helped here, but, on the other hand, we can argue that at least for this case, the only situations were we found the transformation list relevant for the actual outcome was when opting for recursion instead of iteration and maybe discouraging variable mutation.

Finally, some questions to consider:

1. Favouring simpler constructs and thinking in small steps can help when we are stuck. Is TPP bringing anything new or does the TDD practice suffice?
2. Is the TPP transformation list’s order universal, i.e. is it the same in every situation?
3. Can the premise be boiled down to a single rule - Avoid mutation & Prefer recursion over iteration?