Пролог - какая логика стоит за этим

Question

Я пытался понять, как работает этот код, но мне не удалось. Он объединяет два списка, а затем полностью изменяет результат.

reverse(L, RL):- reverse(L, [], RL).
reverse([], RL, RL).
reverse([H|T], S, RL):- reverse(T, [H|S], RL).


concat([], L, L).
concat([H|T1], L2, [H|T]):- concat(T1, L2, T).


concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L)

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

вот пример

5 ?- trace,concat_reverse([1,3],[4,5],S).
   Call: (7) concat_reverse([1, 3], [4, 5], _G1444) ? creep
   Call: (8) concat([1, 3], [4, 5], _G1569) ? creep
   Call: (9) concat([3], [4, 5], _G1564) ? creep
   Call: (10) concat([], [4, 5], _G1567) ? creep
   Exit: (10) concat([], [4, 5], [4, 5]) ? creep
   Exit: (9) concat([3], [4, 5], [3, 4, 5]) ? creep
   Exit: (8) concat([1, 3], [4, 5], [1, 3, 4, 5]) ? creep
   Call: (8) reverse([1, 3, 4, 5], _G1444) ? creep
   Call: (9) reverse([1, 3, 4, 5], [], _G1444) ? creep
   Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep
   Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep
   Call: (12) reverse([5], [4, 3, 1], _G1444) ? creep
   Call: (13) reverse([], [5, 4, 3, 1], _G1444) ? creep
   Exit: (13) reverse([], [5, 4, 3, 1], [5, 4, 3, 1]) ? creep
   Exit: (12) reverse([5], [4, 3, 1], [5, 4, 3, 1]) ? creep
   Exit: (11) reverse([4, 5], [3, 1], [5, 4, 3, 1]) ? creep
   Exit: (10) reverse([3, 4, 5], [1], [5, 4, 3, 1]) ? creep
   Exit: (9) reverse([1, 3, 4, 5], [], [5, 4, 3, 1]) ? creep
   Exit: (8) reverse([1, 3, 4, 5], [5, 4, 3, 1]) ? creep
   Exit: (7) concat_reverse([1, 3], [4, 5], [5, 4, 3, 1]) ? creep
S = [5, 4, 3, 1].

Answer 1

Отказ от ответственности: я не знаю вашего учителя, поэтому, возможно, вам придется по-другому это сказать ...

Скажите, что у вас было много трудностей, и спросите, почему код не читается:

concat_reverse(L1,L2,L):-reverse(L2,R,L),reverse(L1,[],R).

А потом:

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

iseq([]) -->
   [].
iseq([E|Es]) -->
   iseq(Es),
   [E].

concat_reverse2(L1,L2,L) :-
   phrase( ( iseq(L2), iseq(L1) ), L).

В общем, я бы не советовал использовать отладчик для понимания предиката.

Answer 2

Давайте посмотрим на это понемногу.

Вы использовали:

concat_reverse([1,3],[4,5],S).

Пролог пытается объединить это.

concat_reverse(L1,L2,L)

Матчи.L1 объединяется с [1,3] и L2 объединяется с [4,5].Итак, мы смотрим на правую сторону:

concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L)

Пролог сначала ищет объединение на глубину, поэтому он проверяет concat(L1,L2,LN), снова с объединенными L1 и L2.

Давайте посмотрим на два concat вместе:

concat([], L, L).
concat([H|T1], L2, [H|T]):- concat(T1, L2, T).

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

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

На следующем уровне мы сопоставляем то же самоесостояние.Мы делаем это снова, и мы достигаем состояния остановки.Нашим ничем не важным является второй список.Таким образом, мы пытаемся вылезти обратно из глубины первого поиска через объединение.Мы добавляем заголовок первого списка совпадений над нами в дереве поиска.Это объединяет.Мы снова поднимаемся.Мы готовим следующий уровень вверх.Это объединяет.Что вы знаете, мы смогли объединить термин concat первого concat_reverse матча.

Теперь мы рассмотрим reverse часть матча concat_reverse.Это Exit(8)/Call(8) в вашей трассировке стека.Мы снова идем вниз, выполняя поиск в глубину с помощью следующих команд:

reverse(L, RL):- reverse(L, [], RL).
reverse([], RL, RL).
reverse([H|T], S, RL):- reverse(T, [H|S], RL).

Ну, есть только одно совпадение, одно с двумя терминами.Но теперь мы ищем оба трехчленных варианта для reverse.Наш список не пуст, поэтому мы не совпадаем с первым (опять же, это будет нашим условием остановки).Мы можем сопоставить второй.

Я собираюсь остановиться, потому что продолжение этого не добавит ничего нового.По сути, работа интерпретатора пролога заключается в поиске соответствия, унификации и глубины поиска.

Надеюсь, у вас будет или уже был урок о том, почему пролог выполняет поиск в глубину и почему это означает, что он не может быть завершен с опровержением (и что вы можете сделать как программист, чтобы предотвратить поиск в бесконечной глубине),

Обычно, когда вы пишете код пролога, вы пишете его как индуктивное доказательство или рекурсивную функцию.Начните с вашего условия остановки, затем обработайте общий случай с точки зрения условия остановки.Определите вещи с точки зрения композиции, например, concat_reverse.

Я думаю, вы должны взглянуть на более простой пример, чтобы немного лучше понять объединение.В этом примере есть ненужные сложности (хотя эти сложности всегда помогут вам, когда придет время написать собственный пролог-код для домашней работы).Попробуйте посмотреть на reverse в изоляции, без concat и concat_reverse.

Answer 3

concat_reverse(L1,L2,L) :-
        concat_reverse(L1,L2,[],L).

concat_reverse([],[],L,L).
concat_reverse([],[B|R2],L3,L) :-
        concat_reverse([],R2,[B|L3],L).
concat_reverse([A|R1],L2,L3,L) :-
        concat_reverse(R1,L2,[A|L3],L).

Answer 4

При чтении (или написании) Пролога мне нравится рассказывать небольшую историю.

Например, при чтении concat_reverse я объясняю это так: «L является concat_reverse для L1 и L2, если, во-первых, LN является объединением L1 и L2, а во-вторых, L является обратным LN».

Когда я читаю concat, я говорю: «Объединение [] и L является L.» «Конкатенация [H | T1] и L2 равна [H | T], если конкатенация T1 и L2 равна T».

По сути, объяснение должно как-то упростить выражение. Если бы я написал «concat», я бы подумал: «Что такое тривиальная истина о concat? Конкатенация любого списка в пустой список - это оригинальный список. Как насчет общего случая [H | T]? Конкатенация L к этому M, если глава M - это H, а остальная часть M - это конкатенация T в L. Другими словами, concat ([H | T], L) - это M, если M - [H | RM], и concat (T, L) является RM. "

Что касается обратного, история немного сложнее, потому что нет простого высказывания "RL - это обратное L, если ...". Но мы все еще можем придумать историю. Например, мы можем сказать: «S - это суффикс обратного к L (называемый RL), если соответствующий суффикс L обращен, а затем S присоединяется к результату».

Таким образом, для пустого суффикса мы имеем реверс ([], RL, RL) - RL является суффиксом RL, если пустой суффикс L обращен и RL присоединен к нему.

В общем случае, если суффикс L равен [H | T], тогда суффикс RL равен S, только если [H | S] также является суффиксом RL.

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

concat_of_reversed_suffix_and_S([H|T], S, RL) :- concat_of_reversed_suffix_and_S(T, [H|S], RL).

Это немного яснее - обратное значение [H | T] является обратным к T, за которым следует H. Если [H | T] - суффикс L, а S - суффикс или RL, то обратное значение T сопровождаемый H, сопровождаемый S, является точно RL. Мы произносим это длинное предложение следующим образом:

reverse([H|T], S, RL) :- reverse(T, [H|S], RL).

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

В этом случае вы можете увидеть:

   Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep
   Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep

[3,4,5] - суффикс L, [1] - суффикс RL. Это верно только в том случае, если [3,1] также является суффиксом RL, оставляя [4,5] в качестве (меньшего) суффикса L для рассмотрения.