Подчеркнем, что соединение разностных списков происходит неявно, в процессе унификации, поэтому операционное поведение программ с разностными списками труднее для понимания и при отладке часто имеет смысл использовать трассировку.
Как правило, Пролог-программы с явными обращениями к предикату append могут быть переработаны в более эффективные за счет исключения простого append и использования разностных списков и разностного предиката append, что в ряде случаев по сути равносильно использованию переменных-накопителей.
Заметим, что имя функтора dl выбрано произвольно и может быть заменено на любой другой бинарный фунтор, и даже опущено - тогда первый и второй аргументы разностного списка становятся двумя отдельными аргументами предиката, использующего разностный список. При этом рассмотренный выше разностный append от трех аргументов превратится в
append_dl (Z1, Z2, Z2, Z3, Z1, Z2).
4. При программировании ряда предикатов могут потребоваться средства управления механизмом бектрекинга пролог-интерпретатора. В языке Пролог для этого используются два основных стандартных предиката без аргументов - предикаты fail и cut (обычно обозначаемый как !).
Предикат fail инициирует бектрекинг - при его выполнении происходит возврат к последней по времени точке бектрекинга (при этом автоматически восстанавливается вся операционная обстановка этой точки, включая значения переменных) и возобновляется доказательство текущей цели от этой точки. Fail по сути является предикатом, который никогда не выполняется, т.к. отсутствуют определяющие его предложения, поэтому можно использовать вместо fail любой неопределенный предикат с другим именем.
Заметим, что по смыслу предикат fail должен стоять последним в списке целей правой части любого пролог-правила (предложения).
Стандартный прологовский предикат ! предотвращает бектрекинг, в этом смысле его действие противоположно действию fail. Предикат ! употребляется для сокращения дерева доказательства цели путем отсечения некоторых его ветвей, поэтому он называется отсечением.
В общем случае выполнение отсечения ! в предложении S общего вида:
P:- R1, ..., Rk, !, Rk+1, ..., Rn.
где 0 £ k £ n,
относящемуся к пролог-процедуре P и используемого при доказательстве цели G, означает уничтожение всех последних по времени точек бектрекинга, возникающих с момента входа в процедуру P (т.е. начиная с поиска предложения этой процедуры, заголовок или левая часть которого унифицируема с текущей доказываемой целью G). Напомним, что под пролог-процедурой Р понимается набор из всех предложений, в левой части которых стоит предикат Р.
При выполнении отсечения, во-первых, отбрасываются все точки бектрекинга, возникающие при доказательстве целей R1, ..., Rk, расположенных левее предшествующих отсечению (то есть отбрасываются все альтернативные решения конъюнкции целей R1, ..., Rk), а во-вторых, уничтожается также точка бектрекинга, связанная с возможными альтернативами доказательства цели G, поэтому другие предложения процедуры P, заголовок которых унифицируем с G, будут при доказательстве отброшены.
В то же время выполненное отсечение не влияет на цели Rk+1, ..., Rn, расположенные правее его и возникающие при их доказательстве точки бектрекинга, таким образом, эти цели могут порождать более одного решения.
Однако, если при доказательстве конъюнкции Rk+1, ..., Rn возник неуспех (fail), и процесс возврата, исчерпав все альтернативы в возникших при этом доказательстве точках бектрекинга, достиг точки отсечения, то далее он распространяется до последней по времени точки бектрекинга, возникшей перед входом в процедуру P.
По семантике отсечения подразделяются на зеленые и красные [Стерлинг, с.127-132, 136-140]. Зеленые отсечения не изменяют декларативное значение (смысл) логической программы - множество возможных ее решений, то есть при них отсекаются ненужные ветви доказательства и уничтожаются лишние точки бектрекинга. Полезность таких отсечений определяется тем, что экономится время доказательства и, что более важно, необходимая память (вся связанная с точками бектрекинга информация запоминается в стеке).
Очевидно, что все вводимые в детерминированную программу отсечения являются зелеными (если они не отсекают единственное решение).
Красные отсечения изменяют декларативное значение программы, они обычно появляются, когда в недетерминированной программе необходимо по каким-либо причинам отбросить часть решений. Примером красного отсечения является отсечение в предикате member:
member (X, [X| Xl]):-!
member (X, [Y| Yl]):- member (X, Yl).
Вычисление в прототипе (o, i) приводит к поиску только первого вхождения элемента X в список Xl, поэтому результат вычислений будет отличаться от результата вычислений этого предиката, но без отсечения.
Отметим, что введение отсечения приводит к потере модульности предиката (становится важным порядок предложений в программе), а также очень часто - к потере его инвертируемости. Таким образом, программы с отсечениями менее гибки и менее декларативны, чем их аналоги без отсечений.
5. При программировании может оказаться полезным еще один стандартный пролог-предикат not, реализующий ограниченную форму отрицания - отрицание как безуспешное выполнение. Точнее, not(G) успешно завершает работу тогда, когда его аргумент - цель G - не может быть доказана (т.е. возникает неуспех).
Большинство реализаций Пролога запрещает использовать внутри цели G к моменту ее доказательства свободные переменные, за исключением анонимных, во избежание некорректностей, связанных с логической трактовкой их значений.
Семантика предиката not может быть определена двумя пролог-предложениями с помощью предикатов fail и cut (при этом G - метапеременная):
not(G):- G, !, fail.
not(G).
Таким образом, можно считать предикат cut слабой формой логического отрицания.
Во многих случаях при решении задачи подходит как предикат not, так и отсечение. Если же выбирать между этими предикатами, то, несмотря на меньшую эффективность, использование not предпочтительнее, чем менее понятная конструкция с отсечением. |
Главная
Каталог файлов
