📝ステヌトマシン(FSM)

📝ステヌトマシン(FSM)

October 31, 2022

📝ステヌトマシン(有限オヌトマトン/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モデルが関係しおる.

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

See Also #


Tags