In traditional design, you identify the capabilities and characteristics of a planned system, then create an overall design that accommodates them. In evolutionary design, you grow the system one aspect at a time (and evolve the design to match). But will you hit a dead end?
You can certainly hit a dead end with evolutionary design. After all, traditional designs sometimes hit dead ends too! – even at implementation time.
Evolutionary design implicitly makes a bet: if we hit a dead end, we can recover from it and move forward again, and the lower overall complexity of the system makes us come out ahead.
I recently hit a dead end on a project I’ve been doing; I’ll talk about how that came about, and what I’m doing to recover.
Two Escapes: Backwards and Sideways
In the worst case, we might be at a dead end and realize our whole approach can’t work.
This may require us to move backwards – we have to remove and replace a substantial piece of design. (We may be able to keep the system running e.g., by the strangler fig pattern [see References], but in the end we’re throwing out the current approach.)
Other times, we may be able to move sideways – keep what we have but evolve it to an alternative “parallel” design.
In either case, there’s a cost to moving away from the dead end.
The example below is an example of a mostly sideways move.
A Recent Dead End
I’ve been working on a program to help a musicologist explore the similarity of tunes. We’re reading a moderately complex file format called “abc notation”.
I’ll leave out details (you’ll thank me), but this is a line-based text format. Each tune looks like this:
X: number T: title More tune header lines K: G Tune body lines
The short version of the problem is that I used a backtracking parser because of the trickiness of the parsing, but found that I need to manage a running state that could affect parsing in an incompatible way.
Phase 1: Header Lines and Notes
I focused on the critical header lines and the notes first. Since each line has different rules, we create a (sub-)parser for each type of line. The main reader goes through the lines and dispatches to the right parser. A simple state machine manages the overall order of lines (X:, T:, header, K:, body).
Example: P: (“parts”) will accept a definition, much like a poetry analysis: AABB is typical, but you might also have (A2B)3CB2A to specify AABAABAABCBBA.
Example: M: (“meter”) can accept C, C|, “normal” ratios like 3/8, or additive ratios like (2+3+2)/8.
The parser I chose takes a functional approach. It lets the parser build arbitrary objects and gracefully handles backtracking.
Phase 2: Header Lines in the Body
Some formats can occur in the tune body as well as the header. This lets you change partway through.
For example, some songs may start in the key of D, then switch partway through to the key of G. Others may start with a 4/4 time signature, but switch to 2/4 for a measure.
To complicate things, some of these lines have a different format in the body. In the tune body, you can use P:A to say that you’re defining the A part, but you can’t use formulas such as A2B.
We handle the changes by using a running state. The tune header defines the initial state, and the body changes it.
Phase 3: Inline Instructions
Everything was fine until I hit the next capability: some header commands are instructions that can be embedded within a line of notes.
For example, you might have this: [P:A] ABC [P:B] DEF, saying to put ABC into part A, and DEF into part B.
This complicates parsing, but worse, it changes interpretation of notes mid-parse.
I hit the wall on this with “unit note length”. You have a header line that tells you the default note length, e.g., 1/8. When you define the notes, you give them relative durations. So, A B2 C means that A is a 1/8 note, B is a 1/4 note (two times a 1/8 note), and C is another 1/8 note.
But, now you can change note length mid-line. This directly affected construction of the notes. And I could see there were other instructions coming that changed other things as well.
Escape the Dead End
At this point, I was at a dead end for my current design, without a simple way to move forward.
I worked out a few options:
1. Back out the original parser decision, and switch to a non-backtracking parser. That would require reworking the file format to remove any deep lookahead, ripping out the old parser, identifying a new one, and installing it. This definitely requires moving backwards.
2. Make the active state an explicit object, managed in the parser. The current parser builds objects bottom-up (synthesized attributes, in compiler lingo). The new approach would add inherited attributes, information coming in from above.
It could be done, but would require passing this state in to almost every rule, and modifying builder methods to take it into account.
I’d call it a sideways move, but it looked like more work than I wanted – running hard to stay in place.
3. Re-conceptualize the system to be like a two-pass compiler: use the existing parser to capture musical events (such as notes) and instructions (such as changing the note length) into an event stream, then have a second pass that tracks and applies the state to build the final tune.
[Thanks to the Friday Geek Night Out group for helping me think through these options!]
I chose the third approach. The parser has enough work to do already, and the second option would complicate it further. Interpreting the event stream separately makes the whole system easier to understand.
A Design Change
Looking at this change really brought out another design decision I wasn’t happy with. In the original, a Tune both gathered and knew the metadata (title, etc.) and the score (notes and rests).
But this two-step aspect was awkward – it doesn’t make sense to ask for the tune while you’re still building it. And the score kept track of the individual events (notes…), but nobody really wanted them once it was built – they’re really fodder used to create the measures. Because parts can rearrange things, the order of the input notes is not necessarily the same as the order the notes will be played.
I’m reworking the code to a different arrangement of behaviors: the TuneBuilder gathers events, and builds the Tune in a “second pass” by merging events and state changes.
It was a nice “pattern moment” – once I recognized “Builder”, it clarified what was wrong with the original approach, and how to fix it.
Coulda, Woulda, Shoulda
I hit a dead end (but recovered:)
What would be different if I’d anticipated the problem in advance?
- I’d have paid better attention to my qualms about mixing accumulating and knowing information, and used a builder sooner.
- I might have pushed harder to work out the implications of the full input language.
- I could have started with the second option, passing down “inherited” information – though I think the third option (making a second pass) has turned out better.
Would a full design in advance have avoided this? Perhaps. But it’s not free – and it comes when we understand the least about the problem and the system.
On the other hand, before I hit this problem, I was able to build out a key feature early on (a Parsons code graph, showing the shape of the melody). My one (so far:) customer was excited to have that much sooner, and she didn’t really notice the two or three episodes of sideways movement.
You can’t always get a full design because some needs haven’t been invented yet. I suspect the inline instructions were a late addition – a redundant convenience. We might have built V1 under the no-backtracking assumption, then been hit with a change in the input format that required it.
Conclusion
Evolutionary design can hit dead ends. (No surprise – up-front design can hit dead ends too.)
In the worst case, we have to completely back away from the current solution. Other times, we’re able to move “sideways” to a related design.
With evolutionary design, the bet is – most of the time we get a sufficient design cheaply, often enough to more than make up for those rare times when we hit a dead end.
References
“Builder” in Design Patterns, by Gamma et al.
“Disaster Strikes! A Design Dead End” – an example in an Elm interpreter.