クリプキクローネ日記帳
ある種の音楽と数学とランニングはミニマルなところが似ていると思う。
ソフトウェアのモデル検査ツールの１つであるSPINの本を読みました。
モデル検査というのは、ソフトウェアの仕様や設計をモデル化して、
そのモデルが所望の性質を満たすかどうかを検査しましょうという話題です。
たとえば２つのプロセスが並列に走るときにデッドロックにならないかどうか、とか、
クライアントがサーバーにAを送ったら必ずBが返ってくる仕様になっているはず、とか
そういうことを検査します。
そしてこういった条件は多くの場合、時相論理で記述します。
大学で数理論理学をやっていながらモデル検査はほぼノータッチでしたが、
実際に時相論理がどう使われているのか前から気になっていたので、今回本を読んでみました。
前置きが長い！
SPINでは、検査対象のモデルを専用言語Promelaで記述し、
検査したい条件を線形時相論理(LTL)で記述します。
このPromelaはとっつきやすいようにCっぽい言語になっていて、
さらにLTLの論理記号も&&, ||, ! のようなC言語の論理記号を用いるので、
ちょっと油断していると普通にCでコーディングしているように見えてきます。
仕様や設計のモデルを検査しようとしたらなぜかコーディングが始まってしまった、となりそうです。
ですが、実際に動いている仕組みはCとは完全に別世界です。
Promelaで記述したモデルは非決定性有限オートマトンに変換されて、
さらにLTLの論理式もオートマトンに変換されて、両方の充足可能性がガンガン探索されます。
力技です。
このオートマトンはすべての変数の値とすべてのプログラムカウンタが指す位置をセットにして１つのノードを作るので、
Promelaの記述を少しでも油断すると簡単に状態爆発します。
すごい世界です。
なので、検査したい性質に関係ない変数や要素は極力省いて、シンプルなモデルを心がける必要があります。
そうは言っても、世の中の特にリアルタイム系のシステムは大抵思わぬところが思わぬところに影響して不具合が出るので、
モデル化の際に何を盛り込んで何を盛り込まないかはすごく難しそうです。
さて、SPINの話ばかりで全く本の話をしていませんでした。
本書はこういったSPINの全体像の説明を基礎からしてくれるいい本です。
タイトルからはツールの使い方の本のような印象を受けますが、
時相論理、オートマトン、非決定性、果てはNP問題まで、
いろんな概念の説明を丁寧にしてくれるので、半分教科書のような雰囲気があります。
かと思えばハッシュテーブルの大きさの調整や半順序簡約などの最適化の話題もあって、実用書的な雰囲気もあります。
あとこの手の本にしては翻訳がすごく読みやすいので、著者が日本人でないことを忘れそうになります。
特に非決定性のところはPromelaとC言語の違いのキモなので、
繰り返ししつこく説明されていてとてもよかったです。
- 2017/02/01(水) 00:00:18|
- 本
-
| トラックバック：0
-
| コメント：0
<<
SPINモデル検査 検証モデリング技法 [中島震(著)] (近代科学者) |
ホーム |
パーフェクトC# 改訂3版 [斎藤友雄, 醍醐竜一(著)] (技術評論社)>>
- トラックバックURLはこちら
- http://myumbrella.blog42.fc2.com/tb.php/346-2d93a9f7
- この記事にトラックバックする(FC2ブログユーザー)
プロフィール
わ
カテゴリ
最近の日記
アーカイヴ
リンク
ブログ内検索
