Is a statechart / finite state machine suitable for modelling a questionnaire

Question

I'd like model the above questionnaire which I believe is a directed acyclic graph.

The two libraries I've been looking at are:

A couple of the issues I have are:

The questionnaire relies on previous states e.g. the answers to previous questions are used to transition to another state (question). Am I right in thinking that "external state" could solve this problem?
If I'm at Q6 and I want to transition to the previous question, then depending on the previous answers, this could be either Q1, Q4, or Q5. I think I could use a stack to push each state as the questionnaire progresses and then pop to get back to a previous state.

Does this all sound feasible or is there a better way to model this problem?

user3743222 · Accepted Answer · 2018-08-16T22:35:19.287

A solution to this problem can be modelized by an extended state machine. You don't necessarily need a hierarchical one. The states and transitions you show can be addressed with a regular state machine, but the 'memory' part is properly addressed with an extended state machine.

In short, your graph remains the same, with the addition of updates to the extended state on each transition. For instance your extended state could be {A1, A2. ..., A6, H}, where Ax stands for the answer to Qx, and H is the history of states the machine has gone through. When you transition from Q1 to Q2, you also update A1 to the answer, and H to [A1]. You do that for all Qs. Arriving on Q6 you have all the information you need to write a guard deciding where to transition based on the history of previous states, and answers.

So, to summarize an answer to your question : yes, external state can be used profitably, and in that case, a stack holding the state history would solve your problem, as you intuited. You can also use a statechart library, of course, as statecharts generalize extended state machines.

As a add-on, I include also my own extended state machine library to the excellent ones you already mentioned : https://github.com/brucou/state-transducer.

You will find there a demo which is very similar to the problem you just described. It is also about a multi-step questionnaire, with the complication that it included error paths.

mogsie · Answer 2 · 2018-08-18T13:19:34.497

Answering the second half of the question here, about figuring out how to get to Q4 and Q5 (and ignoring Q1 to Q6 for now)

The typical first naive way (also my initial way) of representing this as a state machine makes each question into its own state, with each state represented exactly once in the state machine. Using a statechart, you could extract the question 4 and 5 into a compound state in such a way that when Q4AND5 is active, exactly one of Q4 or Q5 are active:

<scxml>
  <state id="Q1"/>
  <state id="Q2"/>
  <state id="Q3"/>
  <state id="Q4AND5">
    <state id="Q4"/>
    <state id="Q5"/>
  </state>
  <state id="Q6"/>
</scxml>

Then transitions from Q3 to Q4AND5 would cause either Q4 or Q5 to become active, because of guarded transitions.

<scxml>
  <state id="Q1">
    <transition event="answer" target="Q2"/>
  </state>
  <state id="Q2">
    <transition event="answer" target="Q3"/>
  </state>
  <state id="Q3">
    <transition event="answer" target="Q4AND5"/>
  </state>
  <state id="Q4AND5">
    <transition cond="if q1 == 'FOO' and q3 == 'BAR'" target="Q4"/>
    <transition cond="if q1 == 'BAR' and q3 == 'FOO'" target="Q5"/>
    <state id="Q4"/>
    <state id="Q5"/>
    <transition event="answer" target="Q6"/>
  </state>
  <state id="Q6"/>
</scxml>

Going back from Q6 would go to Q4AND5 which would cause the machine to enter either Q4 or Q5:

  <state id="Q6">
    <transition event="back" target="Q4AND5"/>
  </state>

Now, after the question was modified to include Q1 to Q6 transition, it becomes apparent that modeling each question as a distinct state doesn't cut it. It's also not quite correct. If you think about it, there are two Q6 states, one after arriving at Q6 from Q1, and another after arriving at Q6 from Q4AND5. If we instead split those two Q6s into two distinct states, then it's quite easy to acommodate this new transition:

<scxml>
  <state id="Q1">
    <transition event="answer" target="Q6B" cond="q1 == 'BAZ'"/>
    ...
  </state>
  ...
  <state id="Q6A">
    <transition event="back" target="Q4AND5"/>
  </state>
  <state id="Q6B">
    <transition event="back" target="Q1"/>
  </state>
</scxml>

The problem is now that Q6 is represented by two states (Q6A and Q6B). The solution here is to decouple from the names of the states themselves, and declare in each state which question to show, typically by way of an action or a change to some variable. Below I've define a data element that the statechart updates to the name of the correct question to show.

<scxml>
  <datamodel>
    <data id="question"> <!-- The name of the question to show -->
  </datamodel>
  <state id="Q1">
    <assign location="question" expr="'Q1'"/>
    <transition event="answer" target="Q6B" cond="q1 == 'BAZ'"/>
    <transition event="answer" target="Q2"/>
  </state>
  <state id="Q2">
    <assign location="question" expr="'Q2'"/>
    <transition event="answer" target="Q3"/>
    <transition event="back" target="Q1"/>
  </state>
  <state id="Q3">
    <assign location="question" expr="'Q3'"/>
    <transition event="answer" target="Q4AND5"/>
    <transition event="back" target="Q2"/>
  </state>
  <state id="Q4AND5">
    <transition event="answer" cond="if q1 == 'FOO' and q3 == 'BAR'" target="Q4"/>
    <transition event="answer" cond="if q1 == 'BAR' and q3 == 'FOO'" target="Q5"/>
    <transition event="back" target="Q3"/>
    <state id="Q4">
      <assign location="question" expr="'Q4'"/>
    </state>
    <state id="Q5">
      <assign location="question" expr="'Q5'"/>
    </state>
    <transition event="answer" target="Q6A"/>
  </state>
  <state id="Q6A">
    <assign location="question" expr="'Q6'"/>
    <transition event="back" target="Q4AND5"/>
  </state>
  <state id="Q6B">
    <assign location="question" expr="'Q6'"/>
    <transition event="back" target="Q1"/>
  </state>
</scxml>

This decoupling makes it easier to change the statechart, move things around without changing every user of the statechart. Conversely: depending on the state names outside the statechart/state machine causes the state names themselves to become the state machine's API, meaning it cannot be changed easily.

I've updated the question to add an additional route from Q1 to Q6. I think this better illustrates the problem. @mogsie how would the transition "back" actually work? — Stephen S, Aug 16 '18 at 16:41
@StephenS SCION-CORE lets you capture "snapshots", which is a serializable json object containing the state machine configuration (set of states) and datamodel ("external state" you referred to). You could store a stack of snapshots and use this to implement the "back" functionality. — jbeard4, Aug 16 '18 at 17:05
@jbeard4 I take it that the datamodel could be queried for previous answers, which could then be include in conditions? — Stephen S, Aug 16 '18 at 21:55
@mogsie I see what you mean regarding the complexity. Thinking about it, I probably don't need to model "back" transitions, I think the stack idea would be sufficient, especially given jbeard4's input. I do feel as if there is a better way of modelling this. I'll see if any further answers/comments can provide further insight — Stephen S, Aug 16 '18 at 22:02
@stephens sure, you can put whatever you want inside of the datamodel — jbeard4, Aug 16 '18 at 23:17

score 0 · Answer 3 · answered Aug 16 '18 at 22:26

I would approach this using an FSM and remembering the states in a Map or js object. Then you can prevent to trigger a transition checking the states you keep in memory.

That is a practical solution that I would take, you can use a FSM lib but my advice also uses an object to keep the answers.

Is there an implementation of FSM in which transition can take external state? If such thing exists you could write the logic inside the machine but you would have to remember the answers manually (to keep it a generic solution)

Łukasz Makuch · Answer 4 · 2018-08-19T05:44:21.933

0

A real-world questionnaire needs to save the answers somewhere and that's where an external state (like a bunch of key-value pairs) turns out to be useful. Any attempt to store the given answers within the graph (where every possible value would be a separated node) would immediately fail due to a phenomenon known as state explosion.

However, fetching previously given answers and then consuming them with conditional expressions in order to implement transitions is kind of an escape hatch. As an advocate of automata-based programming, I believe that the use of IFs should, most of the time, be limited to the input data and that the external state should not be inspected in such a way, unless the desired behavior cannot be expressed by a reasonable graph.

To prove that it can actually work, I implemented it in Rosmaro and pushed to this repository - https://github.com/lukaszmakuch/so-questionnaire. You can see what does the graph look like in the editor here - https://i.stack.imgur.com/uDkh5.png.

This is a complete, working example that supports:

reading the current question
answering the current question
reading the given answers
going back to the previous question

Here's how it works:

git clone https://github.com/lukaszmakuch/so-questionnaire.git
cd so-questionnaire/
npm i
npm start
$ question()
'Q1'
$ answer('baz')
undefined
$ question();
'Q6'
$ answer('anything')
undefined
$ answers();
{ Q1: 'baz',
  Q2: null,
  Q3: null,
  Q4: null,
  Q5: null,
  Q6: 'anything' }
$ back()
undefined
$ question()
'Q1'
$ answer('foo')
undefined
$ question()
'Q2'
$ answer('test')
undefined
$ answers()
{ Q1: 'foo', Q2: 'test', Q3: null, Q4: null, Q5: null, Q6: null }
$ question()
'Q3'
$ answer('bar')
undefined
$ question()
'Q4'
$ answer('fuzz')
undefined
$ question()
'Q6'
$ back()
undefined
$ question()
'Q4'
$

edited Aug 19 '18 at 05:44

answered Aug 18 '18 at 07:59

Łukasz Makuch

1
1

guards appear in the extended state machine formalism precisely because of the extended state. Otherwise you have a regular standard automata (you can have the extended state out of the automata if you don't read from it), and how do you then avoid state explosion ? You can find some examples where you can do without guards, but in the general case, it is a seriously limiting move. – user3743222 Aug 18 '18 at 15:37
**What is bad practice is to use extended state + guards where a control state could be used instead**. At the very extreme, you can convert an extended state machine with N states to one with only one state, and a bunch of guards by including the control state inside the extended state. While you would not loose semantics, you loose the readability/maintainability of the first. But there is no hard rule such as *never use guards*. – user3743222 Aug 18 '18 at 15:43
A state explosion would occur very fast if the graph were the only memory, that is if every typed character needed to be recorded as a different graph node. This is where extended helps a lot. Data-related state may be stored there, while behavior-related state may be represented by a different model, like a graph. – Łukasz Makuch Aug 18 '18 at 17:51
I believe that such a powerful tool, which guards doubtlessly are, should be used sparingly, as they lead to what state machines are meant to eliminate, that is boolean based decision making. Most of the time when applied to the input they are harmless, because they don't actually interfere in the state. But as soon as the external state is involved, it creates a dependency on events and states from the past. For example, some of the solutions presented earlier make states like Q5 dependent on the data set by much earlier states like Q1 and Q3. It makes nodes and arrows more coupled. – Łukasz Makuch Aug 18 '18 at 17:54
Usually when I'm tempted to do such a thing, I try to look for a graph architecture that could replace it. Of course no graph is a silver bullet and that's why sometimes it's perfectly valid to sprinkle the external state with a couple of IFs. This is especially true when it comes to counters, as it wouldn't be handy to implement 50 nodes only to count to 50. – Łukasz Makuch Aug 18 '18 at 17:54
In this example https://github.com/lukaszmakuch/Rosmaro-React-example-Bunny-App/blob/master/src/bindings/main/FeedingTheBunny/TheBunny/AnEatingBunny/index.js the bunny isn't full unless it's given 5 carrots. Although it would be possible to store the number of eaten carrots in the graph by using 5 nodes, it's a lot easier with an integer. If we decide that the bunny needs to eat more, all we need to do is to change `5` for `10` of adding 5 extra nodes. There's an interesting Wikipedia chapter on guards overuse - https://en.wikipedia.org/wiki/UML_state_machine#Guard_conditions – Łukasz Makuch Aug 18 '18 at 17:56
I hear you but `the use of IFs should be limited to the input data and that the external state should **never** be inspected in such a way` is a far cry from advising diligent use of guards and good modelling. – user3743222 Aug 18 '18 at 21:45
1

Thank you for drawing my attention to this a bit harsh statement on IFs and the external state. You're right, the word "never" shouldn't appear there, as such a technique may actually be useful. I've updated my answer. What I'm trying to say is that with guards and the external it may be tempting to escape the automata-based paradigm far too soon. – Łukasz Makuch Aug 19 '18 at 05:52
@ŁukaszMakuch thanks for all the effort you've put in to providing your answer! I've tried modelling all the "back" states but it's not as manageable as the history stack. – Stephen S Aug 30 '18 at 14:57

score 0 · Answer 5 · answered Aug 18 '18 at 19:52

A different approach than using a compound state for S4 and S5 is to use a compound state for S6 instead:

<scxml>
  <state id="Q1">
    <transition event="answer" target="Q6_from_1" cond="q1 == baz" />
    <transition event="answer" target="Q2"/>
  </state>
  <state id="Q2">
    <transition event="back" target="Q1"/>
    <transition event="answer" target="Q3"/>
  </state>
  <state id="Q3">
    <transition event="back" target="Q2"/>
    <transition event="answer" cond="if q1 == 'FOO' and q3 == 'BAR'" target="Q4"/>
    <transition event="answer" cond="if q1 == 'BAR' and q3 == 'FOO'" target="Q5"/>
  </state>
  <state id="Q4"/>
    <transition event="back" target="Q3"/>
    <transition event="answer" target="Q6_from_4"/>
  </state>
  <state id="Q5"/>
    <transition event="back" target="Q3"/>
    <transition event="answer" target="Q6_from_5"/>
  </state>
  <state id="Q6">
    <state id="Q6_from_1"/>
      <transition event="back" target="Q1"/>
    </state>
    <state id="Q6_from_4"/>
      <transition event="back" target="Q4"/>
    </state>
    <state id="Q6_from_5"/>
      <transition event="back" target="Q5"/>
    </state>
  </state>
</scxml>

The only special state is Q6, since it remembers "where it came from" by the transitions in to the state targetting specific child states.

This can be combined with the idea of a compound state for Q4 and Q5.

Thanks for this @mogsie, much cleaner than your previous answer. I've tried modelling some of the questionnaires this way but it just gets really messy. I reckon the history stack is the more manageable approach. Either that, or potentially programmatically wire up all the "back" transitions — Stephen S, Aug 30 '18 at 13:32

Is a statechart / finite state machine suitable for modelling a questionnaire

5 Answers5