相互再帰の不動点コンビネータ

型無しラムダ計算において，Yコンビネータ
$$\mathbf{Y}:=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$
によりラムダ項$F$の不動点$\mathbf{Y}F=F(\mathbf{Y}F)$が得られ，再帰関数が実現できることはよく知られている．実は，Yコンビネータを用いることでラムダ項$F,G$に対し
$$\begin{array}{r}\{\begin{array}{l}M=FMN\\ N=GMN\end{array}\end{array}$$
なる相互再帰の不動点の組$(M,N)$を作ることができる．そのためにはタプルが必要なので，型無しラムダ計算の枠組みの中でタプルを扱うためにいくつかのエイリアスを定義する．
$$\begin{gathered} [a,b]:=\lambda p.pab \\ {\mathbf{proj}}_{\mathbf{1}}:=\lambda t.t(\lambda a.\lambda b.a) \\ {\mathbf{proj}}_{\mathbf{2}}:=\lambda t.t(\lambda a.\lambda b.b) \end{gathered}$$
これで${\mathbf{proj}}_{\mathbf{1}}[a,b]=a$, ${\mathbf{proj}}_{\mathbf{2}}[a,b]=b$と書ける．続いて,$F,G$のタプルを受け取るバージョン
$$\begin{gathered} F^{\prime }:=\lambda t.F({\mathbf{proj}}_{\mathbf{1}}t)({\mathbf{proj}}_{\mathbf{2}}t) \\ {G}^{\prime }:=\lambda t.G({\mathbf{proj}}_{\mathbf{1}}t)({\mathbf{proj}}_{\mathbf{2}}t) \end{gathered}$$
を用意する．これらを用い，$F,G$をタプルにまとめて不動点を取ればよい．すなわち，
$$P:=\mathbf{Y}(\lambda t.[F^{\prime }t,G^{\prime }t])$$
とすると，
$$\begin{gathered} {\mathbf{proj}}_{\mathbf{1}}P={\mathbf{proj}}_{\mathbf{1}}((\lambda t.[F^{\prime }t,G^{\prime }t])P)={\mathbf{proj}}_{\mathbf{1}}[F^{\prime }P,G^{\prime }P]=F^{\prime }P \\ {\mathbf{proj}}_{\mathbf{2}}P={\mathbf{proj}}_{\mathbf{2}}((\lambda t.[F^{\prime }t,G^{\prime }t])P)={\mathbf{proj}}_{\mathbf{2}}[F^{\prime }P,G^{\prime }P]=G^{\prime }P \end{gathered}$$
なので，$M:={\mathbf{proj}}_{\mathbf{1}}P$, $N:={\mathbf{proj}}_{\mathbf{2}}P$とおけば，
$$\begin{array}{r}\{\begin{array}{l}M=F^{\prime }P=FMN\\ N=G^{\prime }P=GMN\end{array}\end{array}$$
を得る．これは直ちにn個のラムダ項$F_1,\dots ,F_n$の相互再帰に一般化できる．n個のタプルを
$$\begin{gathered} [a_1,\dots ,a_n]:=\lambda p.p{a}_1\dots a_n \\ {\mathbf{proj}}_{\mathbf{i}}:=\lambda t.t(\lambda a_1.\dots \lambda a_n.a_i) \end{gathered}$$
とし，
$$F_i^{\prime }:=\lambda t.F({\mathbf{proj}}_{\mathbf{1}}t)\dots ({\mathbf{proj}}_{\mathbf{n}}t)$$
とおいて
$$\begin{gathered} P:=\mathbf{Y}(\lambda t.[F_1^{\prime }t,\dots ,F_n^{\prime }t]) \\ {M}_i:={\mathbf{proj}}_{\mathbf{i}}P \end{gathered}$$
とすれば，
$$\begin{array}{r}\{\begin{array}{l}{M}_1=F_1{M}_1\dots M_n\\ ⋮\\ M_n=F_n{M}_n\dots M_n\end{array}\end{array}$$
なる不動点の組$(M_1,\dots ,M_n)$を得る．ここでタプルに対する$\mathbf{map}$関数を
$$\mathbf{map}:=\lambda f.\lambda t.[f({\mathbf{proj}}_{\mathbf{1}}t),\dots ,f({\mathbf{proj}}_{\mathbf{n}}t)]$$
で定義すると，Yコンビネータを用いて$P$を計算する部分は
$$\begin{gathered} {\mathbf{Y}}^{\mathbf{\ast }}=\lambda g.\mathbf{Y}(\lambda t.\mathbf{map}(\lambda f.ft)g) \\ [M_1,\dots ,M_n]:={\mathbf{Y}}^{\mathbf{\ast }}[F_1^{\prime },\dots ,F_n^{\prime }] \end{gathered}$$
と書ける．この${\mathbf{Y}}^{\mathbf{\ast }}$をY*コンビネータと言う（らしい）．