Нужна помощь в понимании Prolog append / 3 и inverse / 2 и вывода трассировки

Изображения кода Пролога, которые вы опубликовали, показывают какой-то необычный или очень старый Пролог, в частности, для списка, использование [H:T] теперь выполняется как [H|T], обратите внимание на изменение с : на |, а <= более распространен как :-.

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

Первый предикат, который нужно понять, - это append / 3. Обычно вы никогда не видите данный код для добавления, поскольку это встроенный предикат, но здесь он указан.

В приложении / 3 есть три параметра, все из которых являются списком. Первые два складываются вместе, образуя третье.

?- append_01([],[],R).
R = [].

?- append_01([a],[],R).
R = [a].

?- append_01([],[a],R).
R = [a].

?- append_01([a],[b],R).
R = [a, b].

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

?- append(X,[b],[a,b]).
X = [a] ;
false.

?- append_01([a],Y,[a,b]).
Y = [b].

?- append(X,Y,[a,b]).
X = []    , Y = [a, b] ;
X = [a]   , Y = [b]    ;
X = [a, b], Y = []     ;
false.

или может использоваться просто для проверки аргументов

?- append([a],[b],[a,b]).
true.

?- append([a],[c],[a,b]).
false.

Далее идет предикат обратный / 2, который в Прологе более известен как обратный / 2, и здесь снова приводится исходный код.

Это просто берет один список и меняет его, например

?- inverse([],X).
X = [].

?- inverse([a],X).
X = [a].

?- inverse([a,b],X).
X = [b, a].

однако эта версия исходного кода не работает в других режимах, например.

?- inverse(X,[]).
X = [] ;

Action (h for help) ? abort
% Execution Aborted

но это не имеет значения, чтобы ответить на вопрос.

Следующая часть того, что вы опубликовали, - это след выполнения запроса.

?- inverse([[1,2,3],[5,4]],A).

Чтобы использовать трассировку в вашем коде, поскольку для append / 3 есть встроенный предикат, мне пришлось переименовать предикат. Вот код, который я использовал.

inverse([],[]).

inverse([H|T],D) :-
  inverse(T,Z),
  append_01(Z,[H],D).

append_01([],X,X).

append_01([X|L],M,[X|N]) :-
  append_01(L,M,N).

Использование SWI-Prolog

установить след

?- visible(+all),leash(-all). 

начать трассировку

trace.

выполнить запрос

[trace] ?- inverse([[1,2,3],[5,4]],A).

возвращается

   Call: (8) inverse([[1, 2, 3], [5, 4]], _7548)
   Unify: (8) inverse([[1, 2, 3], [5, 4]], _7548)
   Call: (9) inverse([[5, 4]], _7794)
   Unify: (9) inverse([[5, 4]], _7794)
   Call: (10) inverse([], _7794)
   Unify: (10) inverse([], [])
   Exit: (10) inverse([], [])
   Call: (10) append_01([], [[5, 4]], _7802)
   Unify: (10) append_01([], [[5, 4]], [[5, 4]])
   Exit: (10) append_01([], [[5, 4]], [[5, 4]])
   Exit: (9) inverse([[5, 4]], [[5, 4]])
   Call: (9) append_01([[5, 4]], [[1, 2, 3]], _7548)
   Unify: (9) append_01([[5, 4]], [[1, 2, 3]], [[5, 4]|_7792])
   Call: (10) append_01([], [[1, 2, 3]], _7792)
   Unify: (10) append_01([], [[1, 2, 3]], [[1, 2, 3]])
   Exit: (10) append_01([], [[1, 2, 3]], [[1, 2, 3]])
   Exit: (9) append_01([[5, 4]], [[1, 2, 3]], [[5, 4], [1, 2, 3]])
   Exit: (8) inverse([[1, 2, 3], [5, 4]], [[5, 4], [1, 2, 3]])
A = [[5, 4], [1, 2, 3]].

Я не буду объяснять детали трассировки, поскольку другие вопросы и ответы SO делают тот.

Опубликованная вами трассировка также содержит больше деталей, чем сгенерированная с помощью trace, например привязки (θ).

Чтобы увидеть привязки, используйте gtrace / 0

?- gtrace.
% The graphical front-end will be used for subsequent tracing
true.

затем выполните запрос

[trace]?- inverse([[1,2,3],[5,4]],A).

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

Из комментария OP:

There are some replacements from letters to numbers and theta symbol that make me hard to understand.

Хотя привязки (θ) более специфичны для логические языки, числа также видны в функциональные языки на основе стека, см. Индекс Де Брёйна. Кроме того, вместо того, чтобы писать привязки с использованием вертикального разделителя строк (---), я предпочитаю использовать (↦), как показано на рисунке здесь.

Строки 1-4 - это снова заявленный исходный код.

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

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

Как вы отметили в комментариях, Res(_,_) ссылается на предыдущие строки трассировки. Таким образом, Res (5,2) в строке 6 можно прочитать как строку 6, которая является результатом вызова из строки 5, который затем вызывает строку 2.

Унификации или привязки (θ) показаны как наборы. Я не совсем уверен, что обозначают номера суперсценария и субсценария, но они явно связаны с индексами Де Брёйна. Вам нужно будет попросить своего учителя объяснить супер- и вспомогательные сценарии.

После нескольких попыток объяснить это простым текстом, я наконец прибег к использованию Microsoft Visio, чтобы сделать это в виде графического дерева, что было намного проще, быстрее и точнее.

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

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