Hindley–Milner型推論(Hindley–Milner type inference)とは、型の注釈のないラムダ項に、let で束縛した変数だけを型スキームによって多相的にする型を付け、その型を単一化で機械的に求める方法である。Milner の算法 $W$ は、項に型が付くときは失敗せずにその主要型、すなわち他のすべての型をその代入例として含む型を返し、型が付かないときは失敗する。したがって型が付くかどうかは決定可能である。let を含む項の主要型は項の長さに対して二重指数的に大きくなりうる。
Hindley–Milner 型推論(Hindley–Milner type inference)は、型の注釈のない λ 項に、$\mathbf{let}$ で束縛した変数だけが多相的になる型を付け、その型を機械的に求める方法である。単純型付きλ計算 の主要型の定理を、$\mathbf{let}$ による多相性をもつ体系(Hindley–Milner の型体系)へ広げたもので、ML や Haskell などの関数型言語の型推論の土台になっている。
型の量化を自由に許す System F では、型の付かない項から型を求める問題は決定不能になる。Hindley–Milner の型体系は量化を型の外側(型スキーム)と $\mathbf{let}$ に限ることで、$\mathbf{let}$ で名前を付けた恒等関数を同じ項の中で別々の型に使う多相性を保ちつつ、算法 W が型の付く項にはその 主要型(他のすべての型をその代入例として含む型)を返し、型の付かない項では失敗するようにしている。
主要型の考えは Hindley が組合せ論理について示しHin69、Milner が多相的な型をもつプログラム言語の型検査の算法 W を与えMil78、Damas と Milner が W の返す型が主要型であること(完全性)を示したDM82。この記事では、型体系を定め、W の健全性と完全性を完全に証明する。
型代入は 単純型付きλ計算 の節「主要型」の記法に従う。型代入 $S$ を型 $\tau$ に施したものを $\tau S$ と書き、$S$ を施してから $T$ を施す代入を $ST$ と書く。$\mathrm{dom}(S):=\{\alpha\mid\alpha S\ne\alpha\}$ とし、$\mathrm{dom}(S)$ と $\alpha S$($\alpha\in\mathrm{dom}(S)$)に現れる型変数を合わせた集合を $\mathrm{var}(S)$ とする。型スキームへは、束縛変数を $\mathrm{var}(S)$ と重ならないよう名前を替えて $(\forall\bar\alpha.\,\tau)S:=\forall\bar\alpha.\,(\tau S)$ と施し、文脈には各成分に施す。
| 名前 | 前提 | 結論 |
|---|---|---|
| (var) | $x{:}\sigma$ が $\Gamma$ にあり、$\sigma\succeq\tau$ | $\Gamma\vdash x:\tau$ |
| (abs) | $\Gamma,x{:}\tau\vdash M:\tau'$ | $\Gamma\vdash\lambda x.\,M:\tau\to\tau'$ |
| (app) | $\Gamma\vdash M:\tau\to\tau'$、$\Gamma\vdash N:\tau$ | $\Gamma\vdash MN:\tau'$ |
| (let) | $\Gamma\vdash M:\tau$、$\Gamma,x{:}\mathrm{gen}(\Gamma,\tau)\vdash N:\tau'$ | $\Gamma\vdash\mathbf{let}\ x=M\ \mathbf{in}\ N:\tau'$ |
規則は項の形で一つに決まる。$\lambda$ で束縛した変数は型(量化のない型スキーム)しかもたないが、$\mathbf{let}$ で束縛した変数は、$\Gamma$ に縛られない型変数について一般化される。以下、項の束縛変数は名前を替えて、文脈にある変数とも互いとも異なるようにしておく。
$M_1:=\mathbf{let}\ I=\lambda x.\,x\ \mathbf{in}\ I\,I$ には型が付く。$\vdash\lambda x.\,x:\alpha\to\alpha$ で、空の文脈では $\mathrm{gen}=\forall\alpha.\,\alpha\to\alpha$ である。(var) で前の $I$ に $(\beta\to\beta)\to(\beta\to\beta)$、後の $I$ に $\beta\to\beta$ を当て、(app) で $\vdash M_1:\beta\to\beta$ を得る。
一方、同じ計算をする $M_2:=(\lambda I.\,I\,I)(\lambda x.\,x)$ には型が付かない。$\Gamma\vdash\lambda I.\,I\,I:\tau_1\to\tau_2$ とすると $\Gamma,I{:}\tau_1\vdash I\,I:\tau_2$ で、$I$ は量化のない $\tau_1$ しかもたないので、(app) から $\tau_1=\tau_1\to\tau_2$ となる。右辺のほうが記号が多いので、これは起こらない。System F では $M_2$ に型が付く。$\lambda I.\,I\,I$ の $I$ に型 $\forall X.\,X\to X$ を与えればよい。
$\Gamma$ を文脈、$\tau$ を型、$S$ を型代入とする。
1 と 3 は代入例を変数ごとに比べ、2 は量化される変数が増えることを見る。
1:$\mathrm{ftv}(\tau S)\setminus\mathrm{ftv}(\Gamma S)$ の元を $\bar\gamma$ と並べ、$\mathrm{gen}(\Gamma S,\tau S)$ の代入例 $\tau S[\bar u/\bar\gamma]$ をとる。$\mathrm{gen}(\Gamma,\tau)S=\forall\bar\alpha'.\,\tau[\bar\alpha'/\bar\alpha]S$($\bar\alpha'$ は新しい変数)に、$\alpha'_i\mapsto\alpha_iS[\bar u/\bar\gamma]$ を当てると同じ型になる。実際、$\tau$ の変数 $\delta$ が $\bar\alpha$ の元なら両辺とも $\delta S[\bar u/\bar\gamma]$ であり、$\delta\in\mathrm{ftv}(\Gamma)$ なら $\delta S$ の変数は $\mathrm{ftv}(\Gamma S)$ に属して $\bar\gamma$ と交わらないので、両辺とも $\delta S$ である。
2:$\bar\alpha$ は $\Gamma$ に自由に現れないので $\Gamma Q=\Gamma$ である。$\mathrm{gen}(\Gamma,\tau)=\forall\bar\beta.\,\tau Q$ で、$\bar\beta$ は $\mathrm{var}(S)$ と交わらないので $\mathrm{gen}(\Gamma,\tau)S=\forall\bar\beta.\,\tau QS$ である。$\bar\beta$ は $S$ で動かず、$\mathrm{ftv}(\Gamma S)$ にも現れない($\Gamma$ にも $\mathrm{var}(S)$ にも現れないから)。よって $\bar\beta\subseteq\mathrm{ftv}(\tau QS)\setminus\mathrm{ftv}(\Gamma S)$ であり、$\mathrm{gen}(\Gamma S,\tau QS)$ は $\bar\beta$ を含むより多くの変数を量化するので、代入例はより多い。
3:$\sigma=\forall\bar\beta.\,\tau$ の束縛変数を $\mathrm{ftv}(\sigma')$ と重ならないよう選ぶ。$\tau$ は $\sigma$ の代入例なので $\sigma'$ の代入例であり、$\sigma'$ の自由な変数は代入例にそのまま残る。よって $\mathrm{ftv}(\sigma')\subseteq\mathrm{ftv}(\tau)\setminus\bar\beta=\mathrm{ftv}(\sigma)$ である。$\square$
どちらも導出についての帰納法で(2 はすべての $S$ についてまとめて示す)、(abs)、(app) は帰納法の仮定からすぐ従う。(let) では、1 は lem-hm-gen の 3、2 は lem-hm-gen の 2 と 1 を使う。
1:(var) は、$\Gamma(x)$ の代入例が $\Gamma'(x)$ の代入例であることによる。(let) では、$\Gamma\vdash M:\tau_1$ と帰納法の仮定から $\Gamma'\vdash M:\tau_1$ である。lem-hm-gen の 3 から $\mathrm{ftv}(\Gamma')\subseteq\mathrm{ftv}(\Gamma)$ なので、$\mathrm{gen}(\Gamma',\tau_1)$ は $\mathrm{gen}(\Gamma,\tau_1)$ 以上に多くの変数を量化し、$\Gamma',x{:}\mathrm{gen}(\Gamma',\tau_1)\sqsupseteq\Gamma,x{:}\mathrm{gen}(\Gamma,\tau_1)$ である。$N$ について帰納法の仮定を使えばよい。
2:(var) は、$\sigma\succeq\tau$ なら $\sigma S\succeq\tau S$ であること(束縛変数を $\mathrm{var}(S)$ と重ならないように選ぶ)による。(let) では $\Gamma\vdash M:\tau_1$、$\Gamma,x{:}\mathrm{gen}(\Gamma,\tau_1)\vdash N:\tau'$ とする。lem-hm-gen の 2 の $Q$ について $\Gamma QS=\Gamma S$ だから、$M$ の導出に代入 $QS$ で帰納法の仮定を使うと $\Gamma S\vdash M:\tau_1QS$ を得る。$N$ には $S$ を当てて $\Gamma S,x{:}\mathrm{gen}(\Gamma,\tau_1)S\vdash N:\tau'S$ を得る。lem-hm-gen の 2 により文脈の $x$ の成分を $\mathrm{gen}(\Gamma S,\tau_1QS)$ に替えても以上に一般的なので、1 から $\Gamma S,x{:}\mathrm{gen}(\Gamma S,\tau_1QS)\vdash N:\tau'S$ となり、(let) で閉じる。$\square$
型の等式を解くには単一化を使う。型は 2 項の関数記号 $\to$ と型変数からなる項なので、導出原理 の定理「単一化定理」の算法がそのまま使える。2 つの型 $\tau_1,\tau_2$ が単一化できるとき、その算法が返す最汎単一化子を $\mathrm{mgu}(\tau_1,\tau_2)$ と書く。同記事の証明の不変量から、$\tau_1U=\tau_2U$ となる任意の $U$ について
$$
\mathrm{mgu}(\tau_1,\tau_2)\,U=U
$$
が成り立つ。また算法は $\tau_1,\tau_2$ の変数どうし・部分項どうしを結ぶだけなので、$\mathrm{var}(\mathrm{mgu}(\tau_1,\tau_2))\subseteq\mathrm{ftv}(\tau_1)\cup\mathrm{ftv}(\tau_2)$ である。
文脈 $\Gamma$ と項 $M$ から、型代入と型の組 $W(\Gamma,M)=(S,\tau)$ を返すか失敗する手続きを、$M$ の形で再帰的に定める。「新しい変数」は、その時点までに現れたどの型・文脈・代入にも現れない型変数とする。
各段は項の真部分への呼び出しと単一化だけなので、W はいつも有限の手順で止まる。
$W(\Gamma,M)=(S,\tau)$ とし、この呼び出しの中で選んだ新しい変数の集合を $\mathcal N$ とする。このとき $\mathrm{var}(S)\cup\mathrm{ftv}(\tau)\subseteq\mathrm{ftv}(\Gamma)\cup\mathcal N$ である。とくに $\mathrm{ftv}(\Gamma S)\subseteq\mathrm{ftv}(\Gamma)\cup\mathcal N$ である。
各段で現れる変数を数える。
$W(\Gamma,M)=(S,\tau)$ なら、$\Gamma S\vdash M:\tau$ である。
$M$ についての帰納法である。
代入 $R,R'$ が集合 $X$ の上で一致すること($\alpha R=\alpha R'$、$\alpha\in X$)を $R=_XR'$ と書く。文脈 $\Gamma R$ は $R$ の $\mathrm{ftv}(\Gamma)$ の上の値だけで決まる。
型代入 $R$ と型 $\tau'$ について $\Gamma R\vdash M:\tau'$ ならば、$W(\Gamma,M)$ は失敗せずに $(S,\tau)$ を返し、ある型代入 $T$ で
$$
R=_{\mathrm{ftv}(\Gamma)}ST,\qquad\tau'=\tau T
$$
となる。
$\Gamma,R,\tau'$ を動かして、$M$ についての帰納法で示す。W が選ぶ新しい変数は $\mathrm{ftv}(\Gamma)$ に現れないので、$R$ をそれらの上で替えても $\Gamma R$ は変わらない。これを繰り返し使う。
1. 変数。 $\Gamma(x)=\sigma=\forall\bar\alpha.\,\tau_0$ とし、$\bar\alpha$ は $\mathrm{var}(R)$ と重ならないよう選ぶ。$\Gamma R\vdash x:\tau'$ は (var) によるので、$\tau'=\tau_0R[\bar u/\bar\alpha]$ となる $\bar u$ がある。W は $(\mathrm{id},\tau_0[\bar\beta/\bar\alpha])$ を返す。$T$ を、$\beta_i\mapsto u_i$ とし、それ以外では $R$ と一致する代入とする。$\bar\beta\notin\mathrm{ftv}(\Gamma)$ だから $R=_{\mathrm{ftv}(\Gamma)}T$ である。$\tau_0$ の変数は $\bar\alpha$ か $\mathrm{ftv}(\sigma)\subseteq\mathrm{ftv}(\Gamma)$ に属するので、$\tau_0[\bar\beta/\bar\alpha]T=\tau_0R[\bar u/\bar\alpha]=\tau'$ である。
2. 抽象。 $\Gamma R\vdash\lambda x.\,P:\tau'$ は (abs) によるので、$\tau'=\tau_1\to\tau_2$、$\Gamma R,x{:}\tau_1\vdash P:\tau_2$ である。W が選ぶ $\beta$ について、$R_1$ を $\beta\mapsto\tau_1$ とし他では $R$ と一致する代入とすると、$(\Gamma,x{:}\beta)R_1=\Gamma R,x{:}\tau_1$ である。帰納法の仮定から $W((\Gamma,x{:}\beta),P)=(S,\tau)$ と $T$ があって $R_1=_{\mathrm{ftv}(\Gamma)\cup\{\beta\}}ST$、$\tau_2=\tau T$ となる。よって $R=_{\mathrm{ftv}(\Gamma)}ST$ で、$(\beta S\to\tau)T=\beta R_1\to\tau_2=\tau'$ である。
3. 適用。 $\Gamma R\vdash PN:\tau'$ は (app) によるので、ある $\tau_0$ で $\Gamma R\vdash P:\tau_0\to\tau'$、$\Gamma R\vdash N:\tau_0$ である。帰納法の仮定から $W(\Gamma,P)=(S_1,\tau_1)$ と $T_1$ があって $R=_{\mathrm{ftv}(\Gamma)}S_1T_1$、$\tau_0\to\tau'=\tau_1T_1$ となる。すると $(\Gamma S_1)T_1=\Gamma R\vdash N:\tau_0$ なので、文脈 $\Gamma S_1$ と代入 $T_1$ に帰納法の仮定を使うと、$W(\Gamma S_1,N)=(S_2,\tau_2)$ と $T_2$ があって $T_1=_{\mathrm{ftv}(\Gamma S_1)}S_2T_2$、$\tau_0=\tau_2T_2$ となる。
$Y:=\mathrm{ftv}(\tau_1)\setminus\mathrm{ftv}(\Gamma S_1)$ とおき、$T_2'$ を $Y$ の上で $T_1$、それ以外で $T_2$ と一致する代入とする。2 回目の呼び出しの新しい変数の集合を $\mathcal N_2$ とすると、$Y$ は $\mathrm{ftv}(\Gamma S_1)\cup\mathcal N_2$ と交わらず、lem-hm-vars から $S_2$、$\tau_2$、$\Gamma S_1S_2$ の変数はこの集合に属する。よって $\tau_2T_2'=\tau_0$、$\Gamma S_1S_2T_2'=\Gamma S_1S_2T_2$ で、$Y$ の元は $S_2$ で動かない。以上から、$\tau_1$ の各変数 $\alpha$ について $\alpha S_2T_2'=\alpha T_1$ が成り立ち($\alpha\in\mathrm{ftv}(\Gamma S_1)$ なら $T_1=S_2T_2$ による)、$\tau_1S_2T_2'=\tau_1T_1=\tau_0\to\tau'$ である。
W が選ぶ $\beta$ は $\tau_1S_2$、$\tau_2$、$\Gamma S_1S_2$ に現れない。$U$ を、$\beta\mapsto\tau'$ とし他では $T_2'$ と一致する代入とすると、
$$
(\tau_1S_2)U=\tau_0\to\tau'=(\tau_2\to\beta)U
$$
である。よって $\tau_1S_2$ と $\tau_2\to\beta$ は単一化でき、$V:=\mathrm{mgu}$ について $VU=U$ である。W は $(S_1S_2V,\beta V)$ を返す。$T:=U$ とすると、$\mathrm{ftv}(\Gamma)$ の上で
$$
S_1S_2VU=S_1S_2U=S_1S_2T_2'=S_1S_2T_2=S_1T_1=R
$$
である。2 つ目の等号は $\beta$ が $\Gamma S_1S_2$ に現れないこと、3 つ目は $\Gamma S_1S_2T_2'=\Gamma S_1S_2T_2$、4 つ目は $T_1=_{\mathrm{ftv}(\Gamma S_1)}S_2T_2$ による。また $\beta VU=\beta U=\tau'$ である。
4. let。 $\Gamma R\vdash\mathbf{let}\ x=P\ \mathbf{in}\ N:\tau'$ は (let) によるので、ある $\tau_0$ で $\Gamma R\vdash P:\tau_0$、$\Gamma R,x{:}\mathrm{gen}(\Gamma R,\tau_0)\vdash N:\tau'$ である。帰納法の仮定から $W(\Gamma,P)=(S_1,\tau_1)$ と $T_1$ があって $R=_{\mathrm{ftv}(\Gamma)}S_1T_1$、$\tau_0=\tau_1T_1$ となる。$\Gamma':=(\Gamma S_1,x{:}\mathrm{gen}(\Gamma S_1,\tau_1))$ とおくと、lem-hm-gen の 1 により
$$
\Gamma'T_1=\bigl(\Gamma R,\ x{:}\mathrm{gen}(\Gamma S_1,\tau_1)T_1\bigr)\sqsupseteq\bigl(\Gamma R,\ x{:}\mathrm{gen}(\Gamma R,\tau_0)\bigr)
$$
である($\Gamma S_1T_1=\Gamma R$、$\tau_1T_1=\tau_0$)。lem-hm-stable の 1 から $\Gamma'T_1\vdash N:\tau'$ で、帰納法の仮定から $W(\Gamma',N)=(S_2,\tau_2)$ と $T_2$ があって $T_1=_{\mathrm{ftv}(\Gamma')}S_2T_2$、$\tau'=\tau_2T_2$ となる。W は $(S_1S_2,\tau_2)$ を返す。$\mathrm{ftv}(\Gamma S_1)\subseteq\mathrm{ftv}(\Gamma')$ なので、$\mathrm{ftv}(\Gamma)$ の上で $S_1S_2T_2=S_1T_1=R$ であり、$T:=T_2$ とすればよい。$\square$
健全性と完全性を合わせると、次が従う。
閉じた項 $M$ に型が付くことと、$W(\emptyset,M)$ が失敗しないことは同値である。$W(\emptyset,M)=(S,\tau)$ なら $\vdash M:\tau$ であり、$\vdash M:\tau'$ となる型 $\tau'$ はすべて、ある型代入 $T$ で $\tau'=\tau T$ と書ける。W は常に止まるので、型が付くかは決定可能である。
$W(\emptyset,M)=(S,\tau)$ なら thm-hm-sound から $\vdash M:\tau$ である。$\vdash M:\tau'$ なら thm-hm-complete を $R:=\mathrm{id}$ に使うと、W は失敗せず、$\tau'=\tau T$ となる $T$ がある。$\square$
$\tau$ を $M$ の 主要型 という。lem-hm-stable の 2 から $\tau$ の代入例はすべて $M$ の型なので、$M$ の型の全体はちょうど $\tau$ の代入例の全体である。$\mathbf{let}$ を含まない項では、これは 単純型付きλ計算 の定理「主要型の定理」の閉じた項の場合と同じ内容になる。
ex-hm-let の $M_1$ で W を追う。$W(\emptyset,\lambda x.\,x)=(\mathrm{id},\alpha\to\alpha)$ で、$\mathrm{gen}(\emptyset,\alpha\to\alpha)=\forall\alpha.\,\alpha\to\alpha$ である。本体 $I\,I$ では、前の $I$ から $\beta_1\to\beta_1$、後の $I$ から $\beta_2\to\beta_2$ が出て、$\mathrm{mgu}(\beta_1\to\beta_1,\ (\beta_2\to\beta_2)\to\beta_3)=\{\beta_1\mapsto\beta_2\to\beta_2,\ \beta_3\mapsto\beta_2\to\beta_2\}$ である。よって主要型は $\beta_2\to\beta_2$ である。$M_2$ では、$\lambda I.\,I\,I$ の中で $\mathrm{mgu}(\beta,\ \beta\to\gamma)$ が出現検査で失敗し、W も失敗する。
主要型は項に比べて非常に大きくなりうる。$D:=\lambda x.\,\lambda z.\,z\,x\,x$ の主要型は $\alpha\to(\alpha\to\alpha\to\gamma)\to\gamma$ で、型 $\theta$ を受け取って $\alpha$ が 2 回現れる型 $F(\theta):=(\theta\to\theta\to\gamma)\to\gamma$ を返す。
$f_0:=D$、$f_{k+1}:=\lambda x.\,f_k\,(f_k\,x)$ とし、項
$$
E_k:=\mathbf{let}\ f_0=D\ \mathbf{in}\ \mathbf{let}\ f_1=\lambda x.\,f_0(f_0x)\ \mathbf{in}\ \cdots\ \mathbf{let}\ f_k=\lambda x.\,f_{k-1}(f_{k-1}x)\ \mathbf{in}\ f_k
$$
を考える。$E_k$ の長さは $k$ に比例する。$f_j$ を束縛する時点の文脈 $\Gamma_j$ の型スキームはすべて閉じている(自由な型変数をもたない)ので、W が $f_j$ に与える型は完全に一般化される。$f_j$ の主要型を $\alpha\to F^{(m_j)}(\alpha)$($F$ の $m_j$ 回の合成、$\gamma$ は合成のたびに新しい変数)とすると、$f_{j+1}$ の本体では内側の $f_j$ が $\alpha'\to F^{(m_j)}(\alpha')$、外側の $f_j$ が $F^{(m_j)}(\alpha')\to F^{(2m_j)}(\alpha')$ に具体化される。よって $m_{j+1}=2m_j$、$m_0=1$ で $m_k=2^k$ である。$F^{(m)}(\alpha)$ には $\alpha$ が $2^m$ 回現れるので、$E_k$ の主要型 $\alpha\to F^{(2^k)}(\alpha)$ の右側には $\alpha$ が $2^{2^k}$ 回現れる。型の代入例は元の型より小さくならないので、$E_k$ のどの型も書き下すと $2^{2^k}$ 個以上の記号を含む。
$\mathbf{let}$ を含む項の型付け可能性を決める問題については、Kfoury、Tiuryn、Urzyczyn が、指数時間で解ける問題のどれもがこの問題に帰着できること(DEXPTIME 困難であること)を示し、既知の指数時間の算法とあわせて DEXPTIME 完全であることを導いたKTU90。この記事では証明しない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| (let) の一般化($\mathbf{let}$ を $\lambda$ と適用に替える) | $M_2=(\lambda I.\,I\,I)(\lambda x.\,x)$ | $M_1$ には型が付くのに $M_2$ には付かない |
| $\mathrm{gen}$ で $\mathrm{ftv}(\Gamma)$ を除くこと | $\lambda x.\,\mathbf{let}\ y=x\ \mathbf{in}\ y$ | $\mathbf{let}$ を展開しても型が保たれること |
| 単一化の出現検査 | $\lambda x.\,x\,x$ | thm-hm-sound |
| 単一化子が最汎 | $(\lambda x.\,x)(\lambda z.\,z)$ で余分に $\beta\mapsto\delta\to\delta$ | thm-hm-complete |
let を替える。 ex-hm-let のとおりである。$\mathbf{let}\ x=P\ \mathbf{in}\ N$ と $(\lambda x.\,N)P$ は同じ計算をするが、型付けは異なる。
gen の条件。 $\Gamma$ の自由変数まで一般化すると、$x{:}\alpha\vdash x:\alpha$ から $y{:}\forall\alpha.\,\alpha$ となり、$y$ に任意の型 $\delta$ が付いて $\vdash\lambda x.\,\mathbf{let}\ y=x\ \mathbf{in}\ y:\alpha\to\delta$ が導ける。$\mathbf{let}$ を展開した同じ計算の $\lambda x.\,x$ では、$x{:}\alpha$ に (var) で付く型は $\alpha$ だけなので、$\alpha\to\delta$($\delta\ne\alpha$)は導けない。この型は「受け取った値を任意の型の値として返す」と読めて、意味の上でも正しくない。
出現検査。 出現検査を省くと、$\mathrm{mgu}(\beta,\beta\to\gamma)$ が $\beta\mapsto\beta\to\gamma$ を返す。これは等式を解いておらず($\beta S=\beta\to\gamma$、$(\beta\to\gamma)S=(\beta\to\gamma)\to\gamma$)、W の返す $\lambda x.\,x\,x$ の「型」は導けない。
最汎。 W の 3 で $\mathrm{mgu}(\alpha\to\alpha,\ (\beta\to\beta)\to\gamma)=\{\alpha\mapsto\beta\to\beta,\ \gamma\mapsto\beta\to\beta\}$ の代わりに、さらに $\beta\mapsto\delta\to\delta$ も施す単一化子を使うと、返る型は $(\delta\to\delta)\to(\delta\to\delta)$ になる。正しい型 $\beta\to\beta$ はその代入例でない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する