「Ordered Types for Stream Processing of Tree-Structured Data」

2011年度論文賞受賞者の紹介

「Ordered Types for Stream Processing of Tree-Structured Data」

[Journal of Information Processing Vol.19, pp.74-87]
[論文概要]

 木構造処理プログラムからストリーム処理プログラムへの型に基づく自動変換の枠組みが末永らによって提案されている.彼らの枠組みでは,入力木をストリームから読めるように,木構造処理プログラムが入力木を左から右の深さ優先順序でただ一度だけ読み込むということを順序付き線形型を用いて保証している.しかし,彼らの変換では無駄なバッファリングが挿入されることがある.本論文では,順序付き線形型に加え順序付き非線形型を導入することによって,彼らの枠組みを拡張した.この拡張した枠組みによって無駄なバッファリングを減らすことができ,より効率の良いストリーム処理プログラムを生成できる.





[推薦理由]

 本論文は木構造処理プログラムを効率的なストリーム処理プログラムに変換する系統的な手法を提案している.既存手法は順序付き線形型に基づいているため,木構造は連続的に一度しかアクセスできず,その結果,木構造全体をメモリに保持しなければならない場合があった.本論文では,順序付き線 形型システムを拡張し,順序付き非線形型システムを用いることで,木構造の一部分をメモリに蓄え,任意のアクセスを可能にした.その結果,メモリの使用法を最適化することが可能となった.実験により,ある種のプログラムに対しては提案手法の効果は絶大であることが示された.本論文のプログラム変換手法は線形型の興味深い応用の一つであり,論文賞に値する.

佐藤亮介 君

 1985年生.東北大学工学部2008年卒.東北大学大学院情報科学研究科情報基礎科学専攻博士課程前期3年の課程2010年修了.東北大学大学院情報科学研究科情報基礎科学専攻博士課程後期3年の課程在学中.ソフトウェアの形式的検証に興味を持つ.

末永幸平 君

 1979年生。東京大学理学部情報科学科2003年卒。東京大学大学院情報理工学系研究科コンピュータ科学専攻博士課程2008年修了。博士(情報理工学)。日本IBM東京基礎研究所、リスボン大学、日本学術振興会特別研究員 (PD) を経て、2012年4月より京都大学白眉センター特定助教。 ソフトウェア、ハイブリッドシステムの形式的検証に興味を持つ。

小林直樹 君

 1968年生.1993年東京大学大学院理学系研究科情報科学専攻修士課程修了.東京大学助手,講師,東京工業大学助教授,東北大学教授を経て2012年4月より東京大学大学院情報理工学系研究科教授に就任,現在に至る.博士(理学).ソフトウェアの基礎理論に興味を持つ.日本IBM科学賞,日本学術振興会賞などを受賞.