いのうえけ〜ん
English 
/ ホームページ / 研究紹介 / 発表論文・技術報告・学位論文 / メンバー / ニュース /

コーディングパターンの分析

コーディングパターン

コーディングパターンとは,プログラム中に頻出するコード片です. パターンは,関数呼び出しの列と,それに付随する if文, for文のような制御構造から構成されます.

コーディングパターンは,教科書に掲載されているプログラムや, 過去に開発したプログラムなどを手本としたコーディングを行うときに生じます. たとえば,Java において,データ構造に格納された要素に対する ループ処理は,Iterator クラスを使って,次のように表現されます.

for (Iterator it = list.iterator(); it.hasNext(); ) {
  Item item = (Item)it.next();
  :
}

実際には,登場する for 文ごとに,対象となるデータ,上記のコード例では 変数 list やクラス名 Item に相当する部分や, 実行する処理の本体には差異があります. しかし,ループそのものの記述や動作はまったく同一であることから, 開発者は for 文の先頭を見るだけで,どの変数に対するループ処理であるか, すぐに判断することができます.

コーディングパターンは,プログラムの特定の振る舞いを実現するためのものです. パターンの中には,プログラミング言語に固有の コードの書き方(イディオムと呼ばれます)や, アプリケーションに固有の機能を実現するパターンなどが含まれます. コーディングパターンの知識は, プログラムの動作の理解に有用です. また,ソフトウェア部品の使用方法などを調べるとき, その部品を使ったコーディングパターンは有力な手がかりとなります.

パターンマイニング

井上研究室では,コーディングパターンをソースコードから 自動抽出する手法として,データマイニング手法の1つである シーケンシャル・パターン・マイニング (Sequential Pattern Mining)を使用しています. このマイニング手法は,与えられたデータ列の集合から, 頻出する部分列だけを抽出するというものです.

ソースコードの関数あるいはメソッドを,それぞれ「特徴の列」へと変換します. これらの「特徴の列」の集合から,頻出する特徴の部分列を抽出し, パターンの候補とします. ここでいう「特徴」とは,ソースコードに登場する関数呼び出し(メソッド呼び出し)と if文,for文などの制御構造のことです. 以下に,Iterator を使った for 文から取り出される「特徴」の列を示します.

ここで,抽出された特徴列は,メソッドの呼び出し順序と, 制御構造だけしか保存していません. for 文は LOOP / END-LOOP という要素に変換され, while 文と区別されなくなります. これによって,パターンの出現位置ごとの差異を吸収しています.

このような抽象化をメソッド単位で行った後, パターンマイニング手法を適用します. PrefixSpan というアルゴリズムを用いて, 4つの特徴列 ["acd", "abc", "cba", "aab" ] から 長さ1以上,出現回数2以上のパターンを検出したときの動作を,以下に示します.

PrefixSpan は,まず,各要素を長さ1のパターンであると考えます. 要素 a は与えられた4つの特徴列すべてに, 要素 b と c はそれぞれ3つの特徴列に,また d は1つの特徴列にのみ登場しています. このうち d だけは,出現する特徴列の数が閾値である2に達していないため, パターン候補から除外されます.

残った長さ1のパターン "a", "b", "c" それぞれについて, それらの後続の要素列だけを取り出す「射影」という操作を行います. たとえば,"acd", "abc", "cba", "aab" に対して "a" の後ろに続く要素列を取り出すと,"cd", "bc", "ab" が得られます ("cba" の場合は後続の要素が存在しないため,ここで取り除かれます).

得られた要素の中から,やはり各要素の出現回数を調査します. "cd","bc","ab" の中には,b と c が2回ずつ出現するので, これらを直前の文字 "a" と結合した,"ab","ac" という長さ2のパターンとして 検出します.

さらに "ab","ac" の各パターンについて射影を行い, 後ろに続く要素を調べていくことで,より長い パターンの探索が行われていきます. 新しいパターンが発見されなくなったところで, PrefixSpan は終了します.

シーケンシャルパターンは,要素が同じ順序で並んでいるなら, 連続して並んでいなくてもパターンとして認識します. 以下に,そのようなパターンの例として, 画像作成ツール JHotDraw 5.4b1 で発見されたUndo 機能の実装を示します. JHotDraw はメニューなどから選んだ コマンドを「元に戻す」ための機能を持っています. コマンドごとに「どう元に戻すか」という方法こそ異なっていますが, それを実現するための定型的なメソッド呼び出し列がパターンとして検出されました.

井上研究室では,C言語でのプログラム開発履歴や,Javaプログラムを 対象としたパターンマイニングツールを開発しており, 様々なソフトウェアに対する適用実験を行っています.

コーディングパターンの活用

抽出されたコーディングパターンには,アプリケーション固有の機能を 理解するための手がかりや,部品の利用方法を調べるための ドキュメントとしての価値があります.

一方で,コーディングパターンの性質については未知の部分が多く, 様々な研究課題が残されています. たとえば,「互いに類似したソースコード片」として定義されている コードクローンとの差異の調査や,有用なパターンだけを自動的に抽出するための フィルタリング手法の開発が挙げられます. また,コーディングパターン情報の活用として, たとえば「同じコードの書き間違いを探す」といったバグ修正に対する適用や, コーディングパターンそのものをソフトウェア部品として 再利用する方法などを検討しています.

代表的な論文

研究紹介に戻る


homeホームページへ © ソフトウェア工学講座 mailお問い合わせはこちらまで