Эффективная реализация логических программ
Подготовка программ Prolog к выполнению может осуществляться в двух режимах: интерпретация и компиляция. Интерпретация по существу представляет собой применение алгоритма FOL-BC-Ask, приведенного в листинге 9.3, к программе, представленной в виде базы знаний. Предыдущее предложение включает слова "по существу", поскольку в интерпретаторах Prolog предусмотрены всевозможные усовершенствования, предназначенные для максимального повышения скорости работы. Здесь рассматриваются только два таких усовершенствования.
Во-первых, вместо формирования списка всех возможных ответов для каждой подцели перед переходом к следующей подцели интерпретаторы Prolog вырабатывают один ответ и "дают обещание" выработать остальные после того, как будет полностью исследован текущий ответ. Такое "обещание" оформляется как точка выбора (choice point). После того как в процессе поиска в глубину завершается исследование возможных решений, вытекающих из текущего ответа, и происходит возврат к точке выбора, в этой точке используемые структуры данных дополняются, чтобы в них можно было включить новый ответ для данной подцели и сформировать новую точку выбора. Такой подход позволяет экономить и время, и пространство, а также обеспечивает создание очень простого интерфейса для отладки, поскольку постоянно существует лишь единственный путь решения, подлежащий рассмотрению.
Во-вторых, в приведенной в данной главе простой реализации алгоритма FOL-BC-Ask много времени затрачивается на выработку и компоновку подстановок. В языке Prolog подстановки реализуются с использованием логических переменных, позволяющих сохранить в памяти их текущее связывание. В любой момент времени каждая переменная в программе является либо несвязанной, либо связанной с некоторым значением. Эти переменные и значения, вместе взятые, неявно определяют подстановку для текущей ветви доказательства. Любая попытка продления пути позволяет лишь добавить новые связывания переменных, поскольку стремление ввести другое связывание для уже связанной переменной приводит к неудачному завершению унификации. После того как попытка продления пути поиска оканчивается неудачей, система Prolog возвращается к предыдущей точке выбора и только после этого получает возможность отменить связывания некоторых переменных. Такая операция отмены выполняется благодаря тому, что данные обо всех переменных, для которых было выполнено связывание, отслеживаются в стеке, называемом контрольным стеком (trail). По мере того как в функции Unify-Var осуществляется связывание каждой новой переменной, эта переменная задвигается в контрольный стек. Если попытка достижения некоторой цели оканчивается неудачей и наступает время возвратиться к предыдущей точке пункта выбора, отменяется связывание каждой из этих переменных по мере их выталкивания из контрольного стека.
Но даже в самых эффективных интерпретаторах Prolog, в связи с издержками на поиск по индексу, унификацию и формирование стека рекурсивных вызовов, требуется выполнение нескольких тысяч машинных команд в расчете на каждый этап логического вывода. В действительности интерпретатор постоянно ведет себя так, как если бы он никогда до сих пор не видел данную программу; например, ему приходится каждый раз находить выражения, которые согласуются с целью. С другой стороны, откомпилированная программа Prolog представляет собой процедуру логического вывода для конкретного множества выражений, поэтому ей известно, какие выражения согласуются с целью. В процессе компиляции система Prolog по сути формирует миниатюрную программу автоматического доказательства теоремы для каждого отдельного предиката, устраняя тем самым основную часть издержек интерпретации. Эта система позволяет также применять открытый код для процедуры унификации каждого отдельного вызова, что позволяет избежать необходимости проведения явного анализа структуры терма (подробные сведения об унификации с открытым кодом приведены в [1557]).
Наборы команд современных компьютеров плохо согласуются с семантикой Prolog, поэтому большинство компиляторов Prolog компилирует программу в промежуточный язык, а не непосредственно в машинный язык. Наиболее широко применяемым промежуточным языком является язык WAM (Warren Abstract Machine — абстрактная машина Уоррена) получивший название в честь Дэвида Г.Д. Уоррена, одного из создателей первого компилятора Prolog. Язык WAM представляет собой абстрактное множество команд, которое подходит для преобразования в него программ Prolog и может интерпретироваться или транслироваться в машинный язык. Другие компиляторы транслируют программу Prolog в программу на языке высокого уровня, таком как Lisp или С, а затем используют компилятор этого языка для трансляции в машинный язык. Например, определение предиката Append может быть откомпилировано в код, показанный в листинге 9.4. Ниже приведено несколько замечаний, заслуживающих упоминания в этой связи.
Листинг 9.4. Псевдокод, представляющий собой результат компиляции предиката Append. Функция New-Variable возвращает новую переменную, отличную от всех других переменных, использовавшихся до сих пор. Процедура Call (continuation) продолжает выполнение с заданным продолжением continuation
procedure Append(ах, у, az, continuation) trail <— Global-Trail-Pointer()
if ax = [] and Unify(y, az) then Call{continuation) Reset-Trail(trail)
• Выражения предиката Append преобразуются в процедуру, а этапы логического вывода осуществляются путем вызова этой процедуры, поэтому не приходится выполнять поиск соответствующих выражений в базе знаний.
• Как было описано выше, текущие связывания переменных хранятся в контрольном стеке. На первом этапе выполнения этой процедуры текущее состояние контрольного стека сохраняется в памяти, поэтому оно может быть восстановлено с помощью функции Reset-Trail, если попытка выполнения первого выражения окончится неудачей. Это приводит к отмене всех связываний, сформированных при первом вызове процедуры Unify.
• Сложнейшей частью этой программы является использование продолжений для реализации точек выбора. Продолжение может рассматриваться как структура данных, в которой упакованы процедура и список параметров, вместе взятые, определяющая, что следует делать дальше, после успешного достижения текущей цели. Дело в том, что после достижения цели не было бы достаточно просто возвратить управление из процедуры, подобной Append, поскольку успех может быть достигнут несколькими способами, и каждый из них должен быть исследован. Параметр continuation, определяющий продолжение, позволяет решить эту проблему, поскольку он может быть вызван после каждого успешного достижения цели. В приведенном здесь коде процедуры Append, если первый параметр является пустым, то предикат Append достиг успеха. Затем вызывается продолжение с помощью процедуры Call (притом что в контрольном стеке находятся все подходящие связывания) для того, чтобы определить, что делать дальше. Например, если процедура Append вызвана на верхнем уровне дерева доказательства, то структура данных continuation будет использоваться для вывода информации о связывании переменных.
До того как Уоррен выполнил свою работу по внедрению компиляции в системы логического вывода на языке Prolog, средства логического программирования работали слишком медленно для того, чтобы они действительно могли найти широкое применение. Компиляторы, разработанные Уорреном и другими специалистами, позволили достичь скоростей обработки кода Prolog, способных конкурировать с языком С в самых различных стандартных эталонных тестах [1536]. Безусловно, тот факт, что теперь появилась возможность написать планировщик или синтаксиче-
a <— New-Variable () ; x <— New-Variable () ; z <— New-Variable () if Unify(ax, [a | x]) and Unify(az, [a | z]) then Append(x, y, z, continuation)
ский анализатор текста на естественном языке, состоящий из нескольких десятков строк на языке Prolog, говорит о том, что этот язык становится более подходящим (по сравнению с языком С) для создания прототипов большинства исследовательских проектов в области искусственного интеллекта небольших масштабов.
Значительное повышение скорости позволяет также обеспечить распараллеливание работы. Организация параллельного выполнения может осуществляться по двум направлениям. Первое направление, получившее название ИЛИ-параллелизма, исходит из возможности унификации цели со многими различными выражениями в базе знаний. Каждая из этих операций унификации приводит к появлению независимой ветви в пространстве поиска, которая может привести к потенциальному решению, и поиск решений по всем таким ветвям может осуществляться параллельно. Второе направление, называемое И-параллелизмом, исходит из возможности параллельного решения каждого конъюнкта в теле некоторой импликации. Задача достижения И-параллелизма является более сложной, поскольку для поиска решений всей конъюнкции требуются совместимые связывания для всех переменных. Поэтому при обработке каждой конъюнктивной ветви необходимо обеспечивать обмен данными с другими ветвями для гарантированного достижения глобального решения.