最小限のJavaで素数を列挙(Javaで無限リスト)

以前書いた「ラムダ計算基礎文法最速マスター」では, ラムダ計算に自然数やデータ構造, 条件分岐, ループが用意されていないため, これらをラムダ項を使って模倣する方法を紹介しました. このようなことはどんなプログラミング言語でも起きうることで, たとえば, アセンブリ言語にforループが無いために, C言語で書かれたプログラムをアセンブリ言語コンパイルするときには条件ジャンプ命令とラベルでforループを模倣する, というのも同じことです.

今回は, Javaを最小限の機能だけに制限した純粋オブジェクト指向言語で, 以下のものを実現してみます.

  • 真偽値と条件分岐
  • 自然数と四則演算
  • リスト
  • 無限リスト

さらに, これらすべてを用いて任意個の素数を列挙するプログラムを書いてみます. 完全なソースコードは一番最後にあります.

最小限のJava

Javaはそれ自体純粋なオブジェクト指向言語ですが, 本来オブジェクト指向とは関係ない言語機能も多く備えています. 今回はそのような付随的な言語機能をすべて排除した, 純粋にオブジェクト指向の機能のみに制限したJavaを使います. 具体的には, 以下のものしか書けない言語です.

  1. クラス定義
    • クラス名
    • 親クラス名
    • フィールド定義
    • コンストラク
      • フィールドの初期化のみを行なう
    • メソッド定義
      • メソッド本体は常に単一の式をreturnする
  2. e
    • フィールド取得 e.f
    • メソッド呼出し e.m(...)
    • オブジェクト生成 new C(...)
    • キャスト (C)e

この言語には代入演算が無いので, フィールドに対するアクセスは常に読み取り専用であることに注意して下さい. また, ブーリアン型, 整数型といった非クラス型は無く, フィールドもメソッドも持たないObjectクラスのみが予め定義されています.

言語仕様の詳細が知りたい場合は以下を参考にして下さい.

真偽値と条件分岐

最小限のJavaにはブーリアン型は無いので, クラスで模倣します. 真偽値に対して要求される本質的な操作は条件分岐なので, そのための仕組みも用意します.

class Bool extends Obj {
    Bool(){ super(); }
    Bool neg(){ return new False(); }
    Bool or(Obj b){ return this; }
    Bool and(Obj b){ return (Bool)b.eval(); }
    Obj cond(Obj thn, Obj els){ return thn.eval(); }
}

class True extends Bool { True(){ super(); } }

class False extends Bool {
    False(){ super(); }
    Bool neg(){ return new True(); }
    Bool or(Obj b){ return (Bool)b.eval(); }
    Bool and(Obj b){ return this; }
    Obj cond(Obj thn, Obj els){ return els.eval(); }
}

Boolは真偽値のための抽象基底クラス(実際に抽象クラスを定義する機能は無いので, 単なるクラスで代用し, 実際にはTrueと同じ動作をするもの), Trueが真を表すクラス, Falseが偽を表すクラスです.

条件分岐は真偽値クラスのcondメソッドが行ないます. condメソッドはthen節とelse節を引数として受け取り, Trueクラスではthen節を, Falseクラスではelse節を返します. ただし, 素朴にやると本来の意味の条件分岐とは異なる挙動になってしまいます. たとえば,

if (true) {
    x.foo();
} else {
    x.bar();
}

という条件分岐では, else節のbarメソッドは実行されないことが期待されます. しかし, これをcondメソッドで素朴に模倣すると,

new True().cond(x.foo(), x.bar());

となり, foo, bar両方のメソッドが実行されてしまいます. そこで,

class CallFoo extends Obj {
  X x; CallFoo(X x){ super(); this.x=x; }
  Obj eval(){ return x.foo(); }
}
class CallBar extends Obj {
  X x; CallBar(X x){ super(); this.x=x; }
  Obj eval(){ return x.bar(); }
}
new True().cond(new CallFoo(x), new CallBar(x));

のように, メソッドfoo, bar遅延評価(lazy evaluation, delayed evaluation)できるようにします. 実際にはJavaに遅延評価の仕組みはないので, メソッドを表すオブジェクトを作ることで模倣しています. メソッドそのものは第一級オブジェクトではないので, 「evalを実行するとfooを呼び出すクラス」であるCallFooや「evalを実行するとbarを呼び出すクラス」であるCallBarを定義する必要があります. TrueクラスやFalseクラスのcondメソッドでthen節やelse節に対してevalメソッドを呼び出すことで, 実行すべき節のみが実行されるわけです.

また, 以下のようなObjというクラスを遅延評価のための基底クラスとして定義し, Objectクラスの代わりに使っています.

class Obj extends Object {
    Obj(){ super(); } Obj eval(){ return this; }
}

自然数と四則演算

自然数ペアノの公理に従って定義します*1. ペアノの自然数は, 0を表すものと, ある自然数の次の数を表すための構成子からなります. Java風に書くと,

new Z();                      // 0
new S(new Z());               // 0の次の数, すなわち1
new S(new S(new Z()));        // 0の次の次の数, すなわち2
new S(new S(new S(new Z()))); // 0の次の次の次の数, すなわち3
...

ということです. まずは, 1つ前の数, 1つ後の数, 0かどうかをそれぞれ返すメソッドのみが定義された自然数クラスを見てみましょう.

class N extends Obj {
    N(){ super(); }
    N pre(){ return (N)(Obj)new Error(); }
    N suc(){ return new S(this); }
    ...
    Bool isZero(){ return new True(); }
    ...
}

class Z extends N { Z(){ super(); } }

class S extends Z {
    N n; S(N n){ super(); this.n=n; }
    N pre(){ return this.n; }
    ...
    Bool isZero(){ return new False(); }
    ...
}

N自然数のための抽象基底クラス(実際にはZクラスと同じ挙動), Zが0を表すクラス, Sが「次の数」を構成するためのクラスです. preが1つ前の数を, sucが1つ後の数を, isZeroが0かどうかを返すメソッドです. 0の前の数は存在しないので, Zクラスに対するpreメソッドはエラーになるようにします. Errorクラスは単に

class Error extends Obj { Error(){ super(); } }

と定義されていて, (N)(Obj)new Error()のキャストが必ず失敗する(けれどコンパイルは通る)ことを利用して, 実行時にだけエラーになるようにしています.

加算

0に何を足しても足した数そのものになるので, 0に対する加算メソッドは簡単です.

class N extends Obj {
    ...
    N add(N m){ return m; }
    ...
}

ペアノの公理では, 加算は「a+S(b) = S(a+b)」という規則によって行ないます. そこで, Sクラスのaddメソッドは次のように定義します.

class S extends Z {
    ...
    N add(N m){ return this.n.add(m).suc(); }
    ...
}

乗算に関しても同様に定義できます. 詳しくは末尾のソースコードを見て下さい.

減算

0から0以外を引くことはできないので, 引く数が0でないときにはエラーにします.

class N extends Obj {
    ...
    N sub(N m){ return (N)m.isZero().cond(this, new Error()); }
    ...
}

引かれる数が0でないときは, 「引かれる数の1つ前の数」から「引く数の1つ前の数」を引いた結果を使います. ただし, 引く数が0のときには「引く数の1つ前の数」は存在しないので, 引く数が0かどうかで条件分岐します. 条件分岐における遅延評価のためのクラスSubElseも用意します.

class S extends Z {
    ...
    N sub(N m) { return (N)m.isZero().cond(this, new SubElse(this.n, m)); }
    ...
}
class SubElse extends Obj {
    N n; N m; SubElse(N n, N m){ super(); this.n=n; this.m=m; }
    Obj eval(){ return this.n.sub(this.m.pre()); }
}

除算, 剰余算に関しても, 遅延評価に気をつければ同様に定義できます. 詳しくは末尾のソースコードを見て下さい.

比較演算

0と等しいのは0だけで, 0はどんな数よりも大きくありません. 従って, 0に対する等号演算と大なり演算は次のように定義できます.

class N extends Obj {
    ...
    Bool eq(N m){ return m.isZero(); }
    Bool gt(N m){ return new False(); }
    ...
}

0以外の数の比較演算は相互再帰的に定義されます. 詳しくは末尾のソースコードを見て下さい.

class S extends Z {
    ...
    Bool isSucOf(N m){ return m.eq(this.n); }
    Bool eq(N m){ return m.isSucOf(this.n); }
    Bool gt(N m){ return this.n.ge(m); }
}

残りの比較演算はこれらの演算を使って定義できます. 詳しくは末尾のソースコードを見て下さい.

リスト

リストは, 先頭の要素を返すメソッドcarと, 先頭を除いた残りのリストを返すメソッドcdrを持つクラスとして定義できます. また, 空のリストを表すためにNilクラスを使います.

class List extends Obj {
    List(){ super(); }
    Bool isNil(){ return new True(); }
    Obj car(){ return this; }
    List cdr(){ return new List(); }
}

class Nil extends List { Nil(){ super(); } }

class Cons extends List {
    Obj car; List cdr;
    Cons(Obj car, List cdr){ super(); this.car=car; this.cdr=cdr; }
    Obj car(){ return this.car; }
    Bool isNil(){ return new False(); }
    List cdr(){ return this.cdr; }
}

たとえば, 3つの要素(0, 1, 2)からなるリストは

new Cons(new Z(),
         new Cons(new S(new Z()),
                  new Cons(new S(new S(new Z())),
                           new Nil())));

のようにして作ります.

無限リスト

無限リストは無限の要素を持つリストを表現するためのデータ構造です. 実際に無限個の要素を持つことはできないので, 要素にアクセスするときに, 必要な分の有限個の要素が生成されるように実装します.

無限リストの定義はリストのものによく似ていますが, 「先頭を除いた残りのリスト」の代わりに, 「先頭を除いた残りのリストを生成するための関数」を使います.

class Seq extends Obj {
    Obj val; Next next;
    Seq(Obj val, Next next){ super(); this.val=val; this.next=next; }
    Obj car(){ return this.val; }
    Seq cdr(){ return this.next.get(); }
    ...
}
class Next extends Obj {
    Next(){ super(); } Seq get(){ return new Seq(new Obj(), this); }
}

Seqが無限リストのクラスで, Nextは「残りのリストを生成するための関数」を表す抽象基底クラスです.

これらを用いて, 自然数が順に含まれる無限リストを作ってみましょう. まずは「残りのリストを生成するための関数」を定義します.

class From extends Next {
    N n; From(N n){ super(); this.n=n; }
    Seq get(){ return new Seq(this.n, new From(this.n.suc())); }
}

これを用いると, たとえば

new From(new Z()).get();

は0から始まる自然数全体の無限リストになります.

new From(new Z()).get().car();             // -> new Z()
new From(new Z()).get().cdr().car();       // -> new S(new Z())
new From(new Z()).get().cdr().cdr().car(); // -> new S(new S(new Z()))
無限リストから有限リストへ

無限リストの先頭n個の要素からなる有限部分リストを得るためのメソッドを定義しておくと便利です.

class Seq extends Obj {
    ...
    List take(N n) {
        return (List)n.isZero().cond(new Nil(), new Take(n, this));
    }
}
class Take extends Obj {
    N n; Seq s; Take(N n, Seq s){ super(); this.n=n; this.s=s; }
    Obj eval() {
        return new Cons(this.s.car(), this.s.cdr().take(this.n.pre()));
    }
}

たとえば, 自然数の無限リストの先頭3要素からなる有限部分リストは次のようにして得られます.

new From(new Z()).get().take(new S(new S(new S(new Z()))));
// -> new Cons(new Z(), new Cons(new S(new Z()), new Cons(new S(new S(new Z())), new Nil())))

応用: 任意個の素数を列挙

基本方針

エラトステネスのふるいを使って素数を列挙します. すべての素数を含む無限リストを得るための手続きは以下のようになります.

ステップ1
2以上の自然数を順に並べた無限リストを用意する
ステップ2
無限リストの先頭以降の要素から先頭要素の倍数を取り除く
ステップ3
先頭要素を除いた無限リストに対して, ステップ2以降を行なう

このようにして得られた無限リストに対してtakeメソッドを呼び出すことで, 任意個の素数のリストが得られます.

ステップ1: 2以上の自然数の無限リスト

前述のFromクラスを用いることで可能です.

new From(new S(new S(new Z()))).get();
ステップ2: 倍数を取り除く
new Sift(n, s).get();

とすることで, 無限リストsからnの倍数を取り除いた無限リストを生成するクラスを以下のように定義します.

class Sift extends Next {
    N n; Seq s; Sift(N n, Seq s){ super(); this.n=n; this.s=s; }
    Seq get() {
        return (Seq)((N)this.s.car()).mod(this.n).isZero()
            .cond(new SiftThen(this), new SiftElse(this));
    }
}
class SiftThen extends Obj {
    Sift si; SiftThen(Sift si){ super(); this.si=si; }
    Obj eval(){ return new Sift(this.si.n, this.si.s.cdr()).get(); }
}
class SiftElse extends Obj {
    Sift si; SiftElse(Sift si){ super(); this.si=si; }
    Obj eval(){ return new Seq(this.si.s.car(), new SiftElseNext(this)); }
}
class SiftElseNext extends Next {
    SiftElse se; SiftElseNext(SiftElse se){ super(); this.se=se; }
    Seq get(){ return new Sift(this.se.si.n, this.se.si.s.cdr()).get(); }
}

Siftクラスのgetメソッドでは, sの先頭要素がnの倍数である(nで割った余りが0である)とき, sの先頭以外の要素からnの倍数を取り除いたものを返します. そうでないとき, sの先頭要素と「sの先頭以外の要素からnの倍数を取り除いたもの」を返す関数からなる無限リストを返します. つまり, 先頭要素がnの倍数だった場合はその要素を捨て, そうでなければ先頭要素も残して, 同様のことを残りの要素について繰り返します.

SiftThen, SiftElse, SiftElseNextは遅延評価のためのクラスです.

ステップ3: 倍数を除く操作の繰り返し

Siftクラスを用いて, 先頭要素の倍数を取り除いていく操作を繰り返し適用するクラスを定義します.

class Sieve extends Next {
    Seq s; Sieve(Seq s){ super(); this.s=s; }
    Seq get(){ return new Seq(this.s.car(), new SieveNext(this)); }
}
class SieveNext extends Next {
    Sieve si; SieveNext(Sieve si){ super(); this.si=si; }
    Seq get() {
        return new Sieve(new Sift((N)this.si.s.car(),
                                  this.si.s.cdr()).get()).get();
    }
}
素数の列挙
new Sieve(new From(new S(new S(new Z()))).get()).get().take(n);

とすることで, n個の素数からなるリストが得られます. 末尾のソースコードには, もう少しだけ効率よく列挙するような工夫, 得られたリストを印字するためのコードが含まれていて, 実際に実行した結果は以下のようになります. この例では素数を64個列挙しています.

$ javac primes.java
$ java Test
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311]

*1:ラムダ計算基礎文法最速マスターで定義した自然数も本質的には同じこと(数学的に同型)です