–- 原筆記在 Bear 裡，這是 paste 來分享用的 –-

---

《Statecharts: A visual formalism for complex systems》摘要筆記

端看怎麼表達最容易因此中英夾雜、不是翻譯因此也許跟語句原本的意思有出入、有些解釋重要概念的原文會放在後面的括弧內、有些原文講得夠簡單就直接原句抄錄。

---

論文大綱

• Sections 1: 帶出問題現況、視角和簡述 statechart 是什麼。
• Sections 2-5: 主要內容，介紹 statechart 這個解決辦法。
• Section 6: 介紹一些研究中的、可以擴充 statechart 基本形式的進階功能。
• Section 7: statecharts 的正式語義。
• Section 8: 討論一些前人嘗試擴充 flat state diagrams 的成果，例如 communicating state-machines and augmented transition-diagrams，並與 statechart 比較。
• Section 9: 簡單報告在 statechart 語言累積的經驗，以及其中一個實作。

文中的狀態機範例都是以作者的 Citizen Quartz Multi-Alarm III 腕錶為例。

---

1. Introduction

• 關於軟體和系統工程的文獻幾乎一致地意識到：在「定義與設計巨大且複雜的 reactive system」存在著一個重大的問題。
  • 相對於 transformational system，reactive system 的特徵是：它很大的程度來說是 event-driven 的，需要不斷對內部或外部的刺激做出反應。
    • Transformational system 是例如：各式各樣的數據處理系統。論文中沒有舉出實際的例子，但我想大部分內容導向網站 (Blog、Forum、新聞、主題電商) 的伺服器端、會計、財務、統計、資料分析程式都屬於這種。
      • 以特性歸納，可以說主要在處理資料和計算吧。
    • Reactive system 是例如：電話、汽車、通訊網路、作業系統、導彈、航空設備。
      • 還有各種尋常軟體的人機介面 (man-machine interface of many kinds of ordinary software)。
      • 以特性歸納，可以說主要在處理互動吧。
  • 問題深根蒂固在：用「切實可行而明確、又要嚴謹到足以交由計算機模擬」的方式描述一個 reactive system 是相當困難的。(The problem is rooted in the difficulty of describing reactive behavior in ways that are clear and realistic, and at the same time formal and rigorous, sufficiently so to be amenable to detailed computerized simulation.)
  • Reactive system 表現出來的形式其實是這些東西的組合 (The behavior of a reactive system is really the set of …)：
    • allowed sequences of input and output events
    • conditions
    • actions
    • 也許還有一些額外的資訊，例如時間限制。
  • 讓這個問題格外加劇的是：這組 (通常是巨大而複雜的) sequences 不相容於一種易於被人類大腦解讀的格式：逐級且分層的敘述。是的，這組 sequences 無法被逐級、分層地描述出來。(What makes the problem especially acute is the fact that a set of sequences (usually a very large and complex one) does not seem to lend itself naturally to ‘friendly’ gradual, level-by-level descriptions, that would fit nicely into a human being’s frame of mind.)
    • 相對的，在 transformational systems 中，實際上只需要定義一個轉換 (transformation) 又或是 function：也就是輸入和輸出的關聯，便已足夠。雖然它也可能很複雜，但通常很好拆分 (While transformational systems can also be highly complex, there are several excellent methods that allow one to decompose the system’s transformational behavior into ever-smaller parts in ways that are both coherent and rigorous. Many of these approaches are supported by languages and implemented tools that perform very well in practice.)。
    • 也許可以這樣說：transformational system 的系統架構可以被表示為 tree，但要表示 reactive system 就必須要用 graph。Tree 對人來說容易閱讀和理解，但 graph 就難了。
    • We are of the opinion that for reactive systems, which present the more difficult cases, this problem has not yet been satisfactorily solved.
    • Several important and promising approaches have been proposed, and Section 8 of this paper discusses a number of them.
    • 這篇論文就是沿著此方向前邁進的嘗試。
• 許多文獻都同意狀態 (state) 和事件 (events) 是描述系統中動態行為的媒介。
  • 這種描述的基本片段是 state transition，標準格式是："when event occurs in state A, if condition C is true at the time, the system transfers to state B."
    • e.g., "when the plane is in cruise mode and switch x is thrown it enters navigate mode”, or “when displaying the time, if button y is pressed the watch starts displaying the date".
  • 但人們也大多同意用這種方式描述一個複雜的系統並沒有得到什麼好處。
    • 因為狀態的數量會以指數成長、而且不能分層處理，因此會造就一個無結構可言、沒有實用性、混亂的狀態圖。
• To be useful, a state/event approach must be modular, hierarchical and well-structured.
  • It must also solve the exponential blow-up problem by somehow relaxing the requirement that all combinations of states have to be represented explicitly.
  • A good state/event approach should also cater naturally for more general and flexible statements, such as
    1. "in all airborne states, when yellow handle is pulled seat will be ejected",
    2. "gearbox change of state is independent of braking system",
    3. "when selection button is pressed enter selected mode",
    4. "display-mode consists of time-display, date-display and stopwatch-display".
  • Clause
    1. (1.) calls for the ability to ::cluster states into a superstate::,
    2. (2.) introduces ::independence, or orthogonality::,
    3. (3.) hints at ::the need for more general transitions:: than the single event-labelled arrow, and
    4. (4.) captures ::the refinement of states::.
• Conforming to the "one picture is worth a thousand words" aphorism, one would like to find a way to change or extend the good old state/event formalism in ways that will satisfy these needs, while retaining, or even enhancing, the visual appeal of state diagrams.
  • Flowchart 不足以描述 concurrency (when surveying flowchart techniques, all but challenges the computer science research community to come up with a good visual medium for describing concurrency)。
  • Orthogonality, as described later, represents concurrency。 (?

---

2. State-levels: Clustering and refinement

• 比起用樹狀圖或其他點與線的方式表達階層，用層層嵌套的方框來表示不同層級較好。
• An arrow will be labelled with an event (or an abbreviation of one) and optionally also with a parenthesized condition.

如圖一表示有 A、B、C 三個狀態，例如當系統在 A 狀態時，事件 γ 發生且條件 P 成立，系統的狀態會改變為 C。

[image:075F70EB-C2C3-4D61-80F0-6AA984691048-3639-00022293C972BCBA/螢幕快照 2019-09-14 下午11.25.52.png]

因為事件 β 在狀態 A 或 C 下都會把狀態轉換為 B，我們可以把 A 和 C 歸入 (cluster) 一個 super-state D，並把兩個 β 的箭頭合而為一，如圖二。

[image:276E9191-18A5-4029-B60D-F11CBE7B86A8-3639-00022318A5C12DE6/螢幕快照 2019-09-14 下午11.26.10.png]

D 的語義是「A 或 C」(exclusive-or, XOR)。因此也能說 D 是「A 和 C」的 abstraction。The state D and its outgoing β arrows thus capture a common property of A and C. 這「把『會從所有 sub-state 離開』當作是『離開某個 super-state』」的決策非常重要，也是消滅多餘箭頭的主要方式。

從另一個角度來推進到圖二，也有可能是這樣：首先我們決定使用如圖三的 D、B 兩個狀態，再把狀態 D 細分 (refine) 成由 A、C 兩個狀態構成 (圖四)。然後把 α 以及 δ 延長到直接指向 D 內部的 A 或 C，最後加上 D 內部的狀態轉換，也就是 γ，就可以得到與圖二相同的狀態機。

Thus, clustering, or abstraction, is a bottom-up concept and refinement is a top-down one; both give rise to the or-relationship between a state’s substates.

[image:1F3D0EC5-4D56-4CD7-9340-C6583D33C387-3639-00022521FADAD941/螢幕快照 2019-09-15 上午12.12.50.png]

如果要 zoom-in 或 zoom-out 這種圖，可以這樣：

• 放大檢視狀態 D 內部時，如圖五。
• 縮小檢視時，可以省略 D 內部的細節，並把圖二簡化為圖三。

如果要表達 A 是初始狀態，可以畫作圖六。在圖二的那種狀況，可以直接畫作圖六 (ii)，或圖六 (iii)，來表示在 D 和 B 之間，D 是預設的，又 D 內部 A 是預設的。當然圖六 (iii) 的那種畫法比較便於「縮放」、簡化。

[image:5234A634-60B2-4FE3-B018-FE3B6E078E57-3639-0002259E30731554/螢幕快照 2019-09-15 上午12.18.29.png]

介紹一下範例，Citizen Quartz Multi-Alarm III 錶有以下配備：
- 一個主螢幕、四個附螢幕。
- 可以發出兩種不同音調的蜂鳴器。
- a、b、c、d 四顆按鈕。
它可以：
- Display the time (with am/pm or 24 hour time modes) or the date (day of month, month, day of week).
- 鐘點報時，如果有啟動的話。
- 設定兩組獨立的鬧鐘。
- 有碼表功能，附帶分圈計時。
- 螢幕背光。
- 在螢幕上閃爍低電量警示符號。
- 有蜂鳴器測試功能。

主要的外來事件有：按下和釋放按鈕，我們用 a 來表達 "a" 按鈕被按下、â (a^) 來表達 "a" 按鈕（被按下後）釋放等事件。

[image:64DA3A6E-8485-4D98-8B5E-E527D7BBAA54-3639-00022607E99A8E53/螢幕快照 2019-09-15 上午12.29.05.png]

下圖八展示了此錶從正常狀態 (先把它叫做 display mode) 到不同響鈴狀態的轉換：

[image:97CA4B2C-97B0-4A2A-B4A5-12002D66283E-1423-0000149B106F82AC/螢幕快照 2019-09-15 下午10.14.47.png]

（實際上，鬧鈴響的時候並不會影響任何螢幕上的內容，但我們先無視這件事——它到 Section 5 討論 activities 後才有辦法處理）
上圖符號的意義：
- T 代表目前時間。
- T1 和 T2 代表鬧鈴一和鬧鈴二設定的時間。
- P1 代表：鬧鈴一為啟用狀態 && (鬧鈴二為停用狀態 || 鬧鈴一設定的時間 != 鬧鈴二設定的時間)。P2 也類似。
- P 代表：鬧鈴一為啟用狀態 && 鬧鈴二為啟用狀態 && 鬧鈴一設定的時間 == 鬧鈴二設定的時間。
（之後加入更多描述時，以上條件我們會用更精確的形式來改寫。）
注意圖八被 crusted 的部分 (alarms-beep 方框)，是它讓我們得已用兩條箭頭取代了六條。

接著我們來細分 (refine) 一下那塊 "displays"，如下圖九：

[image:29624B2C-0244-4475-A6F7-DB60BD6ABD71-1423-000015C80493E869/螢幕快照 2019-09-15 下午10.36.11.png]

上圖表達了：
- 不斷按下 a 按鈕，可以在不同顯示模式之間切換。
- 在時間模式按下 d 按鈕，可以查看日期，再按一次 d 可以退回時間模式，另外在顯示日期的狀態閒置兩分鐘會自動切回顯示時間。
- 預設的狀態是顯示時間。也就是說，從圖八的鬧鐘鈴響 (alarms-beep) 狀態回到顯示狀態時，實際上是進入顯示時間狀態。現階段我們可以先接受這件事，之後會再改。

嘗試把現階段的 statechart 用 XState 寫出來：https://xstate.js.org/viz/?gist=664a0b32b42bea37a717aacc15feeb34

論文原檔

[file:B9F99188-D1B7-4C51-AC43-D7EBB3537A0F-3639-0000DD796CB85780/statecharts.pdf]

參考資料

• Welcome to the world of Statecharts

#筆記 #技術