Метапрограммирование

где Object —- терм, который именует объект (и, возможно, задает его параметры), а Methods — список термов Prolog, определяющих методы. Термы  в этом списке име- ют форму предложений Prolog, т.е. обычных фактов и правил Prolog (если не счи- тать того, что они не оканчиваются точкой). Б рассматриваемой реализации Prolog определение любого объекта может задавать целый класс объектов, таких как класс всех прямоугольников, определяемых с помощью предиката rectangle [ Length, Width). В таком случае конкретный прямоугольник со сторонами 4 и 3 определяется с помощью терма rectanglet 4, 3). Это означает, что в общем объект rectangle { Length, Width] с двумя методами, area и describe, может быть определен следующим образом:

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

send( Object, Message)

Для того чтобы объект прямоугольника со сторонами 4 и 3 описал себя и вычислил свою площадь, ему достаточно передать соответствующие сообщения:

Составить программу  для процедуры send{ Object, Message) можно достаточно просто. Вначале необходимо обеспечить выборку методов объекта Object. Эти методы фактически определяют программу Prolog, которая является локальной по отношению к Object. Затем нужно вызвать на выполнение эту программу, задав ей в качестве цели сообщение Message. Программа, представленная в виде списка, состоит из компонентов в форме Head : - Body или просто Head в случае, если тело является пустым. Чтобы выполнить программу с целью Message, требуется найти голову предложения, которая согласуется с целью Message, а затем выполнить соответствующее тело предложения с помощью собственного интерпретатора Prolog.

Прежде чем  реализовать этот замысел в программе, необходимо рассмотреть еще один существенно важный механизм объектно-ориентированного программирования — наследование методов в соответствии с отношением "isa" (является) между объектами. Например, квадрат "isa" прямоугольником. Для вычисления его площади в объекте квадрата может использоваться такая же формула, как и в объектах, прямоугольников. Поэтому для квадрата не требуется его собственный метод area; он может унаследовать этот метод от класса прямоугольников. Для того чтобы получить такую возможность, необходимо определить объект  s q u a r e и дополнительно указать, что он также является прямоугольником.

Это дает возможность успешно  выполнить следующий запрос:

?- send! square( 5), area( Area)!.

 Дгег - 25

Сообщение area{ Area) обрабатывается таким образом: вначале выполняется поиск метода area ( Area) среди методов объекта square ( 5), но найти его не удается. Затем с помощью отношения isa успешно выполняется поиск этого метода в суперобъекте квадрата — в прямоугольнике rectangle ( 5, 5). Суперобъект имеет соответствующий метод area, который вызывается на выполнение.

Интерпретатор для объектно-ориентированных программ, разработанный в соответствии с замыслом, описанным в данном разделе, приведен в листинге 4.1, а в листинге 4,2 приведена законченная объектно-ориентированная программа, относящаяся к геометрическим фигурам.

Листинг 4.1. Простой интерпретатор для объектно-ориентированных программ

 

 

 

 

 

 

 

Листинг 4.2. Объектно-ориентированная  программа, относящаяся к геометрическим фигурам

До сих пор  мы еще не упоминали о проблеме множественного наследования. Подобная проблема возникает, если отношение   i s a определяет такую решетку связей между объектами, что некоторые объекты имеют больше одного родительского объекта, как, например, объект square (см, листинг 4.2). Поэтому существует вероятность того, что некоторый метод может быть унаследован объектом больше чем от одного родительского объекта. В таком случае необходимо найти ответ на вопрос о том, какой из нескольких потенциально наследуемых методов должен использовать- ся в дочернем объекте. В программе, приведенной в листинге 4.1, предусмотрен поиск одного из применимых методов среди объектов в графе, определяемым отношением isa. В листинге 4.1 применяется простая стратегия поиска в глубину, но более подходящими могут оказаться некоторые другие стратегии. Например, поиск в ширину гарантирует, что будет всегда использоваться "ближайший наследуемый" метод.

Завершим этот раздел общим комментарием, касающимся преимуществ объектно-ориентированного программирования. Рассматриваемые здесь в качестве примеров объектно-ориентированные программы могут быть реализованы в обычном стиле Prolog (фактически более компактно) без упоминания объектов и сообщений. Приведенные в этом разделе примеры иллюстрируют общие принципы, но они слишком малы для того, чтобы служить убедительным доказательством возможных преимуществ объектно-ориентированного программирования. Очевидно, что объектно-ориентированная модель является особенно удобной при написании программ для систем машинного моделирования, в которых физические компоненты действительно обмениваются своего рода сообщениями. Например, в производственном процессе в качестве сообщений могут рассматриваться потоки материалов, движущиеся от одно- го станка к другому. Еще одним преимуществом объектно-ориентированной модели является то, что она предоставляет удобную инфраструктуру для организации крупных программ. И память, и процедуры (методы) сосредоточиваются вокруг определений объектов, а механизм наследования предоставляет способ структуризации такой программы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5 ПРОГРАММИРОВАНИЕ, УПРАВЛЯЕМОЕ ШАБЛОНАМИ

5.1 Архитектура,  управляемая шаблонами

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

 

 

5.2. Программы  Prolog, реализованные в виде систем, управляемых шаблонами

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

• В качестве модуля, управляемого шаблонами, может  рассматриваться каждое предложение Prolog в программе. Условная часть  этого модуля представляет собой голову предложения, а часть, определяющая действие, задается с помощью тела предложения.

• База данных системы представляет собой текущий список целей, которых пытается достичь система Prolog.

• Предложение  вызывается на выполнение, если его  голова согласуется, с первой целью  в базе данных.

• Выражение "выполнить  действие модуля (тело предложения)" означает — заменить первую цель в базе данных списком целей в теле предложения (после надлежащей конкретизации переменных).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6 ПРОСТАЯ ПРОГРАММА АВТОМАТИЧЕСКОГО ДОКАЗАТЕЛЬСТВА ТЕОРЕМ, РЕАЛИЗОВАННАЯ В ВИДЕ ПРОГРАММЫ, УПРАВЛЯЕМОЙ ШАБЛОНАМИ

 

Рассмотрим  реализацию простой программы автоматического доказательства теорем в виде системы, управляемой шаблонами. Эта программа автоматического доказательства будет основана на принципе резолюции. В этом описании мы ограничимся доказательством теорем простой логики высказываний лишь для иллюстрации используемого принципа, хотя описанный механизм резолюции может быть легко расширен для обработки выражений исчисления предикатов первого порядка (логических формул, которые содержат переменные). Дело в том, что сама основная система Prolog представляет собой особую разновидность программы автоматического доказательства теорем на основе принципа резолюции. Задачу доказательства теоремы можно определить следующим образом: дана некоторая формула; необходимо показать, что она является теоремой. Это означает, что формула всегда является истинной, независимо от интерпретации символов, которые встречаются в этой формуле. Например, формула:

р v ~р

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

• ~. Отрицание, читается как " n o t " (не).

• S. Конъюнкция, читается как "and" (и).

• v. Дизъюнкция, читается как "сг" (или).

• =>. Импликация, читается как " implies " (следует из).

Для этих операторов определен такой приоритет, что " not " всегда связывает сильнее всех, за ним следует "and", затем "or" и после этого "implies".

Метод резолюции  предусматривает использование такой последовательности доказательства: вначале к предполагаемой теореме применяется операция отрицания, а затем предпринимается попытка показать, что формула, полученная в результате отрицания, содержит противоречие. Если формула, полученная в результате отрицания, действительно является противоречивой, то первоначальная формула должна представлять собой тавтологию (т.е. быть истинной при любой интерпретации). Поэтому общая идея состоит в следующем: если продемонстрировано, что формула, полученная в результате отрицания, содержит противоречие, это равносильно доказательству, что первоначальная формула является теоремой (всегда остается истинной). Процесс, направленный на обнаружение противоречия, состоит из последовательности этапов резолюции.

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

(а => b) S (Ь  => с) => (а => с) 

Эта формула  читается следующим образом: "если b следует из а и с следует  из Ь, то с следует из а".

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

В этой формуле все символы р, q и г представляют собой простые высказывания или их отрицания. Эта форма называется также формой представления в виде предложений (под предложением здесь подразумевается конструкция, аналогичная простому грамматическому предложению в составе сложного), и каждый из ее дизъюнктов рассматривается как предложение. Поэтому составной терм (pi v p; v . . .) также является предложением. В эту форму может быть преобразована любая пропозициональная формула (формула исчисления высказываний). Для данной теоремы, рассматриваемой в качестве примера, такое преобразование может быть выполнено, как описано ниже. Сама эта теорема имеет следующий вид:

(а=>Ь) ь [Ь=>с) -> [а=>с)

Отрицание данной  теоремы выглядит таким образом:

-((a =>b) 6 (Ь=>с) -> (а =>сМ

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

1. Выражение  х=>у эквивалентно -х v у. 

2. Выражение  --{х v у) эквивалентно ~х & -у.

3. Выражение  -{х & у) эквивалентно -х v -у, 4. Выражение ~(~х) эквивалентно х.

Применив правило 1 к рассматриваемой формуле, получим  следующее:

( - [ [а => Ы  & (Ь => с) ) v (а => с) )

С помощью правил 2 и 4 преобразуем формулу в такую  форму:

{а -> Ь) ь (Ь «о с] 5 ~( а -> с!

 Несколько раз воспользовавшись  правилом 1, получим:

(~аvb) t (-bvс) б-(-avс)

Применив правило 2, наконец, получим требуемую форму  представления в виде предложений:

(-a v Ь) & [~Ь v с) & а & -с

Это предложение  состоит из четырех термов: [~а v b), (~b v с), а, --с. Теперь можно приступить к выполнению процесса резолюции.

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