|
103
|
1 <!DOCTYPE html>
|
|
|
2 <html>
|
|
|
3 <head>
|
|
|
4 <meta http-equiv="content-type" content="text/html;charset=utf-8">
|
|
|
5 <title>メタ計算を用いた Continuation based C の検証手法</title>
|
|
|
6
|
|
|
7 <meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 2.3.3 (2016-11-21) [x86_64-darwin16]">
|
|
|
8 <meta name="author" content="Yasutaka Higa" >
|
|
|
9
|
|
|
10 <!-- style sheet links -->
|
|
|
11 <link rel="stylesheet" href="s6/themes/screen.css" media="screen">
|
|
|
12 <link rel="stylesheet" href="s6/themes/print.css" media="print">
|
|
|
13 <link rel="stylesheet" href="s6/themes/blank.css" media="screen,projection">
|
|
|
14
|
|
|
15 <!-- JS -->
|
|
|
16 <script src="s6/js/jquery-1.11.3.min.js"></script>
|
|
|
17 <script src="s6/js/jquery.slideshow.js"></script>
|
|
|
18 <script src="s6/js/jquery.slideshow.counter.js"></script>
|
|
|
19 <script src="s6/js/jquery.slideshow.controls.js"></script>
|
|
|
20 <script src="s6/js/jquery.slideshow.footer.js"></script>
|
|
|
21 <script src="s6/js/jquery.slideshow.autoplay.js"></script>
|
|
|
22
|
|
|
23 <!-- prettify -->
|
|
|
24 <link rel="stylesheet" href="scripts/prettify.css">
|
|
|
25 <script src="scripts/prettify.js"></script>
|
|
|
26
|
|
|
27 <style>
|
|
|
28 .slide {page-break-after: always;}
|
|
|
29 </style>
|
|
|
30
|
|
|
31
|
|
|
32
|
|
|
33
|
|
|
34 </head>
|
|
|
35 <body>
|
|
|
36
|
|
|
37 <div class="layout">
|
|
|
38 <div id="header"></div>
|
|
|
39 <div id="footer">
|
|
|
40 <div align="right">
|
|
|
41 <img src="s6/images/logo.svg" width="200px">
|
|
|
42 </div>
|
|
|
43 </div>
|
|
|
44 </div>
|
|
|
45
|
|
|
46 <div class="presentation">
|
|
|
47
|
|
|
48 <div class='slide cover'>
|
|
|
49 <table width="90%" height="90%" border="0" align="center">
|
|
|
50 <tr>
|
|
|
51 <td>
|
|
|
52 <div align="center">
|
|
|
53 <h1><font color="#808db5">メタ計算を用いた Continuation based C の検証手法</font></h1>
|
|
|
54 </div>
|
|
|
55 </td>
|
|
|
56 </tr>
|
|
|
57 <tr>
|
|
|
58 <td>
|
|
|
59 <div align="left">
|
|
|
60 Yasutaka Higa
|
|
|
61
|
|
|
62 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;">
|
|
|
63 </div>
|
|
|
64 </td>
|
|
|
65 </tr>
|
|
|
66 </table>
|
|
|
67 </div>
|
|
|
68
|
|
|
69 <div class='slide '>
|
|
|
70 <!-- === begin markdown block ===
|
|
|
71
|
|
|
72 generated by markdown/1.2.0 on Ruby 2.3.3 (2016-11-21) [x86_64-darwin16]
|
|
|
73 on 2017-02-12 18:10:22 +0900 with Markdown engine kramdown (1.13.0)
|
|
|
74 using options {}
|
|
|
75 -->
|
|
|
76
|
|
|
77 <!-- _S9SLIDE_ -->
|
|
|
78 <h1 id="section">プログラミング言語とソフトウェアの信頼性</h1>
|
|
|
79 <ul>
|
|
|
80 <li>信頼性の高いソフトウェアを提供したい</li>
|
|
|
81 <li>ソフトウェアの仕様を検証するには二つの手法がある
|
|
|
82 <ul>
|
|
|
83 <li>プログラムの持つ状態を数え上げ、仕様から外れた状態が無いかを確認するモデル検査</li>
|
|
|
84 <li>プログラムの性質を直接証明してしまう定理証明</li>
|
|
|
85 </ul>
|
|
|
86 </li>
|
|
|
87 <li>モデル検査も証明も行ないやすい言語として Continuation based C 言語を開発している</li>
|
|
|
88 </ul>
|
|
|
89
|
|
|
90
|
|
|
91 </div>
|
|
|
92 <div class='slide '>
|
|
|
93 <!-- _S9SLIDE_ -->
|
|
|
94 <h1 id="section-1">二つのアプローチを用いたソフトウェア検証</h1>
|
|
|
95 <ul>
|
|
|
96 <li>モデル検査的アプローチ
|
|
|
97 <ul>
|
|
|
98 <li>メタ計算ライブラリ akasha による網羅的な実行</li>
|
|
|
99 <li>非破壊赤黒木の仕様定義と検証</li>
|
|
|
100 </ul>
|
|
|
101 </li>
|
|
|
102 <li>定理証明的なアプローチ
|
|
|
103 <ul>
|
|
|
104 <li>依存型を持つ証明支援系言語 Agda による CbC の証明</li>
|
|
|
105 <li>部分型を利用して Agda 上に型付きの CbC の項を記述する</li>
|
|
|
106 <li>型システムを通して CbC の形式的な定義を得る</li>
|
|
|
107 <li>SingleLinkedStack の性質の証明</li>
|
|
|
108 </ul>
|
|
|
109 </li>
|
|
|
110 </ul>
|
|
|
111
|
|
|
112
|
|
|
113 </div>
|
|
|
114 <div class='slide '>
|
|
|
115 <!-- _S9SLIDE_ -->
|
|
|
116 <h1 id="continuation-based-c">Continuation based C</h1>
|
|
|
117 <ul>
|
|
|
118 <li>当研究室で開発しているプログラミング言語</li>
|
|
|
119 <li>アセンブラとC言語の中間のような言語であり、構文はほとんど C 言語</li>
|
|
|
120 <li>OS や組み込みソフトウェアなどを対象にしている</li>
|
|
|
121 <li>CodeSegment と DataSegment という単位を用いてプログラミングする</li>
|
|
|
122 </ul>
|
|
|
123
|
|
|
124
|
|
|
125 </div>
|
|
|
126 <div class='slide '>
|
|
|
127 <!-- _S9SLIDE_ -->
|
|
|
128 <h1 id="codesegment">CodeSegment</h1>
|
|
|
129 <ul>
|
|
|
130 <li>CodeSegment とは
|
|
|
131 <ul>
|
|
|
132 <li>処理の単位</li>
|
|
|
133 <li>結合や分割が容易</li>
|
|
|
134 <li>入力と出力を持つ</li>
|
|
|
135 </ul>
|
|
|
136 </li>
|
|
|
137 <li>CodeSegment どうしを接続することによりプログラム全体を作る</li>
|
|
|
138 <li>TODO: 図</li>
|
|
|
139 </ul>
|
|
|
140
|
|
|
141
|
|
|
142 </div>
|
|
|
143 <div class='slide '>
|
|
|
144 <!-- _S9SLIDE_ -->
|
|
|
145 <h1 id="datasegment">DataSegment</h1>
|
|
|
146 <ul>
|
|
|
147 <li>DataSegment とは
|
|
|
148 <ul>
|
|
|
149 <li>データの単位</li>
|
|
|
150 <li>CodeSegment の入出力にあたる</li>
|
|
|
151 <li>接続元の Output DataSegment は接続先の Input DataSegment</li>
|
|
|
152 </ul>
|
|
|
153 </li>
|
|
|
154 <li>TODO: 図</li>
|
|
|
155 </ul>
|
|
|
156
|
|
|
157
|
|
|
158 </div>
|
|
|
159 <div class='slide '>
|
|
|
160 <!-- _S9SLIDE_ -->
|
|
|
161 <h1 id="section-2">メタ計算</h1>
|
|
|
162 <ul>
|
|
|
163 <li>とある計算を実現するための計算</li>
|
|
|
164 <li>ネットワーク接続、例外処理、メモリ確保、並列処理など</li>
|
|
|
165 <li>時に本来行ないたい処理よりも複雑になる</li>
|
|
|
166 <li>CbC は通常レベルの計算とメタ計算を分離して考える
|
|
|
167 <ul>
|
|
|
168 <li>通常レベルではポインタは出てこない、など</li>
|
|
|
169 </ul>
|
|
|
170 </li>
|
|
|
171 <li>TODO: 図</li>
|
|
|
172 </ul>
|
|
|
173
|
|
|
174
|
|
|
175 </div>
|
|
|
176 <div class='slide '>
|
|
|
177 <!-- _S9SLIDE_ -->
|
|
|
178 <h1 id="meta-codesegment">Meta CodeSegment</h1>
|
|
|
179 <ul>
|
|
|
180 <li>メタ計算を行なう CodeSegment</li>
|
|
|
181 <li>通常の CodeSegment どうしの接続の間に入る</li>
|
|
|
182 <li>TODO: 図</li>
|
|
|
183 </ul>
|
|
|
184
|
|
|
185
|
|
|
186 </div>
|
|
|
187 <div class='slide '>
|
|
|
188 <!-- _S9SLIDE_ -->
|
|
|
189 <h1 id="meta-datasegment">Meta DataSegment</h1>
|
|
|
190 <ul>
|
|
|
191 <li>メタ計算用の DataSegment</li>
|
|
|
192 <li>通常の DataSegment を含むような DataSegment</li>
|
|
|
193 <li>TODO: 図</li>
|
|
|
194 </ul>
|
|
|
195
|
|
|
196
|
|
|
197 </div>
|
|
|
198 <div class='slide '>
|
|
|
199 <!-- _S9SLIDE_ -->
|
|
|
200 <h1 id="c">C言語との対応</h1>
|
|
|
201 <ul>
|
|
|
202 <li>CodeSegment は C 言語における返り値の無い関数</li>
|
|
|
203 <li>DataSegment は C 言語における構造体</li>
|
|
|
204 <li>Meta CodeSegment は CodeSegment の前後にある CodeSegment</li>
|
|
|
205 <li>Meta DataSegment は全ての DataSegment の共用体を持つ構造体</li>
|
|
|
206 <li>CodeSegment の接続は goto における軽量継続
|
|
|
207 <ul>
|
|
|
208 <li>末尾のみで行なうスタックを保持しない関数呼び出し</li>
|
|
|
209 </ul>
|
|
|
210 </li>
|
|
|
211 </ul>
|
|
|
212
|
|
|
213
|
|
|
214 </div>
|
|
|
215 <div class='slide '>
|
|
|
216 <!-- _S9SLIDE_ -->
|
|
|
217 <h1 id="gearsos">並列に信頼性高く動作する GearsOS</h1>
|
|
|
218 <ul>
|
|
|
219 <li>CbC を用いたメタ計算の例として本研究室で開発している GearsOS がある</li>
|
|
|
220 <li>並列実行やモデル検査をメタ計算として提供する</li>
|
|
|
221 <li>現在はメモリ管理、Synchronized Queue、非破壊赤黒木などが実装済み</li>
|
|
|
222 <li>今回はこの非破壊赤黒木の検証を行なう</li>
|
|
|
223 </ul>
|
|
|
224
|
|
|
225
|
|
|
226 </div>
|
|
|
227 <div class='slide '>
|
|
|
228 <!-- _S9SLIDE_ -->
|
|
|
229 <h1 id="section-3">赤黒木</h1>
|
|
|
230 <ul>
|
|
|
231 <li>データの保存に用いる二分木</li>
|
|
|
232 <li>特に赤黒木はノードが持つ赤か黒の色を使って木のバランスを取る
|
|
|
233 <ul>
|
|
|
234 <li>ルートノードと葉ノードの色は黒</li>
|
|
|
235 <li>赤ノードは2つの黒ノードを子として持つ(よって赤ノードが続くことは無い)</li>
|
|
|
236 <li>ルートから最下位ノードへの経路に含まれる黒ノードの数はどの最下位ノードでも一定</li>
|
|
|
237 </ul>
|
|
|
238 </li>
|
|
|
239 <li>TODO: 図</li>
|
|
|
240 </ul>
|
|
|
241
|
|
|
242
|
|
|
243 </div>
|
|
|
244 <div class='slide '>
|
|
|
245 <!-- _S9SLIDE_ -->
|
|
|
246 <h1 id="gearsos-">GearsOS における赤黒木の利用例(ノードの挿入)</h1>
|
|
|
247 <ul>
|
|
|
248 <li>挿入したい要素を DataSegment に格納して次の CodeSegment へ goto</li>
|
|
|
249 <li>goto する前に Meta CodeSegment が実行されて木に挿入する</li>
|
|
|
250 <li>GearsOS では木の実装のためにスタックを用いて経路情報を保持している</li>
|
|
|
251 <li>TODO: 図</li>
|
|
|
252 </ul>
|
|
|
253
|
|
|
254
|
|
|
255 </div>
|
|
|
256 <div class='slide '>
|
|
|
257 <!-- _S9SLIDE_ -->
|
|
|
258 <h1 id="section-4">仕様の記述とその確認</h1>
|
|
|
259 <ul>
|
|
|
260 <li>「バランスが取れている」とは何かを表現できる必要がある
|
|
|
261 <ul>
|
|
|
262 <li>実行可能な CbC の式を使った assert になる</li>
|
|
|
263 </ul>
|
|
|
264 </li>
|
|
|
265 <li>そしてそれを保証したい
|
|
|
266 <ul>
|
|
|
267 <li>プログラムの全ての状態においてこれは常に成り立つのか?</li>
|
|
|
268 </ul>
|
|
|
269 </li>
|
|
|
270 </ul>
|
|
|
271
|
|
|
272
|
|
|
273 </div>
|
|
|
274 <div class='slide '>
|
|
|
275 <!-- _S9SLIDE_ -->
|
|
|
276 <h1 id="spin">既存のモデル検査器 spin</h1>
|
|
|
277 <ul>
|
|
|
278 <li>spin
|
|
|
279 <ul>
|
|
|
280 <li>promela と呼ばれる言語でプログラムを記述</li>
|
|
|
281 <li>並列に動作するプログラムの仕様を検証可能</li>
|
|
|
282 <li>検証した promela から実行可能な C ソースを生成可能</li>
|
|
|
283 <li>仕様は bool になる式を用いた assert</li>
|
|
|
284 <li>promela は C とは記述が異なる</li>
|
|
|
285 </ul>
|
|
|
286 </li>
|
|
|
287 </ul>
|
|
|
288
|
|
|
289
|
|
|
290 </div>
|
|
|
291 <div class='slide '>
|
|
|
292 <!-- _S9SLIDE_ -->
|
|
|
293 <h1 id="cbmc">既存のモデル検査器 CBMC</h1>
|
|
|
294 <ul>
|
|
|
295 <li>CBMC
|
|
|
296 <ul>
|
|
|
297 <li>検証対象のCソースを変更しないでも良い</li>
|
|
|
298 <li>C/C++ 言語の記号実行が可能
|
|
|
299 <ul>
|
|
|
300 <li>条件分岐を網羅的に実行</li>
|
|
|
301 </ul>
|
|
|
302 </li>
|
|
|
303 <li>仕様は bool になる式を用いた assert</li>
|
|
|
304 <li>有限ステップ検証する有界モデル検査器</li>
|
|
|
305 </ul>
|
|
|
306 </li>
|
|
|
307 </ul>
|
|
|
308
|
|
|
309
|
|
|
310 </div>
|
|
|
311 <div class='slide '>
|
|
|
312 <!-- _S9SLIDE_ -->
|
|
|
313 <h1 id="akasha">メタ計算ライブラリ akasha</h1>
|
|
|
314 <ul>
|
|
|
315 <li>メタ計算としてプログラムの状態を数え上げる</li>
|
|
|
316 <li>goto された時に挿入される要素の組み合わせを全て列挙して実行する</li>
|
|
|
317 <li>その度に仕様の式は成り立つかをチェックする</li>
|
|
|
318 <li>TODO: 図</li>
|
|
|
319 </ul>
|
|
|
320
|
|
|
321
|
|
|
322 </div>
|
|
|
323 <div class='slide '>
|
|
|
324 <!-- _S9SLIDE_ -->
|
|
|
325 <h1 id="section-5">チェックする仕様</h1>
|
|
|
326 <ul>
|
|
|
327 <li>TODO: たかさについて</li>
|
|
|
328 </ul>
|
|
|
329
|
|
|
330
|
|
|
331 </div>
|
|
|
332 <div class='slide '>
|
|
|
333 <!-- _S9SLIDE_ -->
|
|
|
334 <h1 id="akasha--cbmc-">akasha と CBMC の比較</h1>
|
|
|
335 <ul>
|
|
|
336 <li>akasha は有限の要素数の組み合わせをチェックする
|
|
|
337 <ul>
|
|
|
338 <li>要素数が13個までならどの順で木に挿入しても良い</li>
|
|
|
339 </ul>
|
|
|
340 </li>
|
|
|
341 <li>比較対象として C Bounded Model Checker を使用した
|
|
|
342 <ul>
|
|
|
343 <li>C/C++ の記号実行を行なう</li>
|
|
|
344 <li>実行可能なステップ数411だけ展開しても仕様は満たされる</li>
|
|
|
345 <li>が、恣意的にバグを入れ込んでも反例を返さない</li>
|
|
|
346 <li>akasha は返した</li>
|
|
|
347 </ul>
|
|
|
348 </li>
|
|
|
349 <li>固定の要素数までの仕様検査で十分なのか?</li>
|
|
|
350 </ul>
|
|
|
351
|
|
|
352
|
|
|
353 </div>
|
|
|
354 <div class='slide '>
|
|
|
355 <!-- _S9SLIDE_ -->
|
|
|
356 <h1 id="section-6">定理証明</h1>
|
|
|
357 <ul>
|
|
|
358 <li>任意の回数だけ木の操作を行なっても大丈夫なことを保証したい</li>
|
|
|
359 <li>そのままプログラムの性質を保証してやる</li>
|
|
|
360 <li>プログラムと証明は Curry-Howard Isomorphism により、自然演繹と型付ラムダ計算が対応
|
|
|
361 <ul>
|
|
|
362 <li>プログラムにおける命題は型であり、証明はその導出が存在するかどうか</li>
|
|
|
363 <li>例えば三段論法が書ける
|
|
|
364 <ul>
|
|
|
365 <li>(A -> B) -> (B -> C) -> (A -> C)</li>
|
|
|
366 <li>(int -> bool) -> (bool -> float) -> (int -> float)</li>
|
|
|
367 </ul>
|
|
|
368 </li>
|
|
|
369 </ul>
|
|
|
370 </li>
|
|
|
371 </ul>
|
|
|
372
|
|
|
373
|
|
|
374 </div>
|
|
|
375 <div class='slide '>
|
|
|
376 <!-- _S9SLIDE_ -->
|
|
|
377 <h1 id="agda">証明支援系 Agda</h1>
|
|
|
378 <ul>
|
|
|
379 <li>依存型を持つ言語
|
|
|
380 <ul>
|
|
|
381 <li>型が第一級(型が値である)</li>
|
|
|
382 <li>「型を取って型を返す型」などが定義可能</li>
|
|
|
383 </ul>
|
|
|
384 </li>
|
|
|
385 <li>定理証明が記述可能
|
|
|
386 <ul>
|
|
|
387 <li>この言語の上に CbC の項を表現する</li>
|
|
|
388 <li>Agda 経由で CbC の形式的な定義を得る</li>
|
|
|
389 </ul>
|
|
|
390 </li>
|
|
|
391 </ul>
|
|
|
392
|
|
|
393
|
|
|
394 </div>
|
|
|
395 <div class='slide '>
|
|
|
396 <!-- _S9SLIDE_ -->
|
|
|
397 <h1 id="agda--cbc-">Agda 上に CbC を記述するには?</h1>
|
|
|
398 <ul>
|
|
|
399 <li>CbC と CbC の対応で書ける?
|
|
|
400 <ul>
|
|
|
401 <li>DataSegment -> 構造体(複数の値と名前によって成り立つ)</li>
|
|
|
402 <li>CodeSegment -> 関数型(型を取って型を返す)</li>
|
|
|
403 <li>Meta DataSegment -> 構造体の共用体</li>
|
|
|
404 <li>Meta CodeSegment -> 関数型?</li>
|
|
|
405 </ul>
|
|
|
406 </li>
|
|
|
407 <li>Meta CodeSegment の階層構造をどう定義するか
|
|
|
408 <ul>
|
|
|
409 <li>構造体に相当するレコード型はAgdaにある</li>
|
|
|
410 <li>共用体に相当する直和型も定義可能</li>
|
|
|
411 </ul>
|
|
|
412 </li>
|
|
|
413 </ul>
|
|
|
414
|
|
|
415
|
|
|
416 </div>
|
|
|
417 <div class='slide '>
|
|
|
418 <!-- _S9SLIDE_ -->
|
|
|
419 <h1 id="section-7">メタレベルの型付け</h1>
|
|
|
420 <ul>
|
|
|
421 <li>Meta CodeSegment が持っているべき性質
|
|
|
422 <ul>
|
|
|
423 <li>メタレベルは階層構造を持つ
|
|
|
424 <ul>
|
|
|
425 <li>メタ計算は組み合わせられる</li>
|
|
|
426 </ul>
|
|
|
427 </li>
|
|
|
428 <li>ノーマルレベルの DataSegment を一様に扱える</li>
|
|
|
429 <li>ノーマルレベルの CodeSegment へと goto できる
|
|
|
430 <ul>
|
|
|
431 <li>どんなプログラムからもライブラリとして使える</li>
|
|
|
432 </ul>
|
|
|
433 </li>
|
|
|
434 </ul>
|
|
|
435 </li>
|
|
|
436 <li>構造体では融通が効かない
|
|
|
437 <ul>
|
|
|
438 <li>完全にマッチしなくてはいけない</li>
|
|
|
439 </ul>
|
|
|
440 </li>
|
|
|
441 <li>TODO: ソース</li>
|
|
|
442 </ul>
|
|
|
443
|
|
|
444
|
|
|
445 </div>
|
|
|
446 <div class='slide '>
|
|
|
447 <!-- _S9SLIDE_ -->
|
|
|
448 <h1 id="section-8">部分型</h1>
|
|
|
449 <ul>
|
|
|
450 <li>DataSegment が持つべき制約を表現できる型</li>
|
|
|
451 <li>型 T が期待される文脈で S を用いても良い、というようなことができる
|
|
|
452 <ul>
|
|
|
453 <li>「S <: T」で「S は T の部分型である」と読む</li>
|
|
|
454 <li>全てのDataSegment に対して「MDS <: DS」となるような MDS を用意する</li>
|
|
|
455 </ul>
|
|
|
456 </li>
|
|
|
457 <li>DataSegment X が期待される CodeSegment に Meta DataSegment を渡してやる</li>
|
|
|
458 </ul>
|
|
|
459
|
|
|
460
|
|
|
461 </div>
|
|
|
462 <div class='slide '>
|
|
|
463 <!-- _S9SLIDE_ -->
|
|
|
464 <h1 id="section-9">入力の部分型</h1>
|
|
|
465 <p># 出力の部分型</p>
|
|
|
466
|
|
|
467
|
|
|
468 </div>
|
|
|
469 <div class='slide '>
|
|
|
470 <!-- _S9SLIDE_ -->
|
|
|
471 <h1 id="section-10">部分型で何ができたか?</h1>
|
|
|
472 <ul>
|
|
|
473 <li>Meta CodeSegment を部分型とすることで
|
|
|
474 <ul>
|
|
|
475 <li>ノーマルレベルの CodeSegment の前後に処理を入れても型は整合する</li>
|
|
|
476 <li>Meta CodeSegment を CodeSegment とすることで階層構造を作れる</li>
|
|
|
477 </ul>
|
|
|
478 </li>
|
|
|
479 <li>Meta DataSegment を部分型とすることで
|
|
|
480 <ul>
|
|
|
481 <li>ノーマルレベルからはアクセスできないデータを保持してもOK</li>
|
|
|
482 <li>ノーマルレベルに Meta DataSegment を渡しても良い</li>
|
|
|
483 <li>こちらも階層構造を取ることができる</li>
|
|
|
484 </ul>
|
|
|
485 </li>
|
|
|
486 </ul>
|
|
|
487
|
|
|
488
|
|
|
489 </div>
|
|
|
490 <div class='slide '>
|
|
|
491 <!-- _S9SLIDE_ -->
|
|
|
492 <h1 id="singlelinkedstack-">SingleLinkedStack の証明</h1>
|
|
|
493 <ul>
|
|
|
494 <li>証明支援系 Agda に GearsOS のデータ構造 SingleLinkedStack を定義
|
|
|
495 <ul>
|
|
|
496 <li>スタックは赤黒木に用いられている</li>
|
|
|
497 </ul>
|
|
|
498 </li>
|
|
|
499 <li>その性質を証明する
|
|
|
500 <ul>
|
|
|
501 <li>性質もいくつか考えられる</li>
|
|
|
502 <li>「push して pop するとスタックは元に戻る」</li>
|
|
|
503 </ul>
|
|
|
504 </li>
|
|
|
505 </ul>
|
|
|
506
|
|
|
507
|
|
|
508 </div>
|
|
|
509 <div class='slide '>
|
|
|
510 <!-- _S9SLIDE_ -->
|
|
|
511 <h1 id="agda-">Agda を用いた証明手法</h1>
|
|
|
512 <ul>
|
|
|
513 <li>基本的にはデータの構造に関する帰納法
|
|
|
514 <ul>
|
|
|
515 <li>スタックは内部に SingleLinkedList を持つ</li>
|
|
|
516 <li>SingleLinkedList は NULL か値と次のノードを持つ</li>
|
|
|
517 <li>値がある場合と無い場合との場合分け</li>
|
|
|
518 </ul>
|
|
|
519 </li>
|
|
|
520 <li>挿入する要素を指定せずに push を呼ぶとどうなるのか?
|
|
|
521 <ul>
|
|
|
522 <li>実装依存のコード</li>
|
|
|
523 <li>証明には表れる
|
|
|
524 <ul>
|
|
|
525 <li>TODO: かく…</li>
|
|
|
526 </ul>
|
|
|
527 </li>
|
|
|
528 </ul>
|
|
|
529 </li>
|
|
|
530 </ul>
|
|
|
531
|
|
|
532
|
|
|
533 </div>
|
|
|
534 <div class='slide '>
|
|
|
535 <!-- _S9SLIDE_ -->
|
|
|
536 <h1 id="section-11">まとめ</h1>
|
|
|
537 <ul>
|
|
|
538 <li>Continuation based C 言語を対象にした二種類の検証アプローチ</li>
|
|
|
539 <li>モデル検査的なアプローチ
|
|
|
540 <ul>
|
|
|
541 <li>継続を上書きして可能な状態を数え上げるメタ計算ライブラリ akasha を実装</li>
|
|
|
542 <li>有限の要素数まで保証できた</li>
|
|
|
543 </ul>
|
|
|
544 </li>
|
|
|
545 <li>証明的なアプローチ
|
|
|
546 <ul>
|
|
|
547 <li>証明支援系 Agda 上で CbC のプログラムを定義して直接証明</li>
|
|
|
548 <li>部分型を利用して CbC を型付け</li>
|
|
|
549 <li>データ構造 SingleLinkedStack の証明ができた</li>
|
|
|
550 </ul>
|
|
|
551 </li>
|
|
|
552 </ul>
|
|
|
553
|
|
|
554
|
|
|
555 </div>
|
|
|
556 <div class='slide '>
|
|
|
557 <!-- _S9SLIDE_ -->
|
|
|
558 <h1 id="section-12">今後の課題</h1>
|
|
|
559 <ul>
|
|
|
560 <li>部分型を利用してCbCを型付け</li>
|
|
|
561 <li>依存型をCbC に導入して自身を証明可能にする</li>
|
|
|
562 <li>型情報から stub を自動生成すkる</li>
|
|
|
563 <li>赤黒木の挿入を証明する</li>
|
|
|
564 </ul>
|
|
|
565
|
|
|
566 <!-- vim: set filetype=markdown.slide: -->
|
|
|
567
|
|
|
568 <!-- === end markdown block === -->
|
|
|
569 </div>
|
|
|
570
|
|
|
571
|
|
|
572 </div><!-- presentation -->
|
|
|
573 </body>
|
|
|
574 </html>
|
