fixed point operator による再帰的な記述の除去

fixed point operator があれば、再帰的な記述を再帰しない記述に直せる。再帰的な記述とは、例えば、以下のようなもの。

my $fact = sub {
    my $x = shift;
    $x <= 1 ? 1 : $x * $fact->($x - 1);
};

階乗を求める関数$factの定義内で、$factを参照している。これは一見実行できそうに見えるが、sub の中をコンパイルする段階では$factがまだ未定義のため実行できない*1。これを再帰しない記述に変えるために、fixed point operator というものが使える。fixed point operator とは、以下の性質を満たす$make_fixed_point。

my $x = $make_fixed_point->($f);
$f->($x) eq $x;

任意の$fについて、自身のfixed point($fを適用しても動かない点)を生成できる。ここで、"eq" は同じ関数であるという意味*2。

fixd point operator を使って再帰的な記述を除くには、まず、再帰的な記述を束縛してやる。ここでは$fとして束縛し、それを$baseと置く。

my $recursive = sub {
    my $x = shift;
    # ここに $recursive と $x を使った式が書かれている
};

↓

my $base = sub {
    my $f = shift;
    sub {
        my $x = shift;
        # ここに $f と $x を使った式が書かれる
    };
};

この$baseにfixed point operator を適用すると、元の関数と同等の動作をし、かつ、再帰的な記述のない関数ができる。

my $non_recursive = $make_fixed_point->($base);

これがなぜ元の$recursive と同等かと言えば、$non_recursiveが $base のfixed point であるために、以下のような同値が成り立つからである。結局は、$non_recursive を参照していることになる。

$non_recursive eq $base->($non_recursive)

 eq 

(sub {
    my $f = shift;
    sub {
        my $x = shift;
        # ここに $f と $x を使った式が書かれる
    };
})->($non_recursive)

 eq

sub {
    my $x = shift;
    # ここに $non_recursive と $x を使った式が書かれる
}

ということで、最初の$factを書き換えてみるとこうなる。

my $fact = $make_fixed_point->(sub {
    my $f = shift;
    sub {
        my $x = shift;
        $x <= 1 ? 1 : $x * $f->($x - 1);
    };
});

後必要なのは、$make_fixed_point の実装だ。これは無数に存在することが知られているが、みんな大好きYコンビネータもこの要件を満たしてくれる。Yコンビネータがこの要件を満たすことは、λ計算の方法さえわかれば簡単に確かめられる。Yコンビネータを愚直に実装すると以下。

sub _in_y($) {
    my $f = shift;
    sub {my $x = shift; $f->($x->($x))};
}

sub operator_y {
    my $f = shift;
    (_in_y $f)->(_in_y $f);
};

ところが、この実装はDeep recursion となって動作しない。wikipediaによれば「> Yコンビネータは値渡しの場合は (Y g) が（任意のgについて）展開されてしまうので、プログラミング言語が名前渡し評価戦略をサポートしている場合のみ有用である。」とのこと。

幸いなことに、Yコンビネータをη変換すれば使えるとのことが書いてあるので、ここは深く考えずにwikipediaに載っているZをそのまま利用する。今までの話をすべて合わせて、再帰の記述のない$factを作ったのが以下である。

sub _in_z($) {
    my $f = shift;
    sub {
        my $x = shift;
        $f->(sub {
            my $y = shift;
            ($x->($x))->($y);
        });
    };
}

sub operator_z {
    my $f = shift;
    (_in_z $f)->(_in_z $f);
};

my $make_fixed_point = \&operator_z;
my $fact = $make_fixed_point->(sub {
    my $f = shift;
    sub {
        my $x = shift;
        $x <= 1 ? 1 : $x * $f->($x - 1);
    };
});

print $fact->(1), "\n";
print $fact->(2), "\n";
print $fact->(3), "\n";
print $fact->(4), "\n";

__END__

【実行結果】
1
2
6
24

・・・と、本からまるっと移しただけですが、Yコンビネータは下手に実装を考えると何がなんだか意味不明のものですが、こうやって経緯を順に見てみるとそんなに摩訶不思議なものではないですね。やっぱり複雑なものを考える時には抽象化は大事です。

参考資料

*1:my $fact; $fact = ... というAnyEventでおなじみのイディオムを使えば可能。

*2:正確には、α変換やβ変換すれば等しくなるという意

Pixel Pedals of Tomakomai

北海道苫小牧市出身の初老の日常

fixed point operator による再帰的な記述の除去

参考資料