無名再帰

りょうじ

１月１０日木曜日、晴れ

年末に修正していたバグがいくつか検証を通過してクローズされた。残っていたバグも全部かたづけた。

しかるにまだサーバー側コードの修正に合わせて実装を変更せねばならない。プチ（デス）マーチ感……。

＊　＊　＊

再帰関数とは自分で自分を呼び返して計算する関数のことで、プログラマーはフィボナッチ数列だとか階乗だとかの計算に使う例をよく見るはずだ。（ソートでもよく出る）

再帰関数は美しいんだけれど、慣れないうちは気持ち悪い。
それはつまり GNU の定義みたいなもので（GNU is Not Unix の頭文字を集めたもの）、その定義で自己言及するから結局定義がよくわからない、というもの。（再帰関数の実用では停止条件を入れるので、どこかで止まるんだけれど）

さて。再帰関数は一般に、関数自身の名前で自分を呼び出して再帰する。
ところで「無名再帰」というものがあって、これは名前を使わずに再帰を実現する。

上記 Wikipedia ページに JavaScript の例として以下コードが書かれている。

function Z(f) {
    return (function(x) {
        return f(function(y) {
            return x(x)(y);
        });
    })(function(x) {
        return f(function(y) {
            return x(x)(y);
        });
    });
}

地味に読みづらかったのでアロー演算子を使って書き直してみる。

Z = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))

これを使って階乗を計算できる。
どれどれ？

Z(f => n => n ? n * f(n - 1) : 1) (5) // => 120

できた。

f はラムダ引数なので、たしかに（f を引数とした）関数に名前はついていないのだけれど、引数には（当然）名前がついている。その引数（の名前）で再帰呼び出しをしている……ように見える。なんだか騙されている気がする。

Z コンビネーターの定義は読みづらい。それぞれ途中のラムダ関数に名前をつけないことで無名再帰と言っているのだから本末転倒な気がするけれど、途中の無名関数に名前を振ってみると構造が見えやすくなる。

Z = f => { const g = x => f(y => x(x)(y)); return g(g); }

つまり Z は、 f を引数として呼びだされると、高階関数 g を生成して、高階関数 g を自身 g を引数にして呼び出しその結果を返す。（g 自身に g を適用する……、同じことだけれど言い換えてみた）

＊　＊　＊

Z は関数を一級の言語要素として扱える言語なら、再帰を実現するために使えて実際に動く。

一方で Y というコンビネーターもある。

JavaScript で（アローを使って）定義すると、こういう形。

Y = f => (x => f (x, x))(x => f (x, x))

ただし「不動点コンビネータ」に以下のように書かれているとおり、 JavaScript では Y コンビネーターはつかえない。

評価戦略が値渡しだった場合には (Y g) が (g (Y g)) と展開された後も、引数の値を先に求めようとして (g (g (Y g))) →...→ (g ... (g (Y g))...) のように無限に展開され続けて止まらなくなってしまう

次のように階乗を計算させようとすると……

Y((f, n) => (n == 0 || n == 1) ? 1 : n * f(f, n - 1))(10) // 階乗計算

スタックオーバーフローしてしまう。

Uncaught RangeError: Maximum call stack size exceeded
at Function.valueOf (<anonymous>)
at Y (<anonymous>:1:16)
at Y.x (<anonymous>:1:31)
at Y (<anonymous>:1:42)
at Y.x (<anonymous>:1:31)
at Y (<anonymous>:1:42)
at Y.x (<anonymous>:1:31)
at Y (<anonymous>:1:42)
at Y.x (<anonymous>:1:31)
at Y (<anonymous>:1:42)

（先日つくった Lisp なら、 Y コンビネーターによる再帰を実行できた。 Lisp では引数は名前渡しで関数適用時に評価するため）

＊　＊　＊

C 言語も引数を先に評価してから関数を呼び出すので Y コンビネーターは無理……かとおもいきや、以下ページに何か紹介されていた。

ちょっとだけアレンジして再実装。（構造体の名前を function でなくて object にした）

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

typedef struct object *OBJECT;
struct object {
  void *o; // function pointer (or number)
  void *_; // function context (something like a closure)
};

OBJECT new(OBJECT (*f)(OBJECT, OBJECT), OBJECT _) {
  OBJECT o = malloc(sizeof(*o));
  o->o = f;
  o->_ = _;
  return o;
}

OBJECT call(OBJECT f, OBJECT n) {
  OBJECT g = f->_;
  OBJECT (*fn)(OBJECT, OBJECT) = g->o;
  return fn(f, n);
}

OBJECT Y(OBJECT (*f)(OBJECT, OBJECT)) {
  OBJECT g = new(f, NULL);
  g->_ = g;
  return g;
}

OBJECT num(int n) {
  return new((void *)(intptr_t)n, NULL);
}

int val(OBJECT n) {
  return (intptr_t)n->o;
}

OBJECT fac(OBJECT self, OBJECT n) {
  int nn = val(n);
  return nn == 0 || nn == 1
    ? num(1)
    : num(nn * val(call(self, num(nn - 1))));
}

OBJECT fib(OBJECT self, OBJECT n) {
  int nn = val(n);
  return nn == 0 || nn == 1
    ? num(1)
    : num(val(call(self, num(nn - 1))) + val(call(self, num(nn - 2))));
}

int main() {
  int i;
  OBJECT f;
  f = Y(fac);
  printf("fac:");
  for (i = 0; i < 9; ++i)
    printf(" %d", val(call(f, num(i))));

  puts("");

  f = Y(fib);
  printf("fib:");
  for (i = 0; i < 9; ++i)
    printf(" %d", val(call(f, num(i))));

  return 0;
}

しかし C だと（関数は一級の要素でないため） fib や fac などの名前つき関数を経由しないといけない。この時点で Y コンビネーターと言うには苦しいんじゃないか、という気はする。

関数ポインターを使って呼び出す関数を覚えること、そして call という補助関数を使って適用の時間を遅延させるところがポイントのよう。

ところでこれ、さらに次のように簡略化できる。

#include <stdint.h>
#include <stdio.h>

typedef struct object *OBJECT;

OBJECT call(OBJECT f, OBJECT n) {
  OBJECT (*fn)(OBJECT, OBJECT) = (void *)f;
  return fn(f, n);
}

OBJECT Y(OBJECT (*f)(OBJECT, OBJECT)) {
  return (void *)f;
}

OBJECT num(int n) {
  return (void *)(intptr_t)n;
}

int val(OBJECT n) {
  return (intptr_t)n;
}

OBJECT fac(OBJECT f, OBJECT n) {
  return val(n) == 0 || val(n) == 1
    ? num(1)
    : num(val(n) * val(call(f, num(val(n) - 1))));
}

OBJECT fib(OBJECT f, OBJECT n) {
  return val(n) == 0 || val(n) == 1
    ? num(1)
    : num(val(call(f, num(val(n) - 1))) + val(call(f, num(val(n) - 2))));
}

int main() {
  int i;

  printf("fac:");
  for (i = 0; i < 9; ++i)
    printf(" %d", val(call(Y(fac), num(i))));

  puts("");

  printf("fib:");
  for (i = 0; i < 9; ++i)
    printf(" %d", val(call(Y(fib), num(i))));

  return 0;
}

malloc も消えて随分スッキリ、なんだけれど Y がちっとも Y でないのが気になる。でも確かにこの実装でも再帰する。 fib や fac の「名前」は call の中にも、そして fib や fac の中にも出てこない。

魔法は call にあって、スタックに関数ポインター自身を複製して置いている。これが実際のところ Y の作用なんじゃないか──？　という気はする。

難しい。計算機科学、奥が深い。

いいなと思ったら応援しよう！