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

 

ВВЕДЕНИЕ

 

Пролог - это  язык, предназначенный для поиска решений. Это декларативный язык, то есть формальное определение  (постановка)  задачи может  быть использовано для ее решения. Пролог определяет логические отношения в задаче, как отличные от пошагового решения этой задачи.

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

Благодаря наличию в языке  Prolog возможностей по манипулированию символами он является мощным средством реализации других языков и принципов программирования.

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

В данной работе показано, как можно создать метаинтерпретаторы Prolog — интерпретаторы языка Prolog на самом языке Prolog. Здесь рассматривается специальный метод компиляции программ, называемый обобщением на основе объяснения, который был разработан как один из подходов к машинному обучению. Кроме того, описаны простые интерпретаторы для двух других подходов к программированию: объектно-ориентированное программирование и программиро- вание, управляемое шаблонами.

1 МЕТАПРОГРАММЫ И МЕТАПРОГРАММИРОВАНИЕ

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

Благодаря наличию  в языке Prolog возможностей по манипулированию символами он является мощным языком, который может успешно применяться для метапрограммирования. Поэтому он часто служит в качестве языка реализации для других языков. Многие специалисты отмечают, что Prolog особенно хорошо подходит для использования: в качестве языка быстрой разработки прототипов в тех ситуациях, когда требуется как можно быстрее воплотить в жизнь новые идеи. Это особенно важно в тех случаях, когда возникает необходимость разработать новый язык, осуществить на практике новый принцип программирования или опробовать вновь созданную архитектуру программы. Этот язык позволяет быстро реализовывать новые идеи и проводить эксперименты. При разработке прототипов основное внимание уделяется тому, чтобы новые идеи оформлялись в виде экспериментального образца максимально быстро и с наименьшими затратами, благодаря чему можно было бынемедленно приступать к их проверке. С другой стороны, особое значение повыше- нию эффективности такой реализации не придается. После проверки первоначального замысла прототип может быть реализован повторно, для чего можно воспользоваться другим, более эффективным языком программирования. И даже если потребуется отказаться от прототипа на языке Prolog в пользу другого языка, все равно усилия, затраченные на разработку этого прототипа, не будут напрасными, поскольку он обычно позволяет ускорить творческий этап разработки.

 

2 МЕТАИНТЕРПРЕТАТОРЫ Prolog

2.1 Простейший метаинтерпретатор Prolog

 

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

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

prove( Goal) Как показано ниже, простейший метаинтерпретатор Prolog является тривиальным.

prove [ GoalJ :- call( Goal] .

В данном случае вся работа метаинтерпретатора была передана (с  помощью предиката call) оригинальному интерпретатору Prolog, поэтому такой метаинтерпретатор ведет себя точно так же, как и сам интерпретатор Prolog. Безусловно, что такой вариант метаинтерпретатора не имеет никакого практического значения, поскольку он не предоставляет какие-либо дополнительные возможности. Для того чтобы обеспечить реализацию таких важных средств метаинтерпретатора, как формирование деревьев доказательства, прежде всего необходимо уменьшить "степень детализации" этого интерпретатора, чтобы он мог обрабатывать не только всю программу, но и ее компоненты. Такое уменьшение степени детализации метаинтерпретатора становится возможным благодаря наличию следующего встроенного предиката, предусмотренного во многих реализациях Prolog:

c l a u s e ( Head, Body)

Этот предикат осуществляет "выборку" любого предложения  из программы, применяемой для консультации. Здесь Head — голова предложения, извлеченного из базы данных, a Body — его тело. Для единичного предложения (факта) параметр Body = t r u e . В неединичном предложении (правиле) тело может содержать одну или несколько целей. Если оно содержит одну цель, то Body и есть эта цель. Если тело содержит несколько целей, то их выборка осуществляется в виде следующей пары: Body = ( FirstGoal, OtherGoals)

В этом терме запятая представляет собой встроенный инфиксный оператор. В стандартной системе обозначений Prolog эту пару можно заменить следующим эквивалентным термом: ,( FirstGoal, OtherGoals} где OtherGoals может в свою очередь представлять собой пару, состоящую еще из одной цели и оставшихся целей. В вызове c l a u s e {Head, Body) первый параметр Head не должен быть переменной. Предположим, что программа, применяемая для консультации, содержит обычную процедуру member. В таком случае выборка предложений процедуры member может быть выполнена таким образом:

?- clause( member(X, L), Body). X =_14 L = \JLA | _15] Body = true;

X = _14 L = [_15 I _16] Body = member{ _14, _16)

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

Листинг 2.1.1, Простой метаинтерпретатор Prolog

 

 

 

2.2 Трассировка с помощью метаинтерпретатора

 

Ниже приведен результат первой попытки расширить простой метаинтерпретатор, приведенный в листинге 2.1.1, чтобы создать интерпретатор, обеспечивающий трассировку.

В данном случае операторы отсечения  требуются для предотвращения необходимости  отображать "истинные" (true) и составные цели в форме ( Goall, Goal2). Эта программа трассировки имеет несколько недостатков: она не обеспечивает трассировку недостигнутых целей и не показывает результатов перебора с возвратами, когда повторно выполняется одна и та же цель. В этом отношении программа трассировки, приведенная в листинге 2.2.1, является более совершенной. Кроме того, для удобства чтения отображаемые цели обозначаются в ней отступами, пропорционально той глубине логического вывода, на которой они вызываются. Но и этот метаин- терпретатор все еще ограничивается чистым языком Prolog. Пример вызова рассматриваемой программы трассировки приведен ниже.

?- trace ( ( member! У-, I a, b]) , member! X, [ Ь, с] ) ) ) .

Call: ir.ember( _00B5, [a, b] )

  Call: member( a, t b, c])

Call: member(a, [ c]}

Call: member[a, [ ] }

Fail: member[a, [])

Fail: member(a, [ c])

Fail: member[ a, [ b, c])

Redo: member( a, [ a, b])

Call: member! _00S5, [ b))

Exit: member[ b, [ b])

Exit: member( b, | a, b]]

Call: member! b, [ b, с]]

Exit: member! b, [ b, c])

Ъ trace! Goal): выполнить цель Goal, которая определена в программе Prolog, к и вывести информацию трассировки

trace(Goal) :-

trace! Goal, 0) .

trace( true, Depth) :- !. % Красный оператор отсечения; Depth - глубина вызова

trace( ( Goall, Goal2), Depth) :- !,

trace! Goall, Depth;,                     % Красный оператор отсечения

trace! Goal2, Depth).

trace] Goal, Depth; :-

display! 'Call: ', Goal, Depth),

clause! Goal, Body),

Depthl is Depth + 1,

trace( Body, Depthl),

display! 'Exit: ', Goal, Depth),

display_redo( Goal, Depth).

t r a c e ! Goal, Depth) :-     % Бее альтернативные варианты исчерпаны

display! 'Fail: ', Goal, Depth),

fail.

display! Message, Goal, Depth) :-

tab( Depth), writet Message),

write( Goal), nl.

display_redo( Goal, Depth) :-

true                                      %   Достижение первой цели оказалось несложным

display! 'Redo: ', Goal, Depth), % Затем вывести сообценме о том,

% что начинается переоор  с возвратами,

fail.        % и вынудить систему выполнить перебор

% с возвратами

Эта программа  трассировки выводит описанную  ниже информацию для каждой выполняемой цели.

1. Цель, которая должка  быть выполнена (Call: Goal).

2. Трассировка подцелей  (с отступами).

3. Если цель достигается, то отображается ее окончательная конкретизация (Exit: Instar.tiatedGoal); если цель не достигается, то отображается результат F a i l : Goal.

4. В случае  перебора с возвратами к ранее  достигнутым целям сообщение  принимает вид Redo: InstantiatedGoal (конкретизация этой цели в предыдущем решении).

Безусловно, существует возможность продолжить доработку  этого трассирующего интерпретатора в соответствии с конкретными  требованиями пользователей.

 

 

2.3 Формирование деревьев доказательства

Еще одним широко известным расширением простого интерпретатора, приведенного в листинге 1.1, является формирование деревьев доказательства. Поэтому после достижения некоторой цели вырабатывается дерево ее доказательства, которое может служить для дальнейшей обработки. Формирование деревьев доказательства реализовано для экспертных систем на основе правил. Хотя синтаксис этих правил отличается от синтаксиса Prolog, принципы формирования дерева доказательства остаются одинаковыми. Эти принципы можно легко реализовать в метаинтерпретаторе, приведенном в листинге 1.1. Например, предположим, что можно представить дерево доказательства в зависимости от конкретного случая, как описано ниже.

1. Для цели t r u e деревом доказательства является t r u e .

2. Для пары целей [ Goall, Goal2) деревом доказательства является пара ( Proof I, Proof 2), состоящая из деревьев доказательства этих двух целей.

3. Для цели Goal, согласующейся с головой предложения, телом которого является Body, деревом доказательства служит Goal <= Proof, где Proof — дерево доказательства Body.

Эти требования можно реализовать в простом  метаинтерпретаторе, приведенном в листинге 2.1.1, следующим образом:

:- ор( 500, xfy, <==).

prove[ true, true).

prove{ ( Goall, Goal2), ( Proofl, Proof2)) :-

prove( Goall, Proofl),

prove ( Goal2, Proof2) .

prove( Goal, Goal <== Proofl :-

clause( Goal, Body),

prove[ Body, Proof),

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 ОБОБЩЕНИЕ НА ОСНОВЕ ОБЪЯСНЕНИЯ

 

Идея обобщения  на основе объяснения впервые была реализована в области машинного обучения, целью которого является обобщение заданных примеров в виде общих описаний рассматриваемых понятий. Одним из способов формирования таких описаний является обобщение на основе объяснения (Explanation-Based Generalization — EBG), при котором обычно используется только один пример. Малое количество примеров компенсируется за счет применения в системе фоновых знаний, которые, как правило, именуются теорией проблемной области.

Способ EBG основан на использовании при формировании обобщенных описаний следующей идеи: если дан некоторый экземпляр целевого понятия, то можно воспользоваться теорией проблемной области для объяснения того, как этот экземпляр фактически удовлетворяет данному понятию. Затем анализируется это объяснение и предпринимается попытка обобщить его таким образом, чтобы оно подходило не только для заданного экземпляра, но и для множества "аналогичных" экземпляров. Затем такое обобщенное объяснение становится частью описания рассматриваемого понятия и может в дальнейшем использоваться при распознавании экземпляров этого понятия. Кроме того, требуется, чтобы формируемое описание понятия было операционным; это означает, что оно должно быть сформулировано в терминах понятий, объявленных пользователем как операционные. Интуитивно можно себе представить, что описание понятия является операционным (определяющим некоторую операцию), если его можно (относительно) легко использовать на практике. Задача определения того, что подразумевается под словом "операционный", полностью возлагает- ся на пользователя.