Книга: Программирование на языке Пролог для искусственного интеллекта

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),  большой( X)

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

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

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

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

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

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

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

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

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

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

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

 G1, G2, …, Gm

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

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

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

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

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

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

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

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

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

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

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

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

 Цель: цель

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

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

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

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

          H, Н', 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

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

      H :- 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).

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

Оглавление книги