不動点コンビネータ

提供: miniwiki
移動先:案内、検索
曖昧さ回避 「Yコンビネータ」は不動点演算子について説明しているこの項目へ転送されています。カリフォルニア州の企業については「Yコンビネータ (企業)」をご覧ください。

不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる。ここで関数fの不動点とは、f(x) = xを満たすようなxのことをいう。

すなわち高階関数g が不動点コンビネータであるとは、

任意の関数f に対し、p = g(f)とすると, f(p) = p が成立する

事を指す。

不動点コンビネータの定義は、任意の関数f に対し、

[math]f(\mathbf{g}(f))=\mathbf{g}(f)[/math]

が成立する事であるとも言い換えられる。

第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子に束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。[1][2]

不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算（英: untyped lambda calculus）においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。

不動点コンビネータによる再帰の実現

不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。一方、循環なく関数の意味を定義する（できる）、ということは、計算理論の上では重要である。

まず、再帰関数の性質を簡単に振り返り、記号をいくつか定義する。関数a が再帰的に定義されているとき、aの定義式は何らかの高階関数U を用いて、

[math]a(x) = U(a,x)[/math] ...(1)

と書ける。たとえばa(x) がxの階乗を計算する関数である場合、Uとして

[math]U(f,x) = \begin{cases} 1 & \text{ if } x=0 \\ x * f(x-1) &\text{else}\end{cases}[/math]

を取る事ができる。上述のように定義されたU が(1)を満たすのは明らかであろう。

U を用いて高階関数[math]V[/math]を

[math]V~:~f \mapsto U(f,\cdot)[/math] ...(2)

と定義する。 （すなわちVは関数f を入力として受け取ると 関数「[math]x \mapsto U(f,x)[/math]」を出力する高階関数である。 ラムダ計算の用語で言えば、V はU のカリー化[math]\lambda f.~ (\lambda x.~ U)[/math]にあたる。） V の定義より、[math]V(f)[/math]はそれ自身関数であり、任意のx に対し、

[math]V(f)(x)=U(f,x)[/math] ...(3)

が成り立つ。ここで[math]V(f)(x)[/math]は関数[math]V(f)[/math]にx を入力したときの値。


さて、g を不動点コンビネータとするとき、不動点コンビネータの定義より特に、 [math]\mathbf{g}(V)[/math]はV の定義域の元である事が分かる。 V の定義域は関数の集合だったので、これはすなわち[math]\mathbf{g}(V)[/math]はそれ自身関数である事を意味する。 この関数[math]\mathbf{g}(V)[/math]が(1)式で定義された再帰関数a と一致する事を示す事ができる（後述）。

よって以下のようにすれば不動点コンビネータg で再帰関数a を実現できる事になる：

  1. U のプログラムを書く。
  2. V を(2)式のように定義し、[math]a=\mathbf{g}(V)[/math]とする。

[math]a=\mathbf{g}(V)[/math] の証明

最後に[math]\mathbf{g}(V)[/math]が(1)式で定義された再帰関数a と一致する事を示す。 不動点コンビネータの定義より、[math]\mathbf{g}(V)[/math]は

[math]V(\mathbf{g}(V))=\mathbf{g}(V)[/math] ...(4)

を満たす。

前述したように[math]\mathbf{g}(V)[/math]はそれ自身関数なので、値xに対し[math]\mathbf{g}(V)(x)[/math]を考える事ができる。 [math]\mathbf{g}(V)(x)[/math]は以下を満たす：

[math]\mathbf{g}(V)(x) [/math] [math]=V(\mathbf{g}(V))(x) [/math] ((4)より)
[math]=U(\mathbf{g}(V),x) [/math]、 ((3)より)

すなわち

[math]\mathbf{g}(V)(x)=U(\mathbf{g}(V),x)[/math]。 ...(5)

(1)と(5)を見比べると、(5)は(1)でaを[math]\mathbf{g}(V)[/math] に置き換えたものに等しい事が分かる。 (1)はa の（再帰的な）定義式であったので、これはすなわち[math]\mathbf{g}(V)[/math] がa の定義式を満たす事を意味する。 よって

[math]a=\mathbf{g}(V)[/math]。

が成立する事が分かった。

不動点コンビネータの例

型無しラムダ計算や組合せ論理などの特定の数学的な計算形式化においては、すべての式は高階関数とみなすことができる。これらの形式化では、不動点コンビネータが存在することはすなわち、すべての関数が少なくとも1つの不動点を持つことを意味する。さらに、関数は複数の異なる不動点を持つことができる。

単純型付きラムダ計算などの他のいくつかの体系では、十分に型付けされた不動点コンビネータを書くことはできない。それらの体系で再帰をサポートするには、明示的に言語体系に組み込む必要がある。それでも再帰データ型によって拡張された単純型付きラムダ計算などでは不動点演算子を書くことができるが、ある種の「実用的な」不動点演算子（常にいずれかの適用を返すもの）は制限される。多相ラムダ計算（英: polymorphic lambda calculus、システムF、英: System F）では多相不動点コンビネータは型∀a.(a→a)→aを持つ（aは型変数）。

Yコンビネータ

型無しラムダ計算においてよく知られた（そしておそらく最もシンプルな）不動点コンビネータはYコンビネータと呼ばれる。これはハスケル・カリーによって発見されたもので、次のように定義される。

Y = (λf . (λx . f (x x)) (λx . f (x x)))

実際に関数gを適用することによって、この関数が不動点コンビネータとして動作するのが分かる。

Y g = (λf . (λx . f (x x)) (λx . f (x x))) g (Yの定義より)
= (λx . g (x x)) (λx . g (x x)) (λfのβ簡約、主関数をgに適用)
= (λy . g (y y)) (λx . g (x x)) (α変換、束縛変数の名前を変える)
= g ((λx . g (x x)) (λx . g (x x))) (λyのβ簡約、左の関数を右の関数に適用)
= g (Y g) (第2式より)

これをそのままラムダ計算で使うと、評価戦略が値渡しだった場合には (Y g) が (g (Y g)) と展開された後も、引数の値を先に求めようとして (g (g (Y g))) →...→ (g ... (g (Y g))...) のように無限に展開され続けて止まらなくなってしまうので、次節で示すZコンビネータのように修正する。評価戦略が名前渡しの場合はこのまま使える。

このカリーによるコンビネータのみをYコンビネータとすることもあるが、実装などでは不動点コンビネータを指す名前として他の形であってもYという名前を使っていることもある（#グラフ簡約の節の注を参照せよ）。

SKIコンビネータ計算では次のようになる。

Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))

Zコンビネータ

値渡し評価（適用順序）でも使用可能なバージョンのYコンビネータは、通常のYコンビネータの一部をη変換することで与えられる。

Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

以下はPythonによる例である。 

>>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))
>>> fact = lambda f: lambda x: 1 if x == 0 else x * f(x-1)
>>> Z(fact)(5)
120

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(function(f) { return function(n) { return n == 0 ? 1 : n * f(n - 1); }; })(5) == 120

チューリング不動点コンビネータ

もう一つの一般的な不動点コンビネータは、チューリング不動点コンビネータである（発見者であるアラン・チューリングの名にちなむ）。

Θ = (λx. λy. (y (x x y))) (λx. λy. (y (x x y)))

これはシンプルな値渡し形式も持つ。

Θv = (λx. λy. (y (λz. x x y z))) (λx. λy. (y (λz. x x y z)))

SとKによる最もシンプルな不動点コンビネータ

SKIコンビネータ計算のSとKによる最もシンプルな不動点コンビネータは、ジョン・トロンプによって発見された以下であり、

Y' = S S K (S (K (S S (S (S S K)))) K)

これは次のラムダ式と対応する。

Y' = (λx. λy. x y x) (λy. λx. y (x y x))

その他の不動点コンビネータ

型無しラムダ計算における不動点コンビネータは無数に存在するので、特に珍しいわけではない。2005年、メイヤー・ゴールドバーグ (Mayer Goldberg) は型無しラムダ計算の不動点コンビネータの集合が帰納的可算集合であることを示した。[3]

次のようないくつかの不動点コンビネータ（ジャン・ウィレム・クロップによって組み立てられた）は、主として遊びに使われる。

Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)

ここで

L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

非標準不動点コンビネータ

型無しラムダ計算には不動点演算子と同じボーム木（英: Böhm tree）を持つラムダ式がある。すなわちそれらはλx.x(x(x ... ))と同じ無限の拡張を持つ。これは非標準不動点コンビネータ（英: non-standard fixed point combinators）と呼ばれる。定義より、あらゆる不動点コンビネータは非標準でもあるが、すべての非標準不動点コンビネータが不動点コンビネータであるわけではない。それらのいくつかは「標準」の定義を満たさないからである。これらの変わったコンビネータは特にstrictly non-standard fixed point combinatorsと呼ばれる。例として、B = λx.xxかつM = λxyz.x(yz)としたときのコンビネータN = BM(B(BM)B)が挙げられる。非標準不動点コンビネータの集合は帰納的可算集合ではない。[3]

不動点コンビネータの実装

これまでの節で実装というよりは主に理論の観点から述べてきた、評価戦略が名前渡しの場合と値渡しの場合の違いは、実装においては、非正格(non-strict)なプログラミング言語（ないし処理系）と正格(strict)な言語の場合にほぼそのまま対応する。非正格な（遅延評価の、と言い換えてもだいたい同じ。具体的にはHaskellなどがそう）言語ないし処理系においては、ほぼ不動点コンビネータの意味そのままに循環的に実装できる。正格な場合は修正が必要であり、後述する。理論的には循環が無いことに意味があったが、実装においては循環的で普通は問題が無く、そのほうが効率的でもある。以下にHaskellによる不動点コンビネータの実装を示す。この不動点コンビネータはHaskellにおいては伝統的にfixと呼ばれる。fixは多相不動点コンビネータであることに注意せよ（前述のシステムFに関する議論も参照）。なお、Haskellには型推論があるが、以下では曖昧さをなくすために型は明記する（一般に、こういった特殊な型を使う場合は型を明記したほうが良いし、推論の実装の限界のために明記が必要なこともある）。定義の後に使用例が続く。

なお、型無しラムダ計算におけるカリーのYコンビネータは、そのまま実装しようとすると、Haskellの型チェッカによって拒否される。[4] 

fix :: (a -> a) -> a
fix f = f (fix f)

fix (const 9) -- constは第1引数を返し、第2引数を捨てる関数。9と評価される

factabs fact 0 = 1 -- factabsはラムダ計算の例のFから拝借
factabs fact x = x * fact (x-1)

(fix factabs) 5 -- 120と評価される

fixの適用は遅延評価されるので無限ループにはならない。たとえばfix (const 9)が(const 9)(fix f)として展開されるとき、部分式fix fは評価されない。ところが、Haskellによるfixの定義を正格(strict)プログラミング言語に持ち込むと無限ループになる。なぜなら、fへ渡した引数は事前に展開され、無限の呼び出しの連続f (f ... (fix f) ... ))を生み出すからである。

MLのような正格言語においては、クロージャの使用を強制することによって無限再帰問題を回避することができる。fixの正格なバージョンは型∀a.∀b.((a→b)→(a→b))→(a→b)を持つべきである。要するに、これは関数を取って返す関数でのみ動く。例として、以下はfixの正格なバージョンのOCamlコード実装である。 

let rec fix f x = f (fix f) x (* 余分なxに注目 *)

let factabs fact = function (* factabsはエクストラレベルのラムダ抽象 *)
 0 -> 1
 | x -> x * fact (x-1)

let _ = (fix factabs) 5 (* "120" と評価される *)

これと同じアイデアは（この場合は「貧乏人のクロージャ (poor man's closures) 」として使われる）メソッド内部のインナークラス（Javaではローカルインナークラスと呼ばれる）をサポートしている正格言語で（単相）不動点コンビネータを実装するのに用いることができる。Javaの場合、そのようなクラスが無名だとしても構文はなお扱いにくい（Javaコード）。たとえば、C++の関数オブジェクトでは呼び出し構文は単純化されるが、それらはまだ生成されている段階である。できればboost::bindのような補助関数を用いることが望ましい（C++コード）。

再帰型による符号化の例

再帰データ型（システムFωを参照）をサポートしているプログラミング言語では、型レベルで再帰を適切に計算することによってYコンビネータの型付けが可能になる。変数xを自己適用する必要性は同型の (Rec a -> a) を用いて定義される型 (Rec a) によって管理することができる。

例として、以下のHaskellコードは、型とともに同型写像のInとoutの2つの方向の名前を持つ。 

In :: (Rec a -> a) -> Rec a
out :: Rec a -> (Rec a -> a)

そして次のように書くことができる。 

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

OCamlによる等価なコードは以下。 

type 'a recc = In of ('a recc -> 'a)
let out (In x) = x

let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a))

グラフ簡約

ファイル:FixedPointCombinatorGraphReduction.svg

グラフ簡約（en:Graph reductionを参照）による計算系では、不動点コンビネータへの適用(apply, application)は理論通り展開しても良いが、左の図のように循環のあるグラフに簡約するという一種の、のぞき穴的最適化が知られている。また、これはカリーのYコンビネータではないが(この図のように)便宜的にYという名前で呼ばれていることもある[5]。

他の手段による無名再帰

不動点コンビネータは識別子に束縛されていない関数が自分自身を呼び出す一般的な方法であるが、言語によっては特別な名前などで自分自身を呼び出すことができる。たとえばJavaScriptでは自分自身を参照することができるような名前が用意されており次のように書くことができる。 

// 120を返す
(function(x){
    return x == 0
         ? 1
         : x * arguments.callee(x - 1); // arguments.calleeは自分自身を指す
})(5);

（なお、ECMAScript5のstrict modeではarguments.calleeの使用は禁止されている[6]）

関連項目

脚注

  1. ↑ This terminology appear to be largely folklore, but it does appear in the following:
    • Trey Nash, Accelerated C# 2008, Apress, 2007, ISBN 1590598733, p. 462--463. Derived substantially from Wes Dyer's blog (see next item).
    • Wes Dyer Anonymous Recursion in C#, February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.
  2. ↑ The If Works Deriving the Y combinator, January 10th, 2008
  3. ↑ 3.0 3.1 Goldberg, 2005
  4. ↑ Haskell mailing list thread on How to define Y combinator in Haskell, 15 Sep 2006
  5. ↑ たとえば、Turnerの"A New Implementation Technique for Applicative Languages"（doi:10.1002/spe.4380090105）の Figure. 3 と、その直前の説明を見よ。
  6. ↑ https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions_and_function_scope/arguments/callee

参考文献



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=不動点コンビネータ&oldid=111523」から取得