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

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

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

prove( Coal)

Как показано ниже, простейший метаинтерпретатор Prolog является тривиальным. prove [ GoalJ :-call( Goal] .

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

Часть II. Применение языка Prolog в области искусственного интеллекта

возможным благодаря наличию следующего встроенного предиката, предусмотренно­го во многих реализациях Prolog: clause( Head, Body)

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

В этом терме запятая представляет собой встроенный инфиксный оператор. В стандартной системе обозначений Prolog эту пару можно заменить следующим эк­вивалентным термом: ,( FirstGoal, OtherGoals}

где OtherGoals может в свою очередь представлять собой пару, состоящую еще из одной цели и оставшихся целей. В вызове clause { Head, Body) первый параметр Head не должен быть переменной. Предположим, что программа, применяемая для консультации, содержит обычную процедуру member. В таком случае выборка пред­ложений процедуры member может быть выполнена таким образом:

?- clause( member(X, L), Body).

X =14

L = \JLA | 15]

Body =.true;

X = 14

L = [_15I 16]

Body= member{ _14, _16)

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

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

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

prove( true).

prove( ( Goall, Goal2)) :-prove{ Goall), prove( Goal2).

prove( Goal) :-

clause( Goal, Body), prove( Body) .

Глава 23. Метапрограммировэние 561

Упражнения

23.1. Что произойдет при попытке вызвать на выполнение с помощью метаинтер­
претатора, приведенного в листинге 23.1, сам этот метаинтерпретатор, напри­
мер, следующим образом:

?- prove[ prove! memberf X, [ a, b, с] ) ))-

При такой попытке возникает проблема, поскольку данный метаинтерпретатор не может выполнять встроенные предикаты, такие как clause. Каким образом можно легко модифицировать этот метаинтерпретатор, чтобы он приобрел спо­собность вызывать сам себя на выполнение, как в приведенном выше запросе?

23.2, Модифицируйте метаинтерпретатор, приведенный в листинге 23.1, ограничив
глубину поиска доказательства системой Prolog. Предположим, что модифи­
цированный метаинтерпретатор представляет собой предикат prove [ Goal,
DepthLimit), который достигает успеха, если DepthLimit £ 0. Каждый ре­
курсивный вызов уменьшает этот предел.