あなたの圏は大丈夫？ - 手続き型言語の裏に潜む罠

Monads in PerlやAllows in Perlの話では、合成compと恒等射idを以下のように定めた。

sub comp($$) {
    my ($g, $f) = @_;
    sub { $g->($f->(@_)) };
}

sub id { @_ }

しかし、これは厳密には圏とならない。

合成の結合則 h . (g . f) == (h . g) . f が満たされない

合成によって関数の実行順を定義できるので、副作用があっても結合則は満たされる*1。しかし、関数の構造を Inspection するような機能を使うことで結合則は崩れる。Perlの場合、具体的にはcallerがそれに値する。

以下のfは呼出スタックを2つ戻ってその行数を返す関数だが、合成をかける順番によって入れ子になる関数の個数が違うため、差異が出てしまう。よってテストは失敗する。

use Test::More;

sub f { (caller(1))[2] }
*g = \&id;
*h = \&id;

my $hg_f = comp(comp(\&h, \&g), \&f);
my $h_gf = comp(\&h, comp(\&g, \&f));

is_deeply [$hg_f->()], [$h_gf->()];

恒等射の法則 id . f == f が満たされない

これはPerlの事情。Perlにはコンテキストがあるのだが、今のcompの実装では先行する関数を必ずリストコンテキストで評価してしまうため、コンテキストの変化に追従できない。

以下ではスカラコンテキストでの挙動を比較するテストが失敗する。

use Test::More;

sub f { wantarray ? 'LIST' : 'SCALAR' }

my $id_f = comp(\&id, \&f);

is_deeply [f()], [$id_f->()];
is f(), $id_f->();

結合則と恒等射の法則のテストを通してみる

以下のようにすればテストは通る。

package ComposedSub;
use overload '&{}' => sub {
    my $self = shift;
    sub {
        my $wantarray = wantarray;
        my @result;
        for (@$self) {
            @result = $wantarray ? $_->(@result) : (scalar $_->(@result));
        }
        $wantarray ? @result : $result[0];
    };
}, fallback => 1;

sub new {
    my ($class, @subs) = @_;
    bless \@subs => $class;
}


package main;
use Scalar::Util qw/blessed/;

sub id { wantarray ? @_ : $_[0] }

sub comp($$) {
    my ($g, $f) = @_;

    return $g if $f == \&id;
    return $f if $g == \&id;

    my @subs;
    for ($f, $g) {
        if (blessed $_ and $_->isa('ComposedSub')) {
            push @subs, @$_;
        } else {
            push @subs, $_;
        }
    }

    ComposedSub->new(@subs);
}

まず(h . g) . f と h . (g . f) が完全に同じ構造になるよう ComposedSub というクラスを導入している。これによって結合則が満たされ、括弧を略して h . g . f と書いても差し支えがなくなる。

また、合成時にid()を無視することで恒等射としての性質を与えている。

が、この実装もそんなによいものではない。例えば、この実装では\&main::id のみが恒等射であり、my $hoge = sub { wantarray ? @_ : $_[0] }; は恒等射ではない別の関数である。しかし、常識的に考えると \&main::id と $hoge はイコールとすべきだろう*2。しかしイコールだとすると、comp($f, \&main::id) ≠ comp($f, $hoge) の結果矛盾してしまってうまく収集がつかない。

そもそも、この実装でcompとidが本当に法則を満たしているのか、完全には保証できていない。まだ穴があるかもしれない。そうなるとイタチごっことなる。

【2012-10-11追記】この定義だと直積が定義できなくなる。具体的には<π1,π2>が$hogeとmain::idの2つとなってしまい、一意にならない。ので、CCC的性質が軒並み失われて議論にならなくなる(と思う)。

モデルと現実の差異とうまく付き合う

厳密に言えば、直感的に実装しただけではPerlの関数群は圏の性質を満たさない。しかし、「副作用は考えない」「リストコンテキストでのみ評価する」など、自分の考えているモデルに併せて実装時に制約を入れれば十分圏として機能するので、大抵の場合は問題ないはずだ。

逆に言えばモデルに課せられた制約からはみ出すような実装をすると理論的な恩恵は受けられなくなってしまうので、今回の評価時のコンテキストやcallerのように法則を破ってしまうような要素や、法則を満たすために実装時に課さなければならない制約についてはある程度把握しておくべきだろう。

*1:もちろん同値関係の入れ方によるが、ここでは副作用が同じ順番で発生したら同じ処理、くらいの意味合いで

*2:この辺りは関数群にどのような同値関係を入れるかにも関連してくる