Пролог - бесконечный цикл

В такой ситуации, как ваша, у вас есть два выхода. Либо пробирайтесь сквозь стены текста следов, как вы можете видеть в другом ответе, либо попытайтесь сначала сократить то, что вам нужно понять. Я предпочитаю последнее, потому что не люблю много читать.

Но ваша главная проблема вот в чем. Ты сказал:

И когда я называю is_middle(1,[2,1,3]), я получаю истину.

Да, Пролог нашел решение, но не один раз, а бесконечно много раз. Просто нажмите ПРОБЕЛ или ;, чтобы увидеть это:

?- is_middle(1,[2,1,3]).
true ;
true ;
true ;
true ;
true ;
true ...

Итак, уже ваш первый запрос был проблематичным. Лучший способ это увидеть — добавить false в этот запрос:

?- is_middle(1,[2,1,3]), false.
** LOOPS **

Теперь попробуем уменьшить размер запроса. Мы можем сузить его до:

?- is_middle(1,[1]), false.
** LOOPS **

Теперь мы можем посмотреть на вашу программу. Прежде всего, я удалю порез. В любом случае это неуместно.

Чтобы понять, что на самом деле происходит, я сужу вашу программу, вставив в нее false. С помощью этих дополнительных целей можно исключить множество ненужных деталей. И все же оставшаяся программа вызвала failure-slice. важен для нас, если он все еще зацикливается.

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- false,
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]) :- false.
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X), false.

is_middle(X, In) :-
    middle(In, Out), false,
    member(X, Out).

Сравните это с вашей исходной программой! Гораздо меньше читать. Чтобы решить проблему, вы должны исправить что-то в оставшемся фрагменте. Предлагаю удалить факт remove_first_and_last([X],[X]). Этот факт говорит о том, что что-то удалено, но для этого самого случая ничего не удалено.

Для решения, напрямую использующего dcg:

is_middle(E, Es) :-
   phrase(middle(E), Es).

middle(E) --> [E].
middle(E) --> [_], middle(E), [_].

Это настолько коротко, насколько это возможно, но у него есть крошечная проблема: он не вычисляет ответ однозначно. Вы можете убедиться в этом, посмотрев ответ:

?- is_middle(1, [2,1,3]).
true ;
false.

Это ; false указывает на то, что Пролог не смог окончательно завершить вычисление. Другими словами, остается некоторое пространство. У вас может возникнуть соблазн использовать разрез. Сопротивляться!

Если вам действительно нравится скорость, берите самую быструю версию:

is_middle(X, Xs) :-
   Xs = [_|Cs],
   middle_el(Cs, Xs, X).

middle_el([], [X|_], X).
middle_el([_,_|Cs], [_|Xs], X) :-
   middle_el(Cs, Xs, X).

Если вам нужна интерпретация @DanielLyons, которая допускает, что списки четной длины имеют два средних элемента, посмотрите, как легко принять приведенное выше определение грамматики. Просто добавьте следующие два правила:

middle(E) --> [E,_].
middle(E) --> [_,E].

Как вариант, объедините все четыре правила в одно:

middle(E) --> [E] | [E,_] | [_,E] | [_], middle(E), [_].

Для самого быстрого решения все немного сложнее...

is_middle_dl(X, Xs) :-
   Xs = [_|Cs],
   middle_el_dl(Cs, Xs, X).

middle_el_dl([], [X|_], X).
middle_el_dl([_|Cs], Xs, X) :-
   middle_el_dl2(Cs, Xs, X).

middle_el_dl2([], [A,B|_], X) :-
   ( X = A ; X = B ).
middle_el_dl2([_|Cs], [_|Xs], X) :-
   middle_el_dl(Cs, Xs, X).

Чтобы проверить это, я использую SICStus, так как он дает более читаемые имена переменным:

| ?- length(Xs, N), N mod 2 =:= 0, is_middle_dl(X, Xs).
Xs = [X,_A],
N = 2 ? ;
Xs = [_A,X],
N = 2 ? ;
Xs = [_A,X,_B,_C],
N = 4 ? ;
Xs = [_A,_B,X,_C],
N = 4 ? ;
Xs = [_A,_B,X,_C,_D,_E],
N = 6 ? ;
Xs = [_A,_B,_C,X,_D,_E],
N = 6 ? ;
Xs = [_A,_B,_C,X,_D,_E,_F,_G],
N = 8 ? ;
Xs = [_A,_B,_C,_D,X,_E,_F,_G],
N = 8 ? ;
Xs = [_A,_B,_C,_D,X,_E,_F,_G,_H,_I],
N = 10 ? ;
Xs = [_A,_B,_C,_D,_E,X,_F,_G,_H,_I],
N = 10 ? ...

Отладка Пролога требует некоторых навыков, так что давайте пройдем долгий путь.

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

Стандартным инструментом для отладки Prolog является trace/0. Идея состоит в том, что вы активируете режим трассировки, а затем запускаете свой запрос, например:

?- trace,  is_middle(1,[2,2,3]).

Проблема с trace/0 в том, что может потребоваться некоторое усилие, чтобы понять, что с ним происходит. Каждая строка начинается с одного из этих четырех глаголов: call, exit, redo или fail. Затем идет число, указывающее уровень вложенности вызова. Глаголы call и redo сообщают вам, что вы вводите вычисление; exit и fail говорят вам, что вычисления прекращаются и уровень вложенности вот-вот уменьшится. Вызов/выход - это нормальный случай, неудача/повтор - это то, что делает Пролог особенным, недетерминированность. В общем, бесконечный цикл будет выглядеть как префикс значимой работы (или, возможно, нет), за которым следует бесконечно повторяющийся фрагмент вывода из trace. И мы видим это здесь. Приставка:

Call: (8) is_middle(1, [2, 2, 3]) ? creep
Call: (9) middle([2, 2, 3], _G1194) ? creep
Call: (10) remove_first_and_last([2, 2, 3], _G1194) ? creep
Call: (11) remove_first([2, 2, 3], _G1194) ? creep
Exit: (11) remove_first([2, 2, 3], [2, 3]) ? creep
Call: (11) remove_last([2, 3], _G1197) ? creep
Call: (12) remove_last([3], _G1190) ? creep
Exit: (12) remove_last([3], []) ? creep
Exit: (11) remove_last([2, 3], [2]) ? creep
Exit: (10) remove_first_and_last([2, 2, 3], [2]) ? creep

Повторяющийся фрагмент:

Call: (10) middle([2], _G1200) ? creep
Exit: (10) middle([2], [2]) ? creep
Exit: (9) middle([2, 2, 3], [2]) ? creep
Call: (9) member(1, [2]) ? creep
Call: (10) member(1, []) ? creep
Fail: (10) member(1, []) ? creep
Fail: (9) member(1, [2]) ? creep
Redo: (10) middle([2], _G1200) ? creep
Call: (11) remove_first_and_last([2], _G1200) ? creep
Exit: (11) remove_first_and_last([2], [2]) ? creep

Теперь вы можете видеть, что было бы намного проще вызвать плохое поведение только с помощью этого запроса:

[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Exit: (9) remove_first_and_last([3], [3]) ? creep
   Call: (9) middle([3], _G401) ? creep
   Exit: (9) middle([3], [3]) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (9) middle([3], _G401) ? creep

Теперь должно быть ясно, что проблема связана с взаимодействием middle/2, remove_first_and_last/2 и member/2. Ваше определение member/2 является в точности стандартным определением, так что, вероятно, оно не виновато. Теперь, что интересно, у вас есть middle/2, вызывающий и себя, и remove_first_and_last/2. И middle/2, и remove_first_and_last/2 имеют одинаковое предложение: m([X], [X]).

Такого рода вещи — отличный генератор бесконечной рекурсии, потому что первое, что middle/2 делает в своем предложении second, — это именно то, что он только что пытался сделать, но потерпел неудачу со своим собственным first. пункт. Таким образом, он может обнаружить, что выполняет рекурсивный вызов во втором предложении с точно таким же состоянием, в котором он находился при предыдущем неудачном вызове самого себя.

Решение состоит в том, чтобы посмотреть на remove_first_and_last/2 и понять, что ваше первое предложение там не на самом деле удаляет первый и последний элементы. Удаление предложения remove_first_and_last([X], [X]) исправляет код:

[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Call: (10) remove_first([3], _G398) ? creep
   Fail: (10) remove_first([3], _G398) ? creep
   Fail: (9) remove_first_and_last([3], _G398) ? creep
   Fail: (8) middle([3], _G398) ? creep
   Fail: (7) is_middle(2, [3]) ? creep
false.

Оба ваших теста также теперь работают:

?- is_middle(1,[2,1,3]).
true.

?- is_middle(1,[2,2,3]).
false.

Я думаю, вы добавили сюда базовый случай из чувства долга иметь его. Но реальность такова, что если у вас есть список из одного элемента, он не должен унифицироваться с remove_first_and_last/2 ни при каких обстоятельствах. Это очень похоже на явную обработку случая ошибки с помощью Пролога, что имеет тенденцию мешать работе механизма.

Теперь одна вещь, которой не хватает, это то, как вы хотите обрабатывать списки четной длины? То, что у вас есть сейчас, не будет, с моей сдачей или без нее. Списки четной длины не имеют среднего элемента; это то, что вы намереваетесь? Я подозреваю, что это не так, из-за появления member/2 в is_middle/2.

Комментарии к is_middle/2

То, что у вас есть, может быть реструктурировано так:

is_middle(X, In) :- middle(In, [X]).

Использование member/2 ничего вам не даст, потому что middle/2 никогда не сможет создать неодноэлементный список во втором аргументе. Но если бы это было так, поскольку у вас были бы списки четной длины, это было бы выгодно. Вы даже можете заставить этот код работать таким образом, добавив третье предложение в middle/2:

middle([X,Y], [X,Y]).

Теперь посмотрите, как middle/2 работает со списками четной длины следующим образом:

?- middle([2,1,3,4], X).
X = [1, 3] ;
false.

Однако теперь порез доставляет вам неприятности. Например, 1 и 3 равны is_middle/2:

?- is_middle(1, [2,1,3,4]).
true.

?- is_middle(3, [2,1,3,4]).
true.

К сожалению, если вы запросите средние элементы, у вас будет просто 1:

?- is_middle(X, [2,1,3,4]).
X = 1.

Что случилось с 3? Вы предотвратили его создание с помощью вашего разреза. Я не уверен, почему разрез здесь. Я думаю, вы, должно быть, вставили его, чтобы попытаться контролировать бесконечную рекурсию, но это вам не поможет, так что избавьтесь от него.

Отладка путем случайного добавления сокращений, как правило, не лучшая идея. Гораздо лучше использовать метод среза отказа Ульриха Ноймеркеля (см. .pdf" rel="noreferrer">этот документ или выполните поиск по тегу для получения дополнительной информации).

Бонус DCG

Вы можете перефразировать remove_first_and_last/2 как правило DCG:

remove_first_and_last --> remove_first, remove_last.

Довольно круто, да? :) Это потому, что тип потоков ввода-вывода, который вы выполняете в этом правиле, именно в то, во что преобразуются правила DCG.

Сводка изменений

remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle([X,Y], [X,Y]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).

is_middle(Item,List) :-
    append(Left,[Item|Right],List),
    length(Left,X),
    length(Right,X).

Сложные решения — плохие решения, мой друг.

?- is_middle(X,[1,2,3,4,5]).
X = 3 ;
false.

Полностью обратимый предикат:

?- is_middle(3,L).
L = [3] ;
L = [_G13, 3, _G19] ;
L = [_G13, _G19, 3, _G25, _G28] ;