Как работает связывание в абстрактной машине Уоррена, если одним из аргументов является регистр?

Question

Я пытаюсь создать свою собственную реализацию WAM, и я застрял в упражнении 2.4.

Я не могу понять, как выполнить инструкцию unify_value X4 на рисунке 2.4.

Насколько я понимаю, эта инструкция должна объединять Y из программы с f(W) из запроса.

unify_value X4 звонки unify (X4,S) где S=2 (см. рисунок 2.1) и соответствующая ячейка кучи - "REF 2", а X4 - "STR 5".

Unify (Рисунок 2.7) следует bind эти ценности, но я не понимаю, как deref регистр.

"REF 2" находится в куче, "STR 5" находится в регистре. Как ты bind что-нибудь зарегистрировать?

Answer 1

Мы говорим о "новом" движке Уоррена, WAM, а не старом движке, известном как PLM.

В WAM переменные расположены в двух местах.

1. локальный стек (окружение стека)

2. куча

Регистры не могут содержать переменные. Однако они могут содержать ссылки на переменные. Обратите внимание, что ссылки из кучи указывают только на кучу.

Многое связано с вашим вопросом - довольно изобретательный способ, которым WAM поддерживает этот порядок и в то же время имеет очень дешевую оптимизацию последнего вызова. В момент (последнего) последнего вызова локальные переменные, которые являются аргументами последнего вызова, должны быть каким-либо образом перемещены. В более традиционных машинах Prolog, таких как ZIP, это чрезвычайно трудоемкое мероприятие, которое, по сути, требует сканирования кадра среды на предмет переменных, все еще находящихся в них.

WAM, однако, имеет гораздо лучшее соглашение о вызовах: большинство переменных уже находятся в безопасном месте, которое можно тривиально проанализировать во время компиляции. Лишь немногие из них нуждаются в явной инструкции PUT_UNSAFE, где проверяется значение, и если она все еще является локальной переменной, эта переменная передается в кучу.

Рассмотрим, что является безопасной переменной в WAM:

1. Все переменные, встречающиеся в голове

2. Все переменные, которые появляются в качестве аргумента структуры

Таким образом, только переменные, которые появляются первыми в цели и в последней цели и которые не появляются в некоторой структуре, должны иметь PUT_UNSAFE. Это не так уж много. Кроме того, динамическая проверка может сократить до минимума фактическое копирование в кучу.

Сначала это PUT_UNSAFE выглядит как большая работа, но никогда не забывайте, что WAM позволяет удалить много PUT, в то время как ZIP должен выполнить хотя бы одну инструкцию для каждого аргумента.

Вот небольшой пример использования GNU:

a --> b, c.

расширен до:

a(S0,S) :- b(S0,S1), c(S1,S).

и скомпилирован с помощью команды pl2wam чтобы:

предикат (а /2,1, статический, частный, monofile, глобальный,[
    выделяют (2),
    get_variable(y(0),1),                   % S
    put_variable(y(1),1),                   % S1
    вызов (б / 2),
    put_unsafe_value (y (1), 0),% S1
    put_value (y (0), 1),% S
    DEALLOCATE,
    выполнение (с /2)]).