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は、T->Uというようなメソッドapplyを保持するだけのクラスです。

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

Twitterのフォロー通知メールを受信した時にGrowlで通知する

卒論から現実逃避して作ってみました．

最近はTwitterからのフォロー通知メールとかもMacに最初から付いている
Mailという何ともシンプルなソフトで受信するようにしているわけですが，
フォローされた時にGrowlで通知してくれたらいいなーと思って
Mail用ルールアクションをApple Scriptで書いてみました．

フォロー通知してくれるアプリケーションは普通にありそうですが，
Mailのルールにしておけば常駐させないで済むのが良いですね．

スクリプトは長いのでgistに置きました．
downloadからたぶんダウンロード出来ます．
https://gist.github.com/812436/
結構適当な感じで書いてるので汚ないとか言わないで下さいね．

ちなみに動作にはnkfが必要です．
たぶんSnow Leopardに最初からは入って無かった気がします．

簡単な利用法を説明します．

Apple ScriptからGrowlに通知するためには，
まずアプリケーション名をGrowlに登録しないといけないので，
「GrowlRegist.scpt」を開いて実行します．

次に，「TWMailNotify.scpt」を適当な場所に置き，Mailにフォロー通知用のルールを登録します．
Mailメニューの環境設定→ルールで行けます．
参考までに私はこのようなルールで登録しています．

これでフォローされたらGrowlでこんな感じに通知されます(恐らく)．

なんとアイコンも表示されるのです．

本当は通知をクリックした時にユーザーのホームに飛ぶようにしたいのですが，
Apple Scriptでは不可能なようなので，実現するにはPerl辺りの別の言語で
組む必要がありそうです．

Perl6のgrammarを試してみる

PCにRakudo Starを導入したので、Perl6に追加された機能の中で一番気になっていたgrammarを用いたパーサをためしに書いてみました。

作ったのは四則演算のみを行うシンプルなS式インタプリタです。
命令は+-*/の4つで、各命令は1個以上の引数を取り (+ (+ 1 2) 3) のようなネストした式も認めるものとします。

ソースはこれだけ。

grammar Sexp {
    token num { \d+ }
    token op { '+' | '-' | '*' | '/' }
    rule func { '('  + ')' }
    rule exp {  |  }
 
    rule TOP {
        ^  $
    }
}
 
class SexpActions {
    method num($/) { make eval $/.Str }
    method func($/){
        given $ {
            when '+' { make [+]($>>.ast) } # $[0].ast + $[1].ast + ..
            when '-' { make [-]($>>.ast) }
            when '*' { make [*]($>>.ast) }
            when '/' { make [/]($>>.ast) }
        }
    }
 
    method exp($/) {
        make $/.values[0].ast;
    }
 
    method TOP($/) { make $.ast; }
}

my $s = "(+ 1 2 3 (- 7 (* 2 3)))";
my $m = Sexp.parse($s,actions=>SexpActions);
say $m.ast; # 7

前半のSexpが字句解析・構文解析に当たる部分で、ここで抽象構文木まで作ってくれます。繰り返し要素とかはyaccとかだとわざわざconsセルのような形で再帰的に定義しないといけなくていつも面倒だなーと思うのですが、ルールについても正規表現風に+とかで表現出来るのが素敵ですね。

後半のSexpActionが実際の計算部分です。アクション内では本来構文木を取得出来る.astプロパティの値を、makeを使って自分の好きなものに置き換える事が出来ます。今回は計算するだけなので、計算結果をそのまま割り当てています。

実際書いてみるとかなりシンプルに記述出来て驚きました。同等のものをPerl5の正規表現で書くとなると恐らく結構複雑になるでしょうし、Perl6に追加された中でもかなりパワフルで素晴らしい機能だと思います。

今回のソースコード全文と実際の動作例はこちら
http://ideone.com/2R1IA

仕様についてはここのS05を参照しました：
http://perlcabal.org/syn/

SKKでGoogle日本語入力APIを使う

前回の続き
http://d.hatena.ne.jp/osanine/20101003

前回pyskkservを作ったので、今回はGoogle日本語入力APIでSKKに多文節の変換を実現するというなんともあれな機能を実装してみます。

今回はGoogle IMEのAPIを使います。
http://www.google.com/intl/ja/ime/cgiapi.html

変換したい文字列を送ると変換候補がJSONで送られてくるという面白いAPIです。

変換の度にリクエストを投げるため、あんまりやるとIP制限とかを食らう可能性もあるのでその辺は自己責任でお願いします。あと変換を押してから候補が出るまでが非常に遅くなります。

本当にこの機能が使いたい人はmecab-skkserv[1]なり別のものを使うべきだと思います（

多文節の変換となると例えば、「たけやぶやけた」だと{竹薮/たけやぶ}{焼けた/やけた}のように文節ごとに候補が複数あることが多々ありますが、SKKにはそんな高級な機能は付いていませんので今回は全ての組み合わせを返すというなんとも力技な方法で実装しました。

なので長い文章を変換すると変換候補数が爆発します。ただ大抵の場合は最初のものが一番それらしい候補なので結構なんとかなったりもします。

ちなみに送り仮名を含む時は変換してもちゃんとした候補が出ないため、特に何もしないようにしています。

あとskkservは文字列をeuc-jpに一度変換しないといけないので、♡や♬などUnicode固有の記号類は一切出ません。

例)
input: たけやぶやけた
output: 1/竹やぶ焼けた/竹藪焼けた/竹薮焼けた/たけやぶやけた/タケヤブヤケタ/

input: にわにはにわにわとりがいる
output: 1/庭には二羽鶏がいる/庭には二羽ニワトリがいる/庭には二羽鶏が居る/にわにはにわにわとりがいる/ニワニハニワニワトリガイル/

まあここまでするならSKKじゃなくてATOKなり別のものを使えという話ですね、はい。

というわけでソースはこちら
http://github.com/osa9/pyskkserv

前回と比較して、
mod/GoogleAPI.pyの追加
pyskkserv.pyにモジュールの条件を追加
しただけです。

[1] http://chasen.org/~taku/software/mecab-skkserv/

Pythonでskkservを作ってみる

SKKという革命的で魔法のような入力メソッドのお話です。

SKKにはskkservという変換候補をソケットを通じて取得出来るという便利なものがありまして、仕様を調べてみたら非常にシンプルだったのでPythonでskkservのサーバを作ってみました。
(環境はMac & AquaSKK なので本家SKKで動くかは試してません)

Listenするポートは1178。
SKKからの入力は1文字のコマンドとそれに続く文字列からなります。
文字列はEUCエンコードなので注意してください。

コマンド	説明	入力	出力
0	ソケット切断		(ソケットをclose)
1	変換	変換文字列(半角スペース終端です←)	変換候補(※1)
2	バージョン情報		適当に
3	ホスト情報		適当(ry
4	abbrev	1と同じ	1と同じ

※1
例えば変換候補がHelloとWorldだとすると、
1/Hello/World/\n
のように返します。

候補がなければ
4\n
を返します。

入力例：
"1はろーわーるど "
出力例:
"1/Hello World/ハローワールド/\n"
"4\n" (候補が無い時)

簡単ですね。
まあ実際に使うのは0と1だけなので2〜4は適当に文字列を返しとけば十分です。

あとは特に書くことはないのですが、ソースコードはこちらです。
http://github.com/osa9/pyskkserv/tree/forhatena

慣れないPythonで書いて少し残念なところもありますが、気にしないでください（

起動は、
./pyskkserv.py [port] (デフォルトポート=1178)

とりあえずサンプルとして、
きょう、いま、now、today
辺りに反応して現在時刻や日付を返すものを作成してみました。

例えば、
「きょう」で変換すると「2010年10月3日」というような変換候補が出ます。

関係してるのは、
pyskkserv.py の9行目と19行目(モジュールのロードと起動条件フィルタ)
mod/CurrentTime.py
辺りです。

モジュールは簡単に追加出来るようにしていますので気が向いたらどうぞ。

(続く)

0-1ナップザック問題を並列化する

0-1ナップザック問題のDPのデータフローの図[1]を見ていたら、計算機実験[2]の時にやった並列化が適用出来そうだなあと思ったので実装してみました。

並列化の方法としては、DPの配列R[品物][容量]に対して大きく
(1)列を各スレッドで分割
(2)行を各スレッドで分割
(3)行列をブロックに分割
の3つに分けられます。

(1)は1つの列(容量)を複数のスレッドで分担して、1行ずつ同期をとって処理をしていきます。
同じ行内ではデータの依存関係がないので1行につき1回の同期を取るだけでいいので楽です。

(2)は行(品物)ごとにスレッドで分割するのですが、行同士は依存関係があります。
具体的には、R[i][j]がR[i-1][j]とR[i-1][j-W[i] ] (W[i]は品物iの重量)の結果を利用しますので、
R[i][j]を計算するには最低でもR[i-1][j]までの計算が完了していることが必要になります。
そのため、(1)に比べるとやや複雑な同期処理が必要になります。

(3)は(1)と(2)の併用です。
M×N行列を小さなブロックm×nに分割して計算します。
局所性を高めるために使うこともありますが、今回の例ではあまり使わなさそうです。

というわけで今回は普通のDP、(1)の並列化、(2)の並列化をそれぞれ実装してみました。
ソースはこの辺に置いてあります。直列がn2.c、(1)がn4.c、(2)がn3.cです。ただの再帰はn1.cですが、まあ遅くて使いものにならないです。
http://github.com/osa9/knapsack

ベンチは複数のパターンで検証するべきでしょうが、面倒なので品物=10000、容量=10000の巨大なケース×3で試してみました。
それでも計算量はO(品物*容量)なので数秒で終わってしまいますね。

微妙な差異もあるので、それぞれ5回ずつ実行し、その中で最も速かった実行時間を成績としました。
コンパイラはgcc4.0.1で、コンパイルオプションは -O2 です(並列はpthreadを使っているので-pthreadも)
実行環境はMacBookPro : Core2 Duo 2.26GHzです。

普通のDP : 3.256390s
(1) 1.890291s (2スレッド) 58%
(2) 1.980377s (2スレッド) 61%

今回は行と列のサイズが同じだったので、同期処理のやや少ない(1)が勝っていますね。
2コアなので限界はおよそ50%ですが、スレッドの生成コストなどを考慮するとまあまあじゃないでしょうか。

参考：
[1]ナップザック問題 Knapsack Problem
http://algorithms.blog55.fc2.com/blog-entry-85.html

[2]le4 parallel programming
http://www.yuasa.kuis.kyoto-u.ac.jp/~yasugi/4/top.html