netail.net
自作フリーソフトや，ゲームに関する雑記を公開してます．
日記はソフトウェア工学の論文ネタが中心です．
最近のお知らせ (古いものはこちら)
2004-04-26 古い日記からの変換データ [長年日記] ▲
_ 論文 ▲
Thomas Reps and Genevieve Rosay:Precise Interprocedural Chopping.Proceedings of 3rd FSE, 1995.
Program Chopping というのは，プログラムスライシングの forward と backward を組み合わせて「ある文 s からある文 t までデータが到達する経路」となる．で，Jackson and Rollins がオリジナルを提案したのだが，彼らは intraprocedural なものしか考えていなかったので手続き間でも使えるように変更しました，というもの．
基本の考え方は，手続き内では依存関係を summary edge という形式で作成して，手続き間をcall，parameter in/out で接続したもの．
しかし，実験結果を見た限りでは，えらく時間がかかっている気がする．realizable path を探すために，メソッドの call/return の対応を取りながらグラフの traversal をする必要があるので，実はスライスよりも計算は難しいらしい．
単純にスライスで得られた頂点の積集合を取るだけだと「到達するかもしれない」集合が大きくなりすぎて駄目ということなのだろうか．
_ 論文 ▲
Kim Mens, Bernard Poll, Sebastian Gonzalez:Using Intentional Source-Code Viewsto Aid Software Maintenance.Proceedings of ICSM 2003, pp.169-178.
"intentional source-code view" というのは開発者がある目的のためにソースコード中を抽出したもの．論理型言語を使って結果を抽出し，それに加えて incremental に例外要素の追加・削除を行う．
ケーススタディとして，コード自動生成した部分と手動部分の切り分けとか，コーディング基準が維持されているかどうかとか，実は AspectJ の declare warning などの活用でやっていることに近い気がする．
関連研究として一番近いものが Conceptual Module．論理型言語を使ってモジュールを抽出するという点で同じ．次に Concern Graph．ただし，粒度が違っていて，Conceptual Module は正規表現での行単位マッチに制約されていたりConcern Graph はエンティティ間の関係が限られているといった理由から，提案手法が一番使いやすい，と主張している．わりともっともらしい．ただ，論理型言語の性能は，使える述語次第という気もするが．
その他の関連研究としては，Aspect Browser，Subject-Oriented Programming，データベースにおけるビュー管理やGrundy らのソースコードビューに関する非一貫性の管理とかが挙げられている．
2004-04-25 古い日記からの変換データ [長年日記] ▲
_ 論文 ▲
David Binkley and Mark Harman. Results From a Large-Scale Study of PerformanceOptimization Techniques for Source Code Analyses Based on Graph Reachability Algorithms. 3rd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2003). 27th September 2003, Amsterdam, Netherlands. pages 203-212.
大規模 C プログラムに対するスライス計算をするときに，グラフを事前にどういじったらどのくらい高速化したか，という最適化の実験の話．
Strongly Connected Components の接続の１頂点化，SCC に対するデータ構造的なサポート導入，頂点のトポロジカルソート導入，推移的な辺の除去，というようにだんだん最適化している．
実験の適用対象はけっこう大規模で（というか他の論文と同じだが）100万行分くらい．とはいえ，全部で100万行なので，この書き方は誤解を招きそう．平均的には，３倍くらいの高速化をしている．
例によって，評価している時間はスライス計算の時間のみでグラフ構築時間を見ていない．実はグラフ構築に激しく時間かかってたりしないよなぁ，とちょっと邪推したくなるのだが．CodeSurfer を使ってる人たちで，SDG (System Dependence Graph) 構築時間について言及している人を，あまり見たことがない．昔はとても遅かったらしいが，今はどうなんだろう．
_ 論文 ▲
Laura K. Dillon, R.E.Kurt Stirewalt:Lightweight Analysis of Operational SpecificationsUsing Inference Graphs.
Operational Specifications というのはLOTOS などの形式言語のことらしく，色々な言語に対応するために式評価を Inference Graph としてアーキテクチャ構築で使うコンポーネント図みたいな部品を合成したデータフローグラフとして表現すれば，入力値が要らないものから順番に評価していけば結果が取れますね，という感じ．
何が lightweight なのかはよく分からないが，ルールベースで自動生成するところなのだろうか．inference graph の有用性はいまひとつ分からない．
_ 論文 ▲
David Binkley and Mark Harman. An Empirical Study of Predicate Dependence Levels and Trends 25th IEEE/ACM International Conference on Software Engineering (ICSE 2003). 3-10 May, 2003. Portland, Oregon, USA, Pages 330-339.
プログラムの中に登場する predicate から参照できる Formal parameters の数と，predicate で実際に使われるパラメータの数に関する統計を取ってみた，という論文．predicate の定義が曖昧だが，たぶん if など制御文などで使われる変数式全般．
対象のプログラムは20個の C プログラムで，最大で160KLOCくらい．Predicates per KLOC はどのプログラムでも変わらなかったらしい．
で，結果としては，使えるパラメータ数が増えていくに従って，だんだん参照可能なパラメータは増えていくが，実際に使われるパラメータはあまり増えないので，コンテキストへの依存度（使われる率）は下がっていくらしい．ただし，グローバル変数に関してはそういう関係がなく，グローバル変数が増えるほど使われる傾向にあったらしい．
で，依存度が低ければスライスサイズなども小さくなるので人間の労力を大きく削減できるだろう，ということになる．参照可能な Parameter の数さえ数えればだいたいの傾向がわかって，しかもそんなに計算コストは高くないので便利そう？これ単体で，どうこうできるものではないような気もするが．
_ 論文 ▲
David Binkley, Mark Harman:A Large-Scale Empirical Study of Forward and Backward Static Slice Size and Context Sensitivity.19th IEEE International Conference on Software Maintenance (ICSM 2003). Amsterdam, The Netherlands, 22-26 September 2003. Pages 44-53.
プログラムスライスを全部のスライス基点から計算することで統計的に比較をしている論文．実験時のスライス基点については，基点の選び方が効いてくるので，とりあえず全部計算するのがいい，と思っている様子．
対象プログラムは C で書かれた43プログラム，合計100万行ばかり．静的スライスの計算は CodeSurfer で計算されたもの．グラフ中でループになっているようなStrongly Connected Components (SCC) を１頂点として集約して，手続き内頂点はトポロジカルソートしてから，計算している．
グラフ構築は置いておいて，計算そのものは平均 3000KLOC/sec くらいのペースで処理が進んだらしい．(大きいものほど遅くて，100KLOC/sec を切るものもいくつか)
スライスサイズは，プログラム全体の７％~６０％程度．また，context-sensitive （ある手続きに複数の呼び出し文があるときにそれらを区別する）を省略すると，スライスサイズが sensitive なときの50％増しくらい（物によっては数倍）になったらしい．
ちなみに，forward slice と backward slice とを比べるとforward slice のほうがサイズが小さくなるらしい．何となく正しいような気はするけど．
context-sensitivity に関しては色々研究があるらしくて，呼び出し列を call string という文脈自由文法扱いにしてスライスサイズを減らすための情報に使うらしい．引用されているのは次の二つ．
Krinke, J.: Evaluation context-sensitive slicing and chopping. ICSM 2002, pp.22-31.
Agrawal, G. and Guo, L.: Evaluating explicitly context-sensitive program slicing. Workshop on Program Analysis for Software Tools and Engineering, pp.6-12, 2001.
2004-04-24 古い日記からの変換データ [長年日記] ▲
_ 論文 ▲
プログラム依存グラフの計算簡略化のための方法を探して論文読み．
Mark Harman, Rob Hierons, Sebastian Danicic, Mike Laurence, John Howroyd and Chris Fox: Node Coarsening Calculi for Program Slicing.
8th IEEE Working Conference on Reverse Engineering (WCRE 2001). 2-5 October 2001, Stuttgart, Germany, 2001. Pages 25-34.
制御フローグラフに対して，隣接したノードを集約していくことでノード数を減らしていこうというもの．そのときに，一貫性を維持した中で一番良い結果を出すような方法を考えましょう，というもの．集約時に少しだけ不正確な結果が加わるが，それでも集約を重視するという姿勢．
R-Coarsening という手法をケーススタディ形式で紹介している．
Rb = ( I, D, d, R ) I = ノードのラベル集合 D = そのノードが実行されたときに必ず定義される変数 d = そのノードで定義されることがある変数（Dの要素もすべて含む） R = 参照される変数
という四項組を定義して，
Assignment: v := f(R) --> Rb({f}, {v}, {v}, R)
b1 = Rb(I1, D1, d1, R1), b2 = Rb(I2, D2, d2, R2)
とすると
Sequence: b1;b2
--> Rb(I1∪I2, D1∪D2, d1∪d2, R1∪(R2-D1))
Conditional: if p(R) then b1 else b2
--> Rb({p}∪I1∪I2, D1∩D2, d1∪d2, R∪R1∪R2)
注: D = D1∩D2 なのは，if なので分岐の両方でも更新されるものだけということ.
Loop: while p(R') do b
--> Rb( {p}∪I,φ,d, R∪R')
というようにルールを定義する．論文ではこれが一貫性があって，しかもできうる限りでは最適であるという証明も付属している．ただ，Minimalではない(スライス結果に関係ない文が含まれることがある）．
関連研究としてCFGのグラフ上での変換作業が載っていて，グラフ操作では不必要に不正確になる可能性があることに言及している．
ちなみに，この粗粒度化の方法自体の適用についてどのくらい時間がかかるかは不明．どのくらい粗粒度化するのかとかに依存か．制御フローグラフ構築時にいきなりこれを意識しながら作業すれば，そんなにコストはかからないかもしれない？
そのうち引用することになりそう．
2004-04-23 古い日記からの変換データ [長年日記] ▲
_ The Darwin Award ▲
リアルタイム UML 第２版 p.270 に記載されている「自動車が時速300参る（時速480km程度）で走行することはありません．[注６]」のネタの出所をつい調べてしまった．
http://www.darwinawards.com/darwin/index_darwin1994.html
_ 読書 ▲
研究室に置いてあった「リアルタイムUML第２版」（翔泳社）を読んでみた．ちなみに原著は：Real-Time UML, Second EditionDeveloping Efficient Objects for Embedded Systems.
リアルタイムシステムだから，何か特別なことでも入るかと思ったら，意外とそうでもなかった．（実時間に関する情報が UML 上に埋め込まれているくらいか）
とりあえず，何となく忘れそうになってたことをいくつか再確認．
- オブジェクトのクラスがオブジェクトの債務を規定できるのは，それらのオブジェクトがすべて同じコンテキストで同じように使われる場合のみ
- ひとつのオブジェクトが複数のインタフェースを備えることもある（ソースコード上では区別は付かない場合もあるかもしれないが）……実は自動で分割できると嬉しいかな．嬉しくないかな．
- アクティブオブジェクトとパッシブオブジェクトアクティブなほうは，自律的でイベントを発生させたり，システムの全体を構成する役割を持つパッシブのほうは，クライアントにサービスを提供する
- オブジェクトは債務を果たさなくてはならない．そのために必要な情報を持たなくてはならない．
- 継承による拡張と特化 拡張 = 新しい振る舞いを追加する 特化 = 親クラスの振る舞いを置き換える（ただし Liskov の置換原理は守る）
- アーキテクチャ設計とは，システムを構成するための戦略の決定．たとえばオブジェクトをレイヤ形式で配置するとか，オブジェクト間の接続をオブジェクトブローカーに任せるとか．
- メカニズム設計：コラボレーション（一連の協調動作を行うオブジェクト群）の設計．ただし，同じロールを担当する交換可能なクラスが複数存在するとき，それはパターンとなる．少数のスコープに限定されたパターンをメカニズムと呼ぶ．メカニズム設計として，オブジェクトがどのように協調するかを決定する．
- 詳細設計：データ構造の決定，精度や値域の確定，アルゴリズムの決定．関連，操作，可視性の決定，例外の決定（誰が送出し，誰が捕捉するか）．
2004-04-22 古い日記からの変換データ [長年日記] ▲
2004-04-21 古い日記からの変換データ [長年日記] ▲
_ 論文 ▲
Marek Majkut:Generation of Implementation for the Model Driven Architecture with Syntactic Unit Trees.
なぜかファイルにはさまってた．読み忘れていたのか，それとも読んだが意味がなかったのか．
Syntactic Unit と呼んでいるのはようはテンプレート（スケルトン）コードで，UMLの図からテンプレートの中身を埋めるという話．
どうやって図にコードを対応させるのか，というあたりの具体性があまりない．
_ 論文 ▲
査読の都合で，Cohesion 話の論文をチェック．
Jianjun Zhao, Baowen Xu:Measuring Aspect Cohesion.FASE 2004.
・データの依存関係があるか・呼び出し関係があるかといった関係をもとに，スコアを重み付きで足しこんで 0~1 の範囲で計算する．AOP な適用部分は，アドバイスを扱うこととまた inter-type declaration をアスペクトの一部とみなすこと，だろうか．pointcut 定義についての扱いをどうするべきかはけっこう微妙な気がする．「いつ呼ばれるか」という意味では，外側に影響しているだけなので coupling のほうにしか影響しないのかもしれないが，同一 pointcut にふたつのアドバイスが存在する場合のほうがふたつ，関係ないアドバイスがあるよりはcohesion が高いような気もする．少し怪しいが．
