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

В реализации метода EBG эти абстрактные идеи должны были стать более конкретными. Один из способов их реализации в логике языка Prolog состоит в следующем.

•  Понятие реализуется в качестве предиката,

•      Описание понятия представляет собой определение предиката.

• Объяснением  является дерево доказательства, которое  демонстрирует, как заданный экземпляр  удовлетворяет целевому понятию.

•     Теория проблемной области представлена в виде множества доступных предикатов, определенных как программа Prolog.

В таком случае задача обобщения на основе объяснения может быть сформулирована, как описано  ниже.

Дано

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

• Критерии операционности. Эти критерии определяют предикаты, которые могут использоваться в  определении целевого предиката.

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

Найти

• Обобщение учебного экземпляра и операционное определение целевого понятия; это определение состоит из достаточного условия (в терминах операционных предикатов) для данного обобщенного экземпляра, при котором удовлетворяется целевое понятие.

Метод обобщения  на основе объяснения в такой постановке может рассматриваться как своего рода компиляция программы с преобразованием из одной формы в другую. Первоначальная программа определяет целевое понятие в терминах предикатов теории проблемной области. Откомпилированная программа определяет то же целевое понятие (или подпонятие) в терминах "целевого языка", т.е. только с помощью операционных предикатов. Механизм компиляции, предусмотренный в методе EBG, является довольно необычным. Он предусматривает выполнение первоначальной программы на заданном примере, что приводит к получению дерева доказательства. Затем это дерево доказательства обобщается таким образом, что сохраняется его структура, но постоянные заменяются переменными при любой возможности. В полученном таким образом обобщенном дереве доказательства некоторые узлы указывают на операционные предикаты. Затем дерево сокращается так, что остаются только эти "операционные узлы" и корень. Полученный результат представляет собой операционное определение целевого понятия.

Это описание проще всего проиллюстрировать на примере практического применения метода EBG. В листинге 3.1 приведены два определения теорий проблемной области для EBG. Первая теория проблемной области касается вручения подарка, а вторая описывает движения лифта. Рассмотрим первую проблемную область. Допустим, что учебный экземпляр состоит в следующем:

% Джон вручает сам себе шоколад (разрешает себе его съесть) gives( John, John, chocolate)

Листинг 3.1. Два определения задач для обобщения на основе объяснения

% Для совместимости с некоторыми реализациями Prolog следующие предикаты % определены как динамические:

:- dynamic gives/3, would_please/2, would_comfort/2, feels_sorry_for/2,

go/3, move/2, move_list/2.

$ теория проблемной области, которая относится к теме вручения подарков

gives( Personl, ?erson2, Gift) :-

likes( Personl, Person2),

would_please( Gift, Person21.

 

gives( Personl, Persan2, Gift; :-

feels_sorry_for( Personl, Person2),

would_coinfort [ Gift, Person2) .

would_please( Gift, Person) :-

neecis( Person, Gift).

would_comfort( Gift, Person) :-

likes[ Person, Gift).

feels_sorry_for{ Personl, Person2) :-

likes ( Personl, Perso:i2) ,

sad{ Person2).

feels_sorry_for( Person, Person) :-

sad( Person;.

 

i Операционные предикаты

operational{ likes( _, _)).

operational( needs( _, _)) .

operati.cr.al ( sad [ _) ) .

 

II Пример проблемной ситуация

likes( John, annie).

likes( annie, John).

likes! John, chocolate;,

needs( annie, tennis_racket).

sad{ John).

% Еще одна теория проблемной  области, применяемая для описания движений .лифта

i go( Level, GoalLevel, Moves) если список движений Moves перевозит лифт с этажа Level на этаж GoalLevel

go! Level, GoalLevel, Moves) :-

move_list( Moves, Distance!,   % Список движений и пройденное расстояние

Distance -:- GoalLevel - Level.

move_list( [] , 0) .

move_list( [Movel | Moves], Distance + Distance1) :-

move_list( Moves, Distance),

move( Movel, Distancel).

move[ up, 1) .

move( down, -1) .

 

operational( A =:= B) .

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

gives ( John., John, chocolate) <==

    ( feels_sorry_for{ John, John) <== sad( John), % Джону стало жалко самого себя,

% поскольку ему грустно,

would_comfort{ chocolate, John) <== likes( John, chocolate) % и Джону будет $ приятно, поскольку он любит шоколад

Это доказательство может быть обобщено путем замены постоянных John иchocolate переменными следующим  образом:

gives( Person, Person, Thing! <== % Человек вручает себе какую-то вещь, если ( feels_soi:ry_for( Person, Person) <-- sad( Person), I человеку жалко себя,

% потому что ему грустно,

would^comfort( Thing, Person! <== likes[ Person, Thing) % и человеку будет

% приятно, поскольку  ему нравится эта вешь

)

В листинге 3.1 предикаты sad (грустит) и likes (любит) определены как операционные. Теперь может быть получено операционное определение предиката gives путем удаления из дерева доказательства всех узлов, кроме узлов, указанных как "операционные", и корневого узла. Это приводит к получению такого результата:

   

Таким образом, достаточное условие Condition для предиката gives ( Person, Person, Thing) состоит в следующем:

Condition « ( sad( Person), likes( Person, Thing))

Теперь это  новое определение можно ввести в первоначальную программу, как показано ниже.

asserta ( ( gives( Person, Person, Thing) :- Condition))

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

gives( Person, Person, Thing) :-

sad( Person) ,

likes( Person, Thing).

Благодаря обобщению  заданного экземпляра gives { John, John, chocolate) было сформировано определение (в операционных терминах) как один из общих случаев применения предиката gives для описания одного из способов самоутешения.

Проблемная область с  описанием движений лифта, приведенная в листинге 3.1, является немного более сложной, поэтому проведем с ней эксперименты после реализации метода EBG на языке Prolog. !!!Метод EBG можно запрограммировать как двухэтапный процесс: на первом этапе вырабатывается дерево доказательства для данного примера, а на втором это дерево доказательства обобщается и из него извлекаются "операционные узлы". Для этой цели можно применить описанный выше метаинтерпретатор, который формирует деревья доказательства. Но фактически эти два этапа не требуются. Более удобный способ состоит в том, чтобы откорректировать простой метаинтерпретатор, приведенный в листинге 3.1, таким образом, чтобы операции обобщения чередовались с операциями доказательства заданного экземпляра. Модифицированный подобным образом метаинтерпретатор, который реализует рассматриваемый метод EBG, будет именоваться ebg и теперь будет иметь три параметра:

ebg( Goal, GenGoal, Condition)

где Goal — заданный пример, который должен быть доказан, GenGoal —  обобщен- ная цель. Condition — полученное путем логического вывода достаточное  условие для GenGoal, сформулированное в терминах операционных предикатов. Такой обобщающий метаинтерпретатор приведен в листинге 3.2. Для проблемной области с описанием процесса получения подарков {см. листинг 3.1) метаинтерпретатор ebg может быть вызван следующим образом:

?- ebg( gives! John, John, chocolate), gives! X, Y, Z) , Condition].

x=Y

Condition - ( sacl( X), likes( X, Z))

Листинг 3.2. Программа обобщения на основе объяснения

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

Теперь можно  вызвать на выполнение программу ebg и получить результирующую обобщенную цель и ее условие следующим образом:

Результирующее новое предложение, касающееся предиката до, состоит в следующем:

go( Leveil, Level2, [ up. Up, up] ) :-

0 + 1 + 1 + 1 =-:- Level2 - Level 1.

С помощью метода EBG простая операция перемещения  лифта вверх на три этажа была обобщена как операция перемещения вверх между любыми двумя этажами, находящимися друг от друга на расстоянии в три этажа. Чтобы решить задачу по достижению цели до ( 3, 6, Moves), первоначальная программа выполняет поиск среди последовательностей действий по подъему (up) и спуску (down). А с помощью вновь выведенного предложения задача перемещения вверх с одного этажа на другой на расстояние в три этажа (например, до( 7, 10, Moves}) решается немедленно, без какого-либо поиска.

Метаинтерпретатор ebg, приведенный в листинге 3.2, снова является одной из производных простого метаинтерпретатора, показанного в листинге 2.1. Этот новый метаинтерпретатор вызывает встроенную процедуру copy_term. Вызов этой процедуры в форме

copy_term{ Term, Copy)

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

Последнее предложение  в процедуре ebg заслуживает дополнительного  поясне- ния. Вызов c l a u s e ! GenGoal, GenBody) обеспечивает выборку предложения, которое может использоваться для доказательства обобщенной цели. Это означает, что метаинтерпретатор фактически предпринимает попытку доказать обобщенную цель. Но следующая строка налагает некоторое ограничение на эту операцию:

copy_term( ( GenGoal, GenBody), I Goal, Body))

В ней предъявляется  требование, чтобы переменные GenGoal и Goal были согласованными. Согласование выполняется над копией GenGoai, поэтому переменные в этой общей цели остаются незатронутыми. Причина, по которой требуется такое согласование, состоит в том, что выполнение обобщенной цели должно ограничиваться такими альтернативными ветвями дерева доказательства (предложениями), которые являются применимыми для заданного примера (Goal). Благодаря этому выполнением обобщенной цели управляет сам пример. Подобное управление и составляет суть компиляции программы в стиле EBG. Без такого управления возникает вероятность того, что будет найдено такое доказательство для GenGoal, которое не применимо для Goal. В подобных случаях обобщение полностью не соответствует примеру.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ  ПРОГРАММИРОВАНИЕ

 

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

Чтобы ознакомиться с тем, как этот принцип практически осуществляется в системе Prolog, рассмотрим в качестве примера объектно-ориентированную программу, касающуюся геометрических фигур. Одним из объектов этой программы яв- ляется прямоугольник, а в состав данного объекта могут входить процедуры для описания прямоугольника и вычисления его площади. Если объекту прямоугольника передается сообщение area ( А) , он отвечает, вычисляя площадь прямоугольника, и переменная А становится конкретизированной значением этой площади. В рассмат- риваемой реализации объект будет представлен как отношение object[ Object, Methods)