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

Декларативный смысл касается только отношений определённых в программе и определяет «что должно быть результатом работы программы?»

Процедурный смысл определяет ещё и «как результат был получен», то есть как отношения реально обрабатываются Пролог-системой. Способность Пролог-системы прорабатывать многие процедурные детали самостоятельно является одним из специфических преимуществ Пролога. Это свойство побуждает программиста рассматривать процедурный и декларативный смысл программы относительно независимо друг от друга.

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

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

Формальное определение декларативного смысла программы:

P :- Q,R.

P, Q и R имеют синтаксис терма.

Способы декларативной интерпретации цели предложения:

1. P – истина, если Q и R – истина.

2. Из Q и R следует P.

Процедурное прочтение:

1. Чтобы решить задачу P, сначала надо решить задачу Q, а затем задачу R.

2. Чтобы достичь P, сначала надо достичь Q, а затем R.

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

Формализуем декларативный смысл: он определяет, является ли данная цель истинной (достижимой) и если «да», то при каких значениях переменных она достигается.

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

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

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

1. голова I совпадает с G;

2. все цели I истинны.

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

При дизъюнкции целей:

P :- Q;R.

Запятая (,) связывает цели сильнее, чем точка с запятой (;).

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

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

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

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

Пример:

1. большой (“медведь”).

2. большой (“слон”).

3. маленький (“кот”).

4. коричневый (“медведь”).

5. чёрный (“кот”).

6. серый (“слон”).

7. тёмный (Z) :- чёрный (Z).

8. тёмный (Z) :- коричневый (Z).

? тёмный (X), большой (X).

Решение:

1. Исходный список целевых утверждений.

2. Просмотр всей программы от начала к концу и поиск предложения, у которого голова сопоставима с первым целевым утверждением: тёмный (Х).

Найдено предложение 7.

Замена первого целевого утверждения конкретизированным телом предложения 7 и порождение нового списка целевых утверждений: чёрный (X), большой (X).

3. Просмотр программы в поисках предложения сопоставимого чёрный (Х).

Найдено предложение 5.

У этого предложения нет тела, поэтому список целей, при соответствующей конкретизации переменной Х значением кот (Х=”кот”), сокращается до большой (“кот”).

4. Просмотр программы в поисках предложения сопоставимого с целью большой (“кот”).

Ни одно предложение не найдено. Поэтому происходит возврат к шагу 3 и отмена конкретизации Х=”кот”.

Теперь список целей снова чёрный (X), большой (X).

Продолжаем просмотр ниже предложения 5. Ни одно предложение не найдено, чтобы доказать чёрный (Х). Поэтому происходит возврат к шагу 2 и продолжается просмотр программы ниже предложения 7.

Найдено предложение 8.

Далее происходит замена первой цели:

тёмный (X), большой (X)  коричневый (X), большой (X).

5. Просмотр программы в поисках предложения сопоставимого с целью коричневый (Х).

Найдено предложение 4.

Переменная Х конкретизируется значением медведь. Список целей сокращается до: большой (“медведь”).

6. Просмотр программы в поисках большой (“медведь”). Найдено. Список целей пуст. На выходе конкретизация X=”медведь”.