Mercurial > hg > Papers > 2016 > atton-ipsjpro
changeset 8:84ee0b8dc02e
Add mindmap
author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 28 Jun 2016 18:27:26 +0900 |
parents | 40eab722dfaa |
children | a9e93aee0af1 |
files | paper/mindmap.mm |
diffstat | 1 files changed, 158 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/mindmap.mm Tue Jun 28 18:27:26 2016 +0900 @@ -0,0 +1,158 @@ +<map version="1.0.1"> +<!-- To view this file, download free mind mapping software FreeMind from http://freemind.sourceforge.net --> +<node CREATED="1467104182596" ID="ID_688368422" MODIFIED="1467104546619" TEXT="Verification method of programs using Continuation based C"> +<node CREATED="1467104198314" ID="ID_443591537" MODIFIED="1467104203713" POSITION="right" TEXT="CS/DS"> +<node CREATED="1467104203714" ID="ID_899172723" MODIFIED="1467104212759" TEXT="CS はシンプルな処理のみを含む"> +<node CREATED="1467104212760" ID="ID_864823502" MODIFIED="1467104216191" TEXT="予測可能性"/> +<node CREATED="1467104216649" ID="ID_747353230" MODIFIED="1467104226180" TEXT="単位として小さく"/> +<node CREATED="1467104226987" ID="ID_862092051" MODIFIED="1467104234179" TEXT="無限ループは含まない"/> +<node CREATED="1467104260970" ID="ID_386883351" MODIFIED="1467104263952" TEXT="検証しやすいように"/> +</node> +<node CREATED="1467104236048" ID="ID_266698255" MODIFIED="1467104242460" TEXT="メタな計算"> +<node CREATED="1467104242461" ID="ID_302849859" MODIFIED="1467104247752" TEXT="メモリ管理などの処理"> +<node CREATED="1467104266881" ID="ID_476742009" MODIFIED="1467104272319" TEXT="linear allocator"/> +<node CREATED="1467104273276" ID="ID_203648398" MODIFIED="1467104332360" TEXT="例外処理"/> +<node CREATED="1467104333074" ID="ID_1462677723" MODIFIED="1467104340241" TEXT="複雑なものを排除"/> +</node> +<node CREATED="1467104248015" ID="ID_1557706923" MODIFIED="1467104252627" TEXT="CSの処理を保存するように"/> +<node CREATED="1467104252913" ID="ID_1675647762" MODIFIED="1467104904363" TEXT="検証もここに入るだろう"/> +<node CREATED="1467105308126" ID="ID_1673096180" MODIFIED="1467105315565" TEXT="メタ計算用のデータはメタDSになる"> +<node CREATED="1467105315566" ID="ID_1098172579" MODIFIED="1467105322338" TEXT="今のコードでは context に相当している"/> +</node> +</node> +<node CREATED="1467104301655" ID="ID_1408063984" MODIFIED="1467104307104" TEXT="組み合わせる"> +<node CREATED="1467104307105" ID="ID_526801636" MODIFIED="1467104314564" TEXT="meta は接続部分に入る"/> +<node CREATED="1467104317624" ID="ID_1289533340" MODIFIED="1467104325357" TEXT="切り替えられる"> +<node CREATED="1467105329015" ID="ID_1412071588" MODIFIED="1467105335666" TEXT="通常の goto するだけの meta"/> +<node CREATED="1467105336332" ID="ID_1717421512" MODIFIED="1467105341539" TEXT="例外処理付きの meta"/> +</node> +</node> +<node CREATED="1467104994438" ID="ID_1517687906" MODIFIED="1467105005425" TEXT="並列実行"> +<node CREATED="1467105005425" ID="ID_907477945" MODIFIED="1467105015773" TEXT="依存関係が無いものは自動で実行される"> +<node CREATED="1467105015774" ID="ID_1667782919" MODIFIED="1467105018358" TEXT="ということになってる"/> +<node CREATED="1467105018583" ID="ID_1858528611" MODIFIED="1467105027965" TEXT="Gears には現在スケジューラが無い"/> +</node> +</node> +</node> +<node CREATED="1467104373823" ID="ID_1988531007" MODIFIED="1467104376718" POSITION="left" TEXT="CbC"> +<node CREATED="1467104376719" ID="ID_1705458269" MODIFIED="1467104387375" TEXT="CS/DS を用いてプログラミングする言語"/> +<node CREATED="1467104389619" ID="ID_1304713196" MODIFIED="1467104406891" TEXT="CS はほぼ C function で goto で接続される"> +<node CREATED="1467105476704" ID="ID_784940950" MODIFIED="1467105494212" TEXT="for, while といった基本構文は同じ"/> +<node CREATED="1467105494317" ID="ID_1554202795" MODIFIED="1467105514048" TEXT="__code を function の定義時に付けると CS になる"/> +</node> +<node CREATED="1467104415771" ID="ID_835076590" MODIFIED="1467104448948" TEXT="C の資産を使うために function call もできる"> +<node CREATED="1467105516683" ID="ID_1112085216" MODIFIED="1467105523602" TEXT="printf"/> +<node CREATED="1467105523819" ID="ID_525933212" MODIFIED="1467105524983" TEXT="malloc"/> +<node CREATED="1467105525236" ID="ID_1780380433" MODIFIED="1467105531942" TEXT="pthread"/> +<node CREATED="1467105532212" ID="ID_829428193" MODIFIED="1467105536816" TEXT="他のライブラリ"/> +</node> +<node CREATED="1467104407232" ID="ID_1980396133" MODIFIED="1467104412679" TEXT="DS は構造体で表現されている"> +<node CREATED="1467105537123" ID="ID_1489116959" MODIFIED="1467105552860" TEXT="構造体の union"/> +<node CREATED="1467105556645" ID="ID_1543655706" MODIFIED="1467105559990" TEXT="自動で生成したい"/> +</node> +<node CREATED="1467104919532" ID="ID_390963158" MODIFIED="1467104927291" TEXT="implementations"> +<node CREATED="1467104927292" ID="ID_1136736292" MODIFIED="1467104929949" TEXT="micro C"/> +<node CREATED="1467104930294" ID="ID_677752795" MODIFIED="1467104931309" TEXT="gcc"/> +<node CREATED="1467104931547" ID="ID_983923346" MODIFIED="1467104934833" TEXT="llvm/clang"> +<node CREATED="1467104934833" ID="ID_445358833" MODIFIED="1467104941574" TEXT="今はこれを使っている"/> +</node> +</node> +<node CREATED="1467105049108" ID="ID_1595654033" MODIFIED="1467105066817" TEXT="並列実行"> +<node CREATED="1467105066818" ID="ID_1166826550" MODIFIED="1467105081131" TEXT="各 thread で context を持っていて並列に実行できる"/> +<node CREATED="1467105081401" ID="ID_498561044" MODIFIED="1467105086823" TEXT="twice がある"> +<node CREATED="1467105571389" ID="ID_265071868" MODIFIED="1467105584340" TEXT="並列実行の効果はある"/> +</node> +<node CREATED="1467105087623" ID="ID_841475890" MODIFIED="1467105106414" TEXT="今は素直にmeta側で pthread_create"> +<node CREATED="1467105106415" ID="ID_1873952928" MODIFIED="1467105114189" TEXT="スケジューラを作りたい"> +<node CREATED="1467105114190" ID="ID_213462348" MODIFIED="1467105125775" TEXT="Gears を Cerium と同じくらいにする"/> +<node CREATED="1467105126005" ID="ID_436242008" MODIFIED="1467105133119" TEXT="依存関係をどう記述するか"/> +</node> +</node> +</node> +</node> +<node CREATED="1467104451097" ID="ID_1539282609" MODIFIED="1467105724456" POSITION="right" TEXT="akasha"> +<node CREATED="1467104453043" ID="ID_98539964" MODIFIED="1467104458142" TEXT="実際には CbC のプログラム"> +<node CREATED="1467105159250" ID="ID_1125168168" MODIFIED="1467105164559" TEXT="meta 部分のみを書いてある"/> +<node CREATED="1467105164862" ID="ID_1705620865" MODIFIED="1467105176202" TEXT="llrb 部分は変更していない"> +<node CREATED="1467105176203" ID="ID_1349265303" MODIFIED="1467105183387" TEXT="実行バイナリを作る時にリンクしている"/> +</node> +<node CREATED="1467105187553" ID="ID_436799831" MODIFIED="1467105203039" TEXT="なので context などは akasha 用に再作成している"/> +<node CREATED="1467105203313" ID="ID_1425319166" MODIFIED="1467105220031" TEXT="データ構造のAPIが変わると変更せざるを得ない"> +<node CREATED="1467105220032" ID="ID_1845113140" MODIFIED="1467105225566" TEXT="それは他の言語でもそうか"/> +</node> +</node> +<node CREATED="1467104458392" ID="ID_691068611" MODIFIED="1467104461714" TEXT="全部の状態を列挙する"> +<node CREATED="1467104488690" ID="ID_82006877" MODIFIED="1467104501575" TEXT="今後の目標としては状態の抽象化をして高速化"/> +<node CREATED="1467104503246" ID="ID_43061191" MODIFIED="1467104506535" TEXT="なので bounded"/> +<node CREATED="1467105229544" ID="ID_1781859055" MODIFIED="1467105241412" TEXT="単に全探索"> +<node CREATED="1467105241413" ID="ID_1028101450" MODIFIED="1467105253896" TEXT="メモリ開放のコードは入れてるのでメモリ溢れは一応しづらい"/> +<node CREATED="1467105254159" ID="ID_956584291" MODIFIED="1467105264792" TEXT="時間のみがひたすらにかかる"/> +</node> +<node CREATED="1467105590876" ID="ID_780135548" MODIFIED="1467105610999" TEXT="元のコードを変えない + 全探索なので JavaPathFinder に近い"/> +</node> +<node CREATED="1467104461923" ID="ID_1582798373" MODIFIED="1467104470505" TEXT="assert base で性質を書く"> +<node CREATED="1467104470506" ID="ID_610847415" MODIFIED="1467105860352" TEXT="llrb の高さのみチェック"> +<node CREATED="1467105897059" ID="ID_1999377183" MODIFIED="1467105900533" TEXT="今は insert のみ"/> +</node> +<node CREATED="1467104478348" ID="ID_1552847590" MODIFIED="1467105272062" TEXT="counter example の出力コードも自分で書いている"> +<node CREATED="1467105272590" ID="ID_414429238" MODIFIED="1467105278246" TEXT="ここがバグる可能性も無くはない"/> +<node CREATED="1467105278505" ID="ID_402375225" MODIFIED="1467105294372" TEXT="llrb 用のコードになってるので汎用性は無い"/> +</node> +<node CREATED="1467105444061" ID="ID_668713683" MODIFIED="1467105466207" TEXT="わざとバグをllrbに仕込んでも反例は返してくれた"/> +<node CREATED="1467105903093" ID="ID_14091279" MODIFIED="1467105908213" TEXT="まだチェックしていないこと"> +<node CREATED="1467105848774" ID="ID_304519484" MODIFIED="1467105858494" TEXT="要素が unique か"> +<node CREATED="1467105946394" ID="ID_968623311" MODIFIED="1467105961893" TEXT="全探索してしまえば問題無い"/> +</node> +<node CREATED="1467105874927" ID="ID_271098631" MODIFIED="1467105883200" TEXT="search がきちんとできるか"> +<node CREATED="1467105946394" ID="ID_1461377606" MODIFIED="1467105961893" TEXT="全探索してしまえば問題無い"/> +</node> +<node CREATED="1467105883552" ID="ID_521484669" MODIFIED="1467105886702" TEXT="delete できるか"> +<node CREATED="1467105937347" ID="ID_1716391119" MODIFIED="1467105944199" TEXT="delete implementation ができてから"/> +</node> +</node> +</node> +<node CREATED="1467104512049" ID="ID_1708243238" MODIFIED="1467104519894" TEXT="可能な検証要素数"> +<node CREATED="1467104519895" ID="ID_1261923924" MODIFIED="1467104524491" TEXT="現在は max 12"/> +<node CREATED="1467104524750" ID="ID_1183166569" MODIFIED="1467104836368" TEXT="1 hour くらい"/> +<node CREATED="1467104836638" ID="ID_1967210895" MODIFIED="1467104842905" TEXT="メモリは 1 Gで足りる"/> +</node> +<node CREATED="1467104796356" ID="ID_1248008112" MODIFIED="1467104812011" TEXT="Synchronized Queue"> +<node CREATED="1467104813502" ID="ID_119764172" MODIFIED="1467104816332" TEXT="まだチェックしてない"/> +<node CREATED="1467104816642" ID="ID_852145992" MODIFIED="1467104823011" TEXT="CAS 周りのチェックも必要"/> +</node> +<node CREATED="1467104857827" ID="ID_807870663" MODIFIED="1467104862950" TEXT="検証できないこと"> +<node CREATED="1467104862951" ID="ID_1931709274" MODIFIED="1467104872214" TEXT="CS 自体で無限ループを形成される"/> +<node CREATED="1467104876244" ID="ID_1257276169" MODIFIED="1467104894034" TEXT="実行中に segv するプログラム"/> +</node> +<node CREATED="1467105360442" ID="ID_896233851" MODIFIED="1467105365288" TEXT="並列に実行可能か"> +<node CREATED="1467105365289" ID="ID_1518356839" MODIFIED="1467105381040" TEXT="探索部分は並列で実行可能だと思う"> +<node CREATED="1467105381041" ID="ID_1298030876" MODIFIED="1467105418053" TEXT="高々 /n なので exp に対してはそんなに効果的ではない"> +<node CREATED="1467105422353" ID="ID_268617420" MODIFIED="1467105429157" TEXT="抽象化とかの方が効果が高い"/> +</node> +</node> +</node> +</node> +<node CREATED="1467104547538" ID="ID_899818608" MODIFIED="1467104553523" POSITION="left" TEXT="cbmc"> +<node CREATED="1467104553523" ID="ID_890713893" MODIFIED="1467104560944" TEXT="C の bounded model checker"/> +<node CREATED="1467104561216" ID="ID_1168684794" MODIFIED="1467104568129" TEXT="これもソースを変更しなくても良い"> +<node CREATED="1467104772712" ID="ID_237137885" MODIFIED="1467104781153" TEXT="C の symbolic exectution らしい"/> +</node> +<node CREATED="1467104568538" ID="ID_103150222" MODIFIED="1467104580754" TEXT="非決定製を表現できる input なども builtin である"> +<node CREATED="1467104580755" ID="ID_788717002" MODIFIED="1467104597573" TEXT="そういう意味では検証用コードに書き換えないと"/> +<node CREATED="1467104598999" ID="ID_388191542" MODIFIED="1467104651773" TEXT="cs/ds だと元の処理を壊さない位置にassert を書ける"/> +</node> +<node CREATED="1467104654240" ID="ID_1681700868" MODIFIED="1467104669033" TEXT="cbc コードは goto を return にすることで C にできる"/> +<node CREATED="1467104669291" ID="ID_1379058858" MODIFIED="1467104679027" TEXT="Pointer の null check などもできる"> +<node CREATED="1467104730479" ID="ID_1451855658" MODIFIED="1467104743663" TEXT="デフォルトでいくつかの検証プロパティがある"/> +<node CREATED="1467104743937" ID="ID_1832275750" MODIFIED="1467104756107" TEXT="自前でassertを書くことも可能"/> +</node> +<node CREATED="1467104679330" ID="ID_594229550" MODIFIED="1467104685379" TEXT="llrb は検証できない"> +<node CREATED="1467104685629" ID="ID_1180276746" MODIFIED="1467104697233" TEXT="要素数1でもチェック不可"> +<node CREATED="1467104697234" ID="ID_211544587" MODIFIED="1467104703238" TEXT="1000行くらいのコード"/> +<node CREATED="1467104704027" ID="ID_527386309" MODIFIED="1467104717204" TEXT="loop unwind しすぎると memory に乗らないらしい"/> +</node> +</node> +<node CREATED="1467104757767" ID="ID_624701293" MODIFIED="1467104767730" TEXT="counter example も出してくれる"/> +</node> +</node> +</map>