Defending Intellectual Property with Finite State Machines
(Frame is a new Domain Specific Langauge (DSL) focused on enabling developers to easily create programs using automata. See the Frame documentation as well as Getting Started With Frame to find tools and other resources to explore the Frame language.)
This is the next in a series of articles about Finite State Machines (FSMs) and a new notation called Frame to specify and code them.
Early in my career as a developer, I built a feature for a product that received a patent for Microsoft. The process of working with lawyers to document the system in a way that would be defensible in court was arcane but interesting. This article will tease apart that experience and explain how the system was documented for the patent using state machines in a very natural and accurate way.
At the time I was a development lead at Microsoft on a new product for teaching foreign languages. The product was going to and did compete with Rosetta Stone, which then, as now, leads the market in that space. The feature was a scheduling tool for building “study plans” that would keep the language learner on task and moving forward on his or her goals.
Microsoft received a patent on the feature we created and I had my first experience building a complex application with state machines. It worked so well that I have been interested ever since in why the approach was so effective.
What I realized over time was that state machines (automata) physically organize software in alignment with the solution to the problem being solved. And while I believe this is fundamentally a better way to structure software, I want to explore in this article the additional benefit of automata being a great way to clearly define your intellectual property.
Patently Obvious
Patent law was, and still is, a murky area for me.
Under federal statute, any person who “invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent.”
A “machine” would be anything that would commonly be considered such, from a clockwork to a tractor to a computer.
When I was asked by Microsoft’s attorneys to describe what we had built, I was able to give them three state machine diagrams that modeled the feature’s essential inner workings. These diagrams, along with pictures of the UI that they drove, served as the core functional definition, codified its novelty, and are central to the patent’s IP claims.
We will now explore the architecture of that system from the patent documentation and translate the UML into FMN. We will also see some of the gaps in UML that keep it from being a true specification language.
Machine Composition Architecture for Complex Systems
One of the major challenges with using state machines is that trying to capture all dimensions to a problem in a single state machine quickly results in an explosion of states.
The architectural countermeasure is to decompose the problem into a system of sub-systems. This approach entails creating multiple controllers that will coordinate on the larger problem solution by giving each controller a “domain” of operation to manage. These sub-systems will then be designed to communicate with each other and drive the overall system activity appropriately.
The study planner feature was developed using a certain flavor of this system-of-systems principle. It is comprised of three state machine “controller” (though I didn't’ call them by that name then) subsystems organized into a tree. The root controller of the tree is instantiated first and manages the child controllers:
The diagram above is not part of the patent documentation but is implied by the state machine in Fig. 7 which is:
Above we can see that the Study Planner Wizard state (702) leads to Fig. 8 and the Study Planner state (704) leads to Fig. 9. Functionally what this means is that these states create and destroy another “state controller” that manages the state’s behavior for it — a form of delegation.
In previous articles, I have discussed Frame Machine Notation (FMN) for specifying automata (state machines or just “machines”). The advantages of FMN vs the UML model above are:
- FMN is more precise
- FMN is not constrained by challenges with drawing the model
- FMN can be converted directly to code in any object-oriented language (see article links at the end for how-to)
Here is the equivalent FMN specification for Fig 7:
#StudyPlanFeature
-interface-
start @(|>>|)
cancel
clickHelp
clickReset
clickWizard
planCreated
-machine-
$Begin
|>>|
userHasStudyPlan() ?
-> $StudyPlannerWizard ^ :
-> $StudyPlanner ^ ::
$StudyPlannerWizard
|>| createStudyPlannerWizardController() ^
|planCreated| -> $StudyPlanner ^
|clickReset| clearScreen() ^
|clickHelp| launchHelp() ^
|cancel| -> $HomeScreen ^
|<| destroyStudyPlannerWizardController() ^
$StudyPlanner
|>| createStudyPlannerController() ^
|clickWizard| -> $StudyPlannerWizard ^
|<| destroyStudyPlannerController() ^
$HomeScreenWhen the #StudyPlanFeature controller is created it initializes into the $Begin state:
$Begin
|>>|
userHasStudyPlan() ?
-> $StudyPlannerWizard ^ :
-> $StudyPlanner ^ ::When the controller receives the |>>| (start) message, it tests to see if the user has an existing study plan. If not, the machine transitions into the $StudyPlannerWizard state to create one or otherwise transitions into the $StudyPlanner state to show progress on the existing one.
Study Planner Wizard State Controller
The $StudyPlannerWizard state is what Frame calls a controller managed state. This means that the primary functionality for the state is delegated to another controller that is created upon entry and destroyed upon exit of the state.
$StudyPlannerWizard
|>| createStudyPlannerWizardController() ^
|planCreated| -> $StudyPlanner ^
|clickReset| clearScreen() ^
|clickHelp| launchHelp() ^
|cancel| -> $HomeScreen ^
|<| destroyStudyPlannerWizardController() ^Here is the UI for the wizard state:
An important aspect of the controller managed state architecture is that the parent state shares functional control of the app with the child controller. Notice that the $StudyPlannerWizard state manages the four buttons shown here:
but the child controller will manage everything else for the feature. This layered separation of concerns (or domains) is one of the most powerful aspects to the system-of-systems of controllers paradigm.
Now let's take at the wizard logic in depth.
The Study Planner Wizard Controller
The #StudyPlanWizard controller is created/destroyed when entering/exiting the #StudyPlanFeature:$StudyPlannerWizard state:
As discussed above, the Study Planner Wizard state creates the Wizard upon entry and destroys it upon exit. The parent/child relationship between the two controllers is shown here:
The patent documentation shows the following UML diagram for the wizard:
This machine is the #StudyPlannerWizard controller which we will now examine state by state.
#StudyPlannerWizard:$Begin State
The UML diagram for the Study Planner Wizard starts with a somewhat ambiguous transition from an unknown state to the Wizard Start state:
Upon launch of the Wizard, the UML indicates to show the initial screen and display the date in the banner, followed by a transition to the Wizard Start state.
The FMN for this behavior is more explicit:
$Begin
|>>|
showWizardScreen()
displayDateInBanner()
-> $WizardStart ^#StudyPlannerWizard:$WizardStart State
The $WizardStartState lays out the UI seen above in Fig. 3 above and initializes the hours and the calendar. In this state no days of the week have been selected.
The Wizard Start state initializes the display by showing the hours and the calendar. Clicking a day of the week transitions the machine to the $WizardDayOfWeekSelected state.
$WizardStart => $Default
|>|
displayHours()
displayCalendar() ^
|clickDayOfTheWeek|
-> $WizardDayOfWeekSelected ^Clicking a day of the week that the user wants to study transitions the machine to the$WizardDayOfWeekSelected state.
#StudyPlannerWizard:$WizardDayOfWeekSelected State
Once the user has selected at least one day of the week to study on, The Wizard Day of Week Selected narrows down the options then the user must choose either 2 or 3.
$WizardDayOfTheWeekSelected => $Default
|>|
enableHours()
enableCalendar() ^
|wizardDateEntered|
isValidDate() ?
enableEnterButton()
updateDateBar()
-> $WizardCalendarSelected ^
:
displayAlert()
updateDateBar() ^
::
|advanceMonth|
forwardMonth()
updateDateBar() ^
|backMonth|
backMonth()
updateDateBar() ^
|clickDayOfTheWeek|
noDaysSelected() ? -> $WizardStart :: ^
|clickHoursPerWeek|
-> $WizardHoursSelected ^In analyzing the statechart, I realized there was a missing transition in the UML diagram. As shown, there is no event that triggers a transition into the $WizardHoursSelected state. Here we correct that in the FSM:
|clickHoursPerWeek|
-> $WizardHoursSelected ^#StudyPlannerWizard:$WizardHoursSelected State
The Wizard Hours Selected state disables the calendar and day of the week UI.
Clicking the enter button transitions the machine to the $WizardApprovePlan1 state.
$WizardHoursSelected => $Default
|>|
disableCalendar()
disableDayOfWeek() ^
|clickEnter| -> $WizardApprovePlan1 ^#StudyPlannerWizard:$WizardCalendarSelected State
Upon entry, the Wizard Calendar Selected state disables the day of the week and hours selection UI.
While in the state, the calendar can be manipulated by the user to select a valid date by to complete the course. When the desired date is selected, the enter button is enabled and when the user clicks it the machine transitions to the Wizard Approve Plan 2 state.
$WizardCalendarSelected => $Default
|>|
disableDayOfWeek()
disableHours() ^
|wizardDateEntered|
isValidDate() ?
enableEnterButton() ^
:
displayAlert()
disableEnterButton() ^
::
|advanceMonth|
forwardMonth()
updateDateBar() ^
|backMonth|
backMonth()
updateDateBar() ^
|clickEnter| -> $WizardApprovePlan2 ^#StudyPlannerWizard:$WizardApprovePlan1 State
The Wizard Approve Plan 1 state displays a UI specific to the path of having chosen the hours a day to study.
The UI above showing a transition to a line is an example of ambiguous UML-like notation. It is unclear what the developer should code to implement it as it is not a true state (I know I developed this feature, but it was 20 years ago and have no idea what I actually did).
$WizardApprovePlan1 => $Default
|clickOk|
initializeBookmarks() ^However, the “initializeBookmarks()” action somehow triggers the parent #StudyPlannerFeaturecontroller to transition out of the wizard and over to the Study Planner state :
This shows how the child controllers can drive the activity of their parent and participate in a powerful architecture for structuring controllers.
#StudyPlannerWizard:$WizardApprovePlan2 State
This state is functionally identical to the Wizard ApprovePlan 1 state except for the UI displayed, which will be different and designed to show a plan constrained by end date rather than the hours to study per day.
$WizardApprovePlan2 => $Default
|clickOk|
initializeBookmarks() ^#StudyPlannerWizard:$Default State
As mentioned above, the bar is an ambiguous UML-like notational element added by the lawyers that seems to be intended to operate something like a state, but not exactly. In any case, it shows some sort of default behavior in handling the reset, help and cancel events and is the terminal location for the UML machine.
In contrast, the same functionality is handled in a base $Default state in FMN:
$Default
|help| fireClickHelp() ^
|cancel| fireClickCancel() ^
|reset| -> $WizardStart ^The Study Planner Controller
Once a study plan has been created, the Study Planner Controller is the default UI (shown below) for the feature.
As we can see below, whenever the user logs into the feature and a study plan exists, the root #StudyPlanFeature controller will transition into the Study Planner state and launch the #StudyPlanner controller to manage its fine-grained interactions.
The #StudyPlanner controller machine is modeled here:
#StudyPlanner:$Begin State
The $Begin state is simple and just transitions to the $StudyPlannerIntialize state in response to the start event (|>>|).
$Begin
|>>| -> $StudyPlannerInitialize ^#StudyPlanner:$StudyPlannerInitialize State
The $StudyPlannerIntialize state is a routing state that doesn’t react to any events but instead, upon entry, performs various probes and routes activity to one of three other states:
$ShowProductCompletion$ShowStudyPlannerDayComplete$EvaluteIsBehind
Unlike the UML, the FMN specification disambiguates the priority order of the transitions:
$StudyPlannerInitialize => $Default
|>|
showActivityBar()
initStateDataObject()
isProductDone() ? -> $ShowProductCompletion ^ ::
isStudyPlannerDayDoneAndProductNotDone() ?
noBookmark()
-> $ShowStudyPlannerDayComplete ^ ::
-> $EvaluateIsBehind ^#StudyPlanner:$ShowProductCompletion State
The $ShowProductCompletion state displays a message in the UI to the user that they have successfully completed the study plan. It then waits for the OK button to be clicked, after which it transitions to the $ShowStudyPlan state.
$ShowProductCompletion => $Default
|>| displayProductCompleteMessage() ^
|ok| -> $ShowStudyPlan ^#StudyPlanner:$ShowStudyPlannerDayComplete State
The $ShowStudyPlannerDayComplete state shows a message to the user that they have completed the expected work for the day. It then waits for the OK button to be clicked, after which it transitions to the $ShowStudyPlan state.
$ShowStudyPlannerDayComplete => $Default
|>| displayDayCompleteMessage() ^
|ok| -> $ShowStudyPlan ^#StudyPlanner:$EvaluateIsBehind State
The $EvaluateIsBehind state is another pass-thru state that, upon entry, probes if the activity is complete and takes two slightly different transitions. Both transitions are to the $ShowStudyPlan state, but one path shows a message indicating that the learner’s progress is falling behind.
$EvaluateIsBehind => $Default
|>|
isActivityIncomplete() ?
showBehindMessage() ::
-> $ShowStudyPlan ^#StudyPlanner:$ShowStudyPlan State
All roads lead to the $ShowStudyPlan state which, upon entry, initializes the UI and enables multiple UI interactions to occur.
$ShowStudyPlan => $Default
|>|
setYear()
showMainScreen()
showRightSection() ^
|backMonth|
backMonth()
updateDateBar() ^
|clickOnCalendarDay|
setStudyPlannerDayToToday()
showPlanForToday()
updatePlanBars() ^
|advanceMonth|
isNewYear() ?
showMainScreen()
updatePlanBars() :: ^
|monthClick|
isNewYear() ?! changeMonth() :: ^The UI for the study planner is shown here:
#StudyPlanner:$Default State
According to the UML diagram, |clickWizardButton| event simply calls an action to set a flag that the wizard button had been clicked. This specification, however, is ambiguous as to what is actually happening and how.
$Default
|clickWizardButton|
// on hiding calendar causes "Date Clicked Event"
setWizardClickedFlag() ^The action will actually be used to trigger behavior in the parent controller that will switch it from the Study Planner state to the Study Planner Wizard state:
This interaction between child state controllers and parent controllers is a powerful paradigm. It permits the software architect to solve complex problems using a hierarchy of controllers that separate concerns to manage complex situations.
This concludes our exploration of the UML statecharts and their analogous implementation in FMN.
Automata as Intellectual Property
Software is covered under patent law by what is known as a utility patent. According to upcouncil.com, an invention must meet the following criteria to be eligible for a utility patent:
Useful: The invention must have a purpose and work properly to do that function.
Novel: The invention must be new. All of the claims that make an invention unique can’t appear in an existing patent or in multiple existing patents that a reasonable person could combine. To reject your invention as not being novel, the patent examiner will have to find a patent, a patent application, or a publication that includes all elements of your invention (bold is mine).
Nonobvious: The invention shouldn’t be obvious to a reasonable person. If the invention combines claims from existing patents, it should argue that no one would think to do so or that combining them produces surprising results. If a patent examiner discovers that half of some elements exist in one reference and half exist in another reference, the examiner can combine the two references and reject your invention.
While useful may be in the eye of the beholder, automata can help address questions about software being novel and nonobvious. As stated above, the clearer you can describe the elements of your invention, the more likely it is to be understood as new and therefore patentable.
As discussed in a previous article, software is fundamentally a function that maps the current state and event to behavior.
(state,event) -> behaviorAs a program runs, the mapping function changes with the current state. Here is a simple program that shows a set of mapping functions:
From an IP perspective defining software as a set of mapping functions makes similarity or difference precise. Deciding on how much similarity matters, however, is still in the eye of the judge.
For instance, controlling a radio can be done in many ways, but the diagram above makes clear what the focus of the claim to novelty is. Even though the two systems have exactly the same states and transitions, being able to use voice to trigger the transition behavior is arguably novel.
Systems are clearly different when the set of states are:
Is the addition of a new “Spin Around” state novel? I don’t know, but the difference between the two systems is laid bare by comparing the two machines. With the differences between the system made explicit, the discussion about their importance can be informed.
Conclusion
Patents are powerful tools for good or for ill. The ability to bring new ideas into the world and enable their creators to legally protect their innovations from exploitation is an inherently appealing idea. The opposite is true as well when the system stifles creativity by abuses of the system.
Having a precise language for specifying the inner workings of software would, hopefully, give greater insight into what has been created and therefore give advantage to the deserving parties.
Ideally, systems would not only be specified with Frame notation but also directly implemented from it. This step would deeply link the documentation with the implementation, thus bringing a powerful argument for validity to any discussions about the correctness of the IP claims.
Further Reading
Related Articles
Able to show differences between systems.
