«前月 最新 翌月» 追記

netail.net

自作フリーソフトや,ゲームに関する雑記を公開してます.
日記はソフトウェア工学の論文ネタが中心です.

最近のお知らせ (古いものはこちら)


2006-05-02 [長年日記]

_ 思いつき: DSL + Pointcut Generation = ?

ドメイン特定言語(Domain Specific Language, DSL)を定義して,それをJavaなどのコード生成に使うことを考えると,生成された Java コードをデバッグする環境はあっても, DSL 上でのデバッグ環境を用意するのはちょっと面倒.また,DSL 上で書かれたイベントに,どのソースが対応するかを人間が手で調べるのはうれしくない.ソースコードのほうが粒度が小さいので,適切な位置でブレークポイントを設置してるかどうかも怪しくなってしまう.

これに対して,コード生成時に,DSL 上のイベントにきっちり対応するポイントカット定義を同時に生成する方法があれば,そこにデバッグや表明検査をアスペクトとして組み込んでしまうことができて,少しは幸せになれるかもしれない.単純な実装方法としては,DSL イベントに対応する場所に,対応するイベント通知用メソッド呼び出しなどを無駄に埋め込んでおくといった力技もありうる.

モデルから pointcut 生成するという話は SPLAT でも出てた気がするけれど,保守用コードを入れて意味のありそうな場所を捕まえるポイントカットを作っちゃう,というのは,良いやり方なのかどうか…….どうなんでしょう?


2006-05-04 [長年日記]

_ [近況] UBC行きスケジュール

無事 St. John's College からの acceptance letter が届いた.前に「required documents は揃ってる?」と聞いたときに「揃ってるよ」といわれたものの,実は invitation letter だけ足りてなかったから審査通過となっていなかったらしい.depositなどの費用は本当は到着前に送るのだけど,現地にマネーオーダー(郵便局で買えるらしい)をもっていくことになった.向こうの事務の人に感謝.

9月のASE/AOASIAは,参加のために一時帰国します.>関係しそうな先生方


2006-05-06 [長年日記]

_ [読書] ソフトウェアファクトリー

Jack Greenfield, Keith Short with Steve Cook, Stuart Kent 著「Software Factories / ソフトウェアファクトリー」読了.研究室の輪講で使ってるので,あまり詳しく書くとまずそうだけど,本の全体像だけ.

ソフトウェアの開発をできるだけ自動化したい.1つの方法がモデルからのコード生成で,高い抽象度で(概念に近いレベルで)表現された命令から,それを実現するコード生成できれば,開発者の負担は大きく軽減できる.

そのためには,コンピュータが理解できる(parse可能な)モデルを作る必要がある.そこで,モデルの図ないしテキストで記述するためのドメイン特定言語(DSL)を定義して,それを理解できるような開発環境(およびそれを使ったプロセス)を構築する.

この開発環境は,特定のプロダクトファミリに限定したものとなるかわり,強力なサポートを開発者に提供する.

クラスフレームワーク(共通部分)を作っておいてそこに参加するクラス(可変部分)をモデルから生成する,あるいはパラメータ化されたパターンを自動適用する,コンポーネントのインタフェース記述と接続情報から接続用コードを生成するといったような開発インフラを作ることで,事前投入のコスト(開発環境の構築などのコスト)を一連のプロダクトを開発するときに回収できるだろう,と言っている.

端的には,設計段階でモデルを書くからにはちゃんとモデルの内容がコードに(できれば自動的に)反映されるようにしよう,というもの.コンポーネント間を接続する似たようなコードを何度も書くくらいなら,接続コードのテンプレートを作っておいて,開発者が対話パターンを指定するだけでコードが自動生成されればうれしい.

読んでると,いちおうそういうことが可能なんだな,という気にはなってくるが,ドメインによってどんなDSLを用意すべきか決めるには一連のプロダクトの共通性を発見する必要があり,これはけっこう難しいかもしれない.また,DSLを理解するエディタやデバッガ(しかも正しく動作するもの)を用意するのも,かなり大変なはず.

既存の重厚なプロセスやアジャイルプロセス,モデル駆動型開発,アスペクト指向やデザインパターンなどが一通り整理されており,今後の方向性を示唆しているという意味では非常に面白い本.まだちょっと先の話,という気もしないでもないが.

_ 学振の海外渡航の予定変更の場合の手続きとか,科研費の行使とか

海外渡航の予定変更は,結局必要はなかったけど,せっかく電話して聞いたのでメモ: 海外渡航届で申請した日程と実際の渡航日程が少しだけ変わった場合(1ヶ月以内の「軽微な変更」の場合),公式な書類様式のようなものはなく,学振への電話連絡だけでよいらしい.学内用の事務書類としては「学振には電話連絡した,日程を変更した」といった旨のものを勝手に作ってね,となるらしい.

また,科研費の行使については,研究は継続してるはずなので学振的には(1年近く日本を離れていても)問題なくて,受入研究先の事務手続き次第となる.普通に使えることになったので,ありがたい.


2006-05-10 [長年日記]

_ [近況] とりあえずスタートアップ@UBC

work permit も無事もらえたし,タクシーを使ったので特に迷うこともなく到着.St. John's Collegeでは,2回目の夕食までの様子からして,国際会議で食べさせられてるようなメイン1品+サラダや飲み物を好きなだけという構成みたい.肉入りのパイとかあまり日本では食べないものも出された.野菜や果物もそれなりに多いので,あまり困らなさそう.金曜と土曜にどうするかは考えないといけないけど.

たまたま晩御飯で隣の席に座った人が,文学系か歴史系の研究者っぽい人で,お父さんが日本に1907年から戦争期間くらいまで住んでたらしく,日記の日本語(ただし独学)に変なところがあって読めないからお前は読めるか,とか聞かれて,今度日記の写真を見せてくれると言っていた.

_ カナダドル送金の方法

滞在費の支払いの送金として,郵便のマネーオーダーはアメリカ宛以外は持参などの方法は認められず,東京経由で20〜30日必要とのこと.仕方がないので,淀屋橋にある三菱東京UFJ銀行の大阪中央支店の2階にある窓口で小切手を作成して持参した.所要時間は1時間はかかってないと思うが,ちゃんと免許証などによる住所のチェックもあるし,その後もそれなりに待たされた.他の支店では,取次ぎになるので数日待たされるらしい.

手数料は送金する額は関係なしに1枚作って5000円.といっても,5万円以上になったあたりからは,現金を両替して持参よりも安心だし,レート差のぶん安いと思う.他の銀行はどうなんだろうか…….


2006-05-16 [長年日記]

_ [近況] 初ミーティング終了

先週一週間で道具一式(プリンタ,メール,鍵)も揃ったので,Gail と1対1でとりあえずアイディアとアプローチを説明.フィンランドから来てる別のポスドクの人も似たアイディア(だけど,だいぶ違うアプローチ)を持っているようなので,相補的になるかもしれないね,という話になる.

AOASIA2007 向け原稿のα版は6月1日くらいには書こうか,という話になった.よく考えたらあと二週間しかないから,ちょっとがんばらないといけない.


2006-05-17 [長年日記]

_ タイムゾーン的には

日本時間とずれているのを忘れて昨日書いてしまったので直しました.とりあえずカナダ時間で書くことにします.

_ [論文][ツール] ポインタ解析アルゴリズムのためのデータベースbddbddb

John Whaley, Monica S. Lam: Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams.

Proceedings of PLDI 2004, pp. , Washington, DC, USA, June 2004.

いわゆるポインタ解析アルゴリズム(Points-To Set Analysis)の提案論文.

最初に,recursive call がある部分はループになっている部分(Strongly Connected Components)を1ノードに置換することでaccyclic graphへ変換する.

次に,呼び出し場所が違う場合,メソッドのグラフを呼び出し箇所ごとに丸ごとコピーする("Cloning-Based"と言っているのはそのため).

これらの作業の結果,Call Path ごとに完全に独立したグラフが出来上がる.この上で context-insensitive 解析を実行すれば,context-sensitive な結果が得られることになる.

ただし,普通にコピー操作を実行してしまうと必要な記憶容量が膨大になってしまうので,BDD-Based Deductive DataBase(略して bddbddb)を使ってデータを保存し,その上で論理型言語のDatalogを使ってデータ操作することを提案している.Datalogのプログラムのうち,特定のサブセットだけを扱うことでパフォーマンス向上している様子.

論文は,上記のアイディアと,Datalog言語で定義された解析アルゴリズムを解説している.,基本の代入関係から Points-To 解析をすることで型の到達可能性をちゃんと考慮したコールグラフを作成し,そこから必要なコピー操作を行ってグラフを call path 単位に分解し,その上で context-insensitive な points-to 解析を行う.

アプローチとしては,context-sensitive にしようとしたときのデータ量の爆発を BDD によって抑えようというものだと考えられる.Datalog はリレーショナル代数の処理を書きやすく,リレーションをBDD上で表現して,DatalogをBDD上の操作にマップするというところが工夫で,しかもDatalogを使ってアルゴリズムが比較的簡潔に示されている点はけっこうえらい(AからBに代入があって,BからCに代入があるときAからCに代入があると考える,といったようなルールをDatalogは簡潔に記述できる).

bddbddb 自体は,β版という位置づけだが,sourceforge で公開されている.使い方については,ドキュメントがあまりちゃんと用意されてないので,ちょっと調査中.正直,パフォーマンス上の工夫が凝らされた解析ツールは貴重な存在なので,今回は少しまじめに調べている.


2006-05-20 [長年日記]

_ Nitobe Memorial Garden

滞在してるところから本当に近距離(歩いて5分くらい?)にあったので,行ってきた.良い庭園だったので,秋の紅葉シーズンになったらまた行くかも.

_ [ツール] bddbddb 使ってみました

解析ツールは,joeq_core として別途配布されているので,bddbddb-full.jar だけ取ってきても Java 解析はできません.基本的に cvs を使って bddbddb と関連パッケージを一式 Eclipse に取り込んでから使うという形式が正しいみたいです.

Java バイトコードを解析ツールに食わせるとコールグラフと bdd ファイルが生成されます.コールグラフ自体,多態性を解決できる範囲で解決されているので,これ単体でもけっこう便利そうな印象.

出力された bdd ファイルに対して points-to set analyzis の datalog ファイルを与えるとそれなりに動作します.ただし,bddbddb が依存するパッケージ javabdd をちゃんと用意することと,例として配布されてる datalog ファイルそのままだと微妙なエラーが出たりするというところは,ちょっと厄介です.

また,bdd 1個はリレーション(リレーショナル代数でいうところのリレーション)を表現しており,bdd エンコードされたものを tuple のリストに変換して,tuple に入ってる整数値が意味する中身を map ファイルから探してくることで,中身のデコードができます.ただし,context-sensitive な解析結果などは,コンテキストの数が多すぎてデコードできませんが.何に使うかちゃんと決めて,できる限り datalog で処理をして,最後にデコードしないと役に立たないようです.

この辺の使い方については,あとで文書としてちゃんとまとめます.

ちなみに,メモリは512MBくらいは割り当てないと,厳しいようです.でも,小規模なプログラム(ライブラリ含めてメソッド数1万程度)ならノートPCでも数分で処理が終わるので,そんなに負荷は高くないといえるかもしれません.処理用の別PCがほしくなるくらいには負荷がかかりますが.


2006-05-27 [長年日記]

_ [ツール] bddbddbの使い方

Java コードを joeq/bddbddb で解析したいーという人向けに,how to use bddbddb for java software analysisというメモ書きを作ってみました.日本語・英語両方あります.

急いで書いたんで間違いがなければいいですが.何か発見されたら,ご連絡ください.


2006-05-29 [長年日記]

_ [hyCalendar] 今後の改造プラン

メールで質問を受けて気づいたのですが,今まで「隔週予定」はあっても「5日ごとの予定」とかは書けなかったんですね.30日ごとにチャージしなおす必要があるプリペイドSIMを買ってみたところなので,ちょっと対応してみようかと思います.

ただし,現在は単体テストの導入に向けてかなり大規模な改修を加えている真っ最中です.本業の都合も強く影響しているので,次のリリースはまだ少し(かなり?)先になる予定です.

_ [論文] 良いテスト集合の選択基準の提案

Benoit Baudry and Franck Fleurey, Yves Le Traon: Improving Test Suites for Efficient Fault Localization.

Proceedings of ICSE 2006, pp.82-91, Shanghai, China, May 2006.

各ステートメントに対して「成功/失敗したテストケースの数」をカウント・比較することで「疑わしさ」を計算し,調査すべき対象のステートメントを推薦することができる.しかし,下手にテストを用意すると,ほとんどの文が同じ「疑わしさ」を持ってしまって役に立たないため,疑わしい文とそうでない文をうまく区別できるような良いテスト集合を作ろう,という論文.

論文では,テストケースの最適化の基準の提案と,それを用いることで「バグを発見するまでに調べなければならなかったステートメントの数」がどのくらい小さくなったかを実験している.

この論文では,テストケースの良さの基準を「Dynamic Basic Block(DBB)」と名づけている.DBBは,あるテスト集合に対して,まったく同じテストケースによってカバーされるような文の集合のことを指す.

たとえば,文 p, q, r, s に対してテスト3つのカバレッジが t1 = (p, q, r, s),t2 = (p, q, r) ,t3 = (r, s) だったとすると,(t1, t2) によってカバーされる (p, q),(t1, t2, t3) によってカバーされる(r), (t1, t3) によってカバーされる(s) という3つの Dynamic Basic Block が得られる.(p, q) の片方だけを実行するようなテストケースが作れなければ,これらは区分できないので,同じブロックに属し,「疑わしさ」度合いが常に同じ値になる.

Dynamic Basic Block の数が大きい(1つの集合が少数の文しか含まない)テスト集合というのは,テストごとに違う文の集合を実行することになるので,各文ごとのテストの成功・失敗数をカウントする方法による調査が容易なテスト集合であると考えられる.

この論文では,テストケースを遺伝的アルゴリズムで選ぶ・生成する方法によってテスト集合を洗練する実験を行っている.その評価基準として Dynamic Basic Block を使っており,従来手法より,調べるべきステートメント数を減らせるような少数のテストケースを選択することに成功している.

「良いテスト集合」を得るまでは,カバレッジ計算のためにひたすらテスト実行する必要はあるのが個人的には気になるけれど……,そこは人間の仕事ではないからOKという立場でもいいのかもしれない.