FSM support

[AndreVanDelft]

tl;dr

FSM support would largely enhance SubScript's applicability.
Currently you can define recursive specifications in SubScript that model FSMs,
but at run time these cause arbitrary depth call graphs. It seems to be possible to overcome that.

Introduction

We have been working lately on modeling an induction stove appliance.
This turned out to be harder than we had hoped for.

One of the problems is that some behaviors are more naturally modelled using FSMs, rather than with scripts that have the usual sequences, choices, parallelism, iterations.

Now an FSM consists of states and transitions between those states.
The transitions are most often triggered by events, including timeouts.

It is possible to specify an FSM as a set of recursive equations, e.g.,

A = b1 B + c1 C
B = c2 C + d1 D
C = a1 A + d2 D
D = a2 A

Here A, B, C and D denote the states, and the other elements denote the transition events.

It is possible to use such definitions as scripts. There seem to be 2 problems with that:

• (minor) the name of the current state is not explicitly administered somewhere
• (major) the recursion may cause the call graph to grow to unbounded depths

Solutions seem to be possible.

Administering the name of the current state

It will often be useful to store the name of the current state in a variable. This could be possible in a descendent of something like this:

trait FSM {
  var stateName: Symbol
  script state = let stateName = here.script.parent.script.name
  script main

}

The state script would grap the name from the calling script.
This saves us from providing an explicit parameter, as in state: 'A
Usage would then be like:

class MyFSM extends FSM {
  script ..
    A = state; b1 B + c1 C
    B = state; c2 C + d1 D
    C = state; a1 A + d2 D
    D = state; a2 A

  override script ..
    main = A

    // etc...
}

Limiting recursion depths in the call graph

Suppose the FSM of the example code would switch between states A and C. Then, without provisions, the call graph would contain a chain
call A, script A, ;, +, ;,
call C, script C, ;, +, ;,
call A, script A, ;, +, ;,
...

So for each full recursion cycle you would get 8 nodes.

That would after a while cost more memory than available. To make things worse, large depths would also make the SubScript VM slower, because messages such as AAHappened must each time propagated upwards towards the top of the call graph (which is directed and acyclic, so there is a top).

Now it is possible to get rid of such node chains, with techniques that are similar to tail recursion optimization:

1. In the first + node, when the c1 event happened, the branch b1 B had been excluded. At that point, the + might as well have been bypassed. The current semantics of the VM does not give a provision for that, but variations of the VM, possibly created using plugins, might do so. The bypass could for instance be done when the enclosing script has a specific attribute set, such as "optimizeRecursion". That could be done in the state script.
2. Likewise, the ; nodes may be dropped, and the current child nodes are definitely the last ones.
   Note that this cannot be decided immediately before creating the child nodes, as the child node may in principle set the "iteration" flag of the ; node. Moreover, when activated the child branch must know what kind of node the local root is: is it and-like, as with ;, then the neutral element in that context behaves like 1, etc.
3. Similar logic can in principle also hold for other kinds of operators. Note though that for & and && there are special constraints for removal: that cannot be done when a different branch had been terminated with failure: that 0 would thereafter require that no success can come through any more, so a node would remain to be needed.
4. Also the call A, script A nodes etc may be dropped. This would not have been possible if A (and C) had output parameters or return values. The flagging as state scripts could hint the VM that these nodes are indeed not necessary. However, it should be determined when such call + script node pairs should be removed. Note that the state script itself wants to access the calling script, to obtain the state name. Therefore the removal should not be done too early. Probably when a new call+script node pair is pended just below an older call+script node pair, the latter should go.

Implementation

The above ideas seem well suited for implementation.