Будет ли использование member в предложении forall в SWI-Prolog всегда выводить элементы в одном и том же порядке?

Question

Недавно попав в Пролог, я использовал его для нескольких простых задач и начал задаваться вопросом об использовании member внутри циклов forall, как в приведенном ниже тривиальном примере:

forall(member(A,[1,2,3,4]), print(A)).

В случае, если вы делаете что-то подобное, всегда ли верно, что forall будет обрабатывать элементы в списке в том же порядке каждый раз, когда он вызывается? Должен ли он быть принудительным, например, делать что-то вроде:

A = [1,2,3,4], sort(A, B), forall(member(C,B), print(C)).

Из того небольшого исследования, которое я первоначально провел, я предполагаю, что это сводится к поведению member/2, но документация для функции на веб-сайте SWI-Prolog очень краткая. Однако в нем упоминается детерминизм в отношении member/2, что дало мне понять, что я могу быть на верном пути, говоря, что он всегда извлекает элементы в одном и том же порядке, хотя я далеко не уверен.

Кто-нибудь может дать мне какие-либо гарантии или объяснения по этому поводу?

Answer 1

Недетерминизм в Прологе просто относится к предикату, имеющему потенциально более одного решения. Очевидно, что member/2 такой предикат. Это не означает, что вам нужно беспокоиться о том, что ваши вычисления станут непредсказуемыми. У Пролога есть четко определенное правило вычислений, которое, по сути, говорит о том, что альтернативные решения исследуются в порядке глубины, слева направо. Таким образом, ваша цель member(X,[1,2,3,4]) будет генерировать решения для X в ожидаемом порядке 1,2,3,4.

Сортировка списка [1,2,3,4] не будет иметь никакого значения, так как он уже отсортирован (в соответствии со стандартным порядком терминов Пролога).

Слово предостережения о forall/2Некоторые прологи определяют это, но это, вероятно, менее полезно, чем вы думаете, потому что на самом деле это не "петля". Вы можете использовать его в своем примере, потому что вы выполняете только побочный эффект печати в каждой итерации. Для большинства других целей вы должны ознакомиться с рекурсивными шаблонами, такими как

print_list([]).
print_list([X|Xs]) :- print(X), print_list(Xs).

Answer 2

В N208 определено forall/2 + (call(Generator), + call(Test)), поэтому это делает его менее сомнительным. Но в силу того, что основной стандарт ISO (+)/1 уже выполняет вызов / 1 и что основной стандарт ISO (,)/2 будет подвергаться преобразованию тела, его можно просто определить следующим образом в основном стандарте ISO Пролог:

forall (Генератор, Тест):-
\ + (Генератор, \+ Тест).

SWI-Prolog также реализовал этот способ, и ошибка, наблюдаемая Ульрихом Ноймеркелем, не будет видна при использовании forall/2:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.18)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- \+ ( C= !, \+ (C,fail;writeq(nonconforming))).
nonconforming
true.

?- forall(C=!, (C,fail;writeq(nonconforming))).
false.

Примечание:

Я не знаю, насколько это полезно для цикла. Мне кажется, что использовать его для циклов - неправильный подход, поскольку тест может провалиться, и тогда конструкция также не будет выполнена. Стригниц и Блэкберн также видели следующее определение предиката-помощника, который они называют циклом, управляемым отказом.

Доал (Гол):-
Цель, провал.
сделай все(_).

Я непосредственно пишу Goal, fail; true который также делает работу:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.18)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- member(A,[1,2,3,4]), write(A), nl, fail; true.
1
2
3
4
true.

Answer 3

Строго говоря, в SWI нет гарантии на нескольких уровнях:

1 месяц, это member/2 или же forall/2 будет работать именно так, так как вы можете переопределить их.

?- [user].
member(X,X).
|: % user://1 compiled 0.00 sec, 2 clauses
true.

?- forall(member(A,[1,2,3,4]), print(A)).
[1,2,3,4]
true.

Тем не мение, member/2 определяется в прологе Пролог, который охватывает все детали, которые вас интересуют. Что касается forall(A,B) писать безопаснее \+ (A, \+B) вместо этого, поскольку это зависит только от стандартных функций. Там нет определения forall/2 поэтому трудно сказать, что такое "правильное" поведение.

2до этого SWI будет соответствовать стандарту. Если вы прочитаете документацию, вы заметите, что не существует самопровозглашения (например, SICStus Prolog) для соответствия стандартам. По факту, \+ (A, \+B) не полностью соответствует, как в следующем примере, который должен молча потерпеть неудачу, а печатает nonconforming

?-  \+ ( C= !, \+ (C,fail;writeq(nonconforming))).