Java で遅延評価式を実装する。 - にょきにょきブログ

Java は先行評価式の言語であるが、遅延評価を行えるよう遅延評価式の実装を行う。
遅延評価はサンク( Thunk, 遅延評価 - Wikipedia ) と呼ばれ、値が必要になった時点で計算をする。

要件

式を表す事ができること
値を表すことができること
遅延評価が出来る事
- eval メソッドで評価ができること
以下の演算を行える事
- Add (加算)
- Multiply (乗算)
- Div (除算)
- Pow (冪乗)
- Mod (剰余)

使い方は最後に載せようと思ったが、記事がやけに長くなったのでここでお披露目する。
$(2+7)^{{31}^{(3*7)^{2}}}$ を表すサンクを作る。

public static void main(String[] args) {
      // (2+7)^31 を表すサンクを生成
      Thunk t1 = new Thunk(2).add(7).pow(31);
      // (3*7)^2 を表すサンクを生成
      Thunk t2 = new Thunk(3).multiply(7).pow(2);
      
      System.out.println("Expression 1 : "+t1);
      System.out.println("Expression 2 : "+t2);
      
      // 冪乗する。この時点では計算されない。
      System.out.println("Expression 3 : "+t1.pow(t2));
      
      // eval メソッドを呼び出した時点で計算する
      System.out.println( "Result : " + t1.pow(t2).eval() );
}

// 実行結果

Expression 1 : ((2+7)^31)
Expression 2 : ((3*7)^2)
Expression 3 : (((2+7)^31)^((3*7)^2))
Result : 2814145480......017113209

最後は1万3千桁という巨大な数値になった。
重要なのは、これほど大きな数値の計算でありながら、eval() メソッドを呼ばない限りは計算されないということ。これが遅延評価の威力！

実装

それでは実装。Thunk クラスを作る。
以下、Thunk クラスの要点。
・サンクは単体の数値または式を表す。
・Thunk クラスで扱える式は二項演算であることを前提としているので、Thunk クラス内に Thunk left, Thunk right フィールドを持つ。
・演算子を表す enum, Operator operator フィールドがある。
・単体の値(スカラ値)を表すために、フィールド BigDecimal leftValue がある。
これは、スカラ値を左辺のみの式として表している。

では Thunk クラスのソースコード。フィールド、コンストラクタ関連。

public class Thunk {
      private Thunk left; // 左辺
      private Thunk right; // 右辺
      private Operator operator; // 演算子
      private BigDecimal leftValue; //スカラ値

      private Thunk() {}
      
      public Thunk( Number value ) {
            leftValue = new BigDecimal( value.toString() );
      }
      
      public Thunk( Thunk value ) {
            this.left = value;
      }
      ...
}

演算子を表す enum, Operator を Thunk クラス内に定義する。

public class Thunk {
            ...
      private enum Operator
      {
            ADD, MULTI, DIV, POW, MOD;
            
            public String toString() {
                  switch (this)
                  {
                  case ADD :
                        return "+";
                  case MULTI :
                        return "*";
                  case DIV :
                        return "/";
                  case POW :
                        return "^";
                  case MOD :
                        return " mod ";
                  default :
                        return "";
                  }
            }
      }
}

次に、toString メソッドと任意のサンクを作る valueOf メソッドを実装する。
valueOf メソッドは Thunk クラス内のみで呼び出されることを想定している。

public class Thunk {
      ...
      private static Thunk valueOf( Thunk left, Operator operator, Thunk right ){
            Thunk t = new Thunk();
            t.left = left;
            t.operator = operator;
            t.right = right;
            return t;
      }

      @Override
      public String toString() {
            String result = "";
            result += ( left == null ? leftValue.toPlainString() : left.toString() );
            result += ( operator == null ? "" : operator.toString() );
            result += ( right == null ? "" : right.toString() );
            
            if( right != null )
                  result = "(" + result + ")";
            
            return result;
      }
      ...
}

そして各演算を行う(ように見せる)メソッドを定義する。それぞれ、Java で扱う通常の数値を受け取るメソッドに加え、サンクを受け取るメソッドを定義している。これで式同士の演算が可能になる。

これらのメソッドの定義、かなり単純。必要ならば新たに演算子を追加して実装することも簡単である。

public class Thunk {
      ...
      // 加算
      public Thunk add( Number value ) {
            return add( new Thunk(value) );
      }
      public Thunk add( Thunk value ) {
            return valueOf( this, Operator.ADD, value );
      }
      
      // 乗算
      public Thunk multiply( Number value ) {
            return multiply( new Thunk(value) );
      }
      public Thunk multiply( Thunk value ) {
            return valueOf( this, Operator.MULTI, value);
      }
      
      // 除算
      public Thunk div( Number value ) {
            return div( new Thunk(value) );
      }
      public Thunk div( Thunk value ) {
            return valueOf( this, Operator.DIV, value);
      }

      // 冪乗
      public Thunk pow( Number value ) {
            return pow( new Thunk(value) );
      }
      public Thunk pow( Thunk value ) {
            return valueOf( this, Operator.POW, value);
      }
      
      // 剰余
      public Thunk mod( Number value ) {
            return mod( new Thunk(value) );
      }
      public Thunk mod( Thunk value ){
            return valueOf( this, Operator.MOD, value );
      }
}

ではいよいよ演算を実行する eval メソッドの実装。右辺がない場合は左辺のみを返し、それ以外は BigDecimal クラスに演算を委譲している。
BigDecimal の pow メソッドは int 値しか受け入れてくれないので right.eval().intValue() としている。ここは改良の余地があるが、今回は省略。

public class Thunk {
      ...
      public BigDecimal eval() {
            BigDecimal result = null;
            BigDecimal left = ( this.left == null ? this.leftValue : this.left.eval() );
            
            if( right == null )
                  return left;
            
            switch( operator )
            {
            case ADD : // 加算
                  result = left.add( right.eval() );
                  break;
            case MULTI : // 乗算
                  result = left.multiply( right.eval() );
                  break;
            case DIV : // 除算
                  result = left.divide( right.eval() );
                  break;
            case POW : // 冪乗
                  result = left.pow( right.eval().intValue() );
                  break;
            case MOD : // 剰余
                  result = left.remainder( right.eval() );
                  break;
            }
            
            return result;
      }
      ...
}

以上で遅延評価を表すクラスが実装できた。しかし話はここで終わりではない。

キャッシュ

遅延評価を行うことで、計算結果をキャッシュできるという重要なメリットが生まれる。同じ式は同じ値を返すので式と値をキャッシュすれば良い。
キャッシュを保持するためのフィールドを追加し、eval メソッドを以下のように変更する。
operator != null としているのは、式のみをキャッシュするため。

public class Thunk {
      // cache object
      private static Map<String,BigDecimal> cache = new HashMap<String,BigDecimal>();

      public BigDecimal eval() {
            //check cache
            if( operator != null && cache.containsKey(this.toString()) )
                  return cache.get(this.toString());

            ...

            // insert cache
            cache.put( this.toString(), result );
            
            return result;
      }