netail.net
自作フリーソフトや，ゲームに関する雑記を公開してます．
日記はソフトウェア工学の論文ネタが中心です．
最近のお知らせ (古いものはこちら)
2002-11-09 古い日記からの変換データ ▲
_ 読書 ▲
市役所まで出かけたついでに古本屋に立ち寄り．菊地秀行「マリオネットの譚詩（バラード）」（ソノラマ文庫），ひかわ玲子「少女の王国」（実業之日本社），の二冊を購入．
これで，さらに読書キューが長くなった :-)
2003-11-09 古い日記からの変換データ ▲
_ 論文 ▲
Frank Tip, Adam Kiezun, Dirk Baumer:Refactoring for Generalization using Type ConstraintsProceedings of OOPSLA 2003, pp.13-26
「インタフェースの抽出」リファクタリングを行ったときに，どの変数を，抽出されたインタフェースの型に直したらよいか，あるいはどのメソッドをそのインタフェースに引き上げるかといった決定をするために型制約を使うというもの．
具体的には，オブジェクト参照，戻り値，代入などからA <: B (A is-a B) 関係を決定していって，メソッドを引き上げた場合などにそれが違反されるので引き上げできない，といったことを調べることができる．
ただし，これらの型による制約とは別に，クラスやメンバーの可視性やオーバーロードの発生など考慮すべき要素はあるらしい．
どこまで作業を支援できるのか，というと微妙だが，型制約を調べるだけでもだいぶ助かりそうな気はする．
_ 論文 ▲
微妙に Constraints 関係で拾ってしまったので読んでみる．
Bjorn N. Freeman-BensonKaleidoscope: Mixing Objects, Constraints, and Imperative Programming.Proceedings of ECOOP/OOPSLA '90, pp.77-88
クラス定義にinitially ブロック中に初期の制約を書いたり，assert ... during ... といった微妙な制約が書ける．ただし，使いにくそうだけど．やっぱり記述がプログラムを書くときに直観的に書けそうなものでないと実際に言語として採用されることはないのかなぁ．
_ 論文 ▲
Manuel Fahndrich, K. Rustan M. Leino:Declaring and Checking Non-null Types in an Object-Oriented LanguageProceedings of OOPSLA 2003, pp.302-312
型 T の変数を，null 参照になることがないもの T- とnull 参照をする可能性がある T+ に区分して，
f.foo(); といった呼び出しがあるなら f は T- でなければならない，T- から T+ への代入は OK だが逆は危険，といった制約を型システム上で調べる．
また，コンストラクタなどの，未初期化フィールドが存在している可能性を T_raw とし，T_raw は初期化されたことを調べない限り（ASSERT_INIT を通さない限り）T へ代入できない，参照渡しや Generics，static class fields の扱いについても特別な処置が必要，といったことが議論されている．
コード上では型名の前に [Non-null] といった記述を付加することで簡単に示すことができ，フィールドの値が null でないことといったpre/post condition や，段階的な初期化などをするときに起こる「null が入っているかもしれない」問題に対処できる．
オブジェクト指向言語上でこういうことをやっている人というのは，実はいなかったらしい．
ちなみに，あるオブジェクトへのアクセスを独占しているかどうかをチェックするというのが次の文献にもあるらしい．Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjarne Steensgaard, and David Tarditi. Marmot:An optimizing compiler for Java, Software-Practice and Experience, 30(3), 2000.
_ 論文 ▲
Brian Demsky, Martin Rinard:Automatic Detection and Repair of Errors in Data Structures,Proceedings of OOPSLA 2003, pp.78-95
データ構造の制約を宣言的に記述しておいて，エラーが発生した場合は修復ルーチンを起動する，というような話．主にファイルシステムなど，何らかの原因で壊れる可能性があり，壊れたからといってシステムを止めるわけにはいかないものが主体．どちらかというと耐障害性系の話か．いちおう related work として assertion などの話も出ていて，状態チェックには自動生成したassertion と例外ハンドラを使いたい，みたいなことを言っている．
とりあえず，あまり関係なかったので読み流しておく．
_ 論文 ▲
Darko Marinov, Robert O'Callahan:OBject Equality ProfilingProceedings of OOPSLA 2003, pp.313-325
メモリ効率化のために，複数の同一状態のオブジェクトを同一に差し替える （merge する）というもの．そのためにいったん profiling をする必要がある．
オブジェクトがマージ可能であるには，二つのオブジェクトが・同一クラスのインスタンスで，・各フィールドの値が同じで，・参照しているオブジェクトがマージ可能で，・将来変更されることがなく，・オブジェクトの同一性が利用（identityHashCode 計算や == 比較) されないこと．
そして，オブジェクトが共有されている数と時間の積をmergeability と呼んで，最適化の度合いを表現するメトリクスとする．
モノによっては30~40％程度のメモリ空間を節約できるような場合もあるらしい．
・profiling 結果は実行系列に依存するので安全性にちょっと不安・プロファイラのコストがけっこう高い （実行が16秒程度のプログラムで30分近くかかったり， 30MB程度のメモリが1GB近くまで膨れたりする）というあたりは少し厳しいが，パフォーマンスクリティカルな場面なら使えるかも？
_ 論文 ▲
Dave Clarke, Michael Richmond, James Noble:Saving the World from Bad Beans:Devployment-Time Confinement Checking,Proceedings of OOPSLA 2003, pp.374-387
this 参照を直接返したりして EJB のコンテナの働きをバイパスしようとする Bean をどうにかして捕まえよう，ということで Confined Type のアイディアを使って Bean が confined であることを調べる．
定義上，confined なものと unconfined なものが行き来したりはしない，といったことを調べるわけだが，Deployment のタイミングで調べるというあたりがEJB ならでは，と言えるかも．
実は confined type に関する研究って流行ってる？
参考文献として，次の文献が挙がっていた．Confined Types in Javahttp://www.cs.purdue.edu/homes/jv/pubs/spe00-1.pdf
2005-11-09 ▲
_ [論文] 副作用のないメソッドの自動検出 ▲
Alexandru Salcianu and Martin Rinard: Purity and Side Effect Analysis for Java Programs.
Proceedings of the 6th International Conference on Verification, Model Checking and Abstract Interpretation. Paris, France January 2005.
外部に副作用を残さないメソッドを JML などでは pure メソッドと呼んで，アサーションの定義に使えるようにしているが，@pure の指定は手作業になる．それを自動的に検出する方法を提案している．既存の研究と異なる点は，メソッド内で新しいオブジェクトを確保したとき（一時使用のイテレータなど），そのオブジェクトに対するデータの書き込みは許容するところ．
各メソッドごとにどの変数がどのオブジェクトを指すかを示す Points-To グラフを構築しておき，メソッド呼び出し関係をたどるときに呼び出し側の Points-To グラフのノードと，呼び出し先のグラフとで，対応する引数やthis参照を接続することで，呼び出し先まで含んだ解析グラフにしていくらしい．末端にnativeメソッドが入ってしまうと解析できないので，いくつかには手であらかじめ定義したグラフを与えている．
