CPS Conversion of Imperative Language with Exception Handling and Its Formalization

IPSJ Web Site 19 References

Bibliographic Information

Other Title
  • 例外処理機構を備えた命令型言語のCPS変換とその定式化
  • レイガイ ショリ キコウ オ ソナエタ メイレイガタ ゲンゴ ノ CPS ヘンカン ト ソノ テイシキカ

Search this article

Description

制御フローグラフに類似した一般的な命令型言語を，CPS（継続渡しスタイル）を中間表現としてコンパイルする方法を提案する．CPS とは，「残りの計算」（継続と呼ばれる）を表現する関数を生成することにより，すべての関数呼び出しや条件分岐を末尾位置においた関数型言語の一種であり，Scheme やML といった関数型言語のコンパイラに広く用いられている．命令型言語をCPS に変換することで，スタックフレームや例外ハンドラが継続として明示化され，関数適用や例外処理における複雑な制御の流れが明確化される．結果として，インライン展開や末尾呼び出し最適化を含む多くの最適化が容易に実現できる．我々は命令型言語をCPS に変換する過程の単純な定式化を与え，その正しさを証明する．

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.

Journal

References(19)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top