コーディングパターンの分析
コーディングパターン
コーディングパターンとは,プログラム中に頻出するコード片です.パターンは,関数呼び出しの列と,それに付随する 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 プログラムを対象としたパターンマイニングツールを開発しており,様々なソフトウェアに対する適用実験を行っています.
コーディングパターンの活用
抽出されたコーディングパターンには,アプリケーション固有の機能を理解するための手がかりや,部品の利用方法を調べるためのドキュメントとしての価値があります.
一方で,コーディングパターンの性質については未知の部分が多く,様々な研究課題が残されています.たとえば,「互いに類似したソースコード片」として定義されているコードクローンとの差異の調査や,有用なパターンだけを自動的に抽出するためのフィルタリング手法の開発が挙げられます.また,コーディングパターン情報の活用として,たとえば「同じコードの書き間違いを探す」といったバグ修正に対する適用や,コーディングパターンそのものをソフトウェア部品として再利用する方法などを検討しています.