Расширение DCG: Стойкость игнорируется?

Question

Предположим, у меня есть следующее правило DCG:

 factor(X) --> "(", expr(X), ")".

Обычно это будет переведено на:

 factor(X, A, B) :-
    [40|C] = A, expr(X, C, D), [41|B] = D.

Будет ли система Пролога переведена следующим образом, то есть
объединить объединения в голову и цель?

 factor(X, [40|A], B) :-
    expr(X, A, [41|B]). 

Если расширение DCG не будет устойчивым, оно не будет разрешено
поместить [41|B] в третий аргумент вызова expr.

Но я думаю, что стойкость на месте, так что все должно быть в порядке?

до свидания

PS: для неформального определения стойкости см.:
Ричард О'Киф, 2009:
"Как изобретатель термина" стойкий "в прологическом программировании,
Я должен быть за это. Стойкость в основном
означает, что вы не можете заставить предикат следовать по неверному пути
неправильно введя выходные аргументы. "
http://blog.gmane.org/gmane.comp.ai.prolog.swi/month=20090301

PSS: Для другого перевода DCG см., Например, самый новый
Стандартное предложение DCG. Приложение содержит переводчик DCG
исходный код:
ISO / IEC DTR 13211–3: 2006
Определенные правила грамматики
Клаус Десслер
20 ноября 2012 г.
N238 DIN Draft 2012-11-20

Answer 1

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

opcl --> "".
opcl --> "(", opcl, ")".

С флагом Пролог double_quotes установлен в chars второй пункт теперь может быть расширен до

opcl1(['('|S0],S) :-
   opcl1(S0,S1),
   S1 = [')'|S].

или же

opcl2(['('|S0],S) :-
   opcl2(S0,[')'|S]).

Теперь рассмотрим цель phrase(opcl,"(((())))",

На обычных машинах, таких как WAM (например, YAP, SICStus), ZIP (SWI), TOAM Jr. (B):

opcl1

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

? - фраза (opcl,"(((())))").
правда;
ложный.

Эта точка выбора может быть чисто и безопасно удалена с call_semidet/1,

opcl2

opcl2 создаст четыре экземпляра [')'|_] в куче, которые должны быть восстановлены GC. Но они сохраняют стек вызовов. То есть будут только хвостовые рекурсивные вызовы, которые очень эффективно обрабатываются в WAM, минимально менее эффективно в TOAM Jr. и относительно дороги в SWI.

Вещи становятся еще более дорогостоящими, когда мы рассматриваем выполнение с проверкой событий. В Qu-Prolog он всегда включен, а в SWI, XSB и CX вы можете включить его с помощью флага, например:

? - фраза (opcl,Xs,Xs).
правда;
Xs = ['(',')'|Xs];
Xs = ['(','(',')',')'|Xs] ...?- set_prolog_flag(происходит_проверка, правда).
правда.? - фраза (opcl,Xs,Xs).
правда;
** ПЕТЛИ **

SWI не нужно выполнять разовую проверку opcl1, Но это так для каждого ) в opcl2,

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

звоните //1

Ваш перевод изменит точную связь в пределах call//1, Тем не менее, цель в call//1 всегда должен быть написан таким образом, чтобы он был непоколебимым! В противном случае разницу можно было увидеть уже при звонке phrase(call(Cont),Xs0,Xs)! Для соответствия Cont это будет так же, как phrase(call(Cont),Xs0,XsC), XsC=Xs

---

Что касается вашей цитаты о стойкости: это очень неформальное определение понятия. В конце концов, что означает "неправильно"?

Лучшее определение устойчивости для phrase/3 до сих пор я знаю, это:

phrase(NT, Xs0,Xs) а также phrase(NT, Xs0, XsC), XsC = Xs с XsC свежая новая переменная, всегда одна и та же.