Prolog Рекурсия и завершение

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 не является ошибкой). Мой вопрос: почему? Из ограниченных примеров рекурсии, которые я нашел в Интернете, третья версия моего предиката должна прервать предикат и сделать х определенным ответом.

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

Answer 1

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

Я думаю, мой вопрос, почему мои другие предикаты «знать», они имеют правильный ответ, в то время как это и еще один не?

Ответ на вопрос о наличии точек выбора в стеке. Рассмотрим такую ​​ситуацию:

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

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

Compare, что к этому:

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

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

Если вы получаете посторонние точки выбора, это часто указывает на логическую ошибку.Например, рассмотрим это определение 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. 
?- 

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

Answer 2

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