Альтернативы WAM
Я помню, как однажды прочитал, что по крайней мере две другие альтернативы были изобретены примерно одновременно с WAM. Есть указатели?
3 ответа
До WAM был ZIP от Clocksin. Его дизайн все еще очень интересен. SWI-Пролог использует это. А также B-Prolog медленно перешел от дизайна WAM к ZIP. Конечно, на этом пути было разработано много новых инноваций. Другой альтернативой является VAM.
Сравнение по состоянию на 1993 год:
http://www.complang.tuwien.ac.at/ulrich/papers/PDF/binwam-nov93.pdf
Между тем, самые интересные архитектурные разработки связаны с B-Prolog.
WAM против ZIP
Ключевым отличием между WAM и ZIP является точный интерфейс для аргументов предиката. В WAM все аргументы передаются через регистры, то есть либо реальные регистры, либо, по крайней мере, фиксированные места в памяти. ZIP передает все аргументы через стек.
Давайте рассмотрим минимальный пример:
p(R1,R2,R3,L1,L2,L3) :- % WAM % ZIP
% store L1...L3 % nothing
% nothing % push R1..R3
% init X1..X3 % push X1..X3
q(R1,R2,R3,X1,X2,X3),
% put unsafe X1..X3 % push X1..X3
% load L1..L3 % push L1..L3
r(X1,X2,X3,L1,L2,L3).
До звонка q:
WAM не нужно предпринимать никаких действий для аргументов, которые передаются первой цели в тех же позициях (R1..R3). Это особенно интересно для бинарных предложений, то есть предложений с ровно одной обычной целью в конце. Здесь WAM превосходит.
Другие аргументы L1..L3 должны храниться локально. Поэтому для этих аргументов интерфейс регистра не принес ничего хорошего.
С другой стороны, в ZIP не нужно сохранять аргументы - они уже сохранены в стеке. Это хорошо не только для предложений с более чем одной целью, но также и для других прерывающих целей, таких как ограничения или прерывания.
Как недостаток, ZIP должен нажать еще раз R1..R3,
Оба должны инициализировать X1..X3 и хранить их в стеке.
призвание q:
При звонке qWAM должен выделить пространство стека для X1..X3 а также L1..L3 таким образом 6 ячеек, тогда как ZIP нуждается R1..R3,L1..L3,X1..X3, Так что здесь, WAM более экономно. Кроме того, WAM позволяет обрезать среду (для более сложных ситуаций), что практически невозможно для ZIP.
До звонка r:
это r является последним вызовом, и системы пытаются освободить место для этого предложения при условии, что отсутствует точка выбора.
Для WAM, экзистенциальные переменные X1..X3 должны быть проверены на то, что локальные переменные по-прежнему не определеныput_unsafe), и если они перемещаются в кучу - это дорого, но встречается редко. L1..L3 только что загружены. Вот и все, теперь WAM может безопасно освободить локальный фрейм. Так что оптимизация последнего звонка очень дешевая.
Для ZIP все должно быть как обычно. Только тогда дополнительное сканирование должно проверить все значения в стеке и соответственно переместить их. Это довольно дорого. Возможна некоторая оптимизация, но все же гораздо больше, чем то, что делает WAM. ((Возможным улучшением было бы выдвигать аргументы в обратном порядке. Тогда переменные L1..L3 может быть оставлен на их месте. Таким образом, эти переменные не нуждаются в какой-либо обработке. Я не видел такой реализации (пока).))
В технической заметке, озаглавленной "Набор абстрактных инструкций Prolog", Уоррен также ссылается на другой компилятор, созданный Боуэном, Бердом и Клоксином. Однако он говорит, что две архитектуры имеют много общего, поэтому я не знаю, можно ли считать этот компилятор альтернативой.
Не уверен, что это то, что вы имеете в виду, но первые две реализации Пролога были интерпретатором, написанным на Фортране Colmerauer et al. и собственный компилятор DEC PDP-10 от Warren et al.
Уоррен упоминает об этом в своем предисловии к учебному пособию Айт-Качи по реконструкции WAM. Если это не то, что вы имеете в виду, вы можете найти его в этом документе или в его ссылках.