Декларативное значение программ Prolog

Как было показано в главе 1, могут рассматриваться два значения программ Prolog: декларативное и процедурное. Б этом и следующем разделах приведены более формальные определения декларативного и процедурного значений программ в ос­новном подмножестве языка Prolog. Но вначале снова проанализируем различие ме­жду этими двумя значениями. Рассмотрим следующее предложение:

Р 1- Q,

Здесь Р, о и R имеют синтаксис термов. Ниже приведены некоторые альтернатив­ные декларативные прочтения этого предложения.

Р является истинным, если q и r истинны. Из Q и " следует Р.

Два альтернативных процедурных прочтения этого предложения приведены ниже.

Чтобы решить проблему р, Рначале необходимо решить подлроблему Q,

Для достижения⁰цели°''Р'"вначале необходимо достичь Q, а затем - и.

Часть!. Язык Prolog

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

Рассмотрим формализованное определение декларативного значения.

Декларативное значение программ позволяет установить, является ли заданная цель истинной, а в случае положительного ответа — при каких значениях перемен­ных она является истинной. Чтобы точно определить декларативное значение, необ­ходимо ввести понятие экземпляра предложения. Экземпляром предложения С назы­вается предложение С, в котором вместо каждой из его переменных подставлен неко­торый терм. Вариантом предложения С называется такой экземпляр предложения С, где вместо каждой переменной подставлена другая переменная. Например, рассмот­рим следующее предложение: hasachildf x) :- parent( X, y; .

Ниже приведены два варианта этого предложения.

hasachild( А) -parent(A, 3). hasachildl XI} :- patent ( XI, Х2) .

Экземплярами этого предложения являются следующие: hasachildf peter) :- parent с peter, 2). hasachildl fcarryi :- parentt barry, small(Caroline)).

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

Цель G является истинной (т.е. достижимой, или логически следующей иэ про­граммы), если и только если:

1. в программе имеется предложение С, такое, что

2. существует экземпляр I предложения С, такой, что

а) голова I идентична цели G и

б) все цели в теле I являются истинными.

Из этого определения можно вывести понятие вопроса Prolog следующим образом. Как правило, вопросом в системе Prolog является список целей, разделенных запя­тыми. Список целей является истинным, если все цели в списке являются истинны­ми для одной и той же конкретизации переменных. Значения переменных становят­ся результатом наиболее общей конкретизации.

Поэтому запятая между целями обозначает конъюнкцию целей, при которой все они должны быть истинными. Но Prolog допускает также дизъюнкцию целей, при которой должна быть истинной лишь любая из целей. Дизъюнкция обозначается точкой с запятой. Например, предложение

Р : - Q; R

имеет прочтение: ? является истинным, если истинно Q или R, Поэтому значение этого предложения аналогично значению двух следующих предложений, вместе взятых:

Р : - Q. Р ;- R.

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

Р :- Q, R; S, Т, И.

может рассматриваться следующим образом:

Р :- ( Q, R); ! S, Т, а).

и означает то же, что и предложения р : - Q, R«

P :- S, ' Т, U.

Глава 2. Синтаксис и значение программ Prolog