Cодержание

3.1 Декларативная семантика Пролог-программ

3.2 Дизъюнкция целей

3.3 Процедурная семантика

3.3.1 Пример вычисления

3.3.2 Формальное описание процедуры вычисления целей

3.4 Соотношение между процедурным и декларативным смыслом

3.1 Декларативная семантика Пролог-программ

Различают декларативную и процедурную семантику (смысл, понимание) пролог-программ.
Рассмотрим декларативный смысл более подробно.
Декларативный смысл, касается только отношений, определенных в программе.

Декларативная семантика определяет, что должно быть результатом работы про- граммы, не вдаваясь в подробности, как это достигается.

Пусть задано P:-Q, R.

где P, Q, R -термы.

Тогда с точки зрения декларативного смысла это предложение читается:" P-истиино, если Q R истинны." Или " Из Q и R cледует Р." Т.е. определяются логические связи между головой предложения и целями в его теле.

Таким образом , декларативный смысл программы определяет, является ли данная цель истинной (достижимой), и если - да, то при каких значениях переменных она достигается.

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

Заметим , что это отличается от конкретизации переменной.

Пример:

haschild( X ):-parent( X ,Y).

Предложение С.

Определение.

Пусть дана некоторая программа и цель G, тогда в соответствии с декларативной семантикой, можно утверждать, что:
Цель G истинна (т, е. достижима или логически следует из программы) тогда и только тогда, когда
(1) В программе существует предложение С, такое, что
(2) существует такая его (С) конкретизация I, что
(а) голова I cовпадает с G и
(b) все цели в теле I истинны.

Пример

C(I): C:		female(ann). parent(ann, bob). mother(ann):-parent(ann, Y), female(ann). mother(X) :-parent(X, Y), female(X).

 

		?- mother(ann).

Это определение можно распространить на вопросы следующим образом. В общем случае вопрос - список целей, разделенных запятыми.

Список целей называется истинным (достижимымм), если все цели в этом списке истинны, достижимы, при одинаковых конкретизациях переменных.

Запятая между целями означает конъюнкцию целей, и они должны быть все истинны.

3.2 Дизъюнкция целей

Возможна дизъюнкция целей: истинна должна быть по крайней мере одна из целей.
Дизъюнкция обозначается точкой с запятой ";".

Например

P:-Q;R.

Читается: Р истина, если Q - истина или R - истинна.
Т.е это то же самое, что

P:-R.
P:-Q.

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

P:-Q, R;S, T, U.

понимается как

P:-(Q, R);(S, T, U).

и имеет смысл

P:-Q, R.
P:-S, T, U.

3.3 Процедурная семантика

Процедурная семантика (процедурный смысл) пролог-программы определяет , как пролог-программа отвечает на вопросы.
Ответитиь на вопрос -зто значит удовлетворить цели.

Поэтому процедурная семантика пролога -это процедура вычисления списка целей с учетом программы.

3.3.1 Пример вычисления

Рассмотрим программу и на ее примере - процедуру вычисления списка целей.

Программа 1.

1.большой(медведь).
2.большой(слон).
3.маленький (кот).
4.бурый(медведь).
5.черный(кот).
6.серый(слон).
7.темный(Z):-черный(Z).
7.1
8.темный(Z):-бурый(Z).
8.1
9.?-темный(X),большой(X).
9.1 9.2

Предложения пронумерованы для удобства

Таким образом для вычисления целей потребовалось 7 сопоставлений и один откат.

3.3.2 Формальное описание процедуры вычисления целей.

Пусть список целей

1.Если список целей пуст, вычисление дает успех, если нет, то выполнятся пункт 2.

2.Берется первая цель G1 из списка. Пролог выбирает в базе данных, просматривая сначала, первое предложение С,
С: H :- B1, B2, ..., Bn.
голова которого, сопоставляется с целью G1.
Если такого предложения нет, то неудача.
Если есть, то переменные конкретизируются и цель G1 заменяется на список целей

с конкретизированными значениями переменных.

3.Рассматривается рекурсивно через п.2 новый список целей.

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

3.4 Соотношение между процедурным и декларативным смыслом

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

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

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

(c) M.N.Morozov, 1999.