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

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

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





［推薦理由］

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