Имена переменных Пролога

Question

например ..

insert(X,Ys,[X|Ys]).
insert(X,[Y|Ys],[Y|Zs]) :- insert(X,Ys,Zs)

почему использование Zs в качестве переменной .. базовый случай, очевидно, прост .. глава X :: YS.но рекурсивное утверждение будет продолжением первой цели.

поэтому для вставки (a, [b, c], L) вы получаете L = [a, b, c] во второй раз, когда вы получаете [b, a, c] в третий раз, когда получаете [b,c, a]

но каково фактически техническое определение Zs в программе?

[trace] 1 ?- insert(a,[b,c],L).
   Call: (6) insert(a, [b, c], _G522) ? creep
   Exit: (6) insert(a, [b, c], [a, b, c]) ? creep
L = [a, b, c] ;
   Redo: (6) insert(a, [b, c], _G522) ? creep
   Call: (7) insert(a, [c], _G595) ? creep
   Exit: (7) insert(a, [c], [a, c]) ? creep
   Exit: (6) insert(a, [b, c], [b, a, c]) ? creep
L = [b, a, c] ;

Начинается ли продолжение с рекурсивного вызова?Это означает, что первая цель закончилась в базовом сценарии ... поэтому мы начнем в следующий раз @ рекурсивно?Также я вижу начало использования различных переменных местоположений для L (он же _G522 против _G595).

Answer 1

Zs является результатом вставки X в Ys.

В Prolog вы обычно не говорите о продолжениях, а о точках выбора .Когда insert(a,[b,c],L) вернул свой первый результат, и вы начали возвращаться назад, компилятор Prolog возвращается в цепочку вызовов, чтобы найти последнюю точку выбора:

• последней операцией было выполнение insert 'В первом предложении, которое было детерминированным и связанным L;
• до этого, последней операцией был выбор между обоими предложениями, что было точкой выбора.

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

Answer 2

В Прологе нет никаких продолжений, но есть встроенный возврат.

Если честно, мне потребовалось некоторое время, чтобы понять программу.

Дело в том, что Prolog в значительной степени полагается на сопоставление с образцом, и точки выбора вставляются, когда существует более одного сопоставляемого образца. Если вы хотите детерминированную программу (то есть без точек выбора), вы должны убедиться, что за один раз совпадает только один шаблон (это рекомендуемый способ), или что нежелательный путь выполнения где-нибудь потерпит неудачу (это означает, что вы отбрасываете все вычисления, сделанные в дорожка). Самый простой способ обеспечить одну точку выбора - использовать оператор вырезания (! / 0).

«Каково фактически техническое определение Zs в программе?»

В Прологе вам не нужно объявлять переменные, их можно вводить где угодно, и где они связаны (получают фактическое значение, которое неизменно), иногда трудно понять. Без первого предиката всегда была бы несвязанная переменная во втором списке, но эта переменная связывается при объединении с [X | YS] в первом предикате после рекурсивного вызова. Так как первый предикат не содержит тела, программа завершается и предлагает решение для пользователя. Как вы видите, ваша программа не может заканчиваться вторым предикатом, только первым, но это не удивительно для рекурсивной функции, просто подумайте о классическом факториальном примере.

factorial(0,1). 

factorial(N,F) :-  
   N>0, 
   N1 is N-1, 
   factorial(N1,F1), 
   F is N * F1.