netail.net
自作フリーソフトや，ゲームに関する雑記を公開してます．
日記はソフトウェア工学の論文ネタが中心です．
最近のお知らせ (古いものはこちら)
2006-03-23 [長年日記] ▲
_ AOSD４日目（本会議２日目） ▲
ドイツの人で，steamloomというDynamic AspectサポートVM環境を作ってる人たちが，動的スライスをまじめに実装したツールデモをやっていた．見たかぎり，完成度はそれなりに高そう．
動的スライスを選んだ理由は，omniscient debugging という実行時情報を全部保存するアプローチで元々研究をしているためか，Dynamic Deploy ができるアスペクト指向プログラムの実行環境なので動的スライスでないと（たぶん）ちゃんとした結果が出せないためか，どちらが直接の動機なのかは不明．
あとで少し聞いてみたら，けっこう開発工数はかかっているらしい．
メモリと実行時間がたくさん必要（例題でもMB単位のメモリ，実行時間が3〜25倍必要）というのがネックなものの，まだデータ構造の最適化などはしてないから，もうちょっと良くなるかもしれないとは言っていた．
また，動くものがあるので，実際にどのようにスライスを使えば（どこを基点にするか，intersectionとかunionを使うか，など）問題解決に役立つか調べられるし，問題の解決のためにどの範囲を解析する必要があるか，とか分かればもっと軽くなるかもしれない．
ツールも公開するし論文も publish するよ，と言っていたので楽しみ．
今回のバンケットは，料理はビュッフェ式だったけど，手品ショーとか付いて豪華だった．UBCの人々とか，同じテーブルにいた合気道やってるドイツ人とかと知り合いになった．
2006-03-22 [長年日記] ▲
_ AOSD３日目（本会議１日目） ▲
オブジェクト間の関連（クラス図における association）を，Java Generics の型パラメータを使ったアスペクトで実装したら，アスペクトを好きなクラス間で関連を持たせることができて（そのためのメンバ変数を各クラスに持たせずに済み），パフォーマンスも悪くない，という話をしている人がいた．
The Relationship Aspect Libraryとして公開しているらしい．
このライブラリは，クラス C1, C2 に対して関連がただ１つしかない場合には，たぶん有効．逆に，たとえば，Student, Professor に「授業履修」という関連と「研究室所属」という別個の関連を同時に持たせようとすると，Relation＜Student, Professor＞の関連インスタンスが２つ必要になるので，AspectJ のインタータイプ宣言では，関連情報を保存するフィールドの名前が衝突してしまう気がする．あくまでAspectJのアスペクト継承で実装した場合の問題なので，コード生成ツール（XVCLとか）を使って，雛形アスペクトから名前衝突を起こさないようなアスペクト生成をすればOKだとは思うけど．
2006-03-16 [長年日記] ▲
_ [論文] データの到達条件の解析方法 ▲
Gregor Snelting, Torsten Robschink, Jens Krinke: Efficient Path Conditions in Dependence Graphs.
To appear in ACM Transactions on Software Engineering and Methodology.
Path Condition (PC) というのは，プログラム中のある２点 x, y に対して，x で定義しているある変数が，y に影響を与えるときの条件を指す．たとえば:
a = 1; // 1 if (x > 0) // 2 b = a; // 3 else // 4 b = 0; // 5 c = b; // 6
といった状態で，１行目の変数代入が６行目に影響を与えるのは３行目の文が実行されたときだけなので，PC(1,6) = (x > 0)となる．基本的には，if文やfor文での条件節をどんどんANDでつないでいった形にする．プログラムの入力変数以外（中間データ）に関しては変数を消去していって，プログラムへの入力変数がどのような条件を満たせば，その情報の流れが発生するか，ということを示す．
プログラム中の重要な変数が，他の変数から影響を受けないことを調べるには，先ほどのPCを計算して，それが充足不能であることを示せばよいことになる．これは，static program slicing で「影響を受けるかもしれない」と出てくる false positive を取り除くためにも利用できる．また，充足可能である場合は，その条件を求めれば，いつその情報流が発生するかを調べることができる．
この論文では，このPath Conditionの計算方法と，それを色々なプログラムに適用した場合の時間・空間計算量を評価している．
地点 x から y へは複数のパスがあるので，「影響を与えるとき」というのは各パスでの到達条件のORを取ればよいとか，assertionで書かれた条件も含めるとか，dominator（通過しなければならない頂点）を使って解析を前後で分割するとか，手続きに対するサマリ辺の作り方とかが説明されている．いわゆるプログラムスライシング技術がベースで，このあたりの手法自体はわりと普通．メソッドの多態性なんかも，とりうるサブクラスを調べてきて，((a instanceof A) -> PC_for_M_A ) ∧((a instanceof B)-> PC_for_M_B)のように述語をつないでいくだけで表現することができる．
こうやって計算を進めていくと， Path Condition として長々とした条件節が出てきてしまうので，定理証明系(であってるのかな？)で条件節を簡単化していく．実験結果とかを見てると，「P行目での変数xの値がaになっていて，かつQ行目でyになっていて，…」というような条件式がだらだらと並んだ形になる様子．条件式を読み解くのに知識は必要だが，それほど大変でもないというような書き方はされていた．また，セキュリティ解析では，重要情報の危険な変数への到達可能性が充足不能であることさえ示せればよいので，あまり気にしなくても良いのかもしれない，とも思う．
この手法の良いところは，関数単位で独立に処理できるように規定されていることと，PC(x,y) は x から y に情報流が発生するために少なくとも必要な条件であること（十分な条件とは限らない）．メソッド呼び出し階層が深いときなどは，途中で探索を打ち切ってしまっても，「少なくともこれだけ成り立ってたら，情報流が発生する可能性があります」と情報を出すことができる．探索を途中で打ち切ると，条件が弱くなってしまうぶん（冗長な条件を出すことはない），充足不能性とかを示そうとすると大変になる．しかし，プログラム理解などの他の場面では，コールグラフ上で近い階層だけをざっと調べて大雑把な到達条件を見る，といった使い方もできるかもしれない．
この人々，dynamic な手法（実際にどの条件式の影響を受けたかを調べる）というのも Dynamic Path Conditions in Depndence Graphs (PEPM2006) という論文で発表する様子．けっこうがんばっている．
2006-03-15 [長年日記] ▲
2006-03-13 [長年日記] ▲
_ [読書] プレファクタリング（前半）を読んでみた ▲
とりあえず１６章中，７章を読んでみた．
どのクラスにメソッドを配置するか，継承と委譲のどちらを使うか，命名をどうするかといった設計段階での色々な決定事項についての議論が紹介されている．契約による設計とか，XPとか，テスト駆動型開発とか，色々な人が言ってきたことをトピック別に整理している印象．
全部あくまで指針になっているのは，設計の良し悪しは明らかに良いもの，悪いものを除くと判断が難しいこと（関心事を分離しようとすると個々のクラスは単純になってもクラス数は増える），必ずしもすべての状況に適用できるとは限らないことなどに起因するらしい．
以下は，今まであまり聞いたことがなかった・考えてなかったことのメモ:
ユースケースの処理手順をさらに詳細化すると，クラスに対する一連のメソッド呼び出し（ワークケース）が出てくる．ワークケースが１つもないようなクラスは目的の無いクラスではないかと考えられる．また，理想的には各メソッドに個別にテストを実施するが，個別のメソッドがあまり意味を持たない場合やそこまで時間が取れない場合はワークケース単位でのテストにする．
一括したものを分割するより，分割したものを一括するほうが容易．AとBと書いてあれば，BをAに置換することができるが，逆は簡単にはいかない．異なる概念かもしれないものは，とりあえず分割しておいて，あとで同じものだと分かったらまとめてしまう．
