y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

Hack でチャーチ数を使ってフィボナッチ数を計算する

Hack では ($x ==> $x + 1) という形でラムダ式を簡単に記述できます。そこで、Hack でチャーチ数を実装してフィボナッチ数を計算してみました*1

チャーチ数とは、ラムダ計算の枠組みで自然数を表現したものです。Wikipediaラムダ計算のページに説明があります。
ラムダ計算 - Wikipedia

チャーチ数を定義する

まず、チャーチ数をいくつか定義します。$zero は、$f を受け取って「$x を受け取って $x を戻す関数」を戻す関数です。これが、自然数の 0 を表現するチャーチ数になります。同様に $one は、$f を受け取って「$x を受け取って $f($x) を戻す関数」を戻す関数と定義します。$two, $three と見ていくと分かるように、$f を実行する回数が、そのチャーチ数が表現する自然数になります。

<?hh
$zero  = $f ==> $x ==> $x;
$one   = $f ==> $x ==> $f($x);
$two   = $f ==> $x ==> $f($f($x));
$three = $f ==> $x ==> $f($f($f($x)));

なぜ、これらの関数が自然数を表現しているのかを、簡単な例で確認してみます。次のようなクラスを定義します。犬はメソッド bowwow によって吠えることができます。いくら吠えても犬は犬なので $this を戻します。

<?hh
...

class Dog {
    public function bowwow() {
        echo 'ワン';
        return $this;
    }
}

次のように $bowwow と $dog を定義して、先ほど定義したチャーチ数に渡してみます。すると各行のコメントのとおり、それぞれのチャーチ数が表現する自然数の回数だけ、犬が吠えます。

<?hh
...

$bowwow = $dog ==> $dog->bowwow();
$dog = new Dog();

($zero ($bowwow))($dog); echo "\n"; // 吠えない
($one  ($bowwow))($dog); echo "\n"; // ワン
($two  ($bowwow))($dog); echo "\n"; // ワンワン
($three($bowwow))($dog); echo "\n"; // ワンワンワン

チャーチ数の上の演算を定義する

さて、ここからが面白いのですが、このように定義したチャーチ数の上に自然数の演算を定義できます。まず最初に、与えられたチャーチ数の「次の」チャーチ数を求める演算を定義します。これは、次のように簡単に定義できます。

<?hh
...

$succ = $n ==> $f ==> $x ==> $f(($n($f))($x));

$succ は、チャーチ数 $n を受け取って「$f を受け取り「$x を受け取り $f(($n($f))($x)) を戻す」関数を戻す」チャーチ数を戻します。これは一体どういうことなのか、先ほどの犬が吠える例で確認してみます。上のように定義された $succ を $n = $three, $f = $bowwow, $x = $dog として実行すると、次のように犬が 4 回吠えます。

<?hh
...

(($succ($three))($bowwow))($dog); echo "\n"; // ワンワンワンワン

このように $succ を呼び出すと、$bowwow(($three($bowwow))($dog)) が実行されます。まず、内側の ($three($bowwow))($dog) の部分で犬が 3 回吠えます*2bowwow メソッドの定義により、3 回吠えた後の戻り値は元の $dog なので、それが外側の $bowwow(...) に渡されて、もう一回吠えます。

上記のコードでは、$three, $bowwow, $dog を順番に最後まで渡してしまいましたが、$succ に $three だけを渡しておけば、それが自然数の 4 を表すチャーチ数になります。

<?hh
...

$four = $succ($three);
$five = $succ($four);

($four($bowwow))($dog); echo "\n"; // ワンワンワンワン
($five($bowwow))($dog); echo "\n"; // ワンワンワンワンワン

$succ と同様に、加算や乗算も定義できます。$m と $n の二つのチャーチ数を受け取って結果を戻します。それぞれ、犬が吠える例で考えると、$plus は「犬 ($x) が $n 回吠えて ($f)、さらに $m 回吠える ($f)」、$mult は、「犬 ($x) が「$n 回吠える ($f)」行動を $m 回繰り返す」という感じでしょうか。

<?hh
...

$plus = $m ==> $n ==> $f ==> $x ==> ($m($f))(($n($f))($x));
$mult = $m ==> $n ==> $f ==> $x ==> ($m($n($f)))($x);

なお、加算や乗算は、$succ や $plus を使ってもっと簡潔に定義することもできます。

<?hh
...

$plus = $m ==> $n ==> ($m($succ))($n);        // $n に $succ を $m 回適用する
$mult = $m ==> $n ==> ($m($plus($n)))($zero); // $zero に $plus($n) を $m 回適用する

$plus と $mult が確かに加算と乗算になっていることを確認してみます。そろそろ吠える回数が多くなってきて分かりにくいので、確認用に、チャーチ数から普通の自然数に変換する関数を用意しておきます。to_int 関数は、チャーチ数 $n を受け取り、自然数 0 に "+ 1" する操作を $n 回繰り返します。

<?hh
...

function to_int($n) {
    return ($n($i ==> $i + 1))(0);
}

echo '5 + 3 = ' . to_int(($plus($five))($three)) . "\n"; // 8
echo '5 * 3 = ' . to_int(($mult($five))($three)) . "\n"; // 15

ここまで $succ, $plus, $mult を定義してきましたが、フィボナッチ数を計算するには、一つ手前の自然数を求める必要があります。実は、これをチャーチ数で定義するのはとても難しく、次のような何が何だかさっぱり意味のわからない定義になります。

<?hh
...

$pred = $n ==> $f ==> $x ==> (($n($g ==> $h ==> $h($g($f))))($u ==> $x))($u ==> $u);

何をやっているのか意味は分からないですが、試してみると確かに一つ手前の自然数が得られているようです。

<?hh
...

echo 'pred(5) = ' . to_int($pred($five)) . "\n"; // 4
echo 'pred(1) = ' . to_int($pred($one )) . "\n"; // 0
echo 'pred(0) = ' . to_int($pred($zero)) . "\n"; // 0

さらに、フィボナッチ数を計算するには、条件分岐を扱える必要もあります。これは $pred とは異なり、次のように簡単に定義できます*3。チャーチ数 $n と、$n が 0 を表すときに戻す値 $t、0 以外の自然数を表すときに戻す値 $f を順番に受け取り、$n の値に応じて $t か $f を戻します。

<?hh
...

$ifzero = $n ==> $t ==> $f ==> ($n($x ==> $f))($t);

echo 'ifzero(0) = ' . to_int((($ifzero($zero ))($one))($zero)) . "\n"; // 1
echo 'ifzero(3) = ' . to_int((($ifzero($three))($one))($zero)) . "\n"; // 0

不動点演算子を用いてフィボナッチ数を計算する

ここまでで必要な部品が揃ったので、フィボナッチ数を計算する関数を定義します。括弧が多くなりどうしても見難いのですが、これまでに定義してきた関数を使って、以下のように定義できそうです。

<?hh
...

// これは動きません
$fib = $n ==>
  ((($ifzero($n))                                                  // if (n == 0)
    ($u ==> $zero))                                                // then 0
    ($u ==>                                                        // else
      ((($ifzero($pred($n)))                                       //   if (n == 1)
        ($u ==> $succ($zero)))                                     //   then 1
        ($u ==> ($plus($fib($pred($n))))($fib($pred($pred($n)))))) //   else fib(n - 1) + fib(n - 2)
      ($u ==> $u)))
  ($u ==> $u)

ところが、上記のコードは動作しません。フィボナッチ数の計算では $fib 自身を再帰的に呼び出す必要がありますが、この $fib は右辺の式全体の別名であり、右辺の中で $fib 自身を使うことはできないためです。ラムダ計算再帰呼び出しを実現するには、特別な工夫が必要です。

ラムダ計算再帰呼び出しを実現する仕組みとして、次のような関数を定義します*4。これもまた $pred と同様さっぱり意味がわからないのですが、このように定義した $fix を使うことでラムダ計算再帰呼び出しができるようになります。

<?hh
...

$fix = $f ==> ($x ==> $f($y ==> ($x($x))($y)))($x ==> $f($y ==> ($x($x))($y)));

$fix を使ってフィボナッチ数を計算する関数を定義したものは、以下のとおりです。再帰呼び出ししたい関数 $fib 自体を引数として受け取る形にして、全体を $fix に渡します。こうすることで、なぜか再帰呼び出しができるようになります。

<?hh
...

$fibonacci = $fix(
  $fib ==> $n ==>
    ((($ifzero($n))
      ($u ==> $zero))
      ($u ==>
        ((($ifzero($pred($n)))
          ($u ==> $succ($zero)))
          ($u ==> ($plus($fib($pred($n))))($fib($pred($pred($n))))))
        ($u ==> $u)))
    ($u ==> $u)
);

$fibonacci がたしかにフィボナッチ数の計算になっていることを確認します。

<?hh
...

for ($n = $zero; to_int($n) <= 10; $n = $succ($n)) {
    echo 'fibonacci(' . to_int($n) . ') = ' . to_int($fibonacci($n)) . "\n";
}

// 順に 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 と正しく計算されます

h2tp で PHP のプログラムに変換する

最近の HHVM では、Hack のコードを PHP に変換してくれる h2tp というツールが提供されるようになりました。これを利用して PHP のプログラムを出力させてみます。以下の実行例のように、適当なディレクトリに Hack のプログラムを保存して、h2tp コマンドを実行します。コマンドの引数には、変換元ディレクトリと変換先ディレクトリを指定します。変換先ディレクトリは h2tp が自動的に作成するようです。

$ LANG=C tree
.
`-- hack
    `-- church_sample.hh

1 directory, 1 file
$ h2tp hack php
The Conversion was successful

出来上がった PHP のコードを見てみると、ラムダ式PHP の無名関数に変換されていることがわかります。以下は $one の例です。

<?php
...

$one = function ($f) {
  return function ($x) use ($f) {
    return $f($x);
  };
};

ただし、現在の h2tp は、以下の $succ のように PHP 5.x では実行できないシンタックスのコードを出力してしまう場合もあります。

<?php
...

$succ = function ($n) {
  return function ($f) use ($n) {
    return function ($x) use ($f, $n, $f) {
      return $f($n($f)($x));
    };
  };
};

内側の関数で $f($n($f)($x)) という部分は PHP 5.x の文法では認められていません。PHP 5.x では $n($f) の結果を一度変数に代入する必要があります。PHP 7 では実行できるようです*5

*1:この記事に対応するプログラムは y-uti/hack-church-numerals · GitHub にあります。記事では説明を省略した $pred, $fix についてもソースコードに説明を追加しています。

*2:「まず」何が起きるかというのはプログラミング言語によって違う部分なので注意が必要です。ラムダ計算では計算の順序については特に決められていません。Hack では、多くのプログラミング言語と同様に「関数を呼び出す前に引数を計算する」順序になります。

*3:チャーチ数を定義したのと同様に、ラムダ式で true と false を表現し、その上に論理演算や if を定義していくこともできます。今回の記事では論理値を導入せずにチャーチ数だけで済ませるため、チャーチ数の上の演算として ifzero を定義しました。

*4:この定義は Z コンビネータというものです。不動点演算子には色々な定義が知られており、一番有名なものは Y コンビネータと呼ばれています。Y コンビネータは、Hack のような「関数呼び出しの前に引数を計算する」言語では動作しません。このような言語でも動作するように Y コンビネータを拡張したものが Z コンビネータです。

*5:ちなみに、このコードは HHVM でも実行できません。HHVM では、今回の記事で書いてきたプログラムのように、($n($f))($x) と一つずつ括弧で囲む必要があります。