Интерпретация систем продукций [1980 Уинстон П.

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

Робби переставляет мебель, пользуясь продукциями

Рассмотрим, например, каким образом Робби мог бы справиться с задачей перестановки мебели тети Агаты с места на место. Возникающие цели будут появляться в кратковременной памяти (STM) примерно в следующей форме:

Краткое описание цели, преследуемой каждой продукцией, будет полезным при изучении подробного их описания, которое последует ниже:

Р1 преобразует требование поместить объект на некоторую опору в команду поместить объект в конкретную точку пространства.

Р2 разворачивает цель поместить объект в некоторое положение в цели, связанные со взятием, и в запомненные целевые местоположения.

Р3 помогает забыть утерявшие смысл отношения опоры.

Р4 движет рукой, держащей предмет, и вызывает разжатие кисти, когда перемещение завершается.

Р5 движет свободной рукой в направлении указанного объекта и схватывает его.

Р6 обеспечивает удаление на пол препятствий, стоящих на пути.

Р7 взаимодействует с миром, чтобы идентифицировать препятствия.

Для простоты они будут исследованы нами в порядке, не совпадающем с их организацией в долговременной памяти^*.

Первой нами будет рассмотрена продукция, которая преобразует цели вида ПОМЕСТИТЬ-В в комбинации целей вида ВЗЯТЬ и запомненных целевых местоположений. Как и всякая продукция, она должна быть построена из основных исходных элементов, операций записи, выделения, отметки и коммуникации:

^* (Для лучшего усвоения дальнейшего материала мы рекомендовали бы еще раз просмотреть последние разделы гл, 5.- Прим. перев.)

Имена, начинающиеся с символа >, должны быть сопоставимы со всем чем угодно, и то, с чем они сопоставляются, хранится в памяти. Эти запомненные идентификации вызываются впоследствии, когда те же самые имена используются с дополнительным символом <, появляющимся в качестве префикса.

После выполнения Р2 кратковременная память STM содержит следующее:

Обратите внимание на то, что скобки группируют элементы вместе, упрощая структурные конвенции. Элемент ПОМЕСТИТЬ-В СТОЛ XYZ) помечен путем объединения его с символом ПОМЕЧЕНО. Этим гарантируется, что продукция Р2 не будет запирать систему благодаря бесконечному срабатыванию на одной и той же комбинации в кратковременной памяти.

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

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

Действие получить связано с восприятием ответов от зрительной системы в форме (СТОЛ ПОДДЕРЖИВАЕТ НИЧЕГО) или (СТОЛ ПОДДЕРЖИВАЕТ ЛАМПА). Если ничего не поддерживается, то STM будет содержать элементы, которых достаточно для срабатывания Р5. Заметим, что Р5 должна появиться перед Р7, поскольку те вещи, которые требуются для Р7, являются подмножеством того, что требуется для Р5. Если Р7 была бы первой, то Р5 никогда не могла бы быть активирована.

После активации Р7 в предположении, что стол был свободен, кратковременная память STM содержит следующее:

То, что элемент (ВЗЯТЬ СТОЛ) находится сверху, является прямым результатом действия выделения, примененного в Р7. Этим обеспечиваются условия для срабатывания Р5, что немедленно приводит к следующему:

Следующая продукция ожидает элемента ПЕРЕМЕСТИТЬ СТОЛ: ПРОДУКЦИЯ Р4:

Она приводит к следующим двум манипуляционным командам:

На этом действие заканчивается. Если стол поддерживает что-нибудь, скажем лампу, то картина существенно усложнится. Предположим, что Робби, который несколько неустойчив, всегда предпочитает освободить мебель от стоящих на ней предметов, прежде чем ее передвигать. Продукция Р6 подходит для того, чтобы очистить стол:

Продукция Р1 преобразовалась в новую цель ПОМЕСТИТЬ-В: ПРОДУКЦИЯ Р1:

Необходима еще одна продукция, поскольку разборка нагромождений нарушает отношения поддержки. Для этого подходит РЗ: ПРОДУКЦИЯ РЗ:

Теперь эта полная система из семи продукций могла бы справиться со столом, на котором стоит настольная лампа, если бы только хватило кратковременной памяти. Ее, однако, недостаточно. Целевое положение для стола будет выпадать, если только кратковременная память не будет расширена до 11 элементов. Результирующая последовательность показана на рис. 15.3.

Рис. 15.3. Система продукций решает проблему перемещения стола. Первоначально кратковременная память содержит (ПОМЕСТИТЬ-В СТОЛ XYZ). В дальнейшем содержание кратковременной памяти изменяется, как здесь показано. NIL указывает на пустые ячейки. Связь с сенсорными и моторными устройствами показана символом >>>

Выраженные на естественном языке продукции легко преобразуются в удобную для работы форму

Выбор достаточно прозрачного синтаксиса для РСП себя оправдал. Аналогично, затратив примерно те же усилия для систем продукций, мы получаем что-то вроде следующего синтаксиса:

Такая формула для комбинации ситуация - действие позволяет систему предвижения мебели Робби записать в следующей сжатой форме:

(Символ ** представляет первый элемент в кратковременной памяти STM).

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

Интерпретатор для системы продукций несложен

Рисунок 15.4 изображает структуру интерпретатора для системы продукций. Каждый цикл содержит две части: поиск в списке продукций с целью найти продукцию, образец которой соответствует содержанию кратковременной памяти, и выполнение указаний, определяемых списком действий подошедшей продукции. Все это осуществляется функцией USE-PRODUCTION (ИСПОЛЬЗОВАНИЕ-ПРОДУКЦИИ)^*:

^* (Чтобы легче понять это выражение, заметим, что использованные в нем немые переменные имеют следующий перевод на русский: PRODUCTION - продукции, NEXT -следующий, NAME - имя, PATTERN - образец и ACTIONS - действия.- Прим. перев)

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

По существу функция USE-PRODUCTION просматривает список продукций, пока функция MATCH-STM (СОПОСТАВИМО-C-STM) не найдет подходящую продукцию, с которой функция PERFORM-ACTION (ВЫПОЛНИТЬ-ДЕЙСТВИЕ) сделает то, что необходимо. Из этих двух подчиненных функций функция PERFORM-ACTION проще. Для нее главным образом требуется цикл с использованием громоздкого предложения COND, в котором выполняется каждое из действий, определяемых списком ACTION- LIST (СПИСОК-ДЕЙСТВИЙ). Альтернативными возможностями являются SHOVE (ВНЕСТИ), NOTICE (ВЫДЕЛИТЬ), MARK (ПОМЕТИТЬ), SEND (ПОСЛАТЬ) и RECEIVE (ПОЛУЧИТЬ). Все остальное просто закладывается в кратковременную память:

Операция SHOVE (ВНЕСТИ) осуществляется с помощью вспомогательной функции. Остальные команды, соответствующие действиям, реализуются непосредственно.

Сопоставление с образцом, осуществляемое функцией MATCH-STM, производится с использованием уже нескольких вспомогательных функций:

Просматривая их, можно увидеть, что они выполняют следующие обязанности:

Функция MATCH-STM - это просто управляющая система,которая делает так, чтобы успешно сопоставленные элементы перемещались к началу кратковременной памяти STM.

Функция PULL-TO-FROM-OF-STM (ПЕРЕМЕСТИТЬ-В-НАЧАЛО-STM) просто выполняет такое перемещение.

Функция MATCH 1 (СОПОСТАВЛЕНИЕ 1) с одной стороны следит за образцом, а с другой - за STM, двигаясь вдоль того и другого. Рекурсия устроена так, чтобы лишние элементы STM пропускались. Те элементы из STM, которые оказываются подходящими, записываются для дальнейшего использования.

Функция МАТСН2 (СОПОСТАВЛЕНИЕ2) сравнивает один элемент с другим и реализует все возможности по сопоставлению с образцом.

Символ ? сопоставим с чем угодно. Переменные, начинающие с >, сопоставимы с чем угодно, и при этом в качестве побочного эффекта производится присваивание значения. Переменные с < используют эти присваивания, поскольку такие переменные при проверке на сопоставимость заменяются их значениями. Вложенные структуры из элементов обрабатываются рекурсией. Необычные условия остановки обеспечивают успех сопоставления в том случае, когда полный образец является просто начальной частью некоторого более длинного элемента кратковременной памяти STM.

Эти присвоенные значения, значения, получаемые в ходе сопоставления G образцом, удобно использовать позднее, на этапе осуществления действий. Это делается функцией PERFORM-ACTION (ВЫПОЛНИТЬ-ДЕЙСТВИЕ) с использованием функции SUB-STITUTE-VARIABLES (ПОДСТАВИТЬ-ПЕРЕМЕННЫЕ):

Обратите внимание, что в этой функции вводится новый, специальный символ **, который обозначает текущий первый элемент в STM.

Наконец, имеется лишь одна простая функция RUN (ЗАПУСК), которая повторяет цикл функции (USE-PRODUCTION) (ИСПОЛЬЗОВАНИЕ-ПРОДУКЦИИ).

В различных местах используются также следующие три простые вспомогательные функции: