技術部門:
拡張可能 Java プリプロセッサキット EPP
一杉裕志
電子技術総合研究所
ichisugi@etl.go.jp


1.応募の技術的主張の概要

拡張可能 Java プリプロセッサキット EPP は、 次の2通りの使い方ができるシステムである。 EPP は以下の技術的特長を持つ。

2. 応募の背景

2.1. Java の言語拡張機能の必要性

Java はシンプルで優れた言語であるが、 言語機能を拡張するための機構はほとんど持たない。

クラスおよび継承機構は、 プログラムが扱うデータ構造を拡張するための強力な機構であるが、 古くからある他のオブジェクト指向言語は、 それに加えて制御構造や演算子を拡張する機能も持っている。 C++ はプリプロセッサ、演算子オーバーロード、 Template などの機能を 持っているし、 Smalltalk や CLOS は closure や metaobject の機構を持っている。 つまり、これらの言語はデータ構造、制御構造、演算子のそれぞれを 拡張する機構を備えている。

これらの言語拡張機能なしでは、 使いやすい形でのライブラリ提供は不可能である。 例えば行列を表すクラスがある場合、 add(m1, m2) という記述よりは m1 + m2 の方が明らかに分かりやすい。 行列演算を多用するアプリケーションにとっては、 この種の「シンタックスシュガー」が、記述性・保守性向上のために不可欠である。

Java に対する言語拡張機能が強く求められているもう1つの例として、 分散・並列アプリケーションがある。 Java は標準で socket, thread, 同期などの機構を可搬性の高い形で提供している。 しかしこれらの機構は低レベルであるため、エンドユーザにとっては 必ずしも使いやすいものではない。 より高レベルで使いやすい並列言語機構を提供するためには、 構文等を拡張する機能が必要である。

2.2. 従来技術

Java 言語に言語拡張の機能を提供する従来技術としては以下のようなものがある。 これらのシステムが提供する機能は Java の欠点を補うものの、 新たな並列構文の導入などが行なえるほど強力ではない。 しかも、これらの拡張機能は「だきあわせ」の形でしか提供されていない。 例えば Pizza の Template と JPP の演算子オーバーロードの 両方を使おうと思っても不可能である。 利用者は、プロジェクトの早い段階で使う処理系を選択しなければならず、 しかも一旦選択したら他の機能を利用することはもはや不可能になってしまう。

また、 Java 以外の言語、特に C++ に関して、強力な 言語拡張機能を提供する研究として、 MPC++[5]Open C++[2]EC++ などがある。 これらのシステムは、言語拡張をモジュールの形で提供できるので、 エンドユーザは自分が使いたい拡張機能を複数選んで使うことができる。 しかし、いずれも文法拡張の範囲は制限されている。


3. 応募の構成・新規性・有用性

3.1. EPPの構成

EPP は、ソフトウエア部品の再利用性・拡張性を高める system mixin[10] と 呼ぶ特殊な継承機構を持ったオブジェクト指向言語 Ld-2 によって書かれている。 Ld-2 は現在 Common Lisp の上に実装されている( 図1 )。 (なお、現在 EPP を全て Java で書き直す作業を行なっている。)

EPP の中心部では、構文解析木の構造と、プリプロセッサが持つ3つのパス (構文解析パス、マクロ展開パス、出力パス)の枠組を定義している。 EPP plugin は、この部分に変更を加えることで、 構文解析木のフォーマットを拡張したり、 新たなパスを追加したりすることができる。 特に、出力パスの直前に新たなパスを追加することで、ソースコードに対して 大域的な変換を施す plugin が実装できる。

EPP の Java パーザは、 Yacc などのツールは使わず、 基本的に再帰下降[1]のスタイルで書かれている。 文法は、 Java 言語仕様書[3]を元にしている。 パーザ部には、 差分的拡張を想定した "hook" がメソッドの形で多く埋め込んである。 例えば、 exp-left という名前のメソッドは、非終端記号 Expression に、 左結合演算子の文法ルールを追加するための hook である。 同様に右結合、前置、後置演算子のための hook がほとんど全ての 非終端記号ごとに定義されている。 (付録のプログラムは、 EPP と同じスタイルで記述したパーザの一部である。)

EPP plugin は、パーザ部が持つメソッドを 継承によって拡張することで、文法を拡張し、 新しい構文や演算子を導入することができる。 そして、追加した抽象構文木に対するマクロ展開関数を追加することで、 新たな言語機能を実現できる。

(Application Programs)
EPP Plugins
Java Grammar Rules (1957lines)
EPP Micro Core (597 lines)
Object-Oriented Language Ld-2 (764 lines)
Common Lisp

図1: EPP の構成

3.2. System Mixin

EPP の記述言語 Ld-2 が持つ system mixin[10] と 呼ぶ継承機構について 簡単に説明する。

system mixin は、オリジナルのソースコードに対する差分だけを 抜き出した patch file のようなものである。 複数の system mixin が、アプリケーションの起動時に1列につなぎ合わされ、 1つの完全なシステムになってから、実行される。 通常のオブジェクト指向言語の継承と違うのは、 継承の単位がクラスではなく、クラス階層全体、つまりシステム全体である、 という点である。 また、 C++ などの継承では subclass を定義する時に super class を 静的に指定するが、 system mixin の定義時にはオリジナルのソースコードは 指定しない。この点は CLOS での mixin を使った記述スタイルと似ている。

EPP plugin は、この system mixin を定義するファイルである。 EPP は起動されると、指定された system mixin を標準の Java プリプロセッサに 加えることで、「拡張された」 Java プリプロセッサを構築する。 そしてそれを起動し、プリプロセスを開始する。

3.3. EPP の利点

EPP は、同様の他の言語拡張ツールや Yacc などの Parser generator と比較して 次のような利点を持つ。

3.4. EPP on Java とその利点

先に述べたように、現在 EPP をすべて Java で書き直している。 付録のプログラム例は、 System Mixin plugin および Symbol plugin を追加した Java を用いて書いた再帰下降パーザの一部である。 この例と同じスタイルで、 EPP を書き直す予定である。 これが完了すると、次のような大きな利点がある。

4. 応募システムの実行例

EPP plugin を用いた Java プログラムの例を2つ紹介する。 その他の plugin の実行例については http://www.etl.go.jp/etl/bunsan/‾ichisugi/epp-examples から参照することができる。

まず、 Python 風比較演算子の plugin を使ったプログラム例である。 この plugin は、 0 <= a < 100 といった記述を可能にする。 先頭の #epp ではじまる行で、取り込む plugin を指定している。 この plugin は、オリジナルの Java の比較演算子の文法ルールを取り除き、 独自の文法ルールとマクロ展開関数を追加することで実現されている。

#epp load "pcompare"
public class test {
  public static void main(String[] argv){
    int a = 10;
    if (0 <= a < 100) System.out.println("Correct!");
  }
}
このプログラムは、次のようなプログラムに変換される。 (一時変数 T0 は、 a の値が複数回評価されないために必要。)
public class test {
  public static void main(String argv[]){
    int a = 10; int T0; 
    if((((0) <= (T0 = (a))) && ((T0) < (100))))
       System.out.println("Correct!");
  }
}
なお、この例では見やすくするため改行を入れているが、 EPP のデフォルトの動作では、 オリジナルのソースファイルの行をできるだけ変えずに出力する。 これは、プログラムの symbolic debug を容易にするためである。

次は Tiny Data-Parallel Java plugin を使って、 区分求積によって円周率を計算するプログラム例である。 プログラマーから見ると、 parallel という modifier を指定した class の メソッド run が、コンストラクタで指定された個数の細粒度の仮想プロセッサ上で、 同期をとって実行されるように見える。 (なお、メソッド run の中では、 if 文、 while 文、遠隔代入・遠隔参照なども実行できる。)

#epp load "datap01"

public class CalcPi {
  public static void main(String argv[]){
    int num = Integer.parseInt(argv[0]);       // 仮想プロセッサの数
    DpCalcPi.PE_n = Integer.parseInt(argv[1]); // 実行する Java スレッドの数
    System.out.println("Start execution on "+DpCalcPi.PE_n+" Java threads.");

    DpCalcPi.width = 1.0 / num;
    DpCalcPi p = new DpCalcPi(num); // 仮想プロセッサの生成
    p.run();             // 並列実行
    System.out.println(DpCalcPi.result * DpCalcPi.width);
  }
}

// parallel という modifier のあるクラスは、特別に処理される。
parallel class DpCalcPi {
  static double result;  // 単一変数:全ての仮想プロセッサから共有される
  static double width;   // 単一変数
  double x;              // 並列変数:仮想プロセッサごとに別の値を持つ
  // データ並列メソッド
  public void run(){
    x = (VPID() + 0.5) * width;
    // reduction operator 。値の総和を result に代入。
    set_sum(result, 4.0 / (1.0 + x * x)); 
  }
}
変換結果のプログラムの一部は以下のようになる。 実行時に、指定された数の Java スレッドが生成され、 メソッド run が並列に実行される。 プログラマから見た細粒度の仮想プロセッサは 個々のスレッドに割り当てられ、 for 文によって エミュレートされる。以下の環境で並列実行が確かめられている。
  public void run(){
    ...
    for (vpi = (0); (vpi) < (vpn); vpi++) {
      (vp_x)[vpi] = (((VPID(vpi)) + (0.5)) * (width));
      }
    sync(); 
    for (vpi = (0); (vpi) < (vpn); vpi++) {
      {
        T_sum = (0.0); 
        for (vpi = (0); (vpi) < (vpn); vpi++)
           T_sum += ((4.0) / ((1.0) + (((vp_x)[vpi]) * ((vp_x)[vpi])))); 
        break; 
        } 
      } 
    sync(); 
    for (vpi = (0); (vpi) < (vpn); vpi++) {
      {
        if ((PE_i) == (0)) result = (calc_sum()); else ; 
        break; 
        } 
      } 
    ...
  }

5. まとめ

拡張可能 Java プリプロセッサキット EPP について述べた。 Java は優れた言語であるが、言語機能や構文を拡張する機能を全く持たない。 EPP はこの欠点を補い、様々な新しい言語機能や、 使いやすいライブラリを提供することを可能にする。

参考文献

[1]
A.V. Aho, R.Sethi, and J.D. Ullmann. Compilers: Principles, Techniques and Tools. Addison-Wesley Publishing company, 1987.
[2]
Chiba, S.: "A Metaobject Protocol for C++", In Proc. of OOSPLA'95, pp.285--299, 1995.
[3]
J.Gosling, B.Joy, and Steele. G. The Java Language Specification. Java Series. Sun Microsystems, 1996.
[4]
Hatcher, P.J. and Quinn, M.J.: "Data-Parallel Programming on MIMD Computers", MIT Press, 1991.
[5]
Ishikawa, Y.: "Meta-level Architecture for Extendable C++ Draft Document", Technical Report TR-94024, RWCP, 1994.
[6]
Kumeta, A. and Komuro, M.: "Meta-Programming Framework for Java", The 12th workshop of object oriented computing WOOC'97, Japan Society of Software Science and Technology, March, 1997.
[7]
Yves Roudier, Yuuji Ichisugi: "Java Data-parallel Programming using an Extensible Java Preprocessor", SWoPP'97.
[8]
一杉裕志: "ソフトウエア電子すかしの挿入法、攻撃法、評価法、実装法" 夏のプログラミングシンポジウム, July, 1997.
[9]
一杉裕志: EPP and Lods home page.
http://www.etl.go.jp/etl/bunsan/‾ichisugi
[10]
一杉裕志: "オブジェクト指向言語 Ld-2 ユーザーズマニュアル (DRAFT)", can be obtained from EPP and Lods home page, 1997.

付録:System Mixin を使ったパーザ記述の例

このプログラム例は、 System Mixin plugin および Symbol plugin を追加した Java を用いて書いた再帰下降パーザの一部である。 3.4節で述べたように、 これと同様のスタイルで、現在 EPP の Java による書き直しを行なっている。 なお、このパーザの完全なソースは、 http://www.etl.go.jp/etl/bunsan/‾ichisugi/epp-examples から参照できる。
// 非終端記号 Exp の定義
SystemMixin Exp {
  class Parser {
    // 式を構文解析して構文解析木を返すメソッド
    define Object exp(){
      Object tree = expTop();
      Object newTree;
      // 左再帰ルールが適用可能な間ループをまわる。
      while (true){
        newTree = expLeft(tree);
        if (newTree == null) break;
        tree = newTree;
      }
      return tree;
    }
    // 前置演算子のための hook 。
    define Object expTop(){
      return expRight(exp1());
    }
    // 右結合演算子のための hook 。
    define Object expRight (Object tree) { return tree; }
    // 左結合演算子、後置演算子のための hook 。
    // このメソッドは、もし演算子があれば構文解析木を、なければ null を返す。
    define Object expLeft (Object tree) { return null; }
    // 次の優先度の非終端記号の構文解析を呼び出すメソッド。
    define Object exp1 () { return term(); }
  }
}

// 左結合2項演算子の定義例
SystemMixin Plus {
  class Parser {
    // メソッド expLeft の拡張。
    Object expLeft (Object tree) {
      if (lookahead() == :"+") {
        return Util.list(match(:"+"), tree, exp1());
      } else {
        // 「オリジナル」のメソッドを呼び出す。
        return original(tree);
      }
    }
  }
}

// 右結合2項演算子の定義例
SystemMixin Assign {
  class Parser {
    Object expRight (Object tree) {
      if (lookahead() == :"=") {
        return Util.list(match(:"="), tree, exp());
      } else {
        return original(tree);
      }
    }
  }
}

// 前置演算子の定義例
SystemMixin PrePlusPlus {
  class Parser {
    Object factorTop () {
      if (lookahead() == :"++") {
        match(:"++");
        return Util.list(:"pre++", factor());
      } else {
        return original();
      }
    }
  }
}


To Home Page of Yuuji Ichisugi