STAR

SAM – the State-Action-Model pattern



 


 

In the last six month I went on a journey that started with a discussion with Dr. Lamport on the semantics of TLA+ and continued with the realization of how significant and innovative the Facebook’s React.js Application Architecture is. I spent some time learning AWS Lambda, and just like React, Lambda is so innovative that it has the potential to break every rule we know in Software Engineering.  

I would like to share with you the place where I landed because I feel it may be relevant to the work of many people. After all, both TLA+ and React are used by big names in our industry to solve elegantly what were otherwise intractable problems, with corny solutions that had not changed much since the 70s.

 

Computing is based on an approximation


The general theory of computation, and therefore the programming languages that were inferred from it, assume that a large class of problems can be solved by using deterministic state machines.

Even though we all understand that the true behavior of a computer is based on a State-Action metamodel, this approximation has resulted in avoiding the mention of states, because they are redundant, merely the shadow of every action. So when a computation transitions from state S1 to state S3 via the actions a and b:

we only need to refer to the behavior of the system as [Lamport]:

 

To be fair, it would be horrendous to have to specify every single state in our programs.  Most of them would have no value at all.

As a result of that approximation, programming languages were designed to work on a conceptual view of “state” which we can refer as an “assignment of variables”, which in turn gave the super power to any program to potentially CRUD change the assignment of any variable at any step (looks like a description of the code you are writing? you are not alone). This approach works well in many cases, but there are a few cases when this approximation cannot be used.

The advent of structured programming nailed the coffin of the State-Action behavior by removing any major reason to use something other than an Action Behavior and these days, it is nearly impossible to find programmers who can think outside the Structured Programming box.

But truly, the most tragic consequence of that approximation is the reification of the concept of “control state” behind an assignment of variables. When we program with modern, so called “structured” languages, we have no particular structure that would give us a hint as to:

  1. which control state we are currently in
  2. which actions are possible from that particular control state, automatic or expected

Everyone has to handcode these constructs without any support from frameworks and programming languages. Actually, a culture has grown in our industry which views “State” as evil, and encourages everyone to prefer “stateless” (for whatever that means) architectures.  

 

Control States must be explicit

 

When building systems which core function is to “wait” (such as business process or service orchestration engines) as opposed to systems that execute, you are often facing the excruciating pain of realizing a state-action behavior in an action-assignment-based programming language. The French had designed a programming language that “waits”: the GRAFCET, which found its niche in programming automata, and not surprisingly, was based on the formalism of Petri Nets. However, programming languages which are based on a State-Action formalism remain a rarity. 

To illustrate the importance of control states and their relationship to actions, let’s take the example of … a glass of water (please replace by your favorite beverage, if it makes it easier to grok the argument).

In an action-based behavior, this system would be described by a state variable v (volume of water in the glass) and two actions: add water, drink. 

 

Fig. 1 Types, Actions and States

 

On the other hand, the state-action behavior of the glass relies on three control states, and the corresponding next-actions:

  • full: drink
  • in-between: drink, add water
  • empty: add water

I apologize for the triviality of this example, but it is important to come to the realization that in an action-based model the concept of “control state” will have to be emulated in some fashion or the system will not be able to respond to actions correctly (fill the glass infinitely, drink from a negative value).

In structured programming, correctness is achieved with the use of conditional expressions: “if-then-else” or “switch-case”, which tend to focus the attention of the developer on the next-action predicate, without requiring the identification of control states, and consequently without explicitly specifying the actions that should be enabled in a particular control state.

Actually, even state-action behaviors are challenged to provide a formalism where “control states” are modeled properly: they suffer from an approximation of their own because the action’s metamodel connects the action to the end state, as if, the action of adding water to the glass would be able to know when the glass is full.

That second approximation is more subtle, but when you think of it, it has to be the type, i.e. the target of the action, which should decide which (control) state results from applying a given action. The action should have no knowledge whatsoever of the “current state” (let alone current control state) of its target. It should only present a series of variable assignments to the type which may or may not accept them, and as a result reach a new control state (or not, when the action fails or has no side effects). This seemingly mundane point is, I believe, why writing code is so error prone, because we either ignore the control states altogether and let actions assign variables directly, or, when control state is explicit, the formalism we use lets the action decides which control state should be reached (which is somewhat equivalent).

If we go back to our glass of water, either actions drink or add water can potentially reach two different states, again, it cannot be the action which decides which end state is being reached.

At this point, it is important to realize that functional programming alone would not help much if the mechanism that transitions from one control state to another is flawed. First, control states are facts, not something you can optionally choose to ignore, and second the metamodel of how control states are reached must be defined with the greatest precision. 


The STAR Programming Model

 

STAR stands for (control) State, Type, Action and Relationship. A STAR-based programming model, is a programming model where these four concepts are independent of each other, which is not the case, for instance, in OO where relationships are reified behind the properties of a Type, and there is no support for control state.

TLA+ is one of the formalisms that is closest to be STAR compliant and after my discussions with Dr. Lamport, I derived a tiny extension to TLA+ which makes control states explicit instead of reifying them behind the assignment of variables. As a matter of fact, Dr. Lamport consistently names the equivalent of control state variables with the “pc” moniker:

 


Fig. 2 TLA+ implementation of the Factorial Algorithm [Lamport]

What this fragment of TLA+ says is that if you are in the control state “mult” (multiply) you will transition automatically to the “test” control state and apply the action that will present a new set of values: f’ and i’ to the factorial type {f,i}. 

As you can see TLA+ creates a strong coupling between the current state, the automatic action performed when it is reached and the resulting target state. Of course one could argue that since “test” is not exactly a control state per se but is used instead to compute the resulting control state, the coupling is not as strong as I might suggest. Nevertheless, the metamodel of a TLA+ predicate, as it stands, is based on the standard State-Action behavior with step tuples such as: (Sn , A , Sn+1).

The reification of control states behind the variable assignments creates two challenges. First as we have just discussed (and as discussed in this previous blog), it forces us to introduce synthetic control states (“test”) which have nothing to do with the correctness or livelyness of the system while introducing an infortunate coupling of the true control states (“mult” and “done” in the condition expression). Control states are independent of each other.  

Second, the reification hides the true nature of a “control state”, as explained in the blog post, which is  far better represented as a range or ranges within all the possible assignments of variables (i.e. mathematical intervals) than by the use of conditional expression which are directly tied to action-based behavior: then and else predicates are not meant to be used for states but actions.

A STAR-based programming model is different because:

  • Type (variables) and Control States are distinct
  • Action are not linked to a target state, but to a target type
  • Actions “present” values to the type, they do not “assign variables”
  • Actions are therefore fully functional: f(in,out) with absolutely zero side effect
  • Types derive their current state based on ranges of variable assignments

But the most important implication of the STAR programming model is that Action-based behavior and State-Action behavior can coexist because we introduced the concept of Type that connects the two. An action can and should be implemented with an action-based behavior. If for anything, STAR is reinforcing the correctness of that approach.

 

Fig. 3 STAR-based programming model

 

Please note that in Fig. 3, the relationships (R in STAR) are not represented as the current discussion focuses on the relationships between States, Actions and Types.

I have also voluntarily left “blank” the initiator of the action, and the “response” mechanism which communicates the resulting state derived by the type (which, again, cannot be inferred from the action performed itself) which we’ll discuss in the next section. 

 

React.js

 

React.js is truly a marvel of software engineering, first, because it finally sweeps away decades of failed GUI architectures under the banner of MVC, and of course, because of the amazing virtual DOM concept and its Diff algorithm.

What React.js can teach us is that the response of a model (type) to events (actions) must indeed be factored separately from the consumption of a model (by a view, or an external software agent). Showing us that it is not only possible, but also far superior to existing paradigms, is a major contribution to software architecture that will remain in our industry for decades to come.

Cherry on the cake for an old (state)ful guy like me, React.js components have both an explicit lifecycle with proper control states and an explicit mechanism to assign the value of variables (setState, distinct from properties).

With that in mind, however, React.js alone is too simplistic to deal with the design of complex systems and the team, not surprisingly, augmented the base Reactive pattern with … an action-based behavior: Flux. Yes, I know, some days you just want to cry: crossing control boundaries without the structure of control states to tame complexity and achieve greater correctness is at best naive. 

In Flux, all action requests are dispatched to “stores” which implement the changes to the model and which are then notifying the views of the corresponding changes. If the Reactive foundation is key to achieve the decoupling of the consumer (of the model) from the model, it suffers from all the shortcomings of action-based formalisms which couple the actions and the types, while ignoring the control states.

 

Fig. 4 The Flux Pattern

 

The State-Action-Model Pattern

 

Considering that STAR has now a Javascript implementation, it is easy to replace expand the Flux pattern with a STAR-based programming model (as we’ll see in my next post), or what I call SAM, the State-Action-Model pattern:

 

 

Fig. 5 Aligning Flux and STAR – The State-Action-Model pattern

 

With the SAM pattern we can accommodate any software agent, not just React components (views) and there lies another very important lesson that can be learned from React.js and its component lifecycle: it is indeed possible to replace Request/Response inter-actions (be they synchronous or asynchronous) with a Diff/Notify pattern. React.js gives us the unique opportunity to bury another antiquated pattern that has plagued our industry for decades: RPC. That, again, will become a tremendous legacy of React.js.

AWS Lambda

 

If you have not explored AWS Lambda, one of the latest Amazon Services, I would highly recommend you do. SAM may well become a key pattern for Lambda, because Lambdas are an ideal building block for implementing SAM:

  • Lambdas can be used for implementing Actions (Behavior)
  • A Lamda can aslo be associated to every Type to accept the variable assignments and compute the resulting current state
  • As the assignments are made persistent, say in Dynamo DB, a change event can trigger the corresponding changeEvent to the requestor

 

In this post, we have shown how the introduction of a State-Action-Model behavior (as opposed to State-Action behaviors) is radically changing the way we can write software, without compromising the value of Action-based behaviors (and functional programming) while offering a close alignment with the semantics of TLA+. We have also shown that SAM can be used to augment key innovation such as TLA+ and React.js/Flux. We have also looked at how SAM could become a key pattern for AWS Lambda.

It would be hard to conclude this post without mentioning my favorite quote from Barbara Liskov:

I believe that the fundamental role of programs is to modify state not just the bits


In my next blog post, I create an example: the reliable API Call component, where SAM is implemented with the STAR Component Model which is available in Java and Javascript.


Leave a Reply

Your email address will not be published. Required fields are marked *

− 6 = 3