Prolog
Шрифт:
Рис. 16. 1. Система, управляемая типовыми конфигурациями ( образцами).
ветствие сразу с несколькими предварительными условиями, а следовательно, в принципе могут запуститься несколько модулей одновременно. В связи с этим, подобную организацию можно рассматривать как естественную модель параллельных вычислений, имея в виду, что каждый модуль физически реализован на отдельном процессоре.
Архитектура, ориентированная на образцы, обладает рядом достоинств. Одно из ее главных преимуществ состоит в том, что, разрабатывая подобную систему, мы не должны тщательно продумывать и заранее определять
Высокая степень модульности особенно желательна в системах со сложными базами знаний, поскольку очень трудно предсказать заранее все возможные взаимодействия между отдельными фрагментами знаний. Архитектура, ориентированная на образцы, обеспечивает простое решение этой проблемы: каждый фрагмент знаний, представленный в виде "если-то"-правила, можно считать отдельным модулем, запускаемым своим собственным образцом.
Перейдем теперь к более детальной проработке нашей базовой схемы для систем, ориентированных на образцы, и рассмотрим вопросы реализации. Как следует из рис. 16.1, параллельная реализация была бы для нашей системы наиболее естественным решением. Тем не менее предположим, что нам предстоит реализовать ее на традиционном последовательном процессоре. Тогда если в базе знаний окажется сразу несколько "пусковых" конфигураций, относящихся к нескольким модулям, то возникнет конфликтная ситуация: нам придется принять решение о том, какой из этих потенциально активных модулей будет запущен в действительности. Совокупность всех потенциально активных модулей назовем конфликтным множеством. Очевидно, что реализация схемы рис. 16.1 на последовательном процессоре потребует введения в систему дополнительного, управляющего модуля. Задача управляющего модуля - выбрать и активизировать один из модулей конфликтного множества и тем самым разрешить конфликт. Одно из возможных простых правил разрешения конфликта может основываться, например, на предварительном упорядочивании множества модулей системы.
Основной цикл работы системы, ориентированной на образцы, состоит, таким образом, из трех шагов:
(1) Сопоставление с образцами: найти в базе данных все конфигурации, сопоставимые с пусковыми образцами программных модулей. Результат - конфликтное множество.
(2) Разрешение конфликта: выбрать один из модулей, входящих в конфликтное множество.
(3) Выполнение: запустить модуль, выбранный на предыдущем шаге.
Этот принцип реализации показан в виде схемы на рис. 16.2.
16. 1. 2. Прологовские программы как системы, управляемые образцами
Программы, написанные на Прологе, можно рассматривать как системы, управляемые образцами. Между пролог-программами и этими системами можно установить соответствие примерно следующим образом:
Каждое предложение прологовской программы можно считать отдельным модулем со своим пусковым образцом. Голова предложения соответствует образцу, тело - тому действию, которое выполняет модуль.
База данных системы - это текущий список целей, которые пролог-система пытается удовлетворить.
Предложение пролог-системы "запускается", если его голова сопоставима с целью, расположенной первой в базе данных.
Выполнить действие модуля (т.е. тело предложе
Процесс активизации модулей (предложений) не детерминирован в том смысле, что с первой целью базы данных могут удачно сопоставить свою голову сразу несколько предложений, и, вообще говоря, любое из них может быть запущено. В Прологе этот недетерминизм реализован при помощи механизма возвратов.
Рис. 16. 2. Основной цикл работы системы, управляемой образцами.
В этом примере база данных согласуется с пусковыми образцами
модулей 1, 3 и 4; для выполнения выбран модуль 3.
16. 1. 3. Пример составления программы
С системами, управляемыми образцами, связан свой особый стиль программирования, требующий специфического программистского мышления. Мы говорим в этом случае о программировании в терминах образцов.
В качестве иллюстрации, рассмотрим элементарное упражнение по программированию - вычисление наибольшего общего делителя D двух целых чисел А и В. Рассмотрим классический алгоритм Евклида:
Для того, чтобы вычислить наибольший общий делитель D чисел А и В, необходимо:
Повторять циклически, пока А и В не совпадут:
если А > В, то заменить А на А - В, иначе заменить В на В - А.
После выхода из цикла А и В совпадают; наибольший общий делитель D равен
А (или В).
Тот же самый процесс можно описать при помощи двух модулей, управляемых образцами:
Модуль 1
Условие В базе данных существуют такие два числа X и Y, что X > Y.
Действие Заменить X на разность X - Y.
Модуль 2
Условие В базе данных имеется число X.
Действие Выдать результат X и остановиться.
Очевидно, что всегда, когда условие Модуля 1 удовлетворяется, удовлетворяется также и условие Модуля 2, и мы имеем конфликт. В нашем случае конфликт можно разрешить при помощи простого управляющего правила: всегда отдавать предпочтение Модулю 1. База данных первоначально содержит числа А и В.
Здесь нас ждет приятный сюрприз: оказывается, что наша программа способна решать более общую задачу, а именно, она может вычислять наибольший общий делитель для любого количества чисел. Если в базу данных загрузить несколько целых чисел, то программа выведет их наибольший общий делитель. На рис. 16.3 показана возможная последовательность изменений, которые претерпевает база данных прежде, чем будет получен результат. Обратите внимание на то, что предварительные условия модулей могут удовлетворяться одновременно в нескольких местах базы данных.