Javaだって関数型言語に負けないぐらい魅力的：オブジェクト指向だけで計算してみる
HaskellやScalaなどで一躍大人気となった関数型言語には、その根底に型付きラムダ計算という計算体系の理論が存在しています。この型付きラムダ計算の理論のおかげで、関数型言語では型安全なプログラミングが出来るのです。
ではオブジェクト指向言語にはそのような理論は存在するのでしょうか。
Javaについては、割と最近ですが、Javaをモデル化した計算体系を扱った、
Featherweight Java: a minimal core calculus for Java and GJ [Igarashi et al., 2001]
という論文が存在します。この論文では、JavaとJava 5.0以降で採用されたジェネリクスという仕組みをモデル化したオブジェクト指向の体系を定義し、この体系上での型安全性の証明を行っています。
この論文の体系では構造化定理で言う条件分岐と反復が定義されていません。これはつまり、オブジェクト指向を突き詰めれば条件分岐や反復なんてポリモーフィズムで十分表現出来るのだ、ifやforなんて飾りなのです、偉い人には(ry と言っているに違いありません。
というわけで、今回はこの論文を参考にしつつオブジェクト指向のコアの部分だけで本当に演算が出来そうか試してみましょう。
ルールとか
FGJはJavaを簡略化した体系なので、言語はJavaを使います。ただし、Javaだと表現力が強すぎるのでFGJに合わせて制限を付けます。詳しくは、上記の論文を参照してください。
- 自分で定義したクラス以外は使わない(StringやInteger等の組込みの型も不可)
- nullも使わない
- フィールドは必ずfinalで、コンストラクタで初期化しなければならない。
- アクセス修飾子は自由
- 許される式と文は、return、インスタンスの生成、フィールドへのアクセス、メソッド呼び出しのみ。if/for等も一切使わない。
- 今回はキャストは使わない
サンプルとしてこの体系上で定義したPairクラスを載せてみます。
class Pair<T,U> { // <- ジェネリクスは使える public final T fst; // <- フィールドはfinal public final U snd; public Pair(T fst, U snd) { this.fst = fst; // 代入が許されるのはコンストラクタでのフィールドの初期化のみ this.snd = snd; } public T getFst() { return fst; } // 必ずreturnからはじまる public U getSnd() { return snd; } }
利用方法はこんな感じ
new Pair<A,B>(new A(), new B()).getSnd();
ただし、FGJそのままにすると制限が強すぎて書くのがあまりにも面倒なので、FGJになくても明らかに等価な書き方が出来そうなものは使って良い事にします。
Booleanの表現
最初は型が一切存在しないので、まずは自分で型を定義していく必要があります。
まずは、簡単な真偽値のオブジェクトでの表現を考えてみましょう。
安直に考えると、抽象クラスBooleanと、それを継承したTrue、Falseクラスという構成で作れそうです。ただし、今回は型に関する情報は使えないので、TrueクラスとFalseクラスをどう差別化するかを考える必要があります。
ここはλ計算を参考にして、Booleanクラスに、
<T> T get(T t,T f)
というようなメソッドを作る事にしましょう。True/Falseクラスはそれぞれこのgetをオーバーライドし、Trueクラスは2引数の前者、Falseクラスは後者を返すようにしてみます。
クラス定義はこんな感じになります。
abstract class Boolean { public abstract <T> T get(T t,T f); } class True extends Boolean { @Override public <T> T get(T t, T f) { return t; } } class False extends Boolean { @Override public <T> T get(T t, T f) { return f; } }
それではテストしてみましょう(テストなのでprintとかString使ってます)。
System.out.println(new True().get("True","False")); System.out.println(new False().get("True","False"));
試しにこのようなコードを実行してみます。
すると、
True
False
と表示されるはずです。
これでオブジェクトで真偽値の表現は出来ました。次はBooleanを使った演算を定義してみようと思います。
論理演算を定義する
次はBooleanを使った論理演算を実装してみましょう。
とりあえず論理演算に最低限必要なnot/and/orを実装してみます。これらさえあれば、xorやnandなど他の全ての論理演算は3つの演算の組み合わせによって実現出来ます。
Booleanクラスの中に定義しても良いですが、
今回はBoolean演算用のBoolクラスを作って定義する事にします。
class Bool { public Boolean not(Boolean b) { return b.get(new False(), new True()); } public Boolean and(Boolean a, Boolean b) { return a.get(b.get(new True(), new False()), new False()); } public Boolean or(Boolean a, Boolean b) { return a.get(new True(), b.get(new True(), new False())); } }
Booleanはget()メソッドを呼び出すと、Trueクラスの場合は1引数目を、Falseクラスの場合は2引数目を返すので、その性質を利用して論理演算を定義します。
例えばnotだと、
new Bool().not(new True()) ==> new True().get(new False(), new True()) ==> False new Bool().not(new False()) ==> new False().get(new False(), new True()) ==> True
という風に評価されます。
条件分岐
次は構造化定理の一つでもある条件分岐のifです。これがないと何も出来ないですよね。
Booleanのgetメソッドを見て気付いている方もおられると思いますが、まさにgetがifと同じ働きをします。
さっさと実装してみましょう。
if(b) { return t; } else { return f; }
というような条件分岐は以下のようになります。
class Condition {
public <T> T iif(Boolean b, T t, T f) {
return b.get(t,f);
}
}とても簡単ですね。
ただ実はこの定義には罠があったりします。詳しくは後半で述べます。
ここまでのソースコードと実行例はこちら。
http://ideone.com/yN1g5
自然数の定義
Booleanは割と簡単でしたが、自然数の定義は少し複雑になります。
自然数の定義方法として真っ先に思い浮かぶのがペアノ数のような定義ですね。
つまり抽象クラスNumberを継承したクラスZeroとSuccで自然数を表現するという方法です。
こんな感じのイメージです。
new Zero() ==> 0 new Succ(new Succ(new Zero())) ==> 2
ここまでは良いのですが、問題は定義した自然数をどう扱うかです。
ここではやはりλ計算を参考に、自然数nをf(f(f(x)))のようにある値xに対するn回の関数適用と考えてみる事にします。
ただしJavaでは関数は第一級オブジェクトではなく、また関数ポインタも存在しないので関数をカプセルするためのFunctorというクラスを定義します。Functor
abstract class Functor<T,U> { public abstract U apply(T u); } abstract class Number { public abstract <T> T apply(Functor<T,T> op, T t); } class Zero extends Number { @Override public <T> T apply(Functor<T,T> op, T t) { return t; } } class Succ extends Number { final Number n; public Succ(Number n) { this.n = n; } @Override public <T> T apply(Functor<T,T> op, T t) { return n.apply(op, op.apply(t)); } }
こんな感じの定義になりました。Booleanよりはかなり複雑に見えますね。
Numberのapply()メソッドの使用例は演算の所で説明します。
自然数の演算を定義する その1
次に自然数の演算を定義してみます。
まずは簡単なisZeroを定義してみます。
先程、自然数nはxに対するn回の関数fの適用と定義しました。
例えば、
f : 引数によらずFalseを返す関数
x : True
としてみましょう。
もしnが0なら、0回の関数適用なのでそのままxつまりTrueに、
nが1以上なら、fはFalseを返すのでFalseとなります。
これをこのままJavaのコードに落としてみます。
// 入力値によらず、定数を返すクラス class Const<T,U> extends Functor<T,U> { final U u; public Const(U u) { this.t = t; } @Override public U apply(T _t) { return u; } } class Num { public Boolean isZero2(Number n) { return n.apply(new Const<Boolean,Boolean>(new False()), new True()); }
上記の関数はこのように評価されていきます
new Num.isZero(new Zero()) ==> new Zero().apply(new Const<Boolean,Boolean>(new False()), new True()); ==> True new Num.isZero(new Succ(new Succ(new Zero()))) ==> new Succ(new Succ(new Zero())).apply(new Const<Boolean,Boolean>(new False()), new True()) ==> new Succ(new Zero()).apply(..., new Const<Boolean,Boolean>(new False()).apply(new True())) ==> new Succ(new Zero()).apply(..., new False()) ==> new Zero().apply(..., new Const<Boolean,Boolean>(new False()).apply(new False())) ==> new Zero().apply(..., new False()) ==> False
上手くいきました。
このまま自然数同士の足し算とかけ算を定義してみましょう。
足し算m+nは、mに対して
f : +1する関数
x : n
を適用すれば、nに+1がm回行われる事になるのでm+nになりますね。
かけ算m*nも同様に、mに対して
f : +nする関数
x : 0
を適用すれば、0に+nがm回行われるのでm*nになりそうです。
以上を踏まえて、ソースは以下のようになります。
クラスをいちいち定義するのも面倒ですので匿名クラスを使っていますが、isZeroのようにクラス定義するのと変わりはありません。
また、mulに関しては引数にfinalを付けて匿名クラス内からアクセスしていたりしてますが、この体系ではオブジェクトに対して副作用を持つメソッドはありませんので手抜きという事で許してください。
class Num { ... public Number add(Number lhs, Number rhs) { return lhs.apply(new Functor<Number,Number>() { @Override public Number apply(Number n) { return new Succ(n); }}, rhs); } public Number mul(Number lhs, final Number rhs) { return lhs.apply(new Functor<Number,Number>() { @Override public Number apply(Number n) { return add(n,rhs); }}, new Zero()); } }
これでisZero、足し算add、かけ算mulが定義出来ました。
ちょっと長くなりましたので、自然数の演算は一回章を切ります。
自然数の演算を定義する その2
前半では、足し算とかけ算を定義しました。次は引き算を定義してみます。
引き算m-nはやはり足し算と同様に、nに対して
f : -1する関数
x : m
を適用すれば、mからn回1を引くのでm-nが出来そうです。
(ただし、結果が0より小さくなる事はない事にします)
ただ、-1というのがなかなかやっかいです。
n回の関数適用で、n-1を作らないといけないわけです。
ここでは、例の如くλ計算のアイデアをパクる事にしましょう。
結論から先に書きます。
f : ペア(x,y)に対して(y,y+1)を作る関数
x : (0,0)
これをn回適用してみましょう。
(0,0)
(0,1)
(1,2)
...
(n-1,n)
これを思いついた人は本当にすごいですね。
かくして、結果のペアから先頭を持ってこればn-1が出来るわけです。
ペアを作るクラスPair、-1する関数pred、引き算する関数subの定義は以下のようになります。
class Pair<T,U> { public final T fst; public final U snd; public Pair(T fst, U snd) { this.fst = fst; this.snd = snd; } } class Num { ... public Number pred(Number n) { return n.apply(new Functor<Pair<Number,Number>,Pair<Number,Number>>() { @Override public Pair<Number,Number> apply(Pair<Number,Number> pair) { return new Pair<Number,Number>(pair.snd, new Succ(pair.snd)); } }, new Pair<Number,Number>(new Zero(),new Zero())).fst; } public Number sub(Number lhs, Number rhs) { return rhs.apply(new Functor<Number,Number>() { @Override public Number apply(Number n) { return pred(n); }}, lhs); } }
なかなか難しくなってきましたが、このままどんどん定義していきましょう。
自然数を比較してみる
自然数の基本演算は定義したので、次はこの演算を応用して自然数の比較を実装してみましょう。
まずは、< (less than)と > (greater than)を定義してみます。
m < nは、今までの演算を使えば、 not isZero(n-m) で定義出来そうです。
m > nは、ltが既にあるので両者を引っくり返して n < m するだけですね。
class Comp { public Boolean lt(Number m, Number n) { return new Bool().not(new Num().isZero(new Num().sub(n,m))); } public Boolean gt(Number m, Number n) { return lt(n,m); } }
再帰を実装してみる
問題はeqです。
色々やり方はあると思いますが、今回はせっかくなので再帰を用いた方法で実装してみます。定義は以下のようになります。
eq(m,n) =
True if m = 0 and n = 0
False else if m = 0 or n = 0
eq(m-1,n-1) else
つまりmとnの両方を-1ずつしていき、両方が同時に0になればTrue、片方だけが0になればFalseを返します。
さっさと実装してみましょう。
class Comp { ... public Boolean eq(Number lhs, Number rhs) { return new Condition().iif( new Bool().and(new Num().isZero(lhs), new Num().isZero(rhs)), new True(), new Condition().iif( new Bool().or(new Num().isZero(lhs), new Num().isZero(rhs)), new False(), eq(new Num().pred(lhs), new Num().pred(rhs)))); } }
なんだ、ちょっと複雑だけど簡単じゃないか・・と思いきや、このeq()を呼び出すと無限再帰に陥ります。
理由はifのtrueの場合とfalseの場合の式が結果によらず両方評価されてしまい、lhsかrhsが0の場合にも再帰のeqを呼び出して評価しようとしてしまうためです。詳しくはSICPの特殊形式あたりの章を読んでください。
そこで、ifの使われない結果は評価されないように工夫する必要があります。Javaで遅延評価するためには、どうすれば良いでしょうか。そこでFunctorを使います。クラス内のメソッドは実際に呼び出されるまで評価されませんから、手続きをFunctorオブジェクトにカプセルしておき、ifの評価が終わった後にはじめてその手続きを評価するようにします。
// Voidを表すクラス(java.lang.Voidと被ってるので名前変えた方がいいかもしれない) class Void {} class Condition { public <T> T iif(Boolean b, T t, T f) { return b.get(t,f); } // 遅延評価if。ifでtかfを決定した後にapplyを適用して処理を実行する public <T> T lazyIf(Boolean b, Functor<Void,T> t, Functor<Void,T> f) { return iif(b,t,f).apply(new Void()); } } // 遅延評価Functorの抽象クラス abstract class Lazy<U> extends Functor<Void,U> { public abstract U get(); @Override public U apply(Void _v) { return get(); } } // 値が必要になるまで、eq(pred(lhs),pred(rhs)) の呼び出しを遅延する class LazyEqPred extends Lazy<Boolean> { final Number lhs; final Number rhs; public LazyEqPred(Number lhs, Number rhs) { this.lhs = lhs; this.rhs = rhs; } @Override public Boolean get() { return new Comp().eq(new Num().pred(lhs), new Num().pred(rhs)); } } // 前の方で定義したConst再掲 class Const<T,U> extends Functor<T,U> { final U u; public Const(U u) { this.u = u; } @Override public U apply(T t) { return u; } } // 0引数版Const class Const0<U> extends Const<Void,U> { public Const0(U u) { super(u); } } class Comp { ... /* ちゃんと動かなかったやつ public Boolean eq(Number lhs, Number rhs) { return new Condition().iif( new Bool().and(new Num().isZero(lhs), new Num().isZero(rhs)), new True(), new Condition().iif( new Bool().or(new Num().isZero(lhs), new Num().isZero(rhs)), new False(), eq(new Num().pred(lhs), new Num().pred(rhs)))); } */ // 遅延評価を行い、ちゃんと止まるeq public Boolean eq(Number lhs, Number rhs) { return new Condition().iif( new Bool().and(new Num().isZero(lhs),new Num().isZero(rhs)), new True(), new Condition().lazyIf( new Bool().or(new Num().isZero(lhs),new Num().isZero(rhs)), new Const0<Boolean>(new False()), new LazyEqPred(lhs,rhs))); } }
少し難しくなりましたが何とか定義出来ました。ちなみにeqの定義方法はいくつかあり、わざわざ再帰を使わないでも、もっと簡単に定義出来たりはします。暇な人は考えてみましょう。
これで自然数の基本的な演算と比較を定義出来ました。
応用編：フィボナッチ関数を実装してみよう
自然数や真偽値など色々定義してきましたが、最後に応用として今までの定義を利用してフィボナッチ関数(再帰版)を実装してみましょう。
フィボナッチ関数fibの定義
fib(n) = 0 if n = 0 1 if n = 1 fib(n-1) + fib(n-2) else
ソースコードはこちら
// フィボナッチの遅延再帰クラス class FibRec extends Lazy<Number> { final Number n; public FibRec(Number n) { this.n = n; } public Number get() { return new Num().add( new Fib().fib(new Num().pred(n)), new Fib().fib(new Num().pred(new Num().pred(n))) ); } } // フィボナッチクラス class Fib { public Number fib(Number n) { return new Condition().iif( new Num().isZero(n), new Zero(), new Condition().lazyIf( new Comp().lt(n, new Succ(new Succ(new Zero()))), new Const0<Number>(new Succ(new Zero())), new FibRec(n))); } }
慣れればお手の物ですね！
まとめ
オブジェクトだけでフィボナッチ関数まで表現出来てしまいした。
関数型だけでなく、オブジェクト指向言語にもちゃんとした理論に基づいた計算体系が根底に存在し、型安全なプログラミングを楽しめるという事が分かって頂けたかと思います。Javaはとても素晴しい言語です。
また時間に余裕があれば、この体系でのリスト演算などもやってみたいと思います。
今回の全体のソースコードと実行結果はこちらに置いています。
ご自由にどうぞ。
Gist https://gist.github.com/1174882
Ideone http://ideone.com/nsudG
