日時：2004年10月 7日(木) 18:30から
場所：理窓会館（東京神楽坂） 4階 理科大第 3会議室
JR 中央線飯田橋駅の市ヶ谷寄りの改札から出て向かって右側へ
進み, 神楽坂を登って仲通りへ右折してください.
http://www.hq.sut.ac.jp/~risokai/kaikan.html
に案内図と建物外観の写真があります.
この案内図にある神楽坂と仲通りの角のコンビニはサークル K です.
(少なくとも 8月末にはサークル K でした。その後、サンクスと合併
しているので、改装されている可能性もありますが...)
食事： ありません．飯田橋駅周辺のマクドナルドなどの他、神楽坂には飲食店が
多数ございますので、そちらをご利用ください.
◆発表その 1
話者：
滝本 宗宏(東京理科大学理工学部情報科学科)
題名：
疎な要求駆動型データフロー解析とその応用
概要：
プログラム解析やコード最適化における解析では，データフロー解析が
多く用いられてきた．データフロー解析は，解析対象の情報をプログラ
ム全体から集めることを仮定しているので，プログラムの一部分につい
て解析を行いたい場合や，一部の解析結果を用いてプログラムを変形し，
さらに変形後のプログラム上で他の部分の解析を行うことを繰り返す場
合には，余分なコストが必要になる．このような場合には，情報を必要
とするプログラム点に影響を及ぼしている部分だけを解析する要求駆動
型のデータフロー解析が有効である．しかしながら，データフロー解析
には，1ワード分の情報を並列計算するビットベクタ法や，解析に不要な
部分を訪問せずに解析を行う疎な解析法が存在するのに対して，要求駆
動型のデータフロー解析には，高速化手法が存在しないという問題があっ
た．
本発表では，解析に不要なプログラム点を訪問しない疎な要求駆動型の
データフロー解析を提案する．あるプログラム点について行った解析の
結果によってプログラムを変形する場合，他のプログラム点についての
解析に不要な部分も変わる可能性がある．本手法では，プログラムの深
さに相当するランク情報を用いて不要なプログラム点を動的に計算する
発見的手法を導入する．
◆発表その 2
話者：
山口 文彦(東京理科大学理工学部情報科学科)
題名：
Recognizable な木言語の表現
概要：
木構造はデータ構造として広く用いられており、特に近年では XML の普及などに
よって、木構造を持つデータを処理する要請が多いものと考えられる。
プログラムを作成する際や検索を行う際に、文字列の集合を表す手段としては
正規表現が用いられている。特に 1行程度の簡単な記述が頻繁に利用されている。
そこで本発表では、木の集合を記号列で表現する方法を紹介し、その記法が、
木において regular set に相当する recognizable set を表現していることを
直感的に説明したいと考えている。
さらに、木オートマトンの理論における伝統的な木の扱い方と実際的なデータとの
違いをいくつか指摘して、木言語の表現の拡張について述べる。
出席者：17名
和田英一（IIJ），伊知地宏（ラムダ数教研），紀信邦（ケイエルエス研究所），
太田真，延澤志保（東京理科大），石畑清（明治大），河邊昌彦（早稲田大），
小林良岳，鈴木信吾，多田好克，寺田実，丸山一貴（電通大），
繁富利恵，副田俊介，田中哲朗，林芳樹，筧 一彦（東大）
◆発表その 1（滝本さん，「疎な要求駆動型データフロー解析とその応用」）
- SSAではφが出てくるが，本研究の場合にはどうなるか． A:φ関数は，目的コード上では除去されている．φ関数の除去は，φ関 数が出現しているCFG節の先行節pに，pに対応するφ関数の 引数a_pをφ関数の代入先vに代入するコピー代入v:=a_pを挿入すること によって行う（この説明は，単純化したものであり，COINSが実装してい るφ関数の除去法は，より複雑である）． - bit vector(= rank)の長さは，例えばSPECのものなどではどれくらいになるか． 変数のbit vectorより小さくなるか． A:rankサイズは，測定したSPECで見る限り，64を越えていなかった．し たがって，今回の実験では，Javaのlongサイズに収まっている． もしその長さを超えてしまった場合どうなるか． A:各ワードを繰り返しチェックすることになる．定数コストでチェック する方法もあるが，rank情報を更新するコストが増えるという問題がある． - 解析の速度比較はあったが，結果として得られるobject codeを比較すると どうなるか． A:デモで行った最適化の効果は，従来法を繰り返し適用すれば得ること ができる．本研究は，最適化時間の低減に新規性がある． - COINS自体を最適化してみてはどうか． A:COINSはJavaで実装されており，COINSのフロントエンドとしてJavaを 実装する予定であるが，現時点ではフロントエンドが完成しておらず，実験 は不可能である．
◆発表その 2（山口さん，「Recognizable な木言語の表現」）
- 実用を考えると, ad Hoc な拡張を多く必要とする. ad Hoc な書き方の
部分も含めて, 統一的な書き方ができないか.
A:木構造で表現できるものであれば, Recognizable Expression とのマッチを
考えることができるが, 木での表現が書き易いかどうか, わからない.
- 文字列では, 正規表現の枠を越えた表記が, すでに多く使われている
XML では, 例えば HTML の下に, どんな順番でも HEAD と BODY が 1つずつ
登場するものを検索したい. それは(下降型有限状態)木オートマトンでは
書けない.
A:ここから始めるという立場のつもりで話をした. 今後, 他の(下降型有限状態
以外の)木オートマトンを考えるか, 木オートマトンから離れるか, という
選択はあると思う.
- こんな使い方で有効, という例は何かあるか
A:まだ, 見つかっていない. むしろ, TABLE の転置のような簡単なものでも,
置換だけでは書けないことが分かっている.
例えば, 正規表現が perl スクリプトの中で使われるように,
Recognizable Expression の外側に計算機があって, そこの
プログラミングが簡単になればいいと思う.
- 正規表現と同じ記号を違う意味で使っているので, 分かりにくくなっている.
しかも正規表現も使う.
A:たしかに, その通りです...
- Recognizable Expression の * は, 正規表現の * と対応するのか?
A:monadicな(1列になっている)木において, 対応すると考えてよい.
正規表現では, * は 1つ前の表現の 0回以上の繰り返しで, 複数の表現の連接を
繰り返す場合は()を用いて括る. Recognizable Expression では () で括る
代わりに, いくつ前までを繰り返すかを * の個数で表している. また,
Recognizable Expression の * は 1回以上の繰り返しだが, 必ず和とペアに
なっていて, * を含まない Recognizable Expression を選ぶことで 0回が
表される.
- 木の深さ方向への繰り返しが表現できているということか.
A:その通り. 引数を線形リストで表現すれば, 横(右)方向への繰り返しを,
深さ方向への繰り返しと考えることができる. 実は, いまのところ @ (splice)も,
リストの末尾でしか使っていない. リストの途中に @ が登場すると
下降型有限状態木オートマトンの範疇を超える(そういう拡張をしてもよいと
思う). その拡張をすれば, 左方向への繰り返しも記述できると考えられる。
- Recognizable Tree Expression なら, 判別可能木表現で, 日本語としても
おかしくないのでは?
- XML なんて汚いものに, まじめに取り組まなくても?