Пролог Рекурсия и Завершение

Question

первый вопрос StackOverflow.

Я пишу предикат в прологе, который принимает три параметра. Это (соответственно) символ, список строк, а последний параметр - это список всех строк второго параметра, которые начинаются с первого параметра. Мои письменные заявления заменяют мое полное отсутствие знаний о том, как отследить в SWI-Prolog. Во всяком случае, на код!

---

startString(C, [H1|T1], [H2|T2]) :-
    atom_chars(H1, [C| _ ]),
    H2 = H1,
    startString(C, T1, T2).

startString(C, [ _ |T1], Y) :-
    startString(C, T1, Y),
    write(foo).

startString(_, [], []) :-
    write(foo).

---

Какие выходы:

---

foofoofoo

X = [some, simple]

---

Моя методология верна, но предикат не завершается (отсутствие периода после записи X не является ошибкой). У меня вопрос, а почему нет? Из ограниченных примеров рекурсии, которые я нашел в Интернете, третья версия моего предиката должна завершать предикат и давать x определенный ответ.

Когда я нажимаю ввод, я могу ввести другой запрос, но у меня та же небольшая «проблема» в другом предикате, который я написал в той же программе. Любая помощь с этим предикатом должна также переноситься на другого. Спасибо!

Answer 1

Чтобы расширить ваш вопрос в комментариях к @ ScottHunter,

Полагаю, мой вопрос в том, почему другие мои предикаты "Знают", что они имеют правильный ответ, а этот и еще один - нет?

Ответ связан с наличием точек выбора в стеке. Рассмотрим следующую ситуацию:

reasonably_big(L, X) :- member(X, L), X > 100.

?- reasonably_big([105, 2], X).
X = 105 ;
false.
?-

Сравните это с этим:

?- reasonably_big([2, 105], X).
X = 105.
?-

Во втором случае Пролог «знал», что решений больше нет; в первом случае это не так. Разница между этими двумя ситуациями заключается в том, что в первом случае member оставил точку выбора в стеке: в списке был еще один элемент, который он мог бы рассмотреть, чтобы найти другой ответ. Во втором случае остальная часть списка была пуста, и SWI-Prolog member достаточно умен, чтобы в этом случае не оставлять точку выбора в стеке, поэтому он никогда не спрашивал вас, хотите ли вы другое решение.

Если вы получаете лишние очки выбора, это часто указывает на логическую ошибку. Например, рассмотрим это определение min:

min(X, Y, X) :- X =< Y.
min(X, Y, Y).

Это неисправно, потому что вы всегда можете вернуться назад и получить другое значение; для остроумия:

?- min(3,4, X).
X = 3 ;
X = 4.

Второе решение там ошибочное. Но вы все равно можете получить ненужную точку выбора, сделав неправильное улучшение:

min(X, Y, X) :- X =< Y.
min(X, Y, Y) :- Y =< X.

Посмотрим, что произойдет, когда мы попробуем разные значения:

?- min(4,3,X).
X = 3.
?-

?- min(3,4,X).
X = 3 ;
false.
?-

Первый работал нормально, но второй оставил точку выбора в стеке, имея второе тело. Вы можете устранить это зеленым срезом:

min(X,Y,X) :- X =< Y, !.
min(X,Y,Y) :- Y =< X.

?- min(3,4,X).
X = 3.
?-

?- min(4,3,X).
X = 3.
?-

Срез связывает Пролог с конкретным решением. Он говорит, что, как только вы сделали это здесь, нет необходимости пробовать какие-либо другие решения для этого предиката, потому что мы нашли единственное, что нам нужно. Понимание того, как применять сокращение, является сложной темой, но устранение нежелательных точек выбора является важным использованием.

Answer 2

Вы должны быть осторожны с тем, что вы подразумеваете под словом «прекратить» в Прологе. Тот факт, что вы получили значение, привязанное к X, когда вы попросили пролог доказать startString ('s', some-list, X), означает, что оно завершено (иначе он все равно будет искать значение для X). Но в другом смысле это не так, потому что вы можете попросить (как правило, введя точку с запятой) Пролог, чтобы попытаться найти другое решение, и можете продолжать спрашивать, пока он не исчерпает возможности сделать это. Похоже, что ваша консоль ждет, когда вы скажете, хотите ли вы попытаться найти другое решение или вы сделали это (что происходит, когда вы нажимаете клавишу ввода, и интерпретатор позволяет вам вводить новый запрос).