例外処理機構を備えた命令型言語のCPS変換とその定式化

• Item type: Trans(1)
• 公開日: 2004-11-15
• タイトル: 例外処理機構を備えた命令型言語のCPS変換とその定式化
• タイトル / 言語: en
• タイトル: CPS Conversion of Imperative Language with Exception Handling and Its Formalization
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: ペンシルバニア大学コンピュータ情報科学科
• 著者所属: 東京大学情報理工学系研究科コンピュータ科学専攻
• 著者所属: 東京大学情報理工学系研究科コンピュータ科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer and Information Science, University of Pennsylvania
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo
• 著者名: 住井英二郎; 大根田裕一; 米澤, 明憲
• 著者名(英): Eijiro, Sumii; Yuichi, Oneda; Akinori, Yonezawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 制御フローグラフに類似した一般的な命令型言語を，CPS（継続渡しスタイル）を中間表現としてコンパイルする方法を提案する．CPS とは，「残りの計算」（継続と呼ばれる）を表現する関数を生成することにより，すべての関数呼び出しや条件分岐を末尾位置においた関数型言語の一種であり，Scheme やML といった関数型言語のコンパイラに広く用いられている．命令型言語をCPS に変換することで，スタックフレームや例外ハンドラが継続として明示化され，関数適用や例外処理における複雑な制御の流れが明確化される．結果として，インライン展開や末尾呼び出し最適化を含む多くの最適化が容易に実現できる．我々は命令型言語をCPS に変換する過程の単純な定式化を与え，その正しさを証明する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a method of compiling a generic imperative language (similar to control flow graphs) by using CPS (continuation passing style) as an intermediate representation. CPS is a form of functional programs that puts all function calls and all conditional branches into tail positions by generating functions to represent “the rest of the computation” (called continuations). It is widely used as an intermediate representation in compilers of functional languages such as Scheme and ML. By translating an imperative language into CPS, complicated control flow as in function application and exception handling is clarified because activation records and exception handlers are made explicit as continuations. As a result, many optimizations including inline expansion and tail-call optimization can be easily implemented. We give a simple formulation to the process of converting the imperative language into CPS and prove its correctness.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 45, 号 SIG12(PRO23), p. 67-82, 発行日 2004-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会