🔥虚無との戦い

📝ステートマシン(FSM)

14 min read

オートマトン

有限オートマトンの総称. 機械人形.

📝ステートマシン(有限オートマトン/Finate State Machine/FSM)

有限オートマトン(finate automation). 有限状態機械(Finite State Machine, FSM).

An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.

状態遷移に秩序をもたらす.

日本語だとステートマシンという単語でTopicに上がることがソフトウェア開発では多い印象を受ける(このメモのタイトルもステートマシンにした).

有限オートマトン自体は古くから計算機科学の分野として研究されてきており, ソフトウェア開発というよりはハードウェアの回路設計とかに適応されてきた歴史がある.

2種類のFSM

2つのサブ種類に分類できる

FSMの基礎概念

状態遷移のための制御方法. 以下の 5 つの構成要素からなる.

  • Inputs
  • Outputs
  • States
  • State Transition Graph (STG)
    • Tree
    • Matrix
  • Output Determination

What is a state machine? - Statecharts Finite-state machine - Wikipedia

state

A state is a description of the status of a system that is waiting to execute a transition.

stateの一番simpleな例はon/offの２つ. これはbooleanの値(true/false)で表現することができる. フラグ.

単一の状態変数ではなく, 複数の状態変数の集合も, 状態と呼ぶことが出来る. Wikipediaより.

Program state is the set of all variables in a program and their values at any point in time.

transition

あるstateから別のstateに移ること. その遷移のトリガーをeventという.

event

なにかが起こりFSMに通知されたとき, それはFSMから見ると外部からのeventとなる.

  • External Events: APIを叩いたあとに戻ってきたイベント
  • Internal Events: machine内部で自分で発生するイベント
    • action.
    • 完了通知(done event).

machine

states, transitionsの集合.

オブジェクト指向におけるクラスの概念からの類推で捉えるとわかりやすいかもしれない. クラスとはデータと操作をドメインの単位で集めたもの.

💡ステートマシンを定義するということはクラスを定義すること

FSM: Actorの基礎概念

しばしば実践的工夫としてのライブラリに実装されているたぐいのもの.

Actorモデルが関係してる.

Actors, actions and invoked actors | XState Docs

actor

ステートマシンとは, Actorの実行可能モデルと捉えることが出来る.

ステートマシンを実行すると, それはActorとして振る舞う. すなわち, streamに読み書きするスレッドであり, 情報を他のThreadにsendしたりrecieveすることができる(外部への副作用).

ref. 🤔ステートマシンを初期化するということはアクターを生成すること

  • running
    • runningしつづけるというニュアンスでserviceと呼ばれることもある.
  • activity
    • startとendがあるというニュアンスでactivityと呼ばれることもある.

action

(外の世界ではなく)FSMがキックしたevent. raised eventとも.

一般的にはこれをSide effect: 副作用という.

2種類のactionがある.

  • transition actions
    • transition中に実行されるaction.
    • 非同期で情報取得するような処理もここ.
  • entry/exit actions
    • transitionの開始(entry)や終了(exit)で起こるaction.
    • entry/exitで起動されたactionは外部の処理として忘れることが出来る.
    • fire-and-forget.

Invoking

しばしばtransition actionを起動することをinvokeと表現する.

XStateの記事にはinvokingの種類が書かれている.

Invoking Services | XState Docs

しばしばonDone(onSuccess)/onErrorみたいなコールバックのoptionを伴う.

Stream(EventQueue)

これはソフトウェア実装上の工夫.

ステートマシンにeventを通知する際のキューイングにつかうデータ構造.

外部からのexternal eventsや内部からraiseされたinternal eventsを上手く処理する入口.

📝決定性有限オートマトン

Deterministic Finate Automaton. DFAともいわれる.

状態と入力によって次に遷移するべき状態が 一意に 定まる有限オートマトン.

決定性有限オートマトン - Wikipedia

🔖deterministic

📝状態遷移図

有限オートマトンをグラフィカルに表現した図.

Moore Machine

ムーアマシン. 出力が(入力によらず)現在の状態によってのみ決定される有限オートマトン.

NextState = f (Input, CurrentState)
Output = g (CurrentState)

Mealy Machine

ミーリマシン. 出力が現在状態と入力によって決定される有限オートマトン.

Output = h (Input, CurrentState)

📝Statecharts

FSMの表現方法の一つ. FSMにおいて, 状態を定義して多すぎになってしまい複雑化した状態爆発(state explosion)を解決しようというもの.

1980年代にDavid Harelが提唱. 別名ハレルチャート.

状態管理のイシューを宣言的に解決する手段として近年Webフロントエンド界隈で静かなブーム? Statechartsだけだと日本語情報は少ないのでXStateの記事を探すのがいい. statechartsのキーワードだと古い組込み開発の話題が多い印象.

Statechartsの基礎概念

FSMのstate explosionの解決策であるため, statechartsを理解するにはその前のFSMについて理解する必要もある.

以下のページは単語とそれに対応する図をハイライトしてくれる.

UML:ステートマシン図はstatechartsを参考につくられているようで, ステートマシン図のWikipediaも参考になる. (ref. UML state machine - Wikipedia)

extended states

extended state variablesといい, この機能を持つステートマシンをとくにextended state machineということもある.

XStateとかではcontextと呼ばれるもの. Practicalな理由によって状態変数を全ての状態から読み書きできるようにしたもの.

たとえば, counterの値を条件としてtransitionするなど.

Hierarchy States

state explosionの解決のために, stateに階層構造を導入する. Hierarchy Statesなどと呼ばれる.

  • Compound States: 複数のstateからなるもの. 親state.
  • Atomic States: 単体のstateであり, 他のstateの部分になる, 子state.

あるcompoind stateにenterすると, そのsub stateにも連続してenterする.

regions

別名はparallel state, orthogonal regions.

compound stateはサブstateとして互いに影響しあわない, 複数のstateを持つことができる.

Guarded/Delayed/Automatically Transition

  • 条件付きの状態遷移(guarded transition).
  • 遅延を伴う状態遷移(delayed transition).
  • 自動遷移(automatica transition).
  • self transition
  • local transition

Statecharts References

David Harelさんの論文.

https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/resources/statecharts.pdf

state machine/statechartsについておそらくもっともわかりやすいサイト. statechartsの論文は難しいので開発者向けに使える情報としてシンプルに噛み砕きました, 的な.

Welcome to the world of Statecharts - Statecharts

XStateのページがかわいい絵とともにわかりやすい.

Introduction to state machines and statecharts | XState Docs

📝XState

Statemachine/StatechartsをWebで実装するための有名なフレームワーク(JavaScript).

ステートマシンはJSONで定義する.

🔖状態管理ライブラリ

XState とActorモデル

🤔ステートマシンを初期化するということはアクターを生成すること

XState Visualizer

XStateのFSMを可視化するWebツール.

JSON形式で記述する. 作成した図はWebで(Twitterとかでも)共有できる.

UML:ステートマシン図よりもメチャメチャイケてる気がした.

XState References

💭XStateについて調べはじめて状態という概念がわからない雰囲気オジサン

FST

Finite-state transducer - Wikipedia

Lucene のFinate State TransducerはFSMの100倍速い?

ステートマシンTopics

higher level events

eventsは外部からFSMに通知されるものはなんでもというざっくりとした定義だが, higher level eventsという表現もある. ドメインにおいて定義した特定の状態が発生すると通知するたぐいのもの(becomming empty, 空になったとか).

higher level eventsとは一連のeventsの監視をFSMの外に出す, そしてFSMの内部の状態をシンプルにする. なぜなら条件判定をFSMの内で何度もしなくていいので. これはモデリングの課題となる.

ステートマシンInsights

ステートマシンの機能拡張がステートチャート

ステートマシンの改良がステートチャート.

自分の雑な理解では, FSMにいくつかの機能追加されたようなもの.

特に, 階層的なstate管理が状態爆発を上手く整理するのかと.

statechartsのライブラリはprefixにstate machine and statechartsと書かれているのも, statechartsの基本機能がstate machineだから.

逆に言えば, 目の前の課題を解決する手段がstatechartsではなくstate machineでもよいし, なんならいくつかの状態変数の自前管理でもフラグでもいいわけだ. その課題にあった手段を適切に選ぶべきで, サイズのあわないブカブカパンツをはく必要もない.

🤔ステートマシンを定義するということはクラスを定義すること

What is a state machine? - StatechartsのAbstract machine vs run-timeより.

抽象マシンとランタイムの関係は, オブジェクト指向におけるクラスとオブジェクトに似ている.

🤔ステートマシンを初期化するということはアクターを生成すること

あまり目立たないXStateのCoceptとして📝Actor モデルの布教というものがある.

ref. Concepts | XState Docs

XStateにおけるActorとはステートマシン(💡ステートマシンを定義するということはクラスを定義すること)であり, Actorはstreamを介して他のActor(外部)と情報を交換する(send/recieve).

あるThreadにおける振る舞いを抽象的に定義する.

References

Reactの登場から状態遷移を考え直しましょうというスライド(動画もある).

Infinitely Better UIs with Finite Automata

グラフビュー

バックリンク

Recents