2026-09-05
unify.c
#include <stdio.h>
typedef struct T { char tag; struct T *l, *r; } T;
static int unify(T *a, T *b) {
while (a->tag == 'v' && a->l) a = a->l;
while (b->tag == 'v' && b->l) b = b->l;
if (a == b) return 1;
if (a->tag == 'v') { a->l = b; return 1; }
if (b->tag == 'v') { b->l = a; return 1; }
if (a->tag != b->tag) return 0;
return a->tag != 'f' || (unify(a->l, b->l) && unify(a->r, b->r));
}
int main(void) {
T i = {.tag = 'i'}, b = {.tag = 'b'}, x = {.tag = 'v'};
T f = {'f', &x, &x}, g = {'f', &i, &b};
int ok = unify(&f, &g);
printf("%d %c\n", ok, x.l ? x.l->tag : '-');
}
これは何を出力するでしょうか?
Answer
0 i です。
unify(&f, &g) は x -> x と int -> bool を単一化します。どちらも関数型なので、最後の行で左辺どうし、右辺どうしを順に単一化します。左辺の unify(&x, &i) では x が未束縛の型変数なので、x を int に束縛して 1 を返します。
1 が返ったので && の右側、unify(&x, &b) も評価されます。先頭の while が x の束縛をたどるので、比べるのは x ではなく int と bool です。タグが違うので 0 が返り、ok は 0 になります。x はもう型変数として扱われないため、ここで bool に束縛し直されることもありません。
左辺で書き込んだ x.l = &i は、全体が失敗しても取り消されません。この unify は束縛を構造体へ直接書き込むだけで、失敗したときに元へ戻す仕組みを持たないからです。ok は 0 なのに x は int に決まったまま残り、x.l->tag は i です。型検査器が単一化を「合うかどうか試す」ために使うなら、失敗した試行の束縛が次の試行に持ち越されてしまいます1。
- Prolog の処理系は、単一化で書き換えた変数をトレイル(trail)と呼ぶスタックに記録しておき、失敗して後戻りするときにそこから束縛を外します。書き換える実装で試行を取り消したいなら、同じような記録が要ります。