Posted On: 2020-07-06
When struggling with a problem, it can often be helpful to take a step back, and analyze one's assumptions. Doing so can often lead to finding things that were previously overlooked, not just with the preconditions of the problem, but also with the way one thinks about the problem itself. Sometimes, changing the way one thinks about a problem is the only way to solve it - and such situations are often difficult to determine without slowing down and thinking one's assumptions through. As a way of illustrating what I mean, I will describe one such situation I found myself in, while working on the Salience Engine.
While building the grammar for the Salience Engine, I focused on the kinds of "atoms" that I wanted the grammar to support. Specifically,
I wanted the language to support working with booleans, numbers, and strings. What's more, all expressions in the grammar should ultimately resolve to
a boolean - which means
1 + 1 would not be a valid expression, but
1 + 1 = 2 would be (since it evaluates to
true). By enforcing that all expressions resolve to a boolean, the expression is able to represent the
answer to the question "should this dialogue node be considered potentially salient*?"
From those requirements, I came to think about the grammar as composed of three different layers, one for each of the supported types.
The number layer would be responsible for mathematics, and would pass data to the boolean layer when doing comparisons (such as
1 < 2). Likewise strings would be responsible for concatenation, and would pass to the boolean layer using comparisons (such as
"fish" != "cat").
Unfortunately, while this made it easy to reason about the problem, the actual implementation details of achieving this became quite messy. In many cases, I could describe what I wanted, but when it came time to actually code it, I found that the grammar was often too flexible - with one expression working fine and another ending up with strings in the numbers layer or numbers in the boolean layer.
At first, I assumed that I was simply coding it wrong, and set about fixing each issue as it came up. When I began implementing
variable substitution, however, I found myself in situations that were simply impossible to solve. Variables could contain any one of the three
types (boolean, number, or string), and that massively interfered with the grammar. A simple expression like
$NumberOfPuppies = $NumberofKitties was impossible to interpret: the type system would trip over itself as it couldn't determine whether
it was working with numbers or strings - leading the parser to complain about ambiguity or the system itself to behave incorrectly due to guessing the wrong type.
Taking several steps back from the problem, I began to question my assumption about the types in the grammar. I had assumed that every atom
would always be one of the three types, but as I looked at it from a different angle, I began to see that the variables fundamentally
violated that concept. Yes, technically the system could only store one type inside a variable, but, from a parsing standpoint, variables were all three at once. Even if
$NumberOfPuppies was technically a number, the parser couldn't tell that - it could just as likely be a boolean or a string for all it knew.
Taking this insight and running with it, I created my own custom type that could internally store any one of the three types. I described all the possible operations it supported, taking care to clearly define its behavior when unexpected underlying types were used (multiplying two strings together, for example, would create an Exception.)
Armed with that custom type, I was able to vastly simplify the systems used by the parsing.
Gone were the multiple layers and type conversions of data that flowed between them.
Instead, every operation simply delegated to this new type: a
+ from the parser simply invoked the
Add method of this new type. In the few cases where there was nothing to delegate to, the resulting logic was still quite simple and clear
(for example, if the type returned by an the entire expression was not a boolean, it would create an Exception.)
It is my hope that this story about stepping back while working through the Salience Engine is useful to you. For me, the experience was a pleasant reminder about how taking the time to question one's assumptions can lead to new insights - insights that both illuminate solutions to (previously) impossible problems, and also show the way to much simpler and clearer code.