Пролог — бесконечный цикл с очень простым определением правила

Механизм выполнения Prolog довольно сложен по сравнению с командно-ориентированными языками программирования, также известными как императивные языки (краткая форма: imps). Ваш ТА дал вам отличный пример, где вы можете улучшить свое мастерство в Прологе.

Прежде всего, вам нужно понять поведение завершения append/3. Лучше всего использовать failure-slice, который поможет вам сосредоточиться на той части, которая имеет отношение к завершению. В данном случае это:

append([],B,B) :- false.
append([X|A],B,[X|C]):-append(A,B,C), false.

Этот фрагмент или фрагмент отказа теперь завершается точно во всех случаях, когда заканчивается ваше исходное определение! И поскольку он короче, это немного упрощает понимание терминации. Конечно, эта новая программа больше не будет находить ответы, как для append([a],[b],[a,b]), — вместо этого она потерпит неудачу. Но для терминации в одиночку это идеально.

Теперь давайте рассмотрим аргументы один за другим:

1. аргумент должен иметь непустой элемент списка и завершится ошибкой (и завершится), если аргумент будет [] или любым другим термином. Незавершение может происходить только с частичным списком (это список с переменной вместо [] в конце, например [a,b|L]) или только с переменной.

2. аргумент - это просто переменная B. Не может быть, чтобы этот B мог отличаться от любого другого термина. Таким образом, B вообще не влияет на завершение. Это нейтральное завершение.

3. аргумент по существу такой же, как и первый аргумент. На самом деле эти рассуждения выглядят довольно симметрично, хотя и описывают разные вещи.

Подводя итог, если первый или последний аргумент является (полностью созданным) списком, append/3 завершится.

^{Обратите внимание, что я сказал только если, а не тогда и только тогда. Ведь первый и третий аргумент немного связаны друг с другом через переменную X. Давайте проигнорируем это для данного анализа.}

Теперь перейдем к неудачному фрагменту вашего определения.

append3(A,B,C,D) :- append(A,B,X), false, append(X,C,D).

Обратите внимание, что D больше не встречается в видимой части! Поэтому четвертый аргумент не влияет на завершение этого фрагмента. А так как X происходит впервые, то только A влияет на его завершение. Следовательно, если A — это просто переменная (или неполный список), программа не завершится! Нет необходимости смотреть дальше. Не нужно смотреть на экраны, полные следов.

Чтобы исправить это для такого запроса, как ваш запрос append3(A,B,C,[1,2,3])., D должен несколько повлиять на первую цель.

Одним из возможных исправлений, предложенных другим ответом, будет обмен целями:

append3(A,B,C,D) :- append(X,C,D), false, append(A,B,X).

Давайте посмотрим на переменные append(X,C,D)! C является нейтральным завершением, X встречается впервые и, таким образом, вообще не влияет на завершение. Только D может отменить эту цель. Таким образом, запросы типа append3([1],[2],[3], D) теперь будут зацикливаться! Какая сделка, променять нерасторжение в одном деле на другое!

Чтобы ваша программа работала для обоих случаев, первая цель append/3 должна содержать как D, так и хотя бы одно из A, B или C. Попробуйте найти его сами! Вот спойлер:

append3(A, B, C, D) :- append(A, BC, D), append(B, C, BC).

Теперь первая цель завершается, если A или D является (полностью созданным) списком. Вторая цель требует, чтобы либо B, либо BC были списком. И BC исходит из первой цели, которая является списком, если D один.

Таким образом, append3(A, B, C, D) terminates_if b(A), b(B) ; (D).

См. другой ответ для получения дополнительной информации о завершении, срезах отказа и методе, который я здесь не упомянул, который является завершением вывод.

^{И обратите внимание, что есть еще случаи, когда определения заканчиваются, хотя они довольно неясны, например, append([a|_],_,[b|_]) или append3([a|_],_,_,[b|_])), которые оба терпят неудачу (и, следовательно, завершаются), хотя у них есть только частичные списки. Из-за этого это terminates_if, а не terminates_iff.}

Вам нужно перевернуть предикаты append(A, B, X), append(X, C, D). Поскольку все три переменные A, B и X не связаны в append(A, B, X), пролог пытается удовлетворить его, а затем ограничить его с помощью append(X, C, D), что всегда будет давать сбой после предоставления вам существующих решений. Таким образом, он входит в бесконечный цикл.

Попробуйте просто выполнить append(A, B, X). все из них без привязки. Пролог должен показать вам бесконечную последовательность решений, они терпят неудачу в следующем предложении append(X, C, D).

Переверните предикаты, и все будет в порядке.

append3(A, B, C, D) :-
    append(T, C, D),
    append(A, B, T).