不動点コンビネータ

不動点コンビネータ

不動点コンビネータ（fixed point combinator）とは、特定の条件を満たす関数を指し、その関数の不動点を見つけるための高階関数です。ここでの不動点とは、与えられた関数を適用したときに元の引数を返すような値を指します。具体的には、関数 f と入力 x に対して、f(x) = x が成り立つような x のことです。

定義

不動点コンビネータ g の特性として、任意の関数 f に対して、g(f) が不動点 p を返すとします。この場合、f(p) = p が成立します。この性質から不動点コンビネータは定義されています。また、別の言い回しとして、f(g(f)) = g(f) が成り立つことも確認できます。これは、不動点コンビネータ g が自らを引数とし、その結果を元に再帰的に定義を行う特性を持つことを意味します。

再帰の実現

プログラミングにおいて不動点コンビネータは重要な役割を果たします。第一級関数を持つプログラミング言語では、このコンビネータを用いることで明示的に再帰を記述することなく、再帰を実現することができるのです。この手法は「無名再帰」と呼ばれることがあります。通常、再帰が直接的に利用できる環境では、この手法はまれにしか使用されませんが、計算理論においては非常に意義深いものです。

ラムダ計算における不動点コンビネータ

不動点コンビネータの歴史はラムダ計算の発展と密接に関わっています。特に、無名のラムダ計算においては、ハスケル・カリーによって提案された Y = λf·(λx·f(x x))(λx·f(x x)) という式が広く知られています。この式は一般的に Yコンビネータと呼ばれ、無数の不動点コンビネータの中でよく参照されます。

一方、型付きのラムダ計算においては不動点コンビネータの存在が制約されることがあります。特に、単純型付きラムダ計算などでは全ての関数が不動点を持つとは限りません。再帰データ型を利用することで、型付きラムダ計算でもある程度の不動点演算子を定義することが可能です。

不動点コンビネータの具体例

具体的な不動点コンビネータの例として、各種のYコンビネータと呼ばれるものがあります。例えば、一般的な形式の一つとして、Yコンビネータが次のように定義されます。

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

この式は不動点コンビネータとして非常にシンプルであり、実際に適用しても無限の展開を引き起こすことがあるため注意が必要です。

Zコンビネータと他の形式

無限展開が問題となる場合には、Zコンビネータが適用されます。この Zコンビネータは、評価戦略に応じて異なりますが、属性によりYコンビネータを修正したものです。評価戦略が値渡しの場合はZコンビネータの方が適しています。

さらに、チューリング不動点コンビネータのように、異なる設計理念から生まれたものもあります。これもまた、無限の再帰を利用して計算を行うための重要な技術として位置付けられています。

まとめ

不動点コンビネータは、高階関数を利用してプログラミングと計算理論の中核を成す概念です。このテクニックを用いることで、プログラミングにおける再帰の実現が可能となり、計算の効率性を高める手法として広く利用されています。

もう一度検索