ICSE 勉強会 Comprehending the Drift I 筑波大学 北川研 早瀬 康裕 Mining Message Sequence Graphs Sandeep Kumar, Siau-Cheng Khoo, Abhik Roychoudhury, David Lo 背景 • Dynamic specification mining: 実行トレースからプログラム の振舞いを抽出する研究 – オートマトンに基づく記述 [11,23,28] – temporal ruleに基づく記述 [43,25] – どれも,逐次プログラムが対象 • 並列/分散プログラムからの抽出は難しい – 特に,イベントの半順序を発見する所 • 分散システムの記述には Message Sequence Charts (MSCs, ITU勧告) がよく用いられる – シーケンス図にそっくりだが,縦線はプロセスを表す MSGMiner • 入力: プログラムトレース • 出力: MSG (MSC を頂点とする有向グラフ) – 頂点 (basic MSC) のイベントが全て終了すると,次の頂点 に移動する • 手順 (1) イベント間の半順序関係の抽出 – イベント列 (全順序) から,不要な関係を捨てる – 残す順序関係 • メッセージの送信 <s!r, m> は,対応する受信 <r?s, m> に先立つ • 同一のプロセス内の時系列順序 (2) basic MSC の抽出 • 頻出する部分グラフを抽出する (3) automata の学習 • sk-strings (既存手法) を使用する (4) 拡張 • • broadcast の送受信に対応 不要な順序関係を捨てる • oracle (特別な入力列)を与えて,不要な順序を認識させ る Automatically Detecting and Describing High Level Actions within Methods Giriprasad Sridhara, Lori Pollock, K. Vijay-Shanker Motivating example • コード片に対して,アルゴリズムレベルでの説 明文を生成する手法を提案 背景技術 3.1 プログラムの自然言語的 構文解析 著者らの作った Software Word Usage Model (SWUM) で,プログラム中に出現す る単語の関係を取得する. 動詞節,名詞節などが取り出せる. 以下の組み合わせ • 連続する文から生成 • 制御構造から生成 9 for ( int x = 0 ; x < vAttacks . size() ; x++) { 10 WeaponAttackAction waa=vAttacks . elementAt (x); 11 float fDanger = getExpectedDamage(g, waa) ; 12 if (fDanger> fHighest) { 13 fHighest = fDanger; 14 waaHighest = waa; 15 } 16 } 17 return waaHighest ; Get weapon attack action object (in vectorAttacks) with highest expected damage 説明文の生成例 (Listing 1) 説明文生成の基本 • 3.2 連続する文をまとめる 戦略: よく似た文の連続を,ひとつの処理として説明文を作る • まとめたい例 Listing 3 と,まとめたくない例 Listing 4 アルゴリズム – 上から順に連続する文をチェックし,連結可能な限りつなぐ – 連結可能の基準 • 動詞節が同じ • 名詞節の最後の語 (Head Word) が同じ • (前置詞節もチェックするが省略) – 連結可能な文から,名詞節の共通部分を括り出して複数形に する 制御構造からの説明文生成 • 3.3 条件文を抽象化する 戦略: 分岐後の文が同じ形なら,まとめて説明文にする – Listing 5: 条件節にあるレシーバ型が共通であることを見つけて, 文の生成に利用する – Listing 6: return を見付ける.その引数が定数なら,条件式内の単 語の略語かどうかをチェックする – Listing 7: 同じ変数への代入を見付ける • 3.4 ループ中のパターンを見付ける 戦略: 特徴的なループのパターンを見付けて,説明文にする – max-min: 最大値 (最小値) を見付ける処理 – count: 集合型の中の要素数を数える – contains: 条件を満たす要素が含まれているかどうかを検査する – find: 条件を満たす要素を返す – copy: 集合型の(条件を満たす)要素を,別の集合型にコピーする 5 何に使える? • • • • リファクタリング 関数・メソッド内部用のコメント生成 より良いメソッド名の提案 メソッドのドキュメントコメント(summary comment)生成 (の改善) Portfolio: Finding Relevant Functions and Their Usages Collin McMillan, Mark Grechanik, Denys Poshyvanyk, Qing Xie, Chen Fu mip map dithering texture image graphics Search 意図: mip map 画像を dithering していて,テクスチャに 使っている例を探したい (?) • 全ての単語を含む関数はない • 個々の単語を含む関数が,別々に列挙されるだけで は,理解や再利用には不足 開発者に必要なもの • 関連する関数全て • 適切な組み合わせ 関連する関数も含めたコールグラフを見せよう モデル • 検索対象のデータモデルは,関数間の静的なコール グラフ. – 辺は呼出しの有無のみで引かれる (多重辺,ラベルはな し) • PageRank と,キーワードマッチ(WOS),Spreading Activation Network (SAN) を組み合わせて評価値を出 す – 「SAN」と呼んでいるものの実態 • キーワードマッチの評価値を,コールグラフ上で隣接する頂点に 伝播させる • これにより,直接キーワードにマッチしなかった頂点も検索結果と して表示される • 検索結果は部分グラフ (+ 含まれる頂点のリスト) 検索結果の Web UI • 上位にランクされた関数は,コールグラフ上 で大きく表示される • リストにマウスカーソルを合わせると,対応す るコールグラフの頂点がハイライトされる 評価実験 • Google Code Search, Koders, Portfolio を被験 者実験で評価 – 49人中, Accenture コンサルティング部門の社員 が44人(!) • 15種類のタスクのコンセプトを,それぞれ1つ のクエリで表現 • 検索結果の上位10件を,4段階で評価 • 結果: Portfolio > Koders > Google
© Copyright 2024 ExpyDoc