単純型付きλ計算(simply typed lambda calculus)とは、λ計算の項に、型変数から矢印だけで作った単純型を付ける体系である。型の付く項は β 簡約で型を保ち、どの順に簡約しても正規形で止まる。型の付く項にはほかのすべての型を代入例にもつ主要型があり、単一化の算法で計算できるので、型が付くかどうかは決定可能である。Church 数の型 $(o\to o)\to o\to o$ の上で表現できる自然数の関数は、零の引数の配置ごとに自然数係数の多項式になる拡張多項式にちょうど一致する。
単純型付きλ計算(simply typed lambda calculus)とは、λ計算 の項に、型変数から矢印 $\to$ だけで作った 単純型 を付ける体系である。型 $A\to B$ の項は型 $A$ の入力から型 $B$ の出力を作る関数を表し、自分自身への適用 $xx$ のような項は型が付かずに締め出される。
型の付け方には 2 通りの流儀がある。束縛変数に型を書き込む $\lambda x{:}A.\,M$ の形(Church の流儀)と、型の書かれていない λ 項に型を 割り当てる 形(Curry の流儀)である。前者の基本性質(主部簡約、弱正規化、Curry–Howard 対応)は 型理論 に、Tait の方法による強正規化は 強正規化定理 に、論理との対応の詳しい扱いは Curry–Howard対応 にある。この記事では Curry の流儀を使い、それらの性質を移したうえで、次の 2 つの定理を証明する。
型変数の可算無限集合を 1 つ固定し、$\alpha,\beta,\gamma,o$ などで表す。
変数・適用・抽象の型判断を結論にもつ規則は、それぞれ左・右・中央の規則だけである。導出の最後の規則の上の段が求める判断である。$\square$
Church の流儀の項 $\tilde M$ から型の注釈を消した λ 項を $|\tilde M|$ と書く。Curry の流儀の導出 $\Gamma\vdash M:A$ の各抽象の規則で使った型 $A$ を束縛変数に書き込めば、Church の流儀で型 $A$ をもつ項 $\tilde M$ で $|\tilde M|=M$ となるものが得られる。逆に Church の流儀で型の付く項を消せば、Curry の流儀で同じ型が付く。型変数は 型理論 の「基本型」の役を果たす。
$\Gamma\vdash M:A$ とする。
1。 まず代入補題「$\Gamma,x{:}B\vdash P:C$ かつ $\Gamma\vdash Q:B$ なら $\Gamma\vdash P[Q/x]:C$」を示す。
$P$ の組み立てについての帰納法である。$P=x$ なら $C=B$ で $P[Q/x]=Q$ である。$P$ が $x$ 以外の変数なら $P[Q/x]=P$ で、$P$ の型は $\Gamma$ から読める。$P=P_1P_2$ なら lem-stlc-generation の 2 で $P_1,P_2$ の型を得て帰納法の仮定を使う。$P=\lambda y.\,P_1$ なら、束縛変数の名前を替えて $y\ne x$、$y$ は $Q$ に自由に現れないとしてよい。3 から $C=D\to E$、$\Gamma,x{:}B,y{:}D\vdash P_1:E$ であり、$y$ は $Q$ に自由に現れないので $\Gamma,y{:}D\vdash Q:B$($Q$ の導出の各文脈に $y{:}D$ を加えてもそのまま導出になる)。帰納法の仮定から $\Gamma,y{:}D\vdash P_1[Q/x]:E$ で、抽象の規則により $\Gamma\vdash\lambda y.\,P_1[Q/x]:C$ である。
1 は β 基の位置についての帰納法で示す。根が β 基 $(\lambda x.\,P)Q$ のとき、lem-stlc-generation の 2・3 から $\Gamma,x{:}B\vdash P:A$、$\Gamma\vdash Q:B$ となり、代入補題で $\Gamma\vdash P[Q/x]:A$ である。β 基が真の部分項にあるときは、その部分項を含む直接の部分項に帰納法の仮定を当て、同じ規則で組み立て直す。
型の付かない項では 2 は成り立たない。$\Omega:=(\lambda x.\,xx)(\lambda x.\,xx)$ は自分自身に簡約され、正規形をもたない。ex-stlc-examples の 4 により、$\Omega$ には型が付かない。
型変数に型を割り当てる写像 $s$ で、有限個の型変数以外を動かさないものを 型代入 という。型 $A$ の中の各型変数 $\alpha$ を $\alpha s$ に置き換えた型を $As$ と書き、文脈についても $\Gamma s:=\{x{:}(\Gamma(x))s\}$ とする。代入は右から施し、$s$ を施してから $t$ を施す代入を $st$ と書く。$A=Bs$ となる $s$ があるとき、$A$ は $B$ の 代入例 であるという。
λ 項 $M$ について次が成り立つ。
型の付き方を型変数の連立方程式に置き換え(lem-stlc-constraints)、その解を 導出原理 の定理「単一化定理」の算法で求める。型は、2 変数の関数記号 $\to$ と型変数からなる一階の項とみなせる。証明は prf-stlc-principal にある。
$M$ の束縛変数の名前を付け替えて、束縛変数どうし、および束縛変数と自由変数が相異なるようにしておく。$M$ に現れる変数 $x$ ごとに新しい型変数 $\alpha_x$ を、$M$ の部分項の出現 $p$ ごとに新しい型変数 $\beta_p$ をとり、方程式の有限集合 $E(M)$ を次で定める。
出現 $p$ の部分項を $N_p$、$p$ を囲む抽象の束縛変数の全体を $V_p$ とする。
1。 各出現 $p$ について $\Delta_p:=\{x{:}\alpha_xs\mid x\in V_p\text{ または }x\text{ は }M\text{ の自由変数}\}$ とおき、$\Delta_p\vdash N_p:\beta_ps$ を $N_p$ の大きさについての帰納法で示す(変数の名前が相異なるので $\Delta_p$ は文脈である)。変数の出現では方程式から $\beta_ps=\alpha_xs$ で、$x$ は自由変数か $V_p$ の元なので変数の規則が使える。適用の出現では方程式から $\beta_Ps=\beta_Qs\to\beta_ps$ で、適用の規則を使う。抽象 $\lambda x.\,P$ の出現では $\Delta_P=\Delta_p,x{:}\alpha_xs$ であり、方程式から $\beta_ps=\alpha_xs\to\beta_Ps$ なので抽象の規則を使う。$p$ を全体の出現にとればよい。
2。 $\Gamma\vdash M:A$ の導出を、lem-stlc-generation によって $M$ の組み立てに沿って逆にたどると、各出現 $p$ に型 $A_p$ と文脈 $\Gamma_p$ で $\Gamma_p\vdash N_p:A_p$ となるものが付き、抽象 $\lambda x.\,P$ の出現では $\Gamma_P=\Gamma_p,x{:}B$ となる型 $B$ が決まる。$\beta_ps:=A_p$、束縛変数 $x$ にはその抽象で決まる $B$ を $\alpha_xs$ とし、自由変数には $\alpha_xs:=\Gamma(x)$ とする。変数の出現 $p$ の型 $A_p$ は $\Gamma_p(x)$ であり、$\Gamma_p$ は $\Gamma$ に $p$ を囲む抽象の束縛変数の割り当てを加えたものなので、$A_p=\alpha_xs$ である(名前が相異なるので、割り当てが上書きされることはない)。適用・抽象の方程式は lem-stlc-generation の 2・3 そのものである。$\square$
$E(M)$ の方程式を $l_i=r_i$($1\le i\le m$)とし、新しい $m$ 変数の関数記号 $g$ をとって、2 つの項 $g(l_1,\dots,l_m)$、$g(r_1,\dots,r_m)$ からなる集合を $E'$ とする。型代入が $E(M)$ の解であることと、$E'$ の単一化子であることは同じである。導出原理 の定理「単一化定理」により、$E'$ が単一化可能かどうかは算法で判定でき、可能なら最汎単一化子 $\sigma$ が求まる。lem-stlc-constraints の 1・2 により、$M$ に型が付くことと $E(M)$ に解があることは同値なので、1 が従う。
型が付くとき、$\Gamma_0:=\{x{:}\alpha_x\sigma\}$($x$ は $M$ の自由変数)、$A_0:=\beta_M\sigma$ とおく。$\Gamma\vdash M:A$ なら lem-stlc-constraints の 2 の解 $\theta$ があり、最汎単一化子の性質から $\theta=\sigma s$ となる型代入 $s$ がある。よって $A=\beta_M\sigma s=A_0s$、$\Gamma(x)=\alpha_x\sigma s=\Gamma_0(x)s$ である。任意の $s$ について $\sigma s$ も解なので、lem-stlc-constraints の 1 から $\Gamma_0s\vdash M:A_0s$ である($s$ を恒等写像にとれば $\Gamma_0\vdash M:A_0$)。$\square$
主要型の存在は、組合せ論理について Hindley が示し、Milner がプログラム言語の型推論に用いたので、型推論の算法は Hindley–Milner の名で呼ばれる(Hindley–Milner型推論)。
型変数 $o$ を 1 つ固定し、$\mathsf{N}:=(o\to o)\to o\to o$ とおく。ex-stlc-examples の 3 により $\vdash c_n:\mathsf{N}$ である。$\mathsf{N}^k\to\mathsf{N}$ で $\mathsf{N}\to\cdots\to\mathsf{N}\to\mathsf{N}$($\mathsf{N}$ が $k+1$ 個)を表し、$m=(m_1,\dots,m_k)\in\mathbb{N}^k$ について $c_m:=c_{m_1}\cdots c_{m_k}$(並べて適用する引数の列)と書く。
$Mc_m=_\beta c_{F(m)}$ なら 1 の条件が成り立つ。1 の条件を $f,x$ を付けて書くのは、$\lambda f.\,f$ のように $c_1$ と η 変換でしか等しくない項があるためである。拡張多項式は、定数 $0,1$、射影、加法、乗法と、$\mathrm{sg}(n):=\min\{n,1\}$、$\overline{\mathrm{sg}}(n):=1-\mathrm{sg}(n)$ から合成で作れる関数と一致する。
関数 $F\colon\mathbb{N}^k\to\mathbb{N}$ が型 $\mathsf{N}^k\to\mathsf{N}$ の項で表現できることと、$F$ が拡張多項式であることは同値である。
証明の要は、正規形の項に Church 数を代入した結果を、項の形から読み取ることである(lem-stlc-normal)。証明は prf-stlc-definable にある。
β 正規形の項は、$\lambda y_1\cdots\lambda y_r.\,hN_1\cdots N_q$($h$ は変数、$N_j$ は正規形)の形をしている(項の組み立てについての帰納法で、正規形の適用 $PQ$ の $P$ は抽象でないので、適用を左にたどると変数に行き着く)。
$\Gamma=\{n_1{:}\mathsf{N},\dots,n_k{:}\mathsf{N},\ f{:}o\to o,\ y_1{:}o,\dots,y_r{:}o\}$ とし、$t$ を正規形の項、$m\in\mathbb{N}^k$ の零の型を $S$ とし、$t^\ast:=t[c_{m_1}/n_1,\dots,c_{m_k}/n_k]$ とおく。$z$ は $t$ に現れない変数とする。
$t$ の大きさについての帰納法で示す。lem-stlc-generation により、$t=hN_1\cdots N_q$ なら $\Gamma(h)=B_1\to\cdots\to B_q\to C$($C$ は $t$ の型)で $\Gamma\vdash N_j:B_j$ であり、型 $o$ の項は抽象でない。
1 の場合。 $h=y_j$ なら $q=0$ で $p=0$。$h=f$ なら $q=1$ で、$N_1$ に 1 を使い $p=p_1+1$。$h=n_i$ なら $q=2$、$\Gamma\vdash N_1:o\to o$、$\Gamma\vdash N_2:o$ であり、$t^\ast=c_{m_i}N_1^\ast N_2^\ast=_\beta(N_1^\ast)^{m_i}N_2^\ast$($N_1^\ast$ を $m_i$ 回重ねて適用)である。$N_2$ に 1 を使って $(p_2,h_2)$ を得る。$i\in S$ なら $(p_2,h_2)$ が答えである。$i\notin S$ なら $N_1$ に 2 を使って $(p_1,h_1)$ を得る。β 等式は代入で保たれるので、任意の項 $L$ について $N_1^\ast L=_\beta f^{p_1}(h_1[L/z])$ である。$h_1=z$ なら $m_i$ 回の適用で $f^{m_ip_1+p_2}h_2$ となり、$p=x_ip_1+p_2$。$h_1\ne z$ なら最後の適用だけが残って $f^{p_1}h_1$ となり、$p=p_1$。
2 の場合。 $t=\lambda y.\,s$ なら $\Gamma,y{:}o\vdash s:o$ で、$s$ に 1 を使う($y$ を $y_{r+1}$ とみる)。$t^\ast z=_\beta s^\ast[z/y]$ なので、得た頭が $y$ なら $z$ に替える。$t$ が抽象でなければ、型 $o\to o$ になるのは $t=f$($p=1$、$h=z$)か $t=n_iN_1$ だけである。後者では $t^\ast z=_\beta(N_1^\ast)^{m_i}z$ で、1 の場合と同じく、$i\in S$ なら $(0,z)$、$i\notin S$ なら $N_1$ の $(p_1,h_1)$ から $h_1=z$ のとき $(x_ip_1,z)$、そうでなければ $(p_1,h_1)$ である。どの場合も多項式は $S$ と $t$ だけで決まる。$\square$
表現できるなら拡張多項式。 $M$ が $F$ を表現するとする。thm-stlc-reduction により $M$ は正規形 $M'$ をもち、$\vdash M':\mathsf{N}^k\to\mathsf{N}$、$M=_\beta M'$ である。$M'$ は閉じているので頭の変数が束縛されていなければならず、$M'$ は抽象である。$n_1{:}\mathsf{N},\dots,n_j{:}\mathsf{N}$ の文脈で、変数を頭とする項の型は $\mathsf{N}$、$o\to o$、$o$ のどれかなので、型 $\mathsf{N}^{k-j}\to\mathsf{N}$($j< k$)の正規形はやはり抽象である。よって $M'=\lambda n_1\cdots\lambda n_k.\,R$ で、$R$ は型 $\mathsf{N}$ の正規形であり、$R=n_i$ か $R=\lambda f.\,T$($f{:}o\to o\vdash T:o\to o$ の形)である。$R=n_i$ なら $Mc_mfx=_\beta f^{m_i}x$ で、$F(m)=m_i$ である。$R=\lambda f.\,T$ なら、lem-stlc-normal の 2($r=0$)により $T^\ast x=_\beta f^{p_S(m)}x$ となる多項式 $p_S$ がある(頭は $x$ しかありえない)。よって $Mc_mfx=_\beta f^{p_S(m)}x$ である。$f^ax$ と $f^bx$ は正規形なので、$a\ne b$ なら β 等しくない(λ計算 の系「正規形の一意性と β 同値の判定」)。したがって零の型が $S$ の $m$ で $F(m)=p_S(m)$ である。
拡張多項式なら表現できる。 次の閉じた項はすべて型が付き、Church 数に当てると Church 数そのものに β 簡約される。
$$
\mathsf{add}:=\lambda a.\,\lambda b.\,\lambda f.\,\lambda x.\,af(bfx),\quad
\mathsf{mul}:=\lambda a.\,\lambda b.\,\lambda f.\,a(bf),
$$
$$
\mathsf{sg}:=\lambda a.\,\lambda f.\,\lambda x.\,a(\lambda u.\,fx)x,\quad
\overline{\mathsf{sg}}:=\lambda a.\,\lambda f.\,\lambda x.\,a(\lambda u.\,x)(fx).
$$
実際、$\mathsf{add}\,c_ac_b\to^\ast\lambda f.\,\lambda x.\,f^a(f^bx)=c_{a+b}$、$\mathsf{mul}\,c_ac_b\to^\ast\lambda f.\,(c_bf)^a$ の形を経て $c_{ab}$、$\mathsf{sg}\,c_a$ は $a=0$ なら $c_0$、$a\ge1$ なら $c_1$、$\overline{\mathsf{sg}}$ はその逆である。定数関数 $\lambda n_1\cdots\lambda n_k.\,c_0$、$\lambda n_1\cdots\lambda n_k.\,c_1$ と射影 $\lambda n_1\cdots\lambda n_k.\,n_i$ も同じ性質をもつ。Church 数に当てて Church 数になる項を合成した項($\lambda n_1\cdots\lambda n_k.\,G(H_1n_1\cdots n_k)\cdots(H_ln_1\cdots n_k)$ の形)もこの性質をもつので、上の注意の式で拡張多項式を表す項が得られる。$\square$
この定理は Schwichtenberg(1976)による。表現できない関数の典型は、1 を引く関数 $\mathrm{pred}(m):=\max\{m-1,0\}$ である。零の型 $\emptyset$($m\ge1$)の上で $\mathrm{pred}(m)=p(m)$ となる自然数係数の多項式 $p$ があれば、$p(x)-(x-1)$ は無限個の零点をもつので $p(x)=x-1$ となり、係数 $-1$ が自然数でないことに反する。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| 型が付く(thm-stlc-reduction の 2) | $\Omega=(\lambda x.\,xx)(\lambda x.\,xx)$ | 正規形をもたない |
| 型に型変数を使う(thm-stlc-principal) | 型を定数 $o$ 1 つから作る体系での $\mathsf{I}$ | $o\to o$ と $(o\to o)\to o\to o$ が付くが、どちらも他方の代入例でなく主要型がない |
| 入力と出力が同じ $\mathsf{N}$(thm-stlc-definable) | $\lambda a.\,\lambda b.\,ba$(型 $\mathsf{N}\to\mathsf{N}_{o\to o}\to\mathsf{N}$) | べき乗 $(a,b)\mapsto a^b$ が表せる |
| 体系が単純型だけ(thm-stlc-definable) | Gödel の体系 T の $\mathrm{R}\,0\,(\lambda z.\,\lambda y.\,y)$ | $\mathrm{pred}$ が表せる |
1 行目.$\Omega\to\Omega$ がただ 1 つの 1 歩で、簡約は終わらない。型が付かないことは ex-stlc-examples の 4 による。
2 行目.型変数をもたない体系では代入で型を変えられないので、異なる 2 つの型はどちらも他方の代入例でない。$\mathsf{I}$ には $A\to A$ の形の型がすべて付き、それより一般的な型の候補はない。型変数があれば $\alpha\to\alpha$ が主要型である(ex-stlc-principal)。
3 行目.$\mathsf{N}_{o\to o}:=((o\to o)\to o\to o)\to(o\to o)\to o\to o$ とおくと、$c_b$ には型 $\mathsf{N}_{o\to o}$ も付き(ex-stlc-examples の 3 で $A=o\to o$)、$(\lambda a.\,\lambda b.\,ba)c_ac_bfx=_\beta c_bc_afx=_\beta f^{a^b}x$ である($c_b$ は「$b$ 回の合成」で、$f$ を $a$ 回反復する操作 $c_a$ を $b$ 回合成すると $a^b$ 回の反復になる。$b=0$ では $c_0c_afx=_\beta fx$)。$a,b\ge1$ の上で $a^b$ は多項式でない($a=2$ を固定すると $2^b$ はどの多項式よりも速く増える)ので、入力の型をそろえれば表せない。
4 行目.体系 T は自然数の型 $\mathsf{Int}$、定数 $0$、後者 $\mathrm{S}$ と再帰子 $\mathrm{R}$ を加え、$\mathrm{R}uv0\to u$、$\mathrm{R}uv(\mathrm{S}t)\to v(\mathrm{R}uvt)t$ という変換をもつ(GLT89 §7.1.2–7.1.4、p. 47)。$v:=\lambda z.\,\lambda y.\,y$ とすると $\mathrm{R}\,0\,v\,0\to0$、$\mathrm{R}\,0\,v\,(\mathrm{S}t)\to v(\mathrm{R}\,0\,v\,t)t\to^\ast t$ なので、$\mathrm{pred}$ が表せる(同 §7.3.2、p. 49 も 1 を引く関数が定義できることを述べる)。単純型付きλ計算の範囲では表せないことは上で示した。$\square$
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する