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

% ebg{ Goal, GeneralizedGoal, SufficientCondition; если

достаточное условие SufficientCondition, заданное в терминах операционных % предикатов, гарантирует, что GeneralizedGoal, обобщениецели Goal, % является истинным. Обобщениецели GeneralizedGoal не должно быть задано с помошью переменной

ebg ( true, true, true) :- !.

еЬд( Goal, GenGoai, GenGoal) :-operational( GenGoal} , call)Goal) .

ebg( (Goall,Goal2) , (Genl,Gen2), Cond} :- !, ebg ( Goall, Gen]., Condi) , ebg( Goal2, Gen2, Cond2), and{ Condi, Cond2, Cond). * Cond = (Condi,CondZ) в упрощенном виде

(Goal,Body)), % Новая копия % терма [GenGoal,GenBody)

ebg( Goal, GenGoal, Cond) :-not operational! Goal) , clause! GenGoal, GenBody) , copy_term( [GenGoal,GenBody),

ebg( Body, GenBody, Cond) .

% and( Condi,CondH, Cond) если

I условие Cond представляет собой конъюнкцию условий Condi и Cond2

Ъ (возможно, з упрощенном виде)

and[ true,Cond, Cond) :- !. % [true and Cond) <==> Cond

and[ Cond, true,Cond,- :- !. % (Cond and true) <==> Cond.

cffl*f Condi , - COTid-2-; - f ■ Coud±/-етзпйЗ-г}--.-............................................................................... -

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

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

?- Goal - до{ 3, 6, Moves) , GenGoal -до( Levell, LeveI2, GenMoves), ebg( Goal, GenGoal, Condition), asserta( ( GenGoal :- Condition)). Goal = got 3, 6, [ up, up, up] ) GenGoal - go ( Levell , Level2, ( up, up, up]) Condition = (0+1 + 1 + 1=:= Level2 - Levell) Moves = [ up, up, up]



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

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

go( Leveil, Level2,[ up. Up, up] ) :-0 + 1 + 1 + 1 =-:- Level2 - Level 1.

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

Метаинтерпретатор ebg, приведенный в листинге 23.4, снова является одной из производных простого метаинтерпретатора, показанного в листинге 23.1. Этот новый метаинтерпретатор вызывает встроенную процедуру copyterm. Вызов этой процеду­ры в форме copy_term{ Term, Copy)

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

Последнее предложение в процедуре ebg заслуживает дополнительного поясне­ния. Вызов

clause! GenGoal, GenBody)

обеспечивает выборку предложения, которое может использоваться для доказатель­ства обобщенной цели. Это означает, что метаинтерпретатор фактически предприни­мает попытку доказать обобщенную цель. Но следующая строка налагает некоторое ограничение на эту операцию: copy_term( ( GenGoal, GenBody), I Goal, Body))

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

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

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



завершению. При компиляции программы с помощью метода EBG необходимо сле­дить за тем, чтобы новые предложения не вступали в противоречие с первоначаль­ными предложениями неконтролируемым способом.

Упражнение

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

Наши рекомендации