Назад | Содержание| Вперёд 2. 4. Процедурная семантика Процедурна...

Назад | Содержание| Вперёд

2. 4. Процедурная семантика

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

целилогически следовали из программы. Можно

сказать, что процедурная семантика Пролога - это

процедура вычисления списка целей

сучетом заданной программы. "Вычислить цели"это значит попытаться достичь их.

Назовем эту процедуру вычислить. Какпоказано на рис. 2.9, входом и выходом этойпроцедуры являются:

входом - программа и список целей,

выходом - признак успех/неуспех иподстановка переменных.

Рис. 2. 9. Входы и выходыпроцедуры вычисления списка целей.

Смысл двух составляющих выхода такой:

(1) Признак успех/неуспех принимаетзначение "да", если цели достижимы, и"нет" - в противном случае. Будем говорить,что "да" сигнализирует об успешномзавершении и "нет" - о неуспехе.

(2) Подстановка переменныхпорождается только в случае успешногозавершения; в случае неуспеха подстановкаотсутствует.

ПРОГРАММА

большой( медведь). %Предложение 1

большой( слон). % Предложение 2

маленький( кот). %Предложение 3

коричневый ( медведь). % Предложение 4

черный ( кот). %Предложение 5

серый( слон). % Предложение 6

темный( Z) :- % Предложение 7:

черный( Z). % любой черный

% объект является темным

темный( Z) :- % Предложение 8:

коричневый(Z). % Любойкоричневый

% объект является темным

ВОПРОС

?- темный( X), большой( X) %Кто одновременно темный

% и большой?

ШАГИ ВЫЧИСЛЕНИЯ

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

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

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

темный(X).

Найдена формула 7:

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

Замена первого целевого утвержденияконкретизированным телом предложения 7 -порождение нового списка целевых утверждений.

черный(X), большой( X)

(3) Просмотр программы для нахожденияпредложения, сопоставимого с черный( X).Найдено предложение 5: черный ( кот). Уэтого предложения нет тела, поэтому список целейпри соответствующей конкретизации сокращаетсядо

большой(кот)

(4) Просмотр программы в поисках цели большой(кот). Ни одно предложение не найдено. Поэтомупроисходит возврат к шагу (3) и отменаконкретизации Х = кот. Список целейтеперь снова

черный(X), большой( X)

Продолжение просмотра программы нижепредложения 5. Ни одно предложение не найдено.Поэтому возврат к шагу (2) и продолжение просмотраниже предложения 7. Найдено предложение (8):

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

Замена первой цели в списке на коричневый(Х), что дает

коричневый(X), большой( X)

(5) Просмотр программы для обнаруженияпредложения, сопоставимого коричневый( X).Найдено предложение коричневый( медведь).У этого предложения нет тела, поэтому списокцелей уменьшается до

большой(медведь)

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

Рис. 2. 10. Пример,иллюстрирующий процедурную семантику

Пролога: шаги вычислений,выполняемых процедурой вычислить.

В главе 1 в разд. "Как пролог-система отвечаетна вопросы" мы уже фактически рассмотрели, чтоделает процедура вычислить. Воставшейся части данного раздела приводитсянесколько более формальное и систематическоеописание этого процесса, которое можнопропустить без серьезного ущерба для пониманияостального материала книги.

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

Чтобы вычислить список целевых утверждений

G1, G2, ..., Gm

процедура вычислить делает следующее:

Если список целей пуст - завершает работу успешно.

Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'.

ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.

Если С найдено и имеет вид

Н :- B1, ..., Вn.

то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком G1, ..., Gm. Пусть С' - это

Н' :- B1', ..., Вn'.

Сопоставляется G1 с H'; пусть S - результирующая конкретизация переменных. В списке целей G1, G2, .... Gm, цель G1 заменяется на список В1', .., Вn', что порождает новый список целей:

В1', ..., Вn', G2, ..., Gm

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

Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей

В1'', .... Вn", G2', ..., Gm'

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

Более компактная запись этой процедуры вобозначениях, близких к Паскалю, приведена нарис. 2.11.

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

procedure вычислить (Прогр, СписокЦелей,Успех)

Входные параметры:

Прогр: список предложений

СписокЦелей: список целей

Выходной параметр:

Успех: истинностноезначение; Успех принимает значение

истина, если список целевых утверждений

(их конъюнкция) истиннен с точки зрения Прогр

Локальные переменные:

Цель: цель

ДругиеЦели: список целей

Достигнуты: истинностное значение

Сопоставились: истинностное значение

Конкрет: конкретизация переменных

Н, Н', B1, B1', ..., В_n , В_n': цели

Вспомогательные функции:

пycтой( L): возвращает истину, если L - пустой список

голoвa( L): возвращает первый элемент списка L

хвост( L): возвращает остальную часть списка L

конкат( L1, L2): создает конкатенацию списков - присоединяет

список L2 к концу списка L1

сопоставление( T1,T2, Сопоставились, Конкрет): пытается

сопоставить термы Т1 и T2; если они сопоставимы, то

Сопоставились - истина, а Конкретпредставляет

собой конкретизацию переменных

подставить(Конкрет, Цели): производит подстановкупеременных

в Цели согласно Конкрет

begin

if пустой( СписокЦелей) thenУспех : = истина

else

begin

Цель : = голова(СписокЦелей);

ДругиеЦели: = хвост( СписокЦелей);

Достигнута: = ложь;

while notДостигнута and

"в программе есть еще предложения" do

begin

Пусть следующее предложение в Прогр есть

Н :- B1, .... Вn.

Создать вариант этого предложения

Н' :- В1', .... Вn'.

сопоставление( Цель, Н',

Сопоставились, Конкрет)

if Сопоставились then

begin

НовыеЦели : =

конкат( [В1', ..., Вn' ], Другие Цели);

НовыеЦели : =

подставить( Конкрет, НовыеЦели);

вычислить( Прогр, НовыеЦели, Достигнуты)

end

end;

Успех : =Достигнуты

end

end;

Рис. 2. 11. Вычислениецелевых утверждений Пролога.

Всякий раз, как рекурсивный вызов процедуры вычислитьприводят к неуспеху, процесс вычисленийвозвращается к ПРОСМОТРУ ипродолжается с того предложения С, котороеиспользовалось последним. Поскольку применениепредложения С не привело к успешномузавершению, пролог-система должна дляпродолжения вычислений попробоватьальтернативное предложение. В действительности

система аннулирует результаты частивычислений, приведших к неуспеху, и осуществляет

возврат

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

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

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

Упражнение

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

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

Сравните свое описание шагов вычисления сописанием на рис. 2.10, где вычислялся, по существу,тот же вопрос, но с другой последовательностьюцелей:

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

В каком из этих двух случаев системе приходитсяпроизводить большую работу для нахожденияответа?

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление