単一化(unification)とは、変数を含む項の等式の組に対し、変数に項を代入して各等式の両辺を文字どおり同じ項にする代入(単一化子)を求めることである。単一化できる問題には、他のすべての単一化子をそれへの代入で与える最汎単一化子があり、削除・分解・衝突・向き替え・出現検査・消去の規則をどの順に使っても計算でき、名前の付け替えを除いて一意である。導出原理や型推論の基礎となる。可換性などの等式を法とすると最汎単一化子がないことがある。
単一化(unification)とは、変数を含む 2 つの項(または項の等式の有限個の組)に対して、変数に項を代入して両辺を文字どおり同じ項にする代入(単一化子)を求めることである。たとえば $f(a,x)$ と $f(y,b)$ は、$x$ に $b$、$y$ に $a$ を代入すれば両方とも $f(a,b)$ になる。単一化子はふつう無数にあるが、単一化できる問題には最汎単一化子、すなわち他のどの単一化子もそれにさらに代入を施して得られるものがあり、しかも機械的に計算できる。
単一化は、一階の 導出原理 で節どうしを組み合わせるとき、Hindley–Milner型推論 で型の等式を解くとき、論理型プログラミング言語の実行、項書き換え系の臨界対の計算など、記号計算のいたるところで使われる。この名前と最初の系統的な扱いは J. A. Robinson による(BS01 §1.2, p. 442)。
導出原理 では、集合を 1 元にする代入として単一化子を定義し、不一致の組を順にたどる Robinson の算法で最汎単一化子の存在を証明した。この記事では、問題を等式の組とみて 6 つの書き換え規則で解く方法をとり、規則をどの順に使っても最汎単一化子が得られること、最汎単一化子が名前の付け替えを除いて一意なこと、その大きさが指数的になりうること、等式の公理を法とする単一化では最汎単一化子がないことがあることを示す。
関数記号の集合 $\mathcal F$(各記号に引数の個数が決まっている。個数 $0$ の記号は定数)と、可算無限個の変数の集合 $\mathcal V$ から作られる項の全体を $T(\mathcal F,\mathcal V)$ と書く。項 $t$ に現れる変数の集合を $\operatorname{Var}(t)$、$t$ に現れる記号(関数記号と変数)の個数を $\lvert t\rvert$ と書く。
代入とは写像 $\sigma\colon\mathcal V\to T(\mathcal F,\mathcal V)$ で、$x\sigma\neq x$ となる $x$ が有限個のものをいう。その集合を $\operatorname{Dom}(\sigma)$ と書く。$t\sigma$ は $t$ の各変数 $x$ を一斉に $x\sigma$ に置き換えた項、合成 $\sigma\theta$ は $x(\sigma\theta):=(x\sigma)\theta$ で定め、$t(\sigma\theta)=(t\sigma)\theta$ である。$\{x_1\mapsto t_1,\dots,x_n\mapsto t_n\}$ は $x_i$ を $t_i$ に、他の変数をそれ自身に写す代入、$\varepsilon$ は何も替えない代入である。$\sigma\sigma=\sigma$ のとき $\sigma$ は冪等であるという。変数を変数に写し、$\operatorname{Dom}(\sigma)$ 上で単射で、像が $\operatorname{Dom}(\sigma)$ に一致する代入を名前の付け替えという。
代入 $\sigma,\theta$ について、ある代入 $\lambda$ で $\theta=\sigma\lambda$ となるとき $\sigma\preceq\theta$ と書き、$\sigma$ は $\theta$ より一般的であるという。$\preceq$ は反射的かつ推移的な関係(前順序)である。
項の等式の有限集合 $P=\{s_1\overset{?}{=}t_1,\dots,s_n\overset{?}{=}t_n\}$ を単一化問題という。代入 $\theta$ がすべての $i$ で $s_i\theta=t_i\theta$ を満たすとき、$\theta$ を $P$ の単一化子といい、単一化子をもつ問題を単一化可能という。$P$ の単一化子 $\sigma$ で、$P$ のどの単一化子 $\theta$ についても $\sigma\preceq\theta$ となるものを $P$ の最汎単一化子(most general unifier、mgu)という。
等式は文字どおりの一致であり、記号の意味(たとえば $+$ の可換性)は考えない。意味を考える場合は後の節「等式理論を法とする単一化」で扱う。項の集合 $E=\{e_1,\dots,e_k\}$ を 1 元にする代入(導出原理 の定義)は、問題 $\{e_1\overset{?}{=}e_2,\dots,e_1\overset{?}{=}e_k\}$ の単一化子と同じものなので、二つの定義は同じ概念を表す。この定義は、2 つの項についての BS01 Definition 2.1(p. 446)を等式の有限集合に広げたものである。
等式の組 $S=\{x_1\overset{?}{=}u_1,\dots,x_n\overset{?}{=}u_n\}$ が解けた形であるとは、$x_i$ が互いに異なる変数で、どの $x_i$ もどの $u_j$ にも現れないことをいう。このとき $\sigma_S:=\{x_1\mapsto u_1,\dots,x_n\mapsto u_n\}$ とおく。$u_j\sigma_S=u_j$ なので $\sigma_S$ は冪等で、$S$ の単一化子である。
| 問題 | 結果 | 理由 |
|---|---|---|
| $f(x,g(y))\overset{?}{=}f(g(u),g(z))$ | mgu $\{x\mapsto g(u),\ y\mapsto z\}$ | 分解すると $x\overset{?}{=}g(u)$、$y\overset{?}{=}z$ |
| $f(x,g(y))\overset{?}{=}f(g(u),h(z))$ | 単一化できない | $g\neq h$(記号の衝突) |
| $x\overset{?}{=}f(x)$ | 単一化できない | $\lvert x\theta\rvert<\lvert f(x)\theta\rvert$(出現検査) |
| $f(x,g(x),x)\overset{?}{=}f(g(u),g(g(z)),z)$ | 単一化できない | $x=g(u)=z$ と $x=g(z)$ から $z\overset{?}{=}g(z)$ |
1 行目:$\theta$ が単一化子であることは $f(x,g(y))\theta=f(g(u),g(z))=f(g(u),g(z))\theta$ から分かる。最汎であることは thm-unif-main から従う(規則で解くとこの解けた形になる)。これに名前の付け替え $\{y\mapsto z,\ z\mapsto y\}$ を合成した $\{x\mapsto g(u),\ z\mapsto y\}$ も最汎単一化子である(Gal15 Example 8.4.1, p. 367 はこちらを挙げる)。
2 行目:どの $\theta$ でも、両辺の第 2 引数の根の記号は $g$ と $h$ で異なる。
3 行目:どの $\theta$ でも $x\theta$ は $f(x)\theta=f(x\theta)$ の真の部分項なので、記号の個数が $1$ 少なく、等しくならない。
4 行目:単一化子 $\theta$ があれば、第 1・第 3 引数から $x\theta=g(u)\theta$ かつ $x\theta=z\theta$、第 2 引数から $g(x\theta)=g(g(z\theta))$ すなわち $x\theta=g(z\theta)$。よって $z\theta=g(z\theta)$ となり、3 行目と同じ理由で不可能である(Gal15 Example 8.4.1, p. 367)。
単一化問題を、まだ解いていない等式の有限多重集合 $P$ と、解けた形の組 $S$ の対 $P;S$、または失敗を表す記号 $\bot$ として扱う。$\theta$ が $P;S$ の単一化子であるとは、$P\cup S$ のすべての等式を満たすことをいう($\bot$ は単一化子をもたない)。次の 6 つの規則で書き換える($\uplus$ は多重集合の和)。
| 規則 | 書き換え | 条件 |
|---|---|---|
| 削除 | $\{s\overset{?}{=}s\}\uplus P;S\ \Rightarrow\ P;S$ | |
| 分解 | $\{f(s_1,\dots,s_n)\overset{?}{=}f(t_1,\dots,t_n)\}\uplus P;S\ \Rightarrow\ \{s_1\overset{?}{=}t_1,\dots,s_n\overset{?}{=}t_n\}\uplus P;S$ | $n=0$ も可 |
| 衝突 | $\{f(\vec s)\overset{?}{=}g(\vec t)\}\uplus P;S\ \Rightarrow\ \bot$ | $f\neq g$ |
| 向き替え | $\{t\overset{?}{=}x\}\uplus P;S\ \Rightarrow\ \{x\overset{?}{=}t\}\uplus P;S$ | $t$ は変数でない |
| 出現検査 | $\{x\overset{?}{=}t\}\uplus P;S\ \Rightarrow\ \bot$ | $x\in\operatorname{Var}(t)$、$x\neq t$ |
| 消去 | $\{x\overset{?}{=}t\}\uplus P;S\ \Rightarrow\ P\{x\mapsto t\};\ S\{x\mapsto t\}\cup\{x\overset{?}{=}t\}$ | $x\notin\operatorname{Var}(t)$ |
$P;\emptyset$ から始めて規則を使えなくなるまで書き換える。この形の規則は Herbrand の記述にさかのぼり、Martelli と Montanari が算法の解析の枠組みとして整えた(BS01 §2.2.3, pp. 448–449)。
$P;S\Rightarrow\Gamma$ を 1 回の書き換えとする。代入 $\theta$ が $P;S$ の単一化子であることと、$\Gamma$ の単一化子であることは同値である。
削除は自明な等式を除くだけである。分解では $f(\vec s)\theta=f(\vec t)\theta\iff$ すべての $i$ で $s_i\theta=t_i\theta$ である。向き替えは等式の左右を入れ替えるだけである。衝突では $f(\vec s)\theta$ と $g(\vec t)\theta$ の根の記号が異なり、出現検査では $x\theta$ が $t\theta$ の真の部分項になるので、どちらも左辺に単一化子がなく、$\bot$ と同じである。
消去:$x\theta=t\theta$ を満たす $\theta$ について、どの項 $u$ でも $u\{x\mapsto t\}\theta=u\theta$ である($u$ の組み立てについての帰納法。$u=x$ なら $t\theta=x\theta$、他の変数では変わらない)。したがって $x\theta=t\theta$ のもとで、$\theta$ が $P,S$ を満たすことと $P\{x\mapsto t\},S\{x\mapsto t\}$ を満たすことは同値である。両辺とも $x\overset{?}{=}t$ を含むので、主張が従う。$\square$
$P$ を有限の多重集合とする。$P;\emptyset$ から始まる書き換えの列はどれも有限で、それ以上書き換えられない状態は $\bot$ か $\emptyset;S$($S$ は解けた形)である。途中のどの $P_k;S_k$ でも $S_k$ は解けた形で、$S_k$ の左辺の変数は $P_k$ に現れない。
不変量。 初めは $S=\emptyset$ で成り立つ。消去以外の規則は $S$ を変えず、$P$ の変数を増やさない。消去で $x\overset{?}{=}t$ を処理するとき、$x$ は $P$ に現れるので $S$ の左辺ではなく、$S$ の左辺の変数は $P$ に現れないから $t$ にも現れない。$S\{x\mapsto t\}$ の右辺から $x$ は消え、新しい右辺 $t$ は $x$ も $S$ の左辺も含まないので、$S\{x\mapsto t\}\cup\{x\overset{?}{=}t\}$ は解けた形である。$P\{x\mapsto t\}$ の変数は元の $P$ の変数から $x$ を除いたものに含まれるので、新しい左辺 $x$ も $S$ の左辺も $P$ に現れない。
停止。 $P$ について、$n_1$ を $P$ に現れる変数の個数、$n_2$ を $P$ の記号の総数、$n_3$ を「$t\overset{?}{=}x$ で $t$ が変数でない」形の等式の個数とし、3 つ組 $(n_1,n_2,n_3)$ を辞書式に比べる。消去は $x$ を $P$ から除くので $n_1$ が減る。削除と分解は $n_1$ を増やさず $n_2$ を減らす。向き替えは $n_1,n_2$ を変えず $n_3$ を減らす。自然数の 3 つ組の辞書式順序は整礎なので、書き換えの列は有限である。
終わりの形。 $P$ が空でなければ、その等式 $s\overset{?}{=}t$ にどれかの規則が使える。$s=t$ なら削除、両辺が変数でなく根が同じなら分解、異なれば衝突、$s$ が変数でなく $t$ が変数なら向き替え、$s$ が変数 $x$ で $x\neq t$ なら、$x\in\operatorname{Var}(t)$ かどうかで出現検査か消去である。よって書き換えられない状態は $\bot$ か $\emptyset;S$ である。$\square$
$P$ を単一化問題とする。$P;\emptyset$ から規則をどの順に使っても、書き換えは有限回で止まり、次が成り立つ。
(a) $P$ が単一化可能でなければ、最後は $\bot$ である。
(b) $P$ が単一化可能なら、最後は $\emptyset;S$ であり、$\sigma_S$ は $P$ の冪等な最汎単一化子で、$\operatorname{Dom}(\sigma_S)\subseteq\operatorname{Var}(P)$ である。さらに $P$ のどの単一化子 $\theta$ についても $\theta=\sigma_S\theta$ が成り立つ。
lem-unif-terminate により書き換えは止まり、最後は $\bot$ か $\emptyset;S$ である。lem-unif-preserve を書き換えの回数についての帰納法で使うと、$P;\emptyset$ と最後の状態は同じ単一化子をもつ。
最後が $\emptyset;S$ なら、$\sigma_S$ は $S$ の単一化子なので $P$ の単一化子であり、$P$ は単一化可能である。逆に最後が $\bot$ なら単一化子はなく、$P$ は単一化可能でない。これで (a) と、(b) の前半(最後が $\emptyset;S$ であること)が分かる。
(b) の残り:$\theta$ を $P$ の単一化子とすると $S$ の単一化子でもある。$x\overset{?}{=}u$ が $S$ の等式なら $x\sigma_S\theta=u\theta=x\theta$、$S$ の左辺にない変数 $y$ では $y\sigma_S\theta=y\theta$ なので、$\theta=\sigma_S\theta$ である。とくに $\sigma_S\preceq\theta$ で、$\sigma_S$ は最汎単一化子である。冪等であることは解けた形から、$\operatorname{Dom}(\sigma_S)\subseteq\operatorname{Var}(P)$ は $S$ の左辺がすべて元の $P$ の変数であることから従う。$\square$
これは BS01 Lemmas 2.2, 2.4、Theorems 2.5–2.6、Corollary 2.7(pp. 450–451)の内容である。規則を使う順は結果の正しさに影響しない。導出原理 の Robinson の算法は、左から最初の不一致の組に規則を使うという特定の順序をとったものにあたる(BS01 pp. 449–450)。
最汎単一化子は一つとは限らない。$P=\{x\overset{?}{=}y\}$ には $\{x\mapsto y\}$ と $\{y\mapsto x\}$ の二つの冪等な最汎単一化子があり、変数の名前が違うだけである。一般にもこれ以上の違いはない。
$\sigma,\sigma'$ を代入とし、$\sigma\preceq\sigma'$ かつ $\sigma'\preceq\sigma$ とする。有限個の変数の集合 $X$ を固定する。このとき名前の付け替え $\rho$ で、すべての $x\in X$ について $x\sigma'=x\sigma\rho$ となるものがある。とくに $\sigma,\sigma'$ が単一化問題 $P$ の最汎単一化子なら、$X=\operatorname{Var}(P)$ についてこれが成り立つ。
$\sigma'=\sigma\lambda$、$\sigma=\sigma'\lambda'$ とおくと $\sigma=\sigma\lambda\lambda'$ である。$\mu:=\lambda\lambda'$ とし、$W:=\bigcup_{x\in X}\operatorname{Var}(x\sigma)$ とおく(有限集合)。
まず、項 $t$ と代入 $\mu$ について $t\mu=t$ なら、$t$ のすべての変数 $y$ で $y\mu=y$ である。$t$ の組み立てについての帰納法による:$t=y$ なら明らかで、$t=f(t_1,\dots,t_n)$ なら $t\mu=f(t_1\mu,\dots,t_n\mu)$ なので各 $t_i\mu=t_i$ である。
$x\in X$ について $x\sigma\mu=x\sigma$ だから、$W$ のすべての $y$ で $y\lambda\lambda'=y$ である。とくに $y\lambda$ は変数である(変数でない項に代入しても変数にはならない)。また $y,z\in W$ で $y\lambda=z\lambda$ なら $y=y\lambda\lambda'=z\lambda\lambda'=z$ なので、$\lambda$ は $W$ 上で単射である。$W':=\{y\lambda: y\in W\}$ とおくと、$y\mapsto y\lambda$ は $W$ から $W'$ への全単射である。
有限集合 $D:=W\cup W'$ で $\lvert D\setminus W\rvert=\lvert D\setminus W'\rvert$ なので、$D\setminus W$ から $D\setminus W'$ への全単射を一つ選んで合わせると、$W$ 上で $\lambda$ と一致する $D$ の置換 $\pi$ が得られる。$\rho$ を、$D$ 上で $\pi$、$D$ の外で恒等な代入とすれば、$\rho$ は $\operatorname{Dom}(\rho)$ を自分自身に全単射に写すので名前の付け替えである。$x\in X$ について $x\sigma$ の変数はすべて $W$ にあり、そこで $\lambda$ と $\rho$ は一致するから、$x\sigma'=x\sigma\lambda=x\sigma\rho$ である。
最後の主張は、最汎単一化子どうしが互いに $\preceq$ で比べられることから従う。$\square$
逆に、最汎単一化子 $\sigma$ と名前の付け替え $\rho$ から作った $\sigma\rho$ も最汎単一化子である($s\sigma=t\sigma$ なら $s\sigma\rho=t\sigma\rho$ なので $\sigma\rho$ は単一化子であり、$\rho$ に逆の付け替え $\rho^{-1}$ を合成すると $\sigma\rho\rho^{-1}=\sigma$ となるので $\sigma\rho\preceq\sigma$、また $\sigma\preceq\sigma\rho$ は定義から明らか)。したがって「最汎単一化子」は名前の付け替えを除いて問題 $P$ から決まる対象とみなせる。
規則による方法は、項を記号の列として書き下すと指数的な時間と大きさを要することがある。次の例では、書き下した最汎単一化子そのものが指数的に大きい(BS01 Example 2.8, p. 453 も同種の例)。
2 引数の関数記号 $f$ と変数 $x_0,x_1,\dots,x_n$ について
$$
P_n=\{x_1\overset{?}{=}f(x_0,x_0),\ x_2\overset{?}{=}f(x_1,x_1),\ \dots,\ x_n\overset{?}{=}f(x_{n-1},x_{n-1})\}
$$
とする。項 $t_0:=x_0$、$t_{k}:=f(t_{k-1},t_{k-1})$ とおくと $\lvert t_k\rvert=2^{k+1}-1$ である。
$\sigma=\{x_k\mapsto t_k : 1\le k\le n\}$ は $P_n$ の単一化子で、$P_n$ の任意の単一化子 $\theta$ は $k$ についての帰納法により $x_k\theta=t_k\theta$ を満たすから $\theta=\sigma\theta$ となり、$\sigma$ は最汎単一化子である。$P_n$ を書くのに要する記号は $4n$ 個だが、$x_n\sigma=t_n$ は $2^{n+1}-1$ 個の記号をもつ。thm-unif-unique により、どの最汎単一化子でも $x_n$ の像は $t_n$ の変数の名前を付け替えたものなので、同じ大きさをもつ。
この爆発は、同じ部分項を何度も書き写すことから来る。項を木ではなく、共通の部分項を共有する有向非巡回グラフとして表せば $t_n$ は $n+1$ 個の節点で表せる。この表し方を使うと、単一化可能かどうかの判定と最汎単一化子の(共有表現での)計算は、問題の大きさについて線形時間でできる(Paterson と Wegman、1978。BS01 §2.3, p. 462)。
関数記号に満たすべき等式があるとき、文字どおりの一致ではなく、その等式から導ける等しさ $=_E$ で両辺をそろえる問題を考える。$\theta$ が $P$ の $E$-単一化子であるとは、すべての等式で $s_i\theta=_E t_i\theta$ となることで、$\sigma\preceq_E\theta$ を「ある $\lambda$ で、$P$ のすべての変数 $x$ について $x\theta=_E x\sigma\lambda$」で定める。理論が空のときがこれまでの単一化である。この拡張では最汎単一化子が存在するとは限らない。
2 引数の記号 $f$ が可換、すなわち $E=\{f(u,v)=f(v,u)\}$ とし、$a,b$ を異なる定数とする。問題 $P=\{f(x,y)\overset{?}{=}f(a,b)\}$ は $E$-単一化子 $\theta_1=\{x\mapsto a,y\mapsto b\}$ と $\theta_2=\{x\mapsto b,y\mapsto a\}$ をもつ。
$P$ の $E$-単一化子 $\sigma$ で $\sigma\preceq_E\theta_1$ かつ $\sigma\preceq_E\theta_2$ となるものはない。$=_E$ は項の中の $f$ の引数を入れ替える操作をくり返して移りあう関係であり、この操作は根の記号と、根が $f$ のときの 2 つの引数の組(順序を問わない)を保つ。$f(x\sigma,y\sigma)=_E f(a,b)$ だから $\{x\sigma,y\sigma\}$ は $\{a,b\}$ と $=_E$ で対応し、定数の $=_E$ による類は定数自身だけなので $x\sigma\in\{a,b\}$ である。$x\sigma$ は変数を含まないので、どの $\lambda$ でも $x\sigma\lambda=x\sigma$ である。よって $\sigma\preceq_E\theta_i$ なら $x\theta_i=_E x\sigma$ すなわち $x\theta_i=x\sigma$ で、$i=1,2$ の両方では $a=b$ となり矛盾する。
一方、$P$ のどの $E$-単一化子 $\theta$ も $\theta_1$ か $\theta_2$ の具体化である。実際、上と同じ理由で $(x\theta,y\theta)$ は $(a,b)$ か $(b,a)$ なので、$\lambda=\theta$ とおけば $x\theta_i\lambda=x\theta$、$y\theta_i\lambda=y\theta$ となる $i$ がある。このように等式理論のもとでは、一つの最汎単一化子のかわりに、すべての単一化子をその具体化として含む単一化子の集まり(完全な集まり)を考える。極小の完全な集まりが 1 元か、有限か、無限か、存在しないかで、問題や理論の「単一化の型」が分かれ、可換性の型は有限、結合性の型は無限である(BS01 Definition 3.4、Examples 3.5–3.7, p. 465)。
この例は、thm-unif-main の「単一化可能なら最汎単一化子がある」が、記号に意味をもたせない一階の項に固有の性質であることを示している。
日本語の「単一化」はこの記事の意味(unification)で使う。次の概念は名前が似ているが別物である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する