netail.net
自作フリーソフトや，ゲームに関する雑記を公開してます．
日記はソフトウェア工学の論文ネタが中心です．
最近のお知らせ (古いものはこちら)
2004-06-07 古い日記からの変換データ ▲
_ [論文]ソースコード編集作業の分析 ▲
aosd-discuss ML で紹介されていた論文をちらっと読んでみる．
Martin P. Robillard, Gail C. Murphy:Automatically Inferring Concern Code from Program Investigation Activities.Proceedings of 18th International Conference on Automated Software Engineering, pp.225-234, October 2003.
ある concern に関係したコードを変更するとき，複数の場所に分散したコードをあちこち見たりしながら作業を進めていくのが普通なので，そのエディタの操作情報を集めていくことで（どんなソースコードを見ていったか記録することで），その作業時に必要な情報はどのあたりにあるのか，とか開発者の作業を補助しようというもの．
修正作業を，調査イベントの順序付き集合transcript E = { e1, e2, ..., en } として捉えると，イベント e = (D, c, X) はc がアクションの種類（エディタの切り替えとか検索とか）でD がエディタに表示されているメソッド，フィールドでX がアクションごとの追加情報（検索して見つけたメソッドとか）．で，検索対象として見つかったようなエレメントのほうが重みを大きくして，どれかを見ただろうという確率を計算する．
で，全イベントで１度でも閲覧された要素をリストアップして，各要素間の関係の強さを計算する．ある二つの要素について，一方を閲覧したアクションの次のアクションでもう一方を閲覧していたら，何らかの関係があるだろう，と考える．
途中の重み計算のパラメータの影響を強く受けているみたいだが，探している作業という頼りないものがベースのわりにはそれなりの結果が出ている気がする．ただ，いつからが調査でいつからがコーディングだとかいった情報がそれなりに必要？また，false positive も出てしまう（仕方がないが）．
単体で使うよりは，他と組み合わせたほうがうれしいかもしれない．スライシングとか concept analysis とか．個人的には面白いと思うけど．
プログラム変更履歴における「誰々もこの辺りを見ていたよ」という協調フィルタリングにノリとしては近いかもしれない．
_ ニュース ▲
コンピュータの埃からの有害物質の検出とかの話．
具体的数値とか載ってます．http://www.computertakeback.com/the_problem/bfr.cfm
ネタはこちら．http://nikkeibp.jp/wcs/leaf/CID/onair/jp/it/311922
部室とかで多数の PC を一度に掃除するときは少し気をつけたほうがいいかも？
_ 日記CGI ▲
国際会議があるたびに論文ネタで埋め尽くされてしまうので，やっぱりカテゴリごとの最終更新くらいは表示されるようにしようかしら．
実体データは XML なのでカテゴリ情報とかの追加は楽なのだが，そこから最新情報だけ切り出しておくのが面倒だったりする．今のところカテゴリ割り当ても何もやってないし．
_ 論文 ▲
ICSE 2004 Technical Papers, Emirical Methods より．
Parastoo Mohagheghi, Reidar Conradi, Ole M. Kili, Henrik Schwarz:An Empirical Study of Software Reuse vs. Defect-Density and Stability.Proceedings of ICSE 2004, pp.282-291.
ソフトウェアの再利用は品質向上に役立つのか？という仮説に対する実験論文．数値の材料としては defect-density （コード量に対する問題の個数）を使う．
１社（Ericsson）のプロジェクトデータなのでexternal validity としては注意が必要だが，この手の実験データを出してる論文は少ないので比較しようがない気がする．
Accept された仮説:再利用コンポーネントは，non-reused コンポーネントと比べて低い defect-density となる．
Reject された仮設:再利用コンポーネントの defect-density はnon-reused コンポーネントと同じである．
non-reused コンポーネントについて，欠陥の個数と，コンポーネントのサイズは関係しない．
再利用コンポーネントとnon-reused コンポーネントは同じように変更される．
再利用コンポーネントのほうがnon-reused コンポーネントよりも変更される．
棄却できなかった仮説:すべてのコンポーネントについて，欠陥の個数と，コンポーネントのサイズは関連がない．
再利用されたコンポーネントについて，欠陥の個数と，コンポーネントのサイズは関連がない．
defect-density とコンポーネントのサイズは関連がない．（すべてのコンポーネントについての場合でも， また再利用コンポーネントに限った場合でも， non-reused に限った場合でも棄却できない）
_ 論文 ▲
ICSE 2004 Technical Papers, Unified Modeling Language より．
Tewfik Ziadi, Loic Helouet, Jean Marc Jezequel:Revisiting Statechart Synthesis with an Algebraic Approach.Proceedings of ICSE 2004, pp.242-
UML 2.0 シーケンス図からステートチャートを合成しようという試み．各オブジェクトに注目して，メッセージの送受信をイベントとみなして状態遷移が起こると考える．で，シナリオごとに生成したステートチャートを合成して大きなステートチャートを構成する．各シナリオの合成したシナリオ（シーケンス図を含んだシーケンス図）が記述できるようになったことや，ループ記述などができるようになったことが大きいらしい．
でもシーケンス図以外からなら（テキストなどで）合成はできたような気がするのだが……．新規性というか，ネタとしての新しさはあんまり感じられないが，実際にアルゴリズムを明示してがんばっているのはかなり偉いかも．
_ 論文 ▲
ICSE 2004 Technical Papers, Verification より．
Dimitra Giannakopoulou, Corina S. Pasareanu, Jamieson M. Cobleigh:Assume-guarantee Verification of Source Code with Design-Level Assumptions.Proceedings of ICSE 2004, p.211-220.
いわゆるモデルチェック手法．状態の爆発を防ぐために，Assume-guarantee 手法というのを用いている．具体的には，＜Ａ＞ Ｍ ＜Ｐ＞ という３項組で，モジュールＭが動作している環境で，仮定Ａが成立しているときＰが成立するのであれば式全体が true になる．で，二つ部品があるとき＜Ａ＞Ｍ1＜Ｐ＞＜true＞Ｍ2＜Ａ＞が両方とも成立しているのであれば＜true＞Ｍ1 + Ｍ2＜Ｐ＞ が成立する．確認したいプロパティＰが成立するかどうかはＭ1とＭ2についてそれぞれモデルチェックを行えばよいので問題の規模を小さくすることができる．途中の＜Ａ＞をうまく作れたら良い．
設計時は Labelled Transition System としてモデル構築して，実装時は，Ｍ1とＭ2に対応するコンポーネントを構築したら，メソッド単位の呼び出し監視とかを使って本当に条件を満たしているかどうかをテストする．
いちおう（１個だけ）実験もしていて，全体を検査するよりは分割しているほうが明らかにコスト的に優位に立っている．
アイディアとしては，モジュール単位での境界を置くタイプだが仮定Ａの作り方次第では，クラス単位などよりも自由な分割ができそうなので面白いかもしれない．
_ 論文 ▲
ICSE 2004 Technical Papers, Quality of Service より．
Eric Wohlstadter, Stefan Tai, Thomas Mikalsen, Isabelle Rouvelleou, and Premkumar Devanbu:GlueQoS: Middleware to Sweeten Quality-of-Service Policy Interactions.Proceedings of ICSE 2004, pp.189-199.
１つの Web サービスが１つのコンポーネントとみなせるようなサービス指向の環境下で，コンポーネント間でのQoS ポリシーの制御を行う手法．
基本的には，各コンポーネントごとに，サービスに関する述語（cpu_load ＜ 0.5 など）を記述して，ポリシーを呼び出す段階でマッチングを取ってコンポーネント間でのやり取りを行っても大丈夫かどうかをチェックする．
基本的にはコンポーネントと QoS 記述は分離しておくべきだという立場．QoS をサーバで集中管理するのは現実的でないので（今後分散環境での Web サービスが主流となると考えると），各コンポーネントが「自分はこういうポリシーだ」と持っている情報を交換できるようなミドルウェアでの実現となっている．
2006-06-07 ▲
_ [論文] Dominance Tree アルゴリズム系を探すのこと ▲
こちらで紹介されているDominance Treeを探索する反復アルゴリズムに相当するものをちゃんと論文にまとめている人を探してみたら，Keith D. Cooper, Timothy J. Harvey, Ken Kennedy: A Simple, Fast Dominance Algorithm. というのがどうやら同じようなものらしい．性能評価も付いている．
しかしこの論文，掲載先は SPE だと書いてあったにも関わらず，SPEの目次には載ってなかった．よく見たらVol.がなくてNo.だけあったり，pp.1-10って書いてあるのにPDFが28ページある．
あまりに怪しいので，関連を調べてみたたら，Finding Dominators in Practiceという論文が，K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Available online at http://www.cs.rice.edu/~keith/EMBED/dom.pdf.と引用していた．こちらの論文は，２フェイズに分けたDominanceツリー処理なんかの性能評価もしているので，こちらを引用したほうが無難かもしれない．
L. Georgiadis, R. F. Werneck, R. E. Tarjan, S. Triantafyllis and D. I. August: Finding Dominators in Practice. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA 2004), Lecture Notes in Computer Science, volume 3221, pages 677-688, Springer-Verlag, 2004.
