読者です 読者をやめる 読者になる 読者になる

北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

モナドのdo記法をPerlのCoroで実装してみた

先に言っときますが、決して役に立つエントリではないので圏論やコルーチンみたいなものに興味がある人だけどうぞw

PythonにおけるHaskellチックなdo記法をジェネレータで実装する方法に心惹かれたので、Perlで真似してみました。

ジェネレータはコルーチン的な振る舞いをするので、PerlではCoroを使うと楽でしょう。以前のエントリで作ったMaybeモナド*1を利用して、以下のようなシンタックスシュガーを作ってみます。

my $may_div = sub {
    my ($x, $y) = @_;
    return $y ? just($x / $y) : nothing;
};

my $maybe_divs = do_monad {
    my $v1 = retrieve $may_div->(3.0, 1.0);
    my $v2 = retrieve $may_div->(2.0, 1.0);
    return $may_div->($v1, $v2);
} $list_monad;

my $maybe_value = $maybe_divs->();

print +(ref $maybe_value ? @$maybe_value : $maybe_value), "\n";

「do_monad {} モナド名」が Haskell の do で、 retrieve が <- の記法を意味しています。この記法を実現するには、sub {$kleisli_div->(3.0, 1.0)} と sub {my $v1 = shift; $kleisli_div->(2.0, 1.0) } と sub { my $v2 = shift; $kleisli_div->($v1, $v2) } のようにdo_monad内の処理を retrieve で分割された 3つの関数と見なしてクライスリ結合を行う必要があります*2

ということで、 retrieve の前後でメインスレッドと強調動作するコルーチンとして実装するとうまく行きます。以下のような実装になります*3。ミソは再帰する $next_kleisli 関数で、こいつが retrieve の左右をクライスリ結合で矛盾の起きないように繋ぎます。retrieveの右側で発生したモナドを、クライスリ射である$next_kleisli経由でretrieveの左側の変数に流し込んで合成します。

use Coro::Generator;
use Devel::Caller qw/caller_cv/;

sub do_monad(&$){
    my ($code, $monad_class) = @_;

    return sub {
        my @args = @_;

        my $result_as_monad;
        my $instruction_iter = generator {
            $result_as_monad = $code->(@args);
            yield undef while 1;
        };

        my $next_kleisli = sub {
            my @val = @_;
            my $monad = $instruction_iter->(@val);
            if($monad){
                return $monad_class->flat->(caller_cv 0)->($monad);
            }else{
                return $result_as_monad;
            }
        };

        return $next_kleisli->();
    };
}

sub retrieve($){
    my $monad = shift;
    return yield $monad;
}

Devel::Callerは、再帰する無名関数の実現のために使っており、 caller_cv 0 がJSでいうarguments.calleeとなります。

ちなみに、この do_monad の実装にはまずい部分があって、クライスリ結合した時にコルーチン側の処理を呼ばないことがあると、ロジックが破綻します。例えば、MaybeのNothingが返された場合の合成がこれにあたります。これは、コルーチンにおいて、真ん中の処理だけskipすることは難しいってことに起因しています。

この実装で Maybe の Nothing のようなものが現れると、以降の処理は合成されずに無視されます。なので、Nothingになった後にまたJustへ復帰するような処理を表現することはできません。

なお、実際に動く実装が欲しければ、書きっぱなしのものですがここここにあります。今回は横着して以前のエントリで実装したモナドを使ったので、etaやmuみたいな圏論の内蔵が丸見えな実装になってますが、もっとシンプルに実装し直した方がわかりやすくなる気はします。

*1:あんまいい実装じゃないけど作り直すの面倒なんでとりあえず。

*2:厳密にはカリー化して考えなきゃならないのでちと違いますが。元エントリを参照するといいです。

*3:【7/20追記】元はCoro::Channelを使って実装してたのですが、Coro::Generatorの方がシンプルになるので書き換えました