Листинг 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, пред­ставляют собой обобщение заданных примеров и поэтому не обязательно экви­валентны первоначальной программе (определения нового понятия могут быть неполными).