平成１２年度未踏ソフトウェア創造事業


採択案件評価書

１．担当ＰＭ 　１２．湯淺　太一
２．採択者氏名 　山本　晃成　（株式会社数理システム)
３．ﾌﾟﾛｼﾞｪｸﾄ実施管理組織 　株式会社数理システム
４．委託金支払額 　10,828,242円
５．テーマ名 　「Java 仮想マシンの継続渡し機構拡張」
６．関連Webサイトへのリンク
７．テーマ概要

近代的なプログラミング言語のコンパイラ実装においては，継続渡し方式というコードを生成することが少なくない．関数や（オブジェクト指向機能の）メソッドを呼び出す際に，それらの実行が終了したあとに何をするかを表現する「継続」を受け渡すことによって，従来の単純なリターンよりも実行効率の良いコードを生成するものである．特に，末尾再帰的な呼出しが連続する場合は，継続の実行によって，複数のリターンを飛び越えて一気に呼出し元に戻ることが可能である．

本提案は，Java 仮想マシン（JVM）に継続実行の機能を付加することによって，JVM をターゲットとするコンパイラが，この継続渡し方式を採用できる環境を提供するものである．具体的には，



(1) 継続の捕捉と実行を行うための，バイトコード命令を JVM に追加する．

(2) 試験的なコンパイラを作成し，拡張した JVMにおいて継続渡し方式の実証実験を行う．


コンパイラの扱うプログラミング言語としては，とりあえず Scheme を念頭に置いているが，将来的には Java への適用も検討する．
８．採択理由

近代的なプログラミング言語のコンパイラ実装においては，継続渡し方式というコードを生成することが少なくない．関数や（オブジェクト指向機能の）メソッドを呼び出す際に，それらの実行が終了したあとに何をするかを表現する「継続」を受け渡すことによって，従来の単純なリターンよりも実行効率の良いコードを生成するものである．

特に，末尾再帰的な呼出しが連続する場合は，継続の実行によって，複数のリターンを飛び越えて一気に呼出し元に戻ることが可能である．

本提案は，Java 仮想マシン（JVM）に継続実行の機能を付加することによって，JVM をターゲットとするコンパイラが，この継続渡し方式を採用できる環境を提供するものである．


具体的には，

(1) 継続の捕捉と実行を行うための，バイトコード命令を JVM に追加する．

(2) 試験的なコンパイラを作成し，拡張した JVM において継続渡し方式の実証実験を行う．コンパイラの扱うプログラミング言語としては，とりあえず Scheme を念頭に置いているが，将来的には Java への適用も検討する．


その普及度から，Java のみならず，様々な言語を JVM に変換するコンパイラの検討が国内外で進められており，今回の提案によって，この方式の適用範囲が拡大し，プログラムの実行性能も向上することが期待される．申請者はこれまでに，Java を利用した仮想並列計算の実証実験を行った経験があり，半年という短期間ではあるが，提案事項の実現性はきわめて高い．また，プロジェクトの進行にあたっては，Java をターゲットとしたコンパイラや，継続渡し方式に近いコンパイラの開発経験が豊富な PMが，おおいに貢献できるものと思われる．
９.開発目標

Java仮想マシン上でスタックを消費しない適切な末尾再帰の最適化を行う事により，JVMバイトコードを出力するScheme処理系であるKawa の末尾再帰処理を高速にする．また，Java 言語からの継続の捕捉/実行を可能として一級継続を実現する．
１０．開発者への助言と指導

一級継続の実装に関して専門家の立場から助言を行い，本テーマに最適と考えられる incrementalstack/heap 方式の採用を提案した．この方式を実際の JVM に実装するにあたって，JVM のフレーム構造，Java とのインターフェイス，JVM の GC（ごみ集め）等に関して，開発者とともに検討し，実装の詳細を決定した．

末尾再帰の最適化については，JVM のフレームの再利用方式や末尾再帰のメソッド呼出し方法を，開発者とともに検討した．


また，実装結果の性能評価について考察を行い，一級継続を必要としない場合にも，今回の実装方式が JVM 一般の性能向上に有効であることを見出した．

これらの成果を学会発表するための指導も行った．
１１．開発成果

JVMを，末尾再帰命令を追加することにより改造し，実行前にバイトコードを末尾再帰命令に書き換えることにより末尾再帰の最適化を実現した．また，継続の捕捉命令，継続の実行命令を追加することにより一級継続に関する所期の目標を達成した．

本テーマでは，JDKに関するSunのライセンスの制約もあるため，実装そのものは公開していない．実現法の詳細については情報処理学会第33回プログラミング研究会(http://www.ipl.t.u-tokyo.ac.jp/~sigpro/program.html)で発表予定である．


（講評）

本実施テーマの当初の目的は，Scheme 言語をはじめとする，いわゆる関数型言語のプログラムを，JVM 上で高速に実行するための環境を開発するものであった．しかし，プロジェクトを進める過程で，今回開発した実装方式が，JVM における一般のプログラムの性能向上にも有効であり，再帰の多用によるスタックオーバーフローの回避にも役立つものとなった．この成果は，学術的にも実用上も価値の高いものである．


これらの成果を活かすために，Kawa コンパイラを改変して，本実施テーマで開発した環境に適合させるなど，関数型言語への応用を進めることが望ましい．

また，今回はJIT (Just-In-Time) コンパイラとの併用は考察しなかったが，併用した場合の実装方式の変更点や性能評価など，開発した実装方式の有効性をさらに向上するための検討が期待される．