不動点コンビネータ

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動: 案内、 検索
曖昧さ回避 「Yコンビネータ」は、この項目へ転送されています。この項目では不動点演算子について記述しています。カリフォルニア州の企業については「Yコンビネータ (企業)」をご覧ください。

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

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

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

事を指す。 なお本稿では単に「関数」といった場合は定義域も値域もビット列の集合であるような関数の事を指す。

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

f(\mathbf{g}(f))=\mathbf{g}(f)

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

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

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


目次

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

不動点コンビネータは第一級関数をサポートしているプログラミング言語において再帰を実現する為に用いる事ができる。

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

a(x) = U(a,x) ...(1)

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

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

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

U を用いて高階関数Vを

V~:~f \mapsto U(f,\cdot) ...(2)

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

V(f)(x)=U(f,x) ...(3)

が成り立つ。

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

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

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

a=\mathbf{g}(V) の証明 [編集]

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

V(\mathbf{g}(V))=\mathbf{g}(V) ...(4)

を満たす。

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

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

すなわち

\mathbf{g}(V)(x)=U(\mathbf{g}(V),x)。 ...(5)

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

a=\mathbf{g}(V)。

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

不動点コンビネータの例 [編集]

型無しラムダ計算や組合せ論理などの特定の数学的な計算形式化においては、すべての式は高階関数とみなすことができる。これらの形式化では、不動点コンビネータが存在することはすなわち、すべての関数が少なくとも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コンビネータは値渡しの場合は (Y g) が（任意のgについて）展開されてしまうので、プログラミング言語が名前渡し評価戦略をサポートしている場合のみ有用である。

その他の不動点コンビネータ [編集]

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

値渡し評価（適用順序）でも使用可能なバージョンの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

YコンビネータはSKIコンビネータ（英: SKI combinator calculus）を使って、次のように表現することができる。

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

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

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))

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

Θ = (λ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)))

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

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]

不動点コンビネータの実装 [編集]

Haskellのように遅延評価をサポートしている言語においては、不動点コンビネータの定義式を利用して不動点コンビネータを定義することができる。この種のプログラミング言語ではその（遅延）再帰機構を用いて効率的に不動点コンビネータの式を解くことができる。Haskellによるこの不動点コンビネータの実装は、しばしばHaskellによるYコンビネータの実装と称されるが、これは間違っている。なぜならば、実際のYコンビネータはHaskellの型チェッカ[4]によって拒否されるからである（ただし後述する再帰型を利用したYの改良版は動く）。以下にHaskellによる不動点コンビネータの実装を示す。この不動点コンビネータはHaskellにおいては伝統的にfixと呼ばれる。fixは多相不動点コンビネータであることに注意せよ（前述のシステムFに関する議論も参照）。なお、Haskellは型推論をサポートしているが、以下では曖昧さをなくすために型を明記する。定義の後に使用例が続く。

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 programming language）に持ち込むと無限ループになる。なぜなら、fへ渡した引数は事前に展開され、無限の呼び出しの連続f (f ... (fix f) ... ))を生み出すからである。この場合、多くの処理系はスタックオーバーフローを引き起こす。

OCamlのような厳格言語においては、クロージャの使用を強制することによって無限再帰問題を回避することができる。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))

他の手段による無名再帰 [編集]

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

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

関連項目 [編集]

脚注 [編集]

  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. ^ a b Goldberg, 2005
  4. ^ Haskell mailing list thread on How to define Y combinator in Haskell, 15 Sep 2006

参考文献 [編集]

「http://ja.wikipedia.org/w/index.php?title=不動点コンビネータ&oldid=46759976」から取得