Fork: 0
nitta-lab / SpecificationSimulatorExperiments
Transfer to URL with SHA Find file
Newer
Older
SpecificationSimulatorExperiments / courseA / Alloy.html
Naoya Nitta on 31 Aug 14 KB Alloy の概要説明を書き終えました．
Raw Blame History 
  1. <!DOCTYPE html>
  2. <html lang="ja" xmlns="http://www.w3.org/1999/html">
  3. <head>
  4.     <meta charset="UTF-8">
  5.     <style>
  6.         c1{
  7.             color: blue;
  8.         }
  9.         c2{
  10.             color: red;
  11.         }
  12.     </style>
  13.     <title>【Alloyの説明】</title>
  14. </head>
  15. <body>
  16. <h1>【Alloy の概要説明】</h1>
  17. <p>
  18.     本実験で用いる Alloy の概要について説明します．<br>
  19.     現時点で本ページの内容を完全に理解する必要はありません．課題に取り組む際に必要に応じて本ページを参照しながら進めるようにください．<br>
  20. </p>
  21. <hr/>
  22. <h2>形式的仕様記述言語とは？</h2>
  23. <p>
  24.     Alloy は代表的な形式的仕様記述言語の一つです．<br>
  25.     形式的仕様記述言語とは，仕様を自然言語ではなく，論理式のような数学的に厳密に意味が定義された形式で記述する方法で，<br>
  26.     <ul>
  27.     <li>仕様を曖昧性なく厳密に記述することができる，</li>
  28.     <li>プログラミング言語よりも高い抽象度でシステムの振る舞いを記述することができる，</li>
  29.     <li>記述した仕様を仮想的に実行したり，コンピュータを用いて解析を行うことができる</li>
  30.     </ul>
  31.     といった特長を持っています．<br>
  32.     コンピュータによる仕様の解析としては，仕様レベルで不具合が存在しないかを網羅的に調べたり，セキュリティホールが存在しないことを確認することなどが挙げられます．<br>
  33.     形式的仕様記述言語による記述は，通常のプログラミング言語におけるソースコードの記述とはかなり異なっております．そのため，最初に形式的な仕様記述を見ると少々戸惑うかもしれません．<br>
  34.     一般的に形式的仕様記述言語の表現能力はプログラミング言語よりも低く，表現能力が低くなればなるほど複雑な振る舞いが記述できなくなる一方で，強力な解析ができるといった関係が成り立っています．<br>
  35. </p>
  36. <hr/>
  37. <h2>Alloy とは？</h2>
  38. <p>
  39.     Alloy は形式的仕様記述言語としては比較的表現能力が高いため，完全に網羅的な解析はできませんが，実用性を大きく損なわない範囲で網羅性を制限した解析を行うことができるといった特長があります．<br>
  40.     本実験では，Alloy による仕様記述と仕様の仮想実行に着目していきます．そのため，Alloy による仕様の解析は行いません．また，Alloy のツールをPCにダウンロードして操作していただく必要もありません．<br>
  41. </p>
  42. <h3>Alloyによる仕様記述:</h3>
  43. <p>
  44.     Alloy では，集合と関係を中心に仕様を記述していきます．また，その記述は宣言的な形式で行われます．<br>
  45.     宣言的記述の対義語は手続き的記述です．我々が通常用いるプログラミング言語では手続き的な記述が用いられています．手続き的な記述ではプログラムは基本的に一番上の行から順番に一行ずつ,
  46.     記述された順に実行されていきます．<br>
  47.     一方宣言的な記述では，記述の順序は関係ありません．すべての行が同時に成り立っていると考えます．連立方程式を考えてみると解りやすいと思います．
  48.     連立方程式では，すべての式が同時に成り立っているため，式の記述順に関係なく同じ解が得られます．そのため，宣言的記述には基本的に時間の経過が存在しません．実行の初期状態から最終状態までのすべての状態が同時に存在していることになります．<br>
  49.     Alloy の概念的な説明はこれくらいにして，具体的に Alloy の記述を見ていきましょう．
  50. </p>
  51. <hr/>
  52. <h2>Alloy による仕様記述の例</h2>
  53. <h3>例題仕様:</h3>
  54. <p>
  55.     簡単なアドレス帳の仕様を Alloy で記述することを考えます．
  56.     アドレス帳の仕様は次の通りです．
  57.     <ul>
  58.     <li>システムはアドレス帳を1つ持つ．</li>
  59.     <li>アドレス帳には所有者の名前が記載されている．</li>
  60.     <li>アドレス帳には連絡先の名前とアドレスの対応を任意個登録することができる．</li>
  61.     <li>アドレス帳において連絡先の名前が重複してはならない．</li>
  62.     <li>アドレス帳は連絡先の名前とアドレスの対応が1つも登録されていない状態を初期状態とする．</li>
  63.     <li>add 操作によって，指定した名前と指定したアドレスの対応をアドレス帳に登録することができる．</li>
  64.     <li>del 操作によって，指定した名前と対応するアドレスをアドレス帳から削除することができる．</li>
  65.     </ul>
  66. </p>
  67. <h3>Alloy による記述例:</h3>
  68. <p>
  69.     以下の仕様記述では名前の集合を <code>Name</code>，アドレスの集合を <code>Addr</code>，アドレス帳の集合を <code>Book</code> で表しています．<br>
  70.     <c1>sig</c1> でこれらの集合を宣言しています．ここで集合はクラス，集合に属している各要素はインスタンスに相当すると考えてください．ただし，Alloy は宣言型の言語なので，インスタンスの状態を変えることができません．状態の変更前と変更後でインスタンスが異なると考えてください．<br>
  71.     <code>Book</code> は，2つのフィールド <code>owner</code> と <code>addr</code> を持っています．Alloy におけるフィールドは，インスタンスの内部構造を表すものではなく，基本的に2つの集合の要素間の関係を表しています．たとえば <code>Book</code> の <code>owner</code> フィールドは，<code>Book</code> の各要素に <code>Name</code> の要素を対応づける関係を表しています．フィールドの詳細な意味については後ほど説明します．<br>
  72. </p>
  73. <p>
  74.     Alloy では，操作も関係で表されます．たとえば add 操作は，連絡先を登録する前の <code>Book</code> の状態と，登録した後の <code>Book</code> の状態の間の関係を表していると考えます．<br>
  75.     より具体的には <c1>pred</c1> を用いて，登録前の <code>Book</code> の状態 <code>b</code>，登録後の <code>Book</code> の状態 <code>b'</code>，登録する連絡先の名前 <code>n</code>，登録するアドレス <code>a</code> の間に成り立つ述語として定義されています．<br>
  76.     述語の本体は 1つ以上の式によって構成されます．これらの式は変数間に成り立つ制約関係を表しているため記述順は関係ありません．たとえば，<code>b'.owner = b.owner</code> は，add 操作前の <code>Book</code> の <code>owner</code> と，add 操作後の <code>Book</code> の <code>owner</code> が同じであることを示しています．
  77.     <code>b'.addr = b.addr + n -> a</code> は，add 操作前の <code>Book</code> の <code>addr</code> （<code>Book</code> の各インスタンスが持つ，名前とアドレスの対応表）に，名前 <code>n</code> とアドレス <code>a</code> の対応を付け足したものが，add 操作後の <code>Book</code> の <code>addr</code> になることを示しています．これらの式は順番を入れ替えても意味は変わりません．
  78. </p>
  79. <p>
  80.     実行は，<c1>run</c1> で指定された述語を呼び出すことによってなされます．ここでは，<code>execute</code> という引数を持たない述語が呼び出されます．<br>
  81.     <code>execute</code> の本体については，いくつか説明が必要です．<br>
  82.     まず，この <code>execute</code> 本体は，1つの論理式で構成されています．一見，4つの論理式が列挙されているように思いますが，全体として論立式は1つです．<br>
  83.     ポイントは存在限量子 <c1>some</c1> です．<c1>some</c1> は，後ろに並んだ変数の値のある組み合わせにおいて，<code>|</code> の後ろに記載された論理式が成り立つということを示しています．似たようなものに <c1>all</c1> と <c1>no</c1> があります．
  84.     <c1>all</c1> は，後ろに並んだ変数の値の任意の組み合わせにおいて，<code>|</code> の後ろの論理式が成り立つということを，<c1>no</c1> は，後ろに並んだ変数の値のどんな組み合わせにおいても，<code>|</code> の後ろの論理式が成り立たないことを示します．<br>
  85.     ここでは，<code>b0, b1, b2, b3</code> という <code>Book</code> のインスタンスのある組み合わせにおいて（<c1>disj</c1> がついているのでこれら4つのインスタンスは互いに異なります），また，<code>n0, n1, n2</code> という <code>Name</code> の互いに異なる3つのインスタンスのある組み合わせについて，
  86.     さらに，<code>a0, a1</code> という <code>Addr</code> の互いに異ならなくてもよいインスタンスのある組み合わせについて，<code>|</code> 以下の論理式が成り立っていることを示しています．<code>|</code> 以下の論理式は <code>{</code> と <code>}</code> で囲まれている4つの論理式をまとめたもの，すなわち4つの論理式が同時に成り立っていることを示す1つの論理式になります．<br>
  87.     この4つの論理式も同時に成り立っているので，記述の順序を変えても意味は変わらないのですが，しかし，実行において最初に init 操作が呼ばれて，次に add 操作が2回呼ばれ，最後に del 操作が呼ばれることを表しています．
  88.     詳細は後ほど説明しますが，これには，<code>Book</code> の4つのインスタンスが関係しています．まず初期化の操作 init に関わるのは <code>b0</code> です．次に，最初の add 操作は，<code>b0</code> を <code>b1</code> に変更します．
  89.     さらに，次の add 操作は，<code>b1</code> を <code>b2</code> に，最後の del 操作は <code>b2</code> を <code>b3</code> に変更します．このようにインスタンス（の状態）を受け渡すことによって，実行が進んでいくことを表すことができます．
  90. </p>
  91. <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333; border-radius: 10px;">
  92. 	<pre>
  93. <c1>sig</c1> Name, Addr {}
  94. <c1>sig</c1> Book {
  95. 	owner: Name,
  96. 	addr: Name -> <c1>lone</c1> Addr
  97. }
  98.  
  99. <c1>pred</c1> init[b: Book, n: Name] {
  100. 	b.owner = n
  101. 	<c1>no</c1> b.addr
  102. }
  103.  
  104. <c1>pred</c1> add[b, b': Book, n: Name, a: Addr] {
  105. 	b'.owner = b.owner
  106. 	b'.addr = b.addr + n -> a
  107. }
  108.  
  109. <c1>pred</c1> del[b, b': Book, n: Name] {
  110. 	b'.owner = b.owner
  111. 	b'.addr = b.addr - n -> b.addr[n]
  112. }
  113.  
  114. <c1>pred</c1> execute[] {
  115. 	<c1>some</c1> <c1>disj</c1> b0, b1, b2, b3: Book, <c1>disj</c1> n0, n1, n2: Name, a0, a1: Addr | {
  116. 		init[b0, n0]
  117. 		add[b0, b1, n1, a0]
  118. 		add[b1, b2, n2, a1]
  119. 		del[b2, b3, n1]
  120. 	}
  121. }
  122.  
  123. <c1>run</c1> execute <c1>for</c1> <c2>2</c2> <c1>but</c1> <c2>4</c2> Book, <c2>3</c2> Name
  124. 	</pre>
  125. </div>
  126. <h3>実行の可視化:</h3>
  127. <p>
  128.     Alloy では実行を可視化することができます．上の仕様記述内の <c1>run</c1> による実行を可視化したものが以下の図です．
  129. </p>
  130. <div class="img-center">
  131.     <img src="../img/Alloy/AlloySample.png" class ="before-image-size"><br>
  132. </div>
  133. <p>
  134.     可視化では実行時に生成される1つのインスタンスが，1つの矩形で表されます．たとえば，図の上部に並んでいる4つの矩形は，<code>execute</code> 述語内で宣言されている4つの変数，<code>b0, b1, b2, b3</code>に対応しています．
  135.     矩形内部には，そのインスタンスが所属しているクラス名とインスタンスのIDが記されています．また，括弧の中にはそのインスタンスを参照している変数名が記されています．<br>
  136.     <code>Book</code> のインスタンスは4つありますが，これは手続き型プログラムで考えると <code>Book</code> の1つのインスタンスの状態が3回変わったことに相当しています．
  137.     <code>Book</code> の初期化後の状態が <code>Book3</code>，最初の add 操作後の状態が <code>Book2</code>，次の add 操作後の状態が <code>Book1</code>，最後の del 操作後の状態が <code>Book0</code> に当たります．
  138.     Alloy は宣言型言語なので，これらは順番に生成されるというわけではなく，最初から同時に存在しています．<br>
  139. </p>
  140. <p>
  141.     <code>Book</code> の <code>owner</code> フィールドは，<code>Book</code> の要素と，<code>Name</code> の要素の間の関係として定義されます．
  142.     <code>Book</code> のインスタンスを1つ指定すれば，<code>owner</code>フィールドを使って <code>b.owner</code> のように <code>Name</code> のインスタンスを1つ取ってくることができるためです．
  143.     この図では，<code>Book</code> のどのインスタンスも同じ <code>Name</code> のインスタンスを参照しています．これは，この実行における <code>Book</code> の状態の変化では，<code>owner</code> が変わらないためです．<br>
  144. </p>
  145. <p>
  146.     <code>addr</code> フィールドは少し複雑です．この仕様では <code>addr</code> フィールドは，<code>addr: Name -> <c1>lone</c1> Addr</code> のように定義されています．
  147.     これは，<code>addr</code> フィールドが <code>Name</code> から <code>Addr</code> への対応関係を参照していることを表しています．
  148.     ここで，<c1>lone</c1> の記述は <code>Name</code> の各要素に対して，対応する <code>Addr</code> がたかだか1つ（0個か1個）であることを示しています．<br>
  149.     たとえば，<code>Book2</code> を見ると，<code>addr</code> は <code>Name1</code> に <code>Addr1</code> を対応させていることがわかります．
  150.     一方，<code>Name0</code> に対応する <code>Addr</code> の要素は存在していません．<code>Book1</code> では add 操作によって，新たに <code>Name0</code> から <code>Addr0</code> への対応が追加されています．
  151.     さらに <code>Book0</code> ではadd 操作によって，<code>Name1</code> から <code>Addr1</code> への対応が削除されています．<br>
  152. </p>
  153. <p>
  154.     Alloy ではこのようにして実行が可視化されます．
  155. </p>
  156. <hr/>
  157. <br>
  158. <a href="DTRAM.html">【DTRAM の概要説明】へ</a>
  159.  
  160. </body>
  161. </html>