System F

同義語:システムF二階のラムダ計算多相ラムダ計算Girard–Reynolds体系second-order lambda calculuspolymorphic lambda calculus

概要

System F(second-order lambda calculus)とは、単純型付きラムダ計算に型の上の量化 $\forall X.\,A$ を加え、型を引数にとる抽象 $\Lambda X.\,M$ と型の適用 $M\,U$ をもつ型付きラムダ計算であり、恒等関数のような多相的な関数を一つの項として書ける。自然数・真偽値・対などのデータ型を型として符号化でき、二階の命題論理の証明と対応する。型の付く項はすべて強正規化可能であり、Girard は可約性の候補をすべて動かす方法でこれを示した。表せる自然数の関数は、二階算術で全域性が証明できる再帰関数にちょうど一致する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 単純型付きλ計算, 強正規化定理

System F(second-order lambda calculus、多相ラムダ計算とも)は、単純型付きλ計算 に型の上の量化 $\forall X.\,A$ を加えた型付きラムダ計算である。項は型を引数にとることができ、たとえば恒等関数は、型ごとに別の項 $\lambda x{:}A.\,x$ を書く代わりに、1 つの項 $\Lambda X.\,\lambda x{:}X.\,x$ として型 $\forall X.\,X\to X$ をもつ。論理の側では二階の命題論理の自然演繹にあたる。Girard が証明論の研究のなかで導入し、Reynolds がプログラム言語の研究から独立に見いだした(GLT89 第 11 章、p. 81)。
この体系の中心の結果は、型の付く項はすべて 強正規化可能 であるという Girard の定理である。型 $\forall X.\,A$ の項は $A$ の中の $X$ に $\forall X.\,A$ 自身を代入した型にも使えるので、強正規化定理 の記事の型についての帰納法はそのままでは通らない。Girard はこれを 可約性の候補 をすべて動かすことで乗り越えた。この記事ではその証明を完全に述べ、帰結として二階の命題論理の無矛盾性と、自然数の型の閉じた正規形が数字に限ることを導く。

型と項

System F の型と項

型変数の可算集合を固定する。型 は、型変数 $X$ から、$A\to B$ と $\forall X.\,A$ によって作られる。項 は、変数 $x$、抽象 $\lambda x{:}A.\,M$、適用 $MN$、型の抽象 $\Lambda X.\,M$、型の適用 $M\,A$ によって作られる。文脈 $\Gamma=x_1{:}A_1,\dots,x_n{:}A_n$ のもとでの型判断 $\Gamma\vdash M:A$ は、次の 5 つの規則で導かれるものとする。

名前前提結論
(var)$x{:}A$ が $\Gamma$ にある$\Gamma\vdash x:A$
(abs)$\Gamma,x{:}A\vdash M:B$$\Gamma\vdash\lambda x{:}A.\,M:A\to B$
(app)$\Gamma\vdash M:A\to B$、$\Gamma\vdash N:A$$\Gamma\vdash MN:B$
($\forall$I)$\Gamma\vdash M:A$、$X$ は $\Gamma$ の型に自由に現れない$\Gamma\vdash\Lambda X.\,M:\forall X.\,A$
($\forall$E)$\Gamma\vdash M:\forall X.\,A$$\Gamma\vdash M\,U:A[U/X]$

型 $\forall X.\,A$ は $\Pi X.\,A$ とも書く(GLT89 の記法)。$\forall X$ と $\Lambda X$ は $X$ を束縛し、束縛された変数の名前だけが違う型・項は同じものとみなす。$A[U/X]$ は型への代入、$M[U/X]$ は項の中の型への代入、$M[N/x]$ は項の代入で、いずれも束縛変数を取り替えて捕獲を避ける。規則は項の形で一つに決まるので、項の型は文脈から一意に定まる。($\forall$I) の 変数の条件(GLT89 §11.2、p. 82)が欠かせないことは、後の反例の表で見る。
簡約 は、どの位置でも次のどちらかの β 基を縮約する一歩 $\to$ で、その $0$ 回以上の繰り返しを $\to^*$ と書く(GLT89 第 11 章、p. 81)。
$$ (\lambda x{:}A.\,M)N\ \to\ M[N/x],\qquad(\Lambda X.\,M)\,U\ \to\ M[U/X]. $$
型は簡約しない。強正規化可能な項の集合 $\mathrm{SN}$、簡約の長さの最大値 $\nu(M)$ は 強正規化定理 の定義と補題「簡約の長さの上限」と同じに定める。その補題の証明は型の β 基があっても変わらない。

主部簡約

$\Gamma\vdash M:A$ かつ $M\to M'$ なら $\Gamma\vdash M':A$ である。

2 つの代入の補題に帰着する

簡約する位置についての帰納法で、根の β 基の場合に帰着する。その場合は次の 2 つの代入の補題による。

代入の補題と根の場合

項の代入.$\Gamma,x{:}A\vdash M:B$ かつ $\Gamma\vdash N:A$ なら $\Gamma\vdash M[N/x]:B$。$M$ の導出についての帰納法で、($\forall$I) では束縛された $X$ を $N$ の型と $\Gamma$ に現れないよう取り替えておけば変数の条件が保たれる。型の代入.$\Gamma\vdash M:B$ なら $\Gamma[U/X]\vdash M[U/X]:B[U/X]$。これも導出についての帰納法で、($\forall$E) では $A[V/Y][U/X]=A[U/X][V[U/X]/Y]$($Y$ は $U$ に現れないように選ぶ)を使う。

根の場合.$(\lambda x{:}A.\,P)N$ の型が $B$ なら、規則は項の形で決まるので $\Gamma,x{:}A\vdash P:B$、$\Gamma\vdash N:A$ であり、項の代入で $\Gamma\vdash P[N/x]:B$。$(\Lambda X.\,P)\,U$ の型が $A[U/X]$ なら $\Gamma\vdash P:A$ で、$X$ は $\Gamma$ に自由に現れないので $\Gamma[U/X]=\Gamma$、型の代入で $\Gamma\vdash P[U/X]:A[U/X]$。$\square$

データ型の符号化

型の上の量化によって、自然数や真偽値などのデータ型を項と型だけで書ける(GLT89 §11.3–11.5、pp. 83–92)。この記事では次の約束を使う。

自然数・真偽値・対

$$ \mathrm{Nat}:=\forall X.\,X\to(X\to X)\to X,\qquad\underline n:=\Lambda X.\,\lambda x{:}X.\,\lambda y{:}X\to X.\,\underbrace{y(y(\cdots(y}_{n}\,x)\cdots)). $$
$\underline n$ を 数字 という。$\mathrm{Bool}:=\forall X.\,X\to X\to X$、$\mathsf{T}:=\Lambda X.\,\lambda x{:}X.\,\lambda y{:}X.\,x$、$\mathsf{F}:=\Lambda X.\,\lambda x{:}X.\,\lambda y{:}X.\,y$ とする。型 $A,B$ の 対 は $A\times B:=\forall X.\,(A\to B\to X)\to X$ で、
$$ \langle M,N\rangle:=\Lambda X.\,\lambda k{:}A\to B\to X.\,k\,M\,N,\qquad\pi_1P:=P\,A\,(\lambda u{:}A.\,\lambda v{:}B.\,u),\qquad\pi_2P:=P\,B\,(\lambda u{:}A.\,\lambda v{:}B.\,v) $$
とおく。関数 $f\colon\mathbb N\to\mathbb N$ が、型 $\mathrm{Nat}\to\mathrm{Nat}$ の閉じた項 $F$ で 表せる とは、すべての $n$ について $F\,\underline n\to^*\underline{f(n)}$ となることをいう。2 変数の関数も同様に定める。

$\pi_1\langle M,N\rangle\to^*M$、$\pi_2\langle M,N\rangle\to^*N$ である。数字 $\underline n$ は「型 $X$ の初期値と $X$ 上の関数を受け取り、関数を $n$ 回施す」項で、$\underline n\,A\,a\,f\to^*f^n(a)$ によって 反復 が書ける。

算術の項

$\mathrm{Nat}$ の上の次の項は、それぞれ後者、和、積、前者を表す。
$$ \begin{aligned} \mathsf{S}&:=\lambda n{:}\mathrm{Nat}.\,\Lambda X.\,\lambda x{:}X.\,\lambda y{:}X\to X.\,y\,(n\,X\,x\,y),\\ \mathsf{add}&:=\lambda m{:}\mathrm{Nat}.\,\lambda n{:}\mathrm{Nat}.\,\Lambda X.\,\lambda x{:}X.\,\lambda y{:}X\to X.\,m\,X\,(n\,X\,x\,y)\,y,\\ \mathsf{mul}&:=\lambda m{:}\mathrm{Nat}.\,\lambda n{:}\mathrm{Nat}.\,\Lambda X.\,\lambda x{:}X.\,\lambda y{:}X\to X.\,m\,X\,x\,(\lambda z{:}X.\,n\,X\,z\,y),\\ \mathsf{pred}&:=\lambda n{:}\mathrm{Nat}.\,\pi_1\bigl(n\,(\mathrm{Nat}\times\mathrm{Nat})\,\langle\underline0,\underline0\rangle\,(\lambda p{:}\mathrm{Nat}\times\mathrm{Nat}.\,\langle\pi_2p,\ \mathsf S(\pi_2p)\rangle)\bigr). \end{aligned} $$
$\mathsf{add}\,\underline m\,\underline n$ は、$y$ を $n$ 回施した結果にさらに $m$ 回施すので $\underline{m+n}$ に簡約される。

前者の項の働き$\mathsf{pred}$ は、対 $\langle k-1,k\rangle$ を $\langle k,k+1\rangle$ に送る関数を $\langle0,0\rangle$ から $n$ 回反復して第 1 成分をとる。$n\ge1$ なら $\langle n-1,n\rangle$ に着くので $\underline{n-1}$、$n=0$ なら $\underline0$ を返す。同じ対の工夫で一般の原始再帰が書ける(GLT89 §11.5.1、pp. 89–90)。ただし $\mathsf{pred}\,(\mathsf S\,x)\to^*x$ は変数 $x$ については成り立たず、数字を入れたときにだけ成り立つ。引数を最後まで分解して組み立て直すからである(同 p. 90)。
$\mathsf{iszero}:=\lambda n{:}\mathrm{Nat}.\,n\,\mathrm{Bool}\,\mathsf T\,(\lambda b{:}\mathrm{Bool}.\,\mathsf F)$ は $\underline0$ を $\mathsf T$ に、それ以外を $\mathsf F$ に送る。

単純型付きλ計算 の定理「表現できる関数の特徴づけ」では、表せる関数は拡張多項式に限られ、前者の関数は表せない。System F では反復の結果の型を $\mathrm{Nat}\times\mathrm{Nat}$ や $\mathrm{Nat}$ 自身に選べるので、表せる関数が大きく広がる。たとえば $\lambda m{:}\mathrm{Nat}.\,\lambda n{:}\mathrm{Nat}.\,n\,\mathrm{Nat}\,\underline1\,(\mathsf{mul}\,m)$ は $m^n$ を表す。どこまで広がるかは後の節「表せる関数」で述べる。

強正規化定理

この節の証明は GLT89 第 14 章(pp. 113–118)の Girard の方法に従う。ただし候補を型ごとに分けず、項の集合として一律に扱う。項が 中立 であるとは、抽象 $\lambda x{:}A.\,M$ でも型の抽象 $\Lambda X.\,M$ でもないことをいう。中立な $M$ について、$MN$ と $M\,U$ の一歩先は $M$ か $N$ の中の縮約によるものだけである。

可約性の候補

項の集合 $\mathcal C$ が 可約性の候補 であるとは、次の 3 条件を満たすことをいう。

  • (CR1) $\mathcal C\subset\mathrm{SN}$。
  • (CR2) $M\in\mathcal C$ かつ $M\to M'$ なら $M'\in\mathcal C$。
  • (CR3) $M$ が中立で、$M$ の一歩先がすべて $\mathcal C$ に属するなら、$M\in\mathcal C$。

$\mathrm{SN}$ 自身は候補である(強正規化定理 の補題「簡約の長さの上限」の 3 と 4)。(CR3) から、中立な正規形、とくに変数はどの候補にも属する。

型の可約性

型 $A$ と、$A$ の自由な型変数を含む有限個の型変数に候補を割り当てる写像 $\mathcal R$ について、項の集合 $\mathrm{RED}_A[\mathcal R]$ を $A$ の組み立てについての帰納法で定める。

  1. $\mathrm{RED}_X[\mathcal R]:=\mathcal R(X)$。
  2. $\mathrm{RED}_{A\to B}[\mathcal R]:=\{M\mid\text{すべての }N\in\mathrm{RED}_A[\mathcal R]\text{ について }MN\in\mathrm{RED}_B[\mathcal R]\}$。
  3. $\mathrm{RED}_{\forall X.A}[\mathcal R]:=\{M\mid\text{すべての型 }U\text{ と候補 }\mathcal C\text{ について }M\,U\in\mathrm{RED}_A[\mathcal R,X\mapsto\mathcal C]\}$。

同じ帰納法により、$\mathrm{RED}_A[\mathcal R]$ は $\mathcal R$ の $A$ の自由な型変数での値だけで決まる。3 は $A$ の可約性しか使わないので正しい帰納的定義だが、量化は $\mathrm{RED}_{\forall X.A}$ 自身も含みうる「すべての候補」を動く。ここで二階の量化の 非可述性 を受け止める(GLT89 §14.1、p. 114)。($\forall$E) の型 $U$ が $\forall X.\,A$ より複雑でも、その可約性は候補の一つとして量化に含まれている。

可約性は候補

すべての型 $A$ と割り当て $\mathcal R$ について、$\mathrm{RED}_A[\mathcal R]$ は可約性の候補である。

型についての帰納法

型変数の場合は $\mathcal R(X)$ が候補だからである。$A\to B$ の場合は 強正規化定理 の補題「可約性の 3 条件」の証明の関数型の場合と同じである(そこで使うのは $A,B$ についての 3 条件と、変数が可約であることだけである)。
$\forall X.\,A$ の場合を示す。$\mathcal R'$ を $\mathcal R$ に $X\mapsto\mathcal C$ を加えたものとし、帰納法の仮定により $\mathrm{RED}_A[\mathcal R']$ は候補である。

  • (CR1):$M\in\mathrm{RED}_{\forall X.A}[\mathcal R]$ なら、$U:=X$、$\mathcal C:=\mathrm{SN}$ として $M\,X\in\mathrm{SN}$ である。$M$ から無限の簡約の列があれば $M\,X$ からもあるので、$M\in\mathrm{SN}$ である。
  • (CR2):$M\to M'$ なら $M\,U\to M'\,U$ であり、$A$ についての (CR2) による。
  • (CR3):$M$ が中立なら、$M\,U$ は β 基でなく、型は簡約しないので、$M\,U$ の一歩先は $M'\,U$($M\to M'$)だけである。仮定によりこれらは $\mathrm{RED}_A[\mathcal R']$ に属し、$M\,U$ は中立なので、$A$ についての (CR3) により $M\,U\in\mathrm{RED}_A[\mathcal R']$ である。$\square$
代入と可約性
  1. $\mathrm{RED}_{A[B/X]}[\mathcal R]=\mathrm{RED}_A[\mathcal R,X\mapsto\mathrm{RED}_B[\mathcal R]\,]$ である。
  2. $P\to P'$ なら $P[U/X]\to P'[U/X]$ である。
  3. 項 $P$ について、すべての型 $U$ と候補 $\mathcal C$ で $P[U/X]\in\mathrm{RED}_A[\mathcal R,X\mapsto\mathcal C]$ ならば、$\Lambda X.\,P\in\mathrm{RED}_{\forall X.A}[\mathcal R]$ である。
1・2 は組み立て、3 は簡約の長さの帰納法

1 は $A$ の組み立てについての帰納法、2 は簡約する位置についての帰納法である。

1・2 の確かめ

1:定義の各段が両辺で一致する。$A=X$ なら両辺とも $\mathrm{RED}_B[\mathcal R]$ で、束縛変数は $B$ に現れないよう選ぶ。2:根の β 基では、$((\lambda y{:}C.\,Q)N)[U/X]$ が $Q[U/X][N[U/X]/y]=Q[N/y][U/X]$ に、$((\Lambda Y.\,Q)V)[U/X]$ が $Q[U/X][V[U/X]/Y]=Q[V/Y][U/X]$ に簡約される($Y$ は $U$ に現れないよう選ぶ)。


3:型 $U$ と候補 $\mathcal C$ を固定し、$\mathcal R':=(\mathcal R,X\mapsto\mathcal C)$ とおく。$(\Lambda X.\,P)\,U\in\mathrm{RED}_A[\mathcal R']$ を示せばよい。仮定を $U=X$、$\mathcal C=\mathrm{SN}$ で使うと、lem-sf-cr の (CR1) から $P\in\mathrm{SN}$ である。$\nu(P)$ についての帰納法で示す。$(\Lambda X.\,P)\,U$ の一歩先は次の 2 種類だけである。

  • $P[U/X]$。仮定により $\mathrm{RED}_A[\mathcal R']$ に属する。
  • $(\Lambda X.\,P')\,U$($P\to P'$)。2 と (CR2) により $P'$ も仮定を満たし、$\nu(P')< \nu(P)$ なので、帰納法の仮定により $\mathrm{RED}_A[\mathcal R']$ に属する。
    $(\Lambda X.\,P)\,U$ は中立なので、(CR3) により $\mathrm{RED}_A[\mathcal R']$ に属する。$\square$

$\lambda$ の抽象については、強正規化定理 の補題「抽象の補題」がそのまま成り立つ(証明は (CR1)–(CR3) と代入の性質しか使わない)。すなわち、すべての $N\in\mathrm{RED}_A[\mathcal R]$ で $P[N/x]\in\mathrm{RED}_B[\mathcal R]$ なら、$\lambda x{:}A.\,P\in\mathrm{RED}_{A\to B}[\mathcal R]$ である。

可約性定理

$\Gamma=x_1{:}A_1,\dots,x_n{:}A_n$、$\Gamma\vdash M:A$ とし、$\Gamma$ と $A$ の自由な型変数を $X_1,\dots,X_k$ とする。任意の型 $U_1,\dots,U_k$、候補 $\mathcal C_1,\dots,\mathcal C_k$ について $\mathcal R:=(X_j\mapsto\mathcal C_j)$ とおき、$N_i\in\mathrm{RED}_{A_i}[\mathcal R]$ とする。このとき
$$ M[\vec U/\vec X][\vec N/\vec x]\in\mathrm{RED}_A[\mathcal R]. $$

導出についての帰納法

$M[\vec U/\vec X][\vec N/\vec x]$ を $M\sigma$ と略す。最後の規則で場合を分ける。(var)、(app)、(abs) は 強正規化定理 の定理「可約性定理」の証明と同じで、(abs) では上の抽象の補題を使う。
($\forall$I):$M=\Lambda Y.\,P$、$A=\forall Y.\,B$、$\Gamma\vdash P:B$ で、$Y$ は $\Gamma$ の型に自由に現れない。$Y$ は $X_j$ とも $U_j$、$N_i$ に現れる型変数とも異なるよう名前を選んでおく。任意の型 $V$ と候補 $\mathcal D$ について、$\mathcal R_1:=(\mathcal R,Y\mapsto\mathcal D)$ とおく。変数の条件から $Y$ は $A_i$ に現れないので $\mathrm{RED}_{A_i}[\mathcal R_1]=\mathrm{RED}_{A_i}[\mathcal R]\ni N_i$ である。帰納法の仮定を $U_1,\dots,U_k,V$ と $\mathcal C_1,\dots,\mathcal C_k,\mathcal D$ に使うと、$(P\sigma)[V/Y]\in\mathrm{RED}_B[\mathcal R_1]$ を得る($Y$ は $N_i$ に現れないので、代入の順序を入れ替えられる)。lem-sf-subst の 3 により $\Lambda Y.\,P\sigma=M\sigma\in\mathrm{RED}_{\forall Y.B}[\mathcal R]$ である。
($\forall$E):$M=P\,U$、$A=B[U/Y]$、$\Gamma\vdash P:\forall Y.\,B$ とする。帰納法の仮定により $P\sigma\in\mathrm{RED}_{\forall Y.B}[\mathcal R]$ なので、型 $U[\vec U/\vec X]$ と候補 $\mathrm{RED}_U[\mathcal R]$($U$ の自由な型変数で $X_j$ でないものには $\mathrm{SN}$ を割り当てて $\mathcal R$ を延ばしておく。lem-sf-cr により候補である)を当てると
$$ M\sigma=(P\sigma)\,(U[\vec U/\vec X])\in\mathrm{RED}_B[\mathcal R,Y\mapsto\mathrm{RED}_U[\mathcal R]\,]=\mathrm{RED}_{B[U/Y]}[\mathcal R] $$
である。最後の等号は lem-sf-subst の 1 である。$\square$

Girard の強正規化定理

System F で型の付く項はすべて強正規化可能である。

恒等的な代入に当てる

$\Gamma\vdash M:A$ とする。thm-sf-adequacy を $U_j:=X_j$、$\mathcal C_j:=\mathrm{SN}$、$N_i:=x_i$ に使う。$\mathrm{SN}$ は候補で、変数は中立な正規形なので $x_i\in\mathrm{RED}_{A_i}[\mathcal R]$ である(lem-sf-cr)。よって $M\in\mathrm{RED}_A[\mathcal R]$ であり、(CR1) により $M\in\mathrm{SN}$ である。$\square$

正規形はただ 1 つに決まる。これは Church–Rosser の定理の拡張による合流性からで、この記事では証明しない(GLT89 第 14 章の冒頭、p. 113)。また、二階算術 PA2 が無矛盾なら、この定理は PA2 の中では証明できない。正規化定理から PA2 の無矛盾性が PA2 の中で導けるので、Gödel の第 2 不完全性定理に反するからである(同所)。証明が「すべての候補」を動く量化を使うのはこのためである。

正規形の形と無矛盾性

型の付く項 $M$ を、適用と型の適用を左にたどって $M=H\,V_1\cdots V_k$($H$ は適用でも型の適用でもない、$V_i$ は項か型)と書く。$M$ が正規形で $k\ge1$ なら、$H$ は抽象でも型の抽象でもない($HV_1$ が β 基になる。型が付くので、$\lambda$ には項が、$\Lambda$ には型が当たる)。よって 型の付く正規形は、$\lambda x{:}A.\,N$、$\Lambda X.\,N$、または変数 $x$ から始まる $x\,V_1\cdots V_k$ のいずれかの形 をしていて、$N$ や項の $V_i$ も正規形である(GLT89 §15.1.1 の頭正規形の議論)。

二階の命題論理の無矛盾性

型 $\forall X.\,X$ をもつ閉じた項は存在しない。

正規形の形を見る

$\vdash M:\forall X.\,X$ とする。thm-sf-sn により $M$ は正規形 $N$ に簡約され、prop-sf-subject により $\vdash N:\forall X.\,X$ である。$N$ は閉じているので変数から始まらず、型が $\forall$ なので $N=\Lambda X.\,N_1$、$\vdash N_1:X$ である。$N_1$ も閉じた正規形なので抽象か型の抽象だが、その型は $\to$ か $\forall$ の形で、型変数 $X$ ではない。矛盾である。$\square$

Curry–Howard対応 によって型を命題、項を証明と読むと、$\forall X.\,X$ は「すべての命題が成り立つ」であり、この系は二階の命題論理(直観主義の、$\to$ と $\forall$ だけのもの)が無矛盾であることを述べる(GLT89 §11.6、p. 93)。

自然数の型の閉じた正規形

型 $\mathrm{Nat}$ の閉じた正規形は数字 $\underline n$($n\ge0$)に限る。

頭の変数で場合を分ける

$\vdash t:\mathrm{Nat}$ を閉じた正規形とする。prf-sf-consistent と同じく型が $\forall$、$\to$、$\to$ であることから(途中の文脈 $x{:}X$ で $x$ から始まる正規形の型は $X$ だけである)、$t=\Lambda X.\,\lambda x{:}X.\,\lambda y{:}X\to X.\,v$ で、$x{:}X,\ y{:}X\to X\vdash v:X$ となる正規形 $v$ がある。$v$ の型は $X$ なので抽象でも型の抽象でもなく、変数 $x$ か $y$ から始まる。$x\,V_1\cdots V_k$ なら $x$ の型 $X$ には何も当てられないので $k=0$、$v=x$ である。$y\,V_1\cdots V_k$ なら、$y$ の型 $X\to X$ には項を 1 つだけ当てられ、型を当てられないので $v=y\,v'$ で、$v'$ は同じ文脈で型 $X$ の正規形である。$v$ の長さについての帰納法により $v=y(y(\cdots(y\,x)\cdots))$ となり、$t$ は数字である。$\square$

これは GLT89 §15.1.1(p. 120)の命題である。同所の注意のとおり、型を $\forall X.\,(X\to X)\to(X\to X)$ に替えると、数字に加えて $\Lambda X.\,\lambda y{:}X\to X.\,y$ も閉じた正規形になる。

表せる関数

thm-sf-sn と正規形の一意性から、型 $\mathrm{Nat}\to\mathrm{Nat}$ の閉じた項 $F$ は全域的な関数を定める。$F\,\underline n$ を任意の順に簡約すれば止まり、prop-sf-subject と prop-sf-numerals から結果はある数字 $\underline m$ である。よって $F$ は $n\mapsto m$ を表し、この関数は計算可能である。逆はどうか。

表せない全域的な再帰関数

全域的な再帰関数で、System F の項で表せないものがある。

対角線論法

型の付く項は規則が項の形で決まるので、型判断は機械的に検査できる。よって型 $\mathrm{Nat}\to\mathrm{Nat}$ の閉じた項を $F_0,F_1,F_2,\dots$ と機械的に列挙できる。$g(n)$ を、$F_n\,\underline n$ を左端の β 基から順に簡約して得た数字 $\underline m$ の $m$ に $1$ を足した値とする。上で見たとおりこの手続きは必ず止まるので、$g$ は全域的な再帰関数である。$g$ を $F_k$ が表すとすると $F_k\,\underline k\to^*\underline{g(k)}$ だが、正規形は一意なので $F_k\,\underline k$ の正規形は $\underline{g(k)-1}$ でもあり、矛盾する。$\square$

GLT89 §15.1.2(p. 121)は、正規化の操作そのものを表せないことの形で同じ議論を述べている。表せる関数の正確な範囲は次の定理で与えられる。

表現定理

System F で表せる関数は、二階の Peano 算術 PA2 で全域的であることが証明できる再帰関数にちょうど一致する。

表現定理の証明の筋

この記事では証明しない(GLT89 §15.2、p. 123 の定理)。一方の向きは、強正規化定理の証明を一つの項 $F$ と数字に限って調べると、使う候補が有限個で PA2 の中で書けることによる(同 §15.1.3、p. 122)。逆向きは、PA2 の証明から項を取り出す実現可能性の方法による。特に、Peano算術 で全域性が証明できる再帰関数はすべて System F で表せる。

型を消した体系と決定不能性

項から型の注釈、型の抽象、型の適用を取り除いた型なしの λ 項を 消去 という。型なしの項 $P$ に型が付く(ある System F の項の消去になっている)かを問う問題を 型付け可能性、型と文脈も与えて問う問題を 型検査 という。この型を消した版を Curry 流の System F という。たとえば $\lambda x.\,xx$ は $\lambda x{:}\forall X.\,X\to X.\,x\,(\forall X.\,X\to X)\,x$ の消去なので型が付く。これは単純型ではできない(型理論 の例「反例:自分自身への適用」)。
消去した項の β 簡約の一歩は、もとの項で型の β 基をいくつか縮約したあとの β 簡約の一歩に持ち上がる。型の β 基の縮約は消去を変えないので、消去した項の無限の簡約の列はもとの項の無限の列に持ち上がり、型の付く項の消去も強正規化可能である。したがって $\Omega=(\lambda x.\,xx)(\lambda x.\,xx)$ には型が付かない。Wells は、Curry 流の System F の型付け可能性と型検査が互いに帰着でき、どちらも決定不能であることを示したWel99。この記事では証明しない。証明は半単一化問題からの帰着による。実用のプログラム言語では、型の量化を型の外側に限り、多相性を let 束縛の変数に限った Hindley–Milner の型体系が、型付け可能性が決定できる部分として使われる。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
($\forall$I) の変数の条件$x{:}X\vdash(\Lambda X.\,x)(X\to X)$prop-sf-subject
型が付く$\Omega=(\lambda x.\,xx)(\lambda x.\,xx)$thm-sf-sn
prop-sf-numerals の「閉じた」$n{:}\mathrm{Nat}\vdash n:\mathrm{Nat}$prop-sf-numerals
prop-sf-numerals の「正規形」$\mathsf{add}\,\underline1\,\underline1$prop-sf-numerals(数字そのものではない)
型の量化を Curry 流の消去に替える消去した項の型付け可能性型検査の決定可能性
反例の確かめ

変数の条件。 条件を外すと $x{:}X\vdash\Lambda X.\,x:\forall X.\,X$ が導け、($\forall$E) で $x{:}X\vdash(\Lambda X.\,x)(X\to X):X\to X$ となる。一歩簡約すると $x[X\to X/X]=x$ で、その型は $X$ であり $X\to X$ ではない。項の型も簡約で変わってしまう。
型が付く。 $\Omega\to\Omega$ で、簡約は終わらない。
閉じた・正規形。 $n$ は正規形だが数字でない。$\mathsf{add}\,\underline1\,\underline1$ は閉じていて型 $\mathrm{Nat}$ をもつが β 基を含み、$\underline2$ に簡約されて初めて数字になる。
消去。 注釈のある System F では、型判断が項の形で決まるので型検査は項の大きさの帰納法で決定できる。型を消すと、注釈を補う方法が無限にあり、Wel99 によって決定不能になる。

関連項目

参考文献

[1]
J. B. Wells, Typability and type checking in System F are equivalent and undecidable, Annals of Pure and Applied Logic, 1999, pp. 111–156
[2]
Jean-Yves Girard, Yves Lafont, Paul Taylor, Proofs and Types, Cambridge Tracts in Theoretical Computer Science 7, Cambridge University Press, 1989, 第 11 章(§11.1 体系と Reynolds の注意 p. 81、§11.2 変数の条件 p. 82、§11.3–§11.5 データ型の表現 pp. 83–92、§11.5.1 整数と対による再帰 pp. 88–90、§11.6 Curry–Howard 対応 p. 93)、第 14 章(冒頭:正規形の一意性と PA2 p. 113、§14.1 可約性の候補 p. 114、§14.2–§14.3 pp. 116–118)、第 15 章(§15.1.1 数字 p. 120、§15.1.2 表せない全域的な再帰関数 p. 121、§15.1.3 p. 122、§15.2 表現定理 p. 123)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する