Пример алгоритма объединения в WAM (абстрактная машина Уоррена)

Question

Упражнение 2.2 в абстрактной машине Уоррена: реконструкция учебника

запрашивает представления для терминов f(X, g(X, a)) и f(b, Y), а затем выполняет объединение по адресу этих терминов (обозначается как a1 и a2 соответственно).

Я построил кучные представления для терминов, и они следующие:

f(X, g(X, a)):
0   STR     1
1           a/0
2   STR     3
3           g/2
4   REF     4
5   STR     1
6   STR     7
7           f/2
8   REF     4
9   STR     3

f(b, Y):
10  STR     11
11          b/0
12  STR     7
13  STR     11
14  REF     14

и теперь меня просят отследить унификацию (a1, a2), но, следуя алгоритму на странице 20 в 1, я получаю:

d1 = deref(a1) = deref(10) = 10
d2 = deref(a2) = deref(0) = 0

0 != 10 so we continue

<t1, v1> = STORE(d1) = STORE(10) = <STR, 11>
<t2, v2> = STORE(d2) = STORE(0) = <STR, 1>

t1 != REF and t2 != REF so we continue

f1 / n1 = STORE(v1) = STORE(11) = b / 0
f2 / n2 = STORE(v2) = STORE(1) = a / 0

and now b != a so the algorithm terminated with fail = true,
and thus unification failed, but obviously there exists
a solution with X = b and Y = g(b, a).

Где моя ошибка?

Answer 1

Я нашел решение сам. Вот мои исправления:

Каждый термин должен иметь свои собственные определения функторов (т. Е. F-функтор во втором члене должен не просто ссылаться на первый f-функтор в первом члене, но должен иметь свои собственные) и указатели на термины (a1 и а2) должен указывать на внешний термин функтор.

Это означает, что a1 = 6 и a2 = 12 в следующем макете

f(X, g(X, a)):
0   STR     1
1           a/0
2   STR     3
3           g/2
4   REF     4
5   STR     1
6   STR     7
7           f/2
8   REF     4
9   STR     3

f(b, Y):
10  STR     11
11          b/0
12  STR     13
13          f/2
14  REF     11
15  REF     15