Что такое дерево SLD для этого запроса?

Рассмотрим следующую программу Пролог (из "Искусство Пролога"):

natural_number(0).
natural_number(s(X)) :- natural_number(X).

plus(X, 0, X) :- natural_number(X).
plus(X, s(Y), s(Z)) :- plus(X, Y, Z).

и запрос:

?- plus(s(s(s(0))), s(0), Z).

И SICStus, и SWI производят ожидаемое Z = s(s(s(s(0)))) ответить, но запросить у пользователя следующий ответ (правильный no/false ответ). Однако я не могу понять, почему существует открытая ветвь в дереве SLD после того, как единственная цель найдена. Я пробовал отлаживать как под SICStus, так и под SWI, но пока не могу интерпретировать результат. Я могу только сказать, что, насколько я мог понять, оба возвращаются к plus(s(s(s(0))), 0, _Z2), Может ли кто-нибудь помочь мне понять это поведение?

Источник

3 ответа

Решение

Эта проблема не имеет прямого отношения к деревьям SLD, поскольку системы Prolog не создают деревья SLD заблаговременно, как вы их описали. Но некоторые оптимизации, найденные в некоторых системах Prolog, по сути, имеют этот эффект и изменяют соответствие головы слепой грубой силы. А именно индексация и устранение точек выбора.

В настоящее время известно ограничение SWI-Пролог. Хотя он выполняет индексацию с несколькими аргументами, он не выполняет исключение точек выбора для каскадной индексации не по первому аргументу. Означает, что он выбирает только один аргумент, но не дальше. Есть некоторые системы Prolog, которые выполняют многопараметрическую индексацию и каскадную индексацию. Например, в Jekejeke Prolog у нас нет No / false:

Пеано Каскад

до свидания

PS: новейшая версия Jekejeke Prolog даже не имеет буквального каскада, поскольку обнаруживает, что индекс первого аргумента не имеет чувствительности. Поэтому, хотя он создает индекс для первого аргумента из-за фактического шаблона вызова, он пропускает индекс первого аргумента и не использует его, а использует только второй аргумент. Пропуск дает немного скорости.:-)

Пропуск виден черезdump/1 команда версии среды разработки:

?- dump(plus/3).
-------- plus/3 ---------
length=2
arg=0
  =length=2
arg=1
  0=length=1
  s=length=1
Yes

Так что это не опустилось в arg=0 и построил arg=1индекс там, но вместо этого построен параллельно arg=0 и arg=1 индекс. Мы все еще можем называть это эвристическим каскадом, поскольку отдельные запросы приводят к нескольким индексам, но на самом деле они не имеют форму каскада.

Источник

Многие системы Prolog не так умны, как мы ожидаем. Это имеет несколько причин, в основном из-за компромиссного выбора исполнителя. То, что кажется важным для некоторых, может быть не так важно для других.

Как следствие, эти оставшиеся точки выбора могут накапливаться во времени и препятствовать освобождению вспомогательных данных. Например, когда вы хотите прочитать длинный список текста. Список настолько длинный, что он не помещается в память сразу, но все же может быть эффективно обработан с library(pio),

Если вы ожидаете ровно один ответ, вы можете использовать call_semidet/1 чтобы сделать это определенным. Посмотрите этот ответ для его определения и варианта использования.

? - плюс (s(s(s(0))), s(0), Z).
Z = s(s(s(s(0))));
ложный.
? - call_semidet (плюс (s(s(s(0))), s(0), Z)).
Z = s(s(s(s(0)))).

Но вы можете увидеть это и с более оптимистичной стороны: современные уровни (такие как в SWI) действительно показывают, когда есть оставшиеся точки выбора. Таким образом, вы можете рассмотреть некоторые контрмеры, такие как call_semidet/1,

Вот несколько связанных ответов:

Источник

Для нас очевидно, что два предложения для плюса являются "дизъюнктивными". Мы можем сказать это, потому что мы знаем, что 0 \= s(Y), Но (я думаю) такой анализ в целом является запретительным, и Пролог затем считает, что такая ветвь еще должна быть доказана: здесь трассировка, показывающая, что вызов (7) все еще "открыт" для альтернатив после того, как найдено первое решение.

Источник
Другие вопросы по тегам