Есть ли стандартный способ увидеть, какая фраза / 3 переводится?
Нет. Значение phrase/3
определено, но фактическая реализация недоступна. Существует несколько различных способов определения phrase/3
. Это может быть так же просто, как в YAP:
phrase(P, S0, S) :-
call(P, S0, S).
Или он может использовать expand_term/2
(или что-то в этом роде). То есть:
phrase(P, S0, S) :-
expand_term(( pseudont --> P ), ( pseudont(CS0, CS) :- Goal) )),
S0 = CS0,
S = CS,
Goal.
Он может выполнить окончательную унификацию после вызова Goal
:
phrase(P, S0, S) :-
expand_term(( pseudont --> P ), ( pseudont(CS0, CS) :- Goal) )),
S0 = CS0,
Goal,
S = CS.
И тем самым ввести (зависящее от реализации) соглашение о том, что расширенные предикаты всегда вызываются с неконкретизированной переменной без псевдонимов в последнем аргументе, что позволило бы реализовать хвостовую рекурсию при наличии полуконтекста.
Все зависит от исполнителя.
Говорит ли это мне, как фраза/3 используется в моем тесте/3?
Нет, это никак не сказать.
Но тогда почему ты спрашиваешь? Или, перефразируя:
Какой эффект может иметь другая, но соответствующая реализация phrase/3
?
Потребление ресурсов
Это должно быть очевидно. Рассмотрим ?- phrase([],Xs).
, который не создает терм в куче в YAP, но делает это для наивного expand_term
-расширения выше. Но тогда потребление ресурсов выходит за рамки текущих стандартов.
Порядок переменных
Рассмотрим тело правила ..., phrase([], Xs, Xs), ...
в YAP: Xs
остается локальной переменной, тогда как фраза на основе expand_term
делает ее глобальной. Во многих реализациях это повлияет на относительный порядок переменных. Теперь стандарт прямо указывает в 7.2.1:
If X and Y are variables which are not identical then
X term_precedes Y shall be implementation dependent
except that during the creation of a sorted list (7.1.6.5,
8.10.3.1 j) the ordering shall remain constant.
Так что это снова не проблема, но все же это может раздражать.
имущество НСТО
Стандарт Prolog (то есть часть 1 ISO/IEC 13211-1) определяет выполнение только в том случае, если это NSTO. То есть, если все унификации, происходящие во время выполнения, NSTO не подлежат проверке (см. 7.3.3).
Теперь рассмотрим ваш случай: phrase(("a",!,"b"), Xs, Ys)
. На первый взгляд это эквивалентно phrase("ab", Xs, Ys)
. Но теперь предположим, что set_prolog_flag(double_quotes,chars)
?- Xs = [c|_], Xs = Ys, phrase(("a",!,"b"), Xs, Ys).
Этот запрос должен потерпеть неудачу, без сомнения. Но это НСТО? Наивно можно предположить, что это можно заменить на:
?- Xs = [c|_], Xs = Ys, Xs = [a,b|Ys].
Что равносильно:
?- Xs = [c|_], Xs = [a,b|Xs].
Ясно, что только Xs = [a,b|Xs]
является STO (при условии проверки). Но также и то, и другое вместе - СД! Чтобы понять это, рассмотрим алгоритм Хербранда в 7.3.2. По сути, он недетерминистически переписывает уравнения «в любом порядке». Вот один из таких выводов:
Xs = [c|Zs], Xs = [a,b|Xs].
(7.3.2 f) Xs = [c|Zs], [c|Zs] = [a,b,c|Zs].
(7.3.2 d) Xs = [c|Zs], c = a, Zs = [b,c|Zs].
(7.3.2 g) failure (not unifiable, positive occurs-check)
Конечно, такой вывод необычен. Обычно при наличии c = a
сразу происходит сбой, но алгоритм в этом отношении недетерминирован. И система уравнений является НСТО только в том случае, если все возможные выводы не приводят к 7.3.2 г. Чтобы процитировать 7.3.3:
A set of equations (or two terms) is "not subject to
occurs-check" (NSTO) iff there exists no way to proceed
through the steps of the Herbrand Algorithm such that
7.3.2 g happens.
заморозить/2 и когда/2
Эти конструкции также могут быть затронуты. Хотя в настоящее время они не охватываются существующими стандартными документами, понимание потенциального воздействия по-прежнему актуально. Рассмотреть возможность:
?- freeze(L, (X=1;X=2)), phrase(("a",!,"b"),L).
L = [a, b],
X = 1.
B, SICStus, SWI, YAP дают один ответ. Так что сокращение существенное.
В любом случае, спасибо за вопрос. Я понял проблему NSTO только при ответе на ваш вопрос! Это явно оказывает некоторое влияние на то, как формулируется перевод DCG.
person
false
schedule
04.01.2013