A Neota Logic System (NLS) Application is an algorithm: a recipe, a procedure for completing a task. A recipe for a plain omelet is to break the eggs, whisk them in a bowl, add some baking powder, and put the mixture in the pan. After 5-6 minutes turn it over, and a short 2 minutes later you have a delicious omelet. The procedure of (safely) pulling out of your driveway is to get into the car, put your seat-belt on, turn the car on, step on the brake, put the car in reverse, release the handbrake, check all your mirrors, and if all is good, release the brake to get the car moving. These are algorithms – recipes, procedures for how to complete a task.
The concept of the algorithm is from Mohammed Al Khwarizmi, a Persian mathematician who lived about 1,000 years ago (algebra is probably named after him too). Bob Kowalski, who is somewhat more recent than Al Kkwarizmi, defines an algorithm as “algorithm = logic + control”1. To define a recipe (an algorithm), you need to provide two things: the ingredients and actions – the logic, and the timing (when should I put the mixture into the pan, when should I turn off the stove, and so on) – the control.
When we want to solve an interesting problem, we usually need to specify an algorithm. That is, we need to tell the computer (or our colleague/partner) what they should do, and, if we are bossy enough, how they should do it. The what is the logic (the ingredients and actions) while the how is the control (the timing). NLS Applications are used to solve complex problems. Therefore: NLS Application = logic + control. Right?
Well, not always. Authors (in most cases) only need to specify the what, the logic. The NLS inference engine will add control. By analyzing the application, NLS can decide the timing of how and when questions should be asked, in order to reach the goal conclusions in as few steps as possible, or the shortest path.
Let’s see an example. Suppose we live in a parallel universe, where people are allowed to vote in the US under the following circumstances:
(1) They live in Hawaii, and they are 15 years of age
(2) They live anywhere else, and they are over 16 years of age
We’ll implement this logic with a Decision Tree, an easy choice for newcomers to NLS. A decision tree that implements this example is the following:
Running this app results in a question regarding the State in which the person lives. Whatever we answer, we get a question on the next page for the person’s age. This logic will always require both the person’s state and age to be answered and will always require these answers in the same order as we see them in the decision tree.
There is control built in to the algorithm simply based on how the decision tree works. It is implicit and inherent in the decision tree logic.
Think further about this logic. If the person’s age is 16 or more, do we need to ask for the person’s state? How should we fix our logic so that our algorithm does not ask unnecessary questions? In this case we need to re-build the decision tree entirely, starting with the age question and then asking the state question only if the age is 15. Like so:
Great! Now we’ll get the age question first and if the age is more than 15 we won’t need to ask the person’s state. Exactly what we wanted.
Suppose now the government changes the rules under which people are eligible to vote, to also include the color of their eyes. Apparently, blue-eyed people can vote if they are 14 years old. Brown-eyed people can vote if they are 15 and live in Hawaii, and all people over 16 years can vote. In a nutshell, people can vote if:
(1) They are blue-eyed and over 14 years old
(2) They are brown-eyed, are 15 years old and live in Hawaii
(3) They are older than 16 years
The obvious way to modify the previous optimal decision tree to reflect the new rules is to add an “eye color” node before “age”. To do that, we’ll need to re-structure our decision tree to include questions regarding the Age multiple times:
Just like in the previous case, knowing a person’s age is possibly sufficient to decide whether they are eligible to vote. However, the question regarding the person’s eye color will be asked first. To optimize this decision tree like before, we need to re-structure it again:
The inherent and implicit control built in to the decision tree logic makes maintaining it difficult as seen in this example. This is simply because this particular logic has built-in control even though the original actual logic is quite simple:
(1) If State == Hawaii AND Age == 15 then Vote = Yes
(2) If Age >= 16 then Vote = Yes
The question now is, can we do better? Can NLS help by allowing us to only specify the logic, and let NLS control how it will get executed? Look at the logic we inferred from the decision tree (the two bullets above). It looks very much like two NLS If/Then Mappings. And actually this is all we need to declaratively specify the solution to this problem. What we say to NLS is: “Look here, everyone who is over 16 is eligible to vote. Also, if someone lives in Hawaii, and they are 15, they are allowed to vote”. These ingredients would be enough for any of us to decide if someone is eligible to vote based on their age and state of residence. Similarly, putting these If/Then Mappings in an NLS application allows NLS to decide if someone is eligible to vote. Running it in NLS results in an optimal question sequence: Age is asked first, since NLS is smart enough to realize that if Age is 16 or more we don’t even need to ask for the person’s state.
If we extend this to reflect the government’s new rules for voting regarding the person’s eye color, we need to only change rule (1) from above, and add rule (3):
(1) If State == Hawaii AND Age == 15 AND Eye Color == brown then Vote = Yes
(2) If Age >= 16 then Vote = Yes
(3) If Eye Color == blue AND Age >= 14 then Vote = Yes
Clearly, modifying the purely declarative logic is very easy. NLS will continue to provide the control, asking the person’s age first and then eye color, followed by state. Eye color and state will only be asked if they are needed.
However, modifying the procedural logic (the decision tree), is a more contrived and error-prone task. Looking at the Optimal Eye-color Decision Tree, there is one small detail that really stands out: we are using a more complex condition in one of the links. This is because we essentially need to consider all the different sub-cases in which someone can vote based on the declarative definition the government gave us. For example, it is very easy to forget that if the person’s age is 15, they can vote not only if their eyes are brown and they live in Hawaii, but if they are blue-eyed as well. This fact is hidden from the declarative specification of this problem, and NLS takes advantage of this; it lets us specify the rules we can intuitively understand, and takes care of how to (best) reach the goal conclusions itself. When using the decision trees in this case, we are actually re-inventing the wheel. We are trying to direct NLS to do something that it’s more suited than us to do; decide when to ask a question, in order to get us to the goal conclusions in the shortest number of questions asked.
The If/Then Mappings let us specify what we want NLS to do – decide if someone is eligible to vote or not, based on rules we intuitively understand. All the control of how to do this is left to the expert, the NLS inference engine. The decision tree, however, makes almost no use of these unique capabilities of NLS: we are telling it how to reach the goal conclusions by manually taking apart the declarative logic of the If/Then Mappings, making sure we take care of all the cases.
Declarative logic is prefered for correctness and scalability. Adding procedural control is error-prone. It is a difficult task, which takes significant analysis to verify that it is correct. Additionally, if turning these mere three rules into a procedural specification involved so much detail and effort, imagine what would happen if we had 20, 50 or even 100 such rules, spanning over 200 variables. Such a beast would really be a nightmare to maintain and extend, doing so is simply not scalable. Maintaining the declarative specification is a much simpler task, easily verifiable and scalable.
NLS Application = Logic + NLS Control
In order to exploit NLS’s capabilities, we let NLS take control. The only thing we need to do while driving is tell it where to go. And it’ll get us there. Using the shortest route. Always.
by: Spyros Hadjichristodoulou
Senior Software Engineer, Neota Logic