DEV Community: rekreanto

Unified State Expressions - Transitions (First Sketch)

rekreanto — Fri, 13 Nov 2020 13:32:50 +0000

Some examples:

The traffic light. Now with behavior

Non-hierarchical Traffic Light


// State Machine Type
TrafficLight :> Green | Yellow | Red


// State Machine Reactions 
// Collapsed view
TrafficLight                   // scope
  ! NEXT                         // transition name

// State Machine Reactions
// expanded view
TrafficLight                   // scope
  ! NEXT : Green  -> Yellow      // reaction
  ! NEXT : Yellow -> Red         // reaction
  ! NEXT : Red    -> Green       // reaction


// State Machine Boundary Actions

TrafficLight
  :> 
  | Green  >> after(<duration>)( NEXT ) // boundary action
  | Yellow >> after(<duration>)( NEXT ) // boundary action
  | Red    >> after(<duration>)( NEXT ) // boundary action

Counter

And the almost simplest counter from 15js:


// State Machine Type
Counter :> <int>


// State Machine Reactions
// collpased view
Counter                     // scope
  ! INCR                      // transition name
  ! RESET                     // transition name
  ! DECR                      // transition name

// State Machine Reactions
// expanded view
Counter                     // scope
  ! INCR  : : (  n ) => n + 1  // reaction
  ! RESET : : ( _n ) => 0      // reaction
  ! DECR  : : (  n ) => n - 1  // reaction

// Note that the reconstructor part is empty

The Linksy Kitchen Timer

(It is the timer in the banner art above.)


// State Machine Type
LinksyKitchenTimer 
  :>
    | Setting :> ( <int min>, <int sec> )
    | Ticking :> ( <int sec> )
    | Paused  :> ( <int sec> )
    | Alarming.

// State Machine Reactions

LinksyKitchenTimer // scope
    ! START   : Setting  -> Ticking  : ( m, s ) => m*60 + s  // reaction
    ! PAUSE   : Ticking  -> Paused   : ( s ) => s      
    ! CANCEL  : Paused   -> Setting  : <history> // residual state is memoized
    ! RESTART : Paused   -> Ticking  : ( s ) => s
    ! OK      : Alarming -> Setting  : <history> // residual state is memoized
    ! TIC     : Ticking  -> Alarming

LinksyKitchenTimer :> Ticking  // scope
  ! TIC : : gt(0) ( s ) => s-1  // reaction

LinksyKitchenTimer :> Setting  // scope
    ! M10 : : ( m, s ) = ( m+10, s ) // reaction
    ! M5  : : ( m, s ) = ( m+ 5, s )
    ! M3  : : ( m, s ) = ( m+ 3, s )
    ! M1  : : ( m, s ) = ( m+ 1, s )
    ! S10 : : ( m, s ) = ( m, s+10 )

// State Machine Boundary Actions
LinksyKitchenTimer :> Ticking  // scope
  >> after( 1s )( TIC )          // boundary action

LinksyKitchenTimer :> Alarming  // scope
  >>  after( 30s )( OK )          // boundary action
  >> <start/stop sound>           // boundary action

Separate definitions are preferred

The Behavior part seems to be 3-10 times larger than the State Type definitions if measured in SLOC. That, I think is a good argument for giving the type information separately; it might otherwise be less readable and less useful.

Unified State Expressions - State (First Sketch)

rekreanto — Wed, 11 Nov 2020 10:26:40 +0000

Constructs

  `alt`              : e.g. `Red`, `Green`, `Yellow`, `Guest`, `LoggedIn`, `About`, `Welcome`
  `branch`           : e.g. `@user`, `@page`
  `or`               : `|`   or `---` e.g. `Red` | `Green` | `Yellow`
  `branch-expand`    : `:`   e.g. `@user: Guest`, `@page: About`
  `sub-expand`       : `:>`  e.g. `Red` :> `Walking` | `Waiting`
  `optional-sub`     : `:>`  e.g. EditEvents :>?
                                             | SelectedEvent <id>
                                             | CreatedEvent <id>
  `atomic-marker`    : `.`   e.g. `Green.`, `Yellow`. // optional
  `composite-marker` : `...` e.g. `Red...` // optional
  `agnostic-view`    : // the omission of atomic/composite marker
  `system-types`     : `<...>`,  such as <int>, <string>, <date>

-- Alternatives (or-states) or Branches (and-states) is per default shown collapsed. The next step, the refinement/branch value, can be shown using the expand-constructs :> or :. Atomic states, marked per a trailing dot . cannot be expanded.

Sample STN Notation for some Traditional Toy State Machine Examples

TrafficLight from xstate.js.org

Example source


  // agnostiv view (we don't express whether or not there are refined states)
  TrafficLight :> Green | Yellow | Red


  // Collapsed explicit view (denotes atomic/compsed nature of states)
  TrafficLight :> 
               | Green.
               | Yellow.
               | Red... // can be expanded


  TrafficLight :> 
               | Green. 
               | Yellow.
               | Red :> // expanded view of Red
                     | Walking.
                     | Waiting.
                     | Stopped.
                     | Blinking.

Counter toy app from 7GUIs

Example source


Counter :> <int>

TempConv toy app from 7GUIs

Example source

// agnostic view
TempConv :> F2C | C2F

// expanded view

TempConv :> 
         | F2C >: <string Fahrenheit>
         | C2F >: <string Celcius>

// this is all the essential state needed to restore the app to its state
// the source number as well as the converted number are derived from the input string

Sample small website GrowersAssociationSite (GA_Site)

Source: This is part of a (toy) site I'm working on as part of my web design educaton.


// collapsed view
GA_Site 
  @lang
  @user
  @page



// expanded view
GA_Site 
  @lang : sv | en | ja | eo
  @user : Guest | LoggedIn <string UserName>
  @page : About 
        | Join 
        | Calendar :> 
                   | BrowseEvents
                   | EditEvents :>?
                                | SelectedEvent <id>
                                | CreatedEvent <id>
                                | UpdatedEvent  <id> 
                                | DeletedEvent  [ <id>, <string date>, <string descr> ]
                                | UndidDeletion <id>

This is a brilliant explanation of Orthogonal States by David Harel... using babies

rekreanto — Wed, 07 Oct 2020 06:51:52 +0000

Look at he banner art above. It is the classic Statechart visual language that we all know and love: useful for modeling behavior for example in a reactive app. But now imagine the same visual formalism populated with cute babies:

This is David Harel, author of the original Statechart paper from 1987, explaining Orthogonal states using babies. It is mind-blowingly endearing and accessible. (Full transcript scrolling in the sidebar etc.) The video appears as part of the excellent edX course "Programming for Everyone – An Introduction to Visual Programming Languages" (formerly Liberate Programming).

Anyone with the slightest interest in Statecharts, or programming, or... just loves poignant anecdotes will love this course. It is entry level, I think no one will feel excluded. Advanced learners might enjoy it for the sheer joy and clarity it radiates. Also, it is never too early to get the mental models of the fundamental concepts right :-) Or you could just wait for David Geddes to publish a Statechart mastery game :-).

[ Art of The State ] What is a HTML tag if the browser is a state machine?

rekreanto — Thu, 01 Oct 2020 12:10:54 +0000

A note to any presumptive reader: This is an ongoing sketch done during a quest to understand what state machines can do for UI construction. Code samples are only intended as art, i.e. hopefully illustrative, possibly interesting, only accidentally executable.

A web page is a state

Once upon a time, all web pages were static. Then the situation was simple: The browser was in the same state as long as the same web page was shown.

Clicking link triggers a transition

When the user clicked a link, the browser performed a transition to another state. These states can be represented by the URL. But what we as users see on the screen is the result of the browser loading and rendering a html page that corresponds to the URL. What we observe is a very simple state machine. We now understands the browser and the web page using sate machine concepts.

So what is a HTML tag?

Lets now zoom in our view and consider a single HTML tag. What is it and where do it belong? We can observe it:

When the html file is loaded and the document is parsed, a given HTML tag will be realized as a DOM element and typically rendered to the screen.
When the user has clicked a non-local link and the current page unloads, the DOM element is deleted.

A HTML tag represents a boundary action

So because the exists in the html file, a node is created upon ENTRY of the web page as a state, and then deleted when the state EXITS. This means that a HTML tag stands for a combination of and Entry action and an Exit action. For convenience, lets call that a boundary action.

Boundary actions are natural and helpful

While the term "Boundary Action" is not typically part of State machine terminology, it has two advantages: It is convenient and it can offer something any sane entry action would kill for: The opportunity to undo what the entry action has done. For example, a friendly implementation will keep the environment in which the entry action was executed alive until the corresponding exit action executes. Let's say the an entry action starts a timer that will trigger a transition after 10 seconds. Then a user events causes the state to transition after only 3 seconds. Since the timer is implemented as a boundary action, it can delete the timer as part of it's exit action.

So let's implement a HTML tag as a boundary action

Assuming we have a state machine that controls the internals of a web page, and that each state accepts boundary actions, how can we implement a HTML tag? Let's give it a try:

Upon entry of the state, the tag should create a DOM element. Upon exit, the element should be removed. In order to keep hold on the environment that the boundary action needs, we use double closures in the spirit of Reified Continuation Passing Style, see

[ The Art of the State ] Why it is impossible to write an Identity Function in JavaScript, and how to do it anyway

rekreanto ・ Sep 28 '20

#ephemerals #continuations #javascript

First iteration:

const tag = 
  ( tagname ) =>     // defined by user
// ::::: [ definition time above ] ::::: [ mount time below ] :::::
  ( parent )  =>     // given by the implementation
// ::::: [ mount time above      ] ::::: [ runtime below    ] :::::
  (  )        => {   // called upon entry
  // ENTRY ACTIONS
  const e = document.createElement( tagname );
  parent.appendChild( e );
  return () => {    // called upon exit
    //EXIT ACTIONS
    parent.removeChild( e );
  }
}

Oh, it seems we have forgotten something? Non-atomic HTML tags can have content, i.e. other HTML tags. It is a really bad idea to forget about one's kids!

Second iteration:

const tag = 
  ( tagname ) =>              // defined by user
  ( ...boundaryActions ) =>   // also defined by user
// ::::: [ definition time above ] ::::: [ mount time below ] :::::
  ( parent )  =>              // given by the implementation
// ::::: [ mount time above      ] ::::: [ runtime below    ] :::::
  (  )        => {            // called upon entry
  // ENTRY ACTIONS
  const e = document.createElement( tagname );
  parent.appendChild( e );
  const entryActions = boundaryActions.map( bAct => bAct( parent ) );
  const exitActions  = entryActions.map( enAct => enAct( ) );
  return () => {              // called upon exit
    //EXIT ACTIONS
    exitActions.forEach( exAct => exAct( ) ); // cleanup children
    parent.removeChild( e );  // cleanup self
  }
}

// Sample HTML 
// N.B. strings and objects are not supported 
// as boundary actions in the code above
tag('div')
  ( tag('h1')( "The Art of The State, part I" )
  , tag('p' )( "...hopefully illustrative, possibly interesting, certainly useless" )
  , tag('h2')( "Are we there yet?" )
  , tag('p' )
    ( "Short answer: No."
    , tag('input')({ type:'text', placeholder: 'WHY NOT?' })
    , tag('ol')
      ( tag('li')( "ENTRY ACTIONS" )
      , tag('li')( "EXIT ACTIONS" )
      )
    )
  )
;

Are we there yet?

Short answer: No.

So, assuming we have a state machine that controls our web page, can we add HTML content in a safe and sane way?
Well, I think we nailed the essentials: To uncreate in the exit action all that we created in the entry action.
But, alas we cannot create any visible DOM nodes, yet. One way to do that would be to look for any string among the boundaryActions inputs, and promote it to boundary action, and make a deletable text node from it. Also, we have no way of adding attributes to the element. That could be done in a similar fashion, looking for an object to promote to boundary action, thus adding/deleting its props to our DOM node. (This way of interpreting data types as something else is used to great advantage in both jQuery and Hiccup.)

Also we should add a variant of out tag implementation that, in the spirit of jQuery don't create a DOM node, but looks it up and allows modifications.

Third, the notion of context is probably incomplete, since, when we map events to transitions, we have no where to send the transition. The DOM creation actions had parent, maybe the event handlers need something similar.

How might those boundary actions be useful?

This is utterly useless in the case described above, where every web page is static. But consider the typical case in 2020, when almost every web page has dynamic elements, then we have different landscape: We can define a web-page according to a plan. A plan where states are explicit and all DOM creation and manipulation can occur absolutely only in one place, namely on the borders of the states. And every action that performs a mutation will also undo that mutation at the exactly appropriate point in time: when it's state exits.

Summary

We found out that under the assumption that the browser is a state machine, and that to visit a page is to be in a state, a HTML tag represents a Boundary Action.
Also, under the further assumption that aspects of a web page can change while it is visited, and that these changes are reified as states, the place where DOM is specified, can no more be restricted to the html file. But in stead of spreading out DOM manipulation to anywhere in any script, we concluded that DOM must be described relative to the current state, and thus can only occur in the form of boundary actions attached to the states.
We found that implementing the boundary actions using double closures, we could provide an encapsulated environment where the boundary action could hold on to references needed for clean-up work during exit.

Open questions:

What do we need on order to make it possible to define event handlers as boundary actions? (i.e. how to support some way to make transitions able to influence the state of the machine)
What primitives do we need for the state machine that is just assumed in this post?
Which primitives can be boundary actions, and which need to be something else?
So instead of a state machine, where states are combines using branching and choice, we are talking about a UI machine, where User Interfaces combines using branching and choice?
Then we should have a primitive that creates a User Interface, taking as parameters boundary actions and sub-UI's?
How to support parameterised states? Can update functions be base case transitions, and can we have "duck stating"*

duck stating -- a term formed after "duck typing", where a type is not what something is but wht it can be used as. Thus, under suck stating, state can be used wither as qualitative state or quantitative state or both.

Can duck stating allow update functions to be used as base case transitions?
Can duck stating be a key to naturally fit in parameterized states (param-or)?

[ The Art of the State ] Why it is impossible to write an Identity Function in JavaScript, and how to do it anyway

rekreanto — Mon, 28 Sep 2020 19:08:19 +0000

Section I: Why it is impossible...
Section II: How to do it anyway
Section III: Is there a cure for CPS Ugliness?
Summary: Ephemeral values makes CPS appear natural and readable

Section I: Why it is impossible...

An Identity function is a function that does nothing. It just returns what it receives. It's like the number zero, it's just there to fill the place without doing anything, and sometimes that is exactly what is needed.

So let's try to write an identity function in JavaScript.

const id = (x) => x;

Let's try it out

id(42)            /* => 42 */

id("forty-two")   /* => "forty-two" */

Our identity function works perfectly, doesn't it?
But what about this?

id(42, 43)         /* => 42 */

...Ouch! We forgot the case where there are multiple input values. Lets fix that.

const id = (...xs) => (...xs); /* Syntax error */
const id = (...xs) => xs;      /* Not identity any more */

Clearly this is not going well. What is the problem?

You can't write a real identity function in JavaScript nor in most languages

The problem is that there is no such thing as "multiple values" outside of function invocations. Unlike natural languages, there is no plural.

What is plural?

You know that you are talking about plural when a "plural" of one is the same thing as that one thing. This is for example not true for an array of one. [42] is not the same as 42. So arrays doesn't qualify as plural. Function invocation syntax is typicly the only place where plural is expressed in a programming langauge. (In Haskell it's complicated though.)

You probably don't have plural and thus can't express an identity function in your favourite language too

This is actually true for almost all programming languages. These is an asymmetry. A function can in no way return exactly what it received. Of course a function can return an array of it's arguments, but that is not the same thing. Doing that, the function then depends on the programmer to remember to splash the array when used as input to the next function call. But convention is not the same as language support. It simply can't be done as part of the language, only as part of an ad-hoc convetion, upheld by programmer discipline. The only language I know of that has plural in some meaningful sense is APL/J. I think.

So to summarize: You can't have a real identity function in most programming languages, because plural is not first class, and do not exist outside of function invocation syntax.

Section II: How to do it anyway

Now it seems quite impossible to write an identity function in JavaScript. Surely only the ECMA-committee can fix that?

The lack of symmetry, and how to fix it

I don't know about you, but this blatant asymmetry of the most fundamental building block is kind of not-so-beautiful, I think. It would be quite nice to be able to fix this!

So is there a way around it? Is there a way that we can program in JavaScript using perfectly symmetrical functions that has the ability, the super-power of not only accepting multiple values, but also returning them?

CPS to the rescue

CPS is short for Continuation Passing Style. CPS is often described considered as counter-intuitive and hard to wrap your head around. The basic idea is straight-forward, though. In stead of just returning a value, every function takes as an argument its continuation (the next function); and then it applies the continuation to whatever it wants to pass on. And since the applying is done by the giving function, it has a much greater freedom that a function that just returns value; one could sensibly call this is function application with consent. More precisely this collaboration between function and arguments is in fact so powerful, that any kind of control flow can be expressed under Continuation passing style. This is awesome: Among the new superpowers that we have gained are the ability to return any number of values! Plural is resurrected! We have symmetric functions that can express any control flow without any built-in language support. Programmers are now empowered and liberated, and resides on the same level as the language creators. Empowered is an understatement! It should come as no surprise that we can actually express our identity function:

/* `K` is often used to name the Continuation */
const cps_id = (...xs) => (K) => K(...xs);
const log = (...xs) => console.log(...xs);

cps_id(42, 43)(log); /* console: 42 43 */

So, with some caveats, we have actually a real identity function! Two problems are:

All of our code must be written in CPS style
CPS style code is harder to read and thus adds incidental complexity

Lets save the problem of how to lift all of JavaScript into the CPS world for another post, and focus on the readability problem.

Section III: Is there a cure for CPS Ugliness?

CPS is actually not only incomparably more empowering and powerful than than traditional applicative code, but also at least as readable! Let's refactor the above formulation of real_id:

/* Traditional CPS style: */
const old_cps_id = (...xs) => (K) => K(...xs);

/* Ephemeral CPS style: */
const Tuple = (...xs) => (K) => K(...xs);
const cps_id = (...xs) => Tuple(..xs);

OK, let's break that down!
First we defined a helper function that encapsulates the Continuation passing. It happens to be identical to the cps version of the identity function that we were looking for all along! That's a bit confusing but it will be clearer with a couple of examples. But first note how the cps_id went from mind-bending to normal, using just this helper (actually a rebranded version of itself).

First a real example of the usefulness of Ephemeral CPS

Sometimes a function just naturally returns two values, e.g. divrem; a function that returns the integer quotient as well as the modulo.

/* Ephemeral CPS style: */
const divrem = (x, y) => Tuple( Math.floor(x/y), x%y );
/* The CPS application chain is more uniform if we start with `Tuple` */
Tuple(14,3)(divrem)(log);  /* console: 4 2 */

Now we see how much more natural and readable the code gets if we encapsulate the continuation-passing in a function. N.B. that we need not call the Ephemeral value constructor Tuple, we could just as well call it Number or String (if those names were not already used), if what we return is a Number or String, or we could do runtime type-checking using a typed variant of Tupleetc:

const plus = (x,y) = Number(x+y);
const divrem = (x,y) = Tuple(Int, Int)( Math.floor(x/y), x%y );

So we can see that in actual code, we can encapsulate the continuation-passing. This means that we have an intermediate value in the middle of the computation that is a closure waiting for a function that wants to be applied. For this intermediate closure, I propose the term ephemeral value, because conceptually it is a value, while in practice it's just a closure waiting to concensualy accept a function in the way it self chooses to do it. CPS expressed using ephemeral values is readable and fits naturally into the programmers mental model of the computation.

Summary: Ephemeral values makes CPS appear natural and readable

We saw that a real identity function can be expressed in a restricted variant of JavaScript, called CPS, and that this identity function can be used to construct what we chose to call an "ephemeral value", that is something we can think of as a value but that in practice is a closure taking as its argument the Function that wants to be applied to the value, thus encapsulating CPS.
We saw that CPS can both easy to read and easy to grasp when we encapsulate it as ephemeral values. We can contemplate a chain of function applications as a duality between the functions and the intermediate values that has a brief existence in between function applications (or not so brief, if we want to wait for some reason).

Well that's enough for now. Kinda cool how a simple identity function can encapsulate CPS like that!

Open questions:

Can we lift the whole of JavaScript into Ephemeral CPS? Would we want to?
Can we to implement AMB as an ephemeral value? And then export it back to real js, so we can actually use it?
Can we make hierarchical ephemeral values? Dispatching trunkward, applying leafward? What are the differences? Similarities?
Can we parameterize ephemeral values with boundary actions thus mimicking State as in State Machines? We probably need a lot more for that to work out?
Can we build a minimal embedded language for Hierarchical state machines using ephemeral values with boundary actions if we just add situated transitions?
Can we add some DOM manipulation and get Hierarchical UI machines, where the fundamental component in stead of being a State is a UI?
What is your favourite open question? Please Comment!

Note: In a follow-up post I use the term Reified Continuation Passing Style to describe CPS encapsulated in Ephemeral values

DEV Community: rekreanto

Unified State Expressions - Transitions (First Sketch)

Some examples:

Non-hierarchical Traffic Light

Counter

The Linksy Kitchen Timer

Separate definitions are preferred

Unified State Expressions - State (First Sketch)

Constructs

Sample STN Notation for some Traditional Toy State Machine Examples

TrafficLight from xstate.js.org

Counter toy app from 7GUIs

TempConv toy app from 7GUIs

Sample small website GrowersAssociationSite (GA_Site)

This is a brilliant explanation of Orthogonal States by David Harel... using babies

[ Art of The State ] What is a HTML tag if the browser is a state machine?

A web page is a state

Clicking link triggers a transition

So what is a HTML tag?

A HTML tag represents a boundary action

Boundary actions are natural and helpful

So let's implement a HTML tag as a boundary action

[ The Art of the State ] Why it is impossible to write an Identity Function in JavaScript, and how to do it anyway

rekreanto ・ Sep 28 '20

Are we there yet?

How might those boundary actions be useful?

Summary

Open questions:

[ The Art of the State ] Why it is impossible to write an Identity Function in JavaScript, and how to do it anyway

Table Of Contents

Section I: Why it is impossible...

You can't write a real identity function in JavaScript nor in most languages

What is plural?

You probably don't have plural and thus can't express an identity function in your favourite language too

Section II: How to do it anyway

The lack of symmetry, and how to fix it

CPS to the rescue

Section III: Is there a cure for CPS Ugliness?

First a real example of the usefulness of Ephemeral CPS

Summary: Ephemeral values makes CPS appear natural and readable

Open questions:

[ Art of The State ] What is a HTML tag if the browser is a state machine?

rekreanto ・ Oct 1 '20