Часть 6.

LISP из простой и элегантной теоретической модели вычислений в богатую, мощную среду для построения больших программных систем. Из-за быстрого разрастания ранних диалектов LISP агентство защиты новейших исследовательских проектов Defense Advanced Research Projects Agency в 1983 году предложило стандартный диалект, получив­ший название Common LISP.

Хотя Common LISP появился как квинтэссенция диалектов LISP, широкое распространение получили другие многочисленные диалекты. Один из них - SCHEME - эле­гантное переосмысление LISP, используемое как для решения задач искусственного ин­теллекта, так и для изучения общих фундаментальных принципов программирования. В данной книге будет использован именно Common LISP.

Выбор языка реализации

Искусственный интеллект сформировался как отдельная область знаний и продемонстрировал свою применимость для решения многих практических задач на основе язы­ков LISP и PROLOG. Однако в последнее время удельный вес этих языков при решении задач искусственного интеллекта несколько снизился. Это объясняется требованиями к разработке программных систем. Системы искусственного интеллекта зачастую служат модулями других больших приложений, поэтому стандарты разработки приводят к необ­ходимости использования единого языка программирования всего приложения. Совре­менные системы искусственного интеллекта реализуют на многих языках, включая Smalltalk, С, C++ и Java. Тем не менее LISP и PROLOG продолжают играть свою роль в разработке прототипов программ и новых методов решения задач.

Кроме того, эти языки служат для обоснования многих средств, которые впоследствии включаются в современные языки программирования. Наиболее ярким примером является язык Java, в котором используются динамическое связывание, автоматическое управление памятью и другие средства, впервые реализованные в языках программирования задач ис­кусственного интеллекта. Создается впечатление, что весь остальной мир программирова­ния до сих пор пытается перенять стандарты от языков реализации искусственного интел­лекта. С этой точки зрения ценность LISP, PROLOG или Smalltalk со временем будет неук­лонно повышаться. Автор уверен, что эти языки пригодятся читателю, даже если впоследствии он найдет свое место в C++, Java или любом другом конкурирующем языке.

608 Часть VI. Языки и технологии программирования для искусственного интеллекта

Введение в PROLOG

Все объекты человеческих размышлений и исследований естественным образом можно разделить на два вида: "связи идей " и "сущность фактов ".

- Дэвид Хьюм (David Hume), К вопросу о человеческом разуме

Единственный способ улучшить наши рассуждения - это сделать их столь же осязаемыми, как математические формулы, чтобы уметь найти ошибку с одного взгляда и иметь возможность в споре с оппонентами просто сказать: "Давайте посчитаем... и посмотрим, кто из нас прав".

- Лейбниц (Leibniz), Искусство открытия

14.0. Введение

Как реализация принципов логического программирования язык PROLOG вносит интересный и существенный вклад в решение задач искусственного интеллекта. Наиболее важное значение имеет декларативная семантика (declarative semantics) - средство прямого выражения взаимосвязей в задачах искусственного интеллекта, а также встро­енные средства унификации и некоторые приемы проверки соответствия и поиска. В этой главе будут затронуты многие важные вопросы логического программирования и организации языка PROLOG.

В разделе 14.1 представлены базовый синтаксис языка PROLOG и несколько простых программ, демонстрирующих использование исчисления предикатов в качестве языка представления. Будет показано, как отслеживать состояние среды PROLOG и использовать оператор отсечения (cut operator) для реализации поиска в глубину на языке PROLOG.

В разделе 14.2 рассматривается вопрос создания абстрактных типов данных (АТД) (abstract data types - ADT) на языке PROLOG. К ним относятся стеки (stack), очереди (queue) и приоритетные очереди (priority queue), используемые для построения продукционной системы в разделе 14.3 и разработки в разделе 14.3 управляющих структур для алгоритмов поиска, описанных в главах 3, 4, 6. В разделе 14.5 по материалам раздела 7.4 разрабатывается планировщик (planner). В разделе 14.6 вводится понятие метапредика-тов (meta-predicate) - предикатов, область интерпретации которых составляют сами выражения языка PROLOG. Например, выражение atom(X) является истинным, если X - это атом, т.е. константа. Метапредикаты можно использовать для наложения огра­ничения типов при интерпретации программы на языке PROLOG. В разделе 14.7 мета­предикаты используются для построения метаинтерпретаторов (meta-interpreter) на

языке PROLOG, которые, в свою очередь, применяются для создания интерпретаторов языка PROLOG, а также для построения интерпретаторов цепочек правил.

В разделе 14.8 иллюстрируется применение языка PROLOG для машинного обучения. В качестве примеров рассматривается поиск в пространстве версий и обучение на основе объяснения из главы 9. В разделе 14.9 строится рекурсивный анализатор на основе семантических сетей, принципы работы которого изложены в главе 13. В завершение обсуждаются общие вопросы процедурного и логического программирования, а также отличия этих подходов от декларативных методов решения задач.

14.1. Синтаксис для программирования логики предикатов

14.1.1. Представление фактов и правил

Несмотря на существование многочисленных диалектов языка PROLOG, в этой книге используется исходная версия языка C-PROLOG, разработанная Уорреном (Warren) и Перейрой (Pereira) [Clocksin и Mellish, 1984]. Чтобы упростить представление данных на языке PROLOG, при описании логики предикатов в главе 2 используются многие соглашения, принятые в этом языке. Однако существуют многочисленные отличия синтаксиса логики предикатов от языка PROLOG. Например, в C-PROLOG символ : - соответствует символу ¬ логики предикатов первого порядка. Приведем еще несколько отличий синтаксиса PROLOG от обозначений, используемых в главе 2.

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

likes(X, susie).

или, еще лучше,

likes(Everyone, susie).

может представлять тот факт, что "каждый любит Сьюзи". Или likes(george, Y), likes(susie, Y).

представляет множество людей, которых любят Джордж и Сьюзи.

Допустим, на языке PROLOG необходимо представить следующее отношение: "Джордж любит Кейт и Джордж любит Сьюзи". Его можно записать в виде

likes(george, kate), likes(george, susie).

Таким образом, "Джордж любит Кейт или Джордж любит Сьюзи" можно представить так:

likes(george, kate); likes(george, susie).

610 Часть VI. Языки и технологии программирования для искусственного интеллекта

И, наконец, "Джордж любит Сьюзи, если Джордж не любит Кейт" описывается так

likes(george, susie) : - not(likes(george, kate)).

Из этих примеров видно, как связки ^, v, ¬ и ¬ из логики предикатов представляют­ся на языке PROLOG. Имена предикатов (наподобие likes), количество и порядок следования параметров и даже постоянное или переменное число параметров определяются требованиями (неявной "семантикой") конкретной задачи. В этом языке программирования не существует никаких ограничений, кроме требования правильного построения формул.

Программа на языке PROLOG - это набор спецификаций из логики предикатов первого порядка, описывающих объекты и отношения между ними в предметной области задачи. На­бор спецификаций называется базой данных (database) конкретной задачи. Интерпретатор PROLOG отвечает на вопросы, касающиеся этого набора спецификаций. Запросы к базе дан­ных - это шаблоны, представленные в том же логическом синтаксисе, что и записи базы данных. Интерпретатор PROLOG использует поиск на основе шаблонов для определения то­го, являются ли эти запросы логическим следствием содержимого базы данных.

Интерпретатор обрабатывает запросы, выполняя поиск в базе данных в глубину слева направо и определяя, является ли данный запрос логическим следствием спецификаций из базы данных. PROLOG- это в основном интерпретируемый язык. Некоторые версии языка PROLOG работают только в режиме интерпретации, другие допускают компиляцию части или всего набора спецификаций для ускорения выполнения программы. PROLOG - это ин­терактивный язык: пользователь вводит запросы в ответ на приглашение ? -.

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

likes(george, kate). likes(george, susie). likes(george, wine). likes(susie, wine). likes(kate, gin), likes(kate, susie).

Этот набор спецификаций имеет очевидную интерпретацию или отображение на "мир" Джорджа и его друзей. Этот мир является моделью для базы данных (раздел 2.3). Затем интерпретатору можно задавать вопросы

?- likes(george, kate).

Yes

?- likes(kate, susie).

Yes

?- likes(george, X).

X = kate

;

X = Susie

; X = wine

?- likes(george, beer).

no

Отметим несколько моментов в этих примерах. Во-первых, при обработке запроса likes (george, X) пользователь последовательно вводит приглашение ;, поэтому интерпретатор возвращает все термы из спецификации базы данных, которые можно

Глава 14. Введение в PROLOG 611

подставить вместо X. Они возвращаются в том порядке, в котором были найдены в базе данных: сначала kate, затем susie и наконец wine. Хотя это противоречит филосо­фии непроцедурных спецификаций, детерминированный порядок - это свойство большинства интерпретаторов, реализованных на последовательных машинах. Программист на языке PROLOG должен знать порядок поиска элементов в базе данных.

Заметим также, что последующие ответы на запрос выдаются после пользовательского приглашения ; (или). При этом происходит возврат к последнему найденному резуль­тату. Последовательные приглашения приводят к нахождению всех возможных ответов на запрос. Если решений больше не существует, интерпретатор выдает ответ по.

Приведенные выше примеры также иллюстрируют допущение замкнутости мира (closed world assumption) или отрицание как ложь (negation as failure). В языке PROLOG предполага­ется, что любое выражение является ложным, если нельзя доказать истинность его отрицания. При обработке запроса likes (george, beer) интерпретатор ищет предикат likes (george, beer) или некоторое правило для получения likes (деогде, beer). Поскольку поиск не завершается успехом, запрос считается ложным. Таким образом, в языке PROLOG предполагается, что все знания о мире представлены в базе данных.

Допущение замкнутости мира приводит к многочисленным практическим и философским сложностям в языке. Например, невозможность включить некоторый факт в базу данных зачастую означает, что его истинность неизвестна. Однако в силу допущения замкнутости мира этот факт трактуется как ложный. Если некоторый предикат был упу­щен или при его вводе была допущена опечатка наподобие likes (george, beer), то ответом на данный запрос будет по. Аспект трактовки отрицания как лжи - очень важный вопрос в области искусственного интеллекта. Хотя это предположение обеспе­чивает простой способ решения проблемы незаданных знаний, более сложные подходы, в том числе многозначные логики (истина, ложь, неизвестно) и немонотонные рассужде­ния (см. главу 9) обеспечивают гораздо более богатый контекст для интерпретации.

Выражения PROLOG, использованные в приведенной выше базе данных, являются примерами спецификации фактов (fact). PROLOG также позволяет определять правила (rule), описывающие взаимосвязи между фактами с использованием логической импликации : -. При создании правила на языке PROLOG слева от символа -. - может распола­гаться только один предикат. Этот предикат должен быть положительным литералом (positive literal), т.е. не должен представлять собой символ с отрицанием (раздел 12.3). Все выражения логики предикатов, содержащие отношения импликации или эквива­лентности (?, ? и ?), должны быть приведены к этой форме, которая получила назва­ние хорновской (Horn clause). В хорновской дизъюнктивной форме в левой части импли­кации (заключении) должен содержаться единственный положительный литерал. Логика хорновских дизъюнктов (Horn clause calculus) эквивалентна полной теории предикатов первого порядка, применяемой для доказательств на основе опровержения (см. главу 12).

Допустим, к спецификациям приведенной выше базы данных требуется добавить правило, определяющее двух друзей. Его можно описать следующим образом.

friends(X, Y) : - likes(X, Z) , likes(Y, Z) .

Это выражение можно интерпретировать так. "X и V - друзья, если существует такое Z, что X любит Z и Y любит Z". Здесь важно отметить два момента. Во-первых, посколь­ку ни в логике предикатов, ни в самом языке PROLOG не определены глобальные пере­менные, то шкала (область определения) переменных X, Y и Z ограничена правилом friends. Во-вторых, переменные, унифицируемые или связываемые с X, Y и Z, согла-

612 Часть VI. Языки и технологии программирования для искусственного интеллекта

сованы по всему выражению. Обработку правила friends интерпретатором языка PROLOG можно проиллюстрировать на следующем примере.

Если к набору спецификаций из предыдущего примера добавлено правило friends, то интерпретатору можно передать запрос.

?- friends(george, susie). yes

Для ответа на этот запрос PROLOG осуществляет поиск в базе данных с помощью алгоритма с возвратом, представленного в главах 3 и 5. Запрос friends (george, susie) унифицируется (проверяется на соответствие) с заключением правила friends(X, Y) :- likes(X, Z) , likes(Y, Z). При этом переменной X соот­ветствует значение george, а У - susie. Интерпретатор ищет значение переменной Z, для которого выражение likes (george, Z) истинно. Это выполняется с помощью первого факта в базе данных, в котором Z соответствует kate.

Затем интерпретатор пытается определить, истинно ли выражение likes (susie, kate). Если оно окажется ложным, то на основе допущения замкнутости мира данное значение для Z (kate) отклоняется. Тогда интерпретатор возвращается для поиска вто­рого значения Z в выражении 1 ikes (george, Z).

Затем проверяется соответствие выражения likes (george, Z) второму дизъюнк­ту в базе данных, при этом переменная Z связывается со значением susie. После этого интерпретатор пытается найти соответствие для выражения likes (susie, susie). Если эта попытка тоже завершается неудачей, то интерпретатор снова переходит к базе данных (возвращается) в поисках следующего значения для Z. На этот раз в третьем пре­дикате будет найдено значение wine, и интерпретатор постарается показать, что likes (susie, wine) истинно. В данном случае значение wine является связкой для значений george и susie. Интерпретатор PROLOG проверяет соответствие целей шаблонам в том порядке, в котором эти шаблоны были введены в базу данных.

Важно отметить взаимосвязь между кванторами всеобщности и существования в логике предикатов и обработкой переменных в программе PROLOG. Если переменная со­держится в спецификации базы данных PROLOG, то предполагается, что она связана квантором всеобщности. Например, выражение likes (susie, У) согласно семантике предыдущих примеров означает "Сьюзи любит каждого". В процессе интерпретации некоторого запроса любой терм, список или предикат может быть связан с У. Аналогично в правиле friends (X, У) :- likes (X, Z) , likes (У, Z) допускаются любые связанные переменные X, У и Z, удовлетворяющие спецификации этого выражения.

Для представления на языке PROLOG переменной, связанной квантором существования, можно использовать два подхода. Во-первых, если известно конкретное значение переменной, то его можно ввести в базу данных напрямую. Так, likes (george, wine) - это экземпляр выражения likes (george, Z), и его можно ввести в базу данных, как это было сделано в предыдущих примерах.

Во-вторых, для поиска экземпляра переменной, доставляющего выражению значение "истина", можно обратиться с запросом к интерпретатору. Например, чтобы определить, существует ли такое значение Z, при котором выражение likes (george, Z) истинно, этот запрос можно передать интерпретатору. Он проверит, существует ли такое значение переменной Z. Некоторые интерпретаторы PROLOG находят все значения, связанные квантором существования. Для получения всех значений с помощью интерпретатора C-PROLOG требуется повторять пользовательское приглашение ;.

Глава 14. Введение в PROLOG 613

14.1.2. Создание, изменение и мониторинг среды PROLOG

При написании программы на языке PROLOG сначала создается база данных спецификации. Для добавления новых предикатов к спецификации в интерактивной среде применяется предикат assert. Так, с помощью команды

?- assert(likes(david, sarah))

к спецификации добавляется предикат likes (david, sarah). Теперь в ответ на запрос

?- likes(david, X).

будет возвращен результат

X = sarah.

С помощью предиката assert можно контролировать добавление новых специфи­каций в базу данных. Предикат asserta (Р) добавляет предикат Р в начало списка пре­дикатов с именем Р, a assertz (Р) - в конец списка предикатов Р. Это важно для по­строения иерархии и выбора приоритетов поиска. Для удаления предиката Р из базы данных используется предикат retract (Р). Следует отметить, что во многих реализа­циях языка PROLOG предикат assert ведет себя более непредсказуемо, т.е. точное время добавления нового предиката в среду может зависеть от многих других факторов, влияющих как на порядок следования предикатов, так и на реализацию возвратов.

Создание спецификации путем последовательного использования предикатов as­sert и retract- очень утомительный процесс. Вместо этого можно создать файл, содержащий все спецификации для языка PROLOG, с помощью обычного редактора. После создания файла (назовем его myf ile) нужно вызвать PROLOG и поместить весь файл в базу данных с помощью команды consult. Так, запрос

?- consult(myfile). yes

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

?- [myfile]. yes

Предикаты read и write используются для взаимодействия с пользователем. Ко­манда read (X) считывает следующий терм из текущего входного потока и добавляет его к X. Входные выражения разделяются точкой. Команда write (X) помещает X в вы­ходной поток. Если X -; не связанная переменная, то выводится целое число, перед ко­торым располагается символ подчеркивания. Это целое число представляет внутренний регистрационный номер переменной, необходимый для работы среды доказательства теорем (принципразделения переменных описан в подразделе 12.2.2).

Предикаты see и tell используются для считывания информации из файла и записи в файл. Команда see (X) открывает файл X и определяет текущий входной поток, как порожденный в X. Если переменная X не связана с существующим файлом, то команда see(X) завершается неудачей. Аналогично команда tell (X) открывает файл для вы­ходного потока. Если файла X не существует, то команда tell (X) создает файл, имя которого совпадает со связанным значением X. Команды seen(X) и told(X) закры­вают соответствующие файлы.

614 Часть VI. Языки и технологии программирования для искусственного интеллекта

Некоторые предикаты языка PROLOG помогают отслеживать состояние базы дан­ных, а также связанных с ней вычислений. Среди них наиболее важными являются listing, trace и spy. При использовании команды listing (имя_предиката), где параметром является имя предиката, в частности member (подраздел 14.1.3), интерпре­татором возвращаются все дизъюнкты из базы данных с соответствующим именем пре­диката. Заметим, что в данном случае число аргументов предиката не указано, поэтому возвращаются все варианты данного предиката, независимо от числа аргументов.

Команда trace позволяет пользователю отслеживать состояние интерпретатора PROLOG. В процессе мониторинга в выходной файл выводятся все целевые утверждения, обрабатываемые интерпретатором PROLOG. Зачастую этой информации для пользователя слишком много. Возможности трассировки во многих средах PROLOG слишком сложны для понимания и требуют дополнительного изучения и опыта. Обычно при трассировке ра­ботающей программы PROLOG можно получить следующую информацию.

Уровень глубины рекурсивных вызовов (помечается в строке слева направо).

Когда предпринимается первая попытка обработки целевого утверждения (иногда

используется команда call).

Когда цель успешно достигнута (с помощью команды exit).

Возможность других соответствий целевому утверждению (команда retry).

Невозможность достижения цели, поскольку все попытки завершились неудачно

(зачастую используется команда fail).

Полная трассировка прерывается командой notrace.

Если требуется более избирательный мониторинг, то применяется команда spy. Имя от­слеживаемого предиката обычно задается в качестве аргумента, но иногда оно определяется с помощью префиксного оператора (указывается после этого оператора). Так, с помощью ко­манды spy member выводится информация обо всех случаях использования предиката member. Аргументом предиката spy может быть также список предикатов с указанием их арности. Так, команда spy [member/2, append/3 ] определяет мониторинг всех случаев использования целевого утверждения member с двумя аргументами и утверждения append с тремя аргументами. Команда nospy удаляет все контрольные точки.

14.1.3. Списки и рекурсия в языке PROLOG

В предыдущих подразделах на нескольких простых примерах представлен синтаксис языка PROLOG. В этих примерах PROLOG предстает как механизм вычисления на базе выражений логики предикатов (в хорновской дизъюнктивной форме). Это согласуется со всеми принципами вывода в рамках логики предикатов, представленными в главе 2. Для проверки соответствия шаблонам в языке PROLOG используется унификация и возвращаются значения переменных (связанные переменные), обеспечивающие истинность выражения. Эти значения унифицированы с переменными в конкретном выражении, но не связаны в общей среде.

Ниже будет показано, что основным механизмом управления при программировании на языке PROLOG является рекурсия. Однако сначала рассмотрим несколько несложных примеров обработки списков. Список (list) - это структура данных, представляющая собой упорядоченный набор элементов (или даже самих списков). Рекурсия - это естест­венный способ обработки списочных структур. Для обработки списков в языке PROLOG

Глава 14. Введение в PROLOG 615

используют процедуры унификации и рекурсии. Сами элементы списков заключаются в квадратные скобки ([ ]) и отделяются друг от друга запятыми. Приведем несколько примеров списка на языке PROLOG.

[1, 2, 3, 4]

[[george, kate], [alien, amy], [don, pat]]

[torn, dick, harry, fred]

Первый элемент списка может отделяться от его хвоста оператором |. Хвост списка - это список после удаления первого элемента. Например, для списка [ torn, dick, harry, fred] первым элементом является torn, а хвостом-список [dick, harry, fred]. С помощью оператора | и процедуры унификации можно разделить список на компоненты.

Если список [torn, dick, harry, fred] соответствует шаблону [X|Y], то

X = torn и Y = [dick, harry, fred].

Если список [torn, dick, harry, fred] соответствует шаблону [X, Y|z], то

X = tom,Y = dick HZ = [harry, fred].

Если список [torn, dick, harry, fred] соответствует шаблону [X, Y,

Z | W], то X = torn, Y = dick, Z = harry, W = [ fred].

• Если список [torn, dick, harry, fred] соответствует шаблону [W, X, Y,

Z|V],toW = tom,X = dick, Y = harry, Z = fred, V =[].

Помимо разбиения списка на отдельные элементы унификацию можно использовать для построения списочной структуры. Например, если X = torn, Y = [dick] и L унифицируется с [X | Y], то переменная L будет связана со списком [ torn, dick]. Термы, отделенные друг от друга запятыми и расположенные до вертикальной черты, являются элементами списка, а находящаяся после вертикальной черты структура всегда является списком, а точнее, его хвостом.

Рассмотрим простой пример рекурсивной обработки списка: проверку принадлежности элемента списку с помощью предиката member. Определим предикат, позволяющий выявить наличие элемента в списке. Предикат member должен зависеть от двух аргу­ментов: элемента и списка. Он принимает значение "истина", если данный элемент со­держится в списке. Например,

?- member(a, [a, b, с, d, e]).

Yes

?- member(a, [I, 2, 3, 4]).

No

?- member(X, [a, b, с]).

X = a

;

X = b

;

X = с

;

no

Чтобы определить предикат member рекурсивно, сначала проверим, является ли X первым элементом списка.

member(X, [Х|т]).

616 Часть VI. Языки и технологии программирования для искусственного интеллекта

Этот предикат проверяет, идентично ли значение X первому элементу списка. Если нет, то естественно проверить, содержится ли X в оставшейся части (Т) списка. Это определяется следующим образом.

member(X, [Y|T]) :- member(X, Т).

Таким образом, проверка наличия элемента в списке на языке PROLOG выполняется с помощью двух строк.

member(X, [Х|Т]).

member(X, [Y|T]):- member(X, Т).

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

member (с, [а, b, с]) с нумерацией.

1: member(X, [х|Т]).

2: member(X, [Y|T]):- member(X, Т).

?- member(с, [a, b, с]).

call 1. fail, since c^a

call 2. X = c, Y = a, T = [b, c], member(c, [b, c])? call 1. fail, since eft call 2. X = c, Y = b, T = [c], member(c, [c])?

call 1. success, с = с yes (to second call 2.) yes (to first call 2.) yes

Хороший стиль программирования на языке PROLOG предполагает использование ано­нимных переменных (anonymous variable). Они служат для указания программисту и интер­претатору того, что определенные переменные используются исключительно для проверки соответствия шаблону, т.е. само связывание переменных не является частью процесса вычис­лений. Так, чтобы проверить, совпадает ли элемент X с первым элементом списка, обычно ис­пользуют запись member (X, [X |_]). Символ _ означает, что, несмотря на важное значе­ние хвоста списка в процессе унификации запроса, содержимое хвоста не играет роли. Ано­нимные переменные необходимо также использовать в рекурсивном утверждении при проверке наличия элемента в списке, если значение головы списка не играет роли.

member(X, [х|_]).

member(X, [_|т]) :- member(X, T).

Хорошим упражнением для углубления понимания природы списков и рекурсивного управления является запись элементов списка по одному в строке. Допустим, требуется таким образом записать элементы списка [а, b, с, d]. Для этого можно определить рекурсивную команду.

writelist([ ]).

writelist([H|T]) :- write(H), nl, writelist(T).

Этот предикат записывает элементы списка по одному в строке, поскольку nl означает переход на новую строку в выходном потоке. Если требуется записать элементы списка в обратном порядке, то рекурсивный предикат должен следовать перед командой

Глава 14. Введение в PROLOG 617

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

reverse_writelist([ ]).

reverse_writelist([H|T]) :- reverse_writelist(T), write(H), nl.

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

14.1.4. Рекурсивный поиск в языке PROLOG

В разделе 5.2 рассматривалась задача "хода конем" размерности 3x3 в рамках теории предикатов. Для перемещения коня использовалась квадратная доска следующего вида.

Допустимые ходы можно представить на языке PROLOG с помощью предиката move. Предикат path определяет алгоритм нахождения пути между его аргументами за О или более ходов. Заметим, что предикат path определен рекурсивно.

move(1, 6). move(3, 4) .move(6, 7).move(8, 3).

move(1, 8). move(3, 8).move(6, 1).move(8, 1).

move(2, 7). move(4, 3).move(7, 6).move(9, 4).

move(2, 9). move(4, 9).move(7, 2).move(9, 2).

path(Z,Z).

path(X, Y) :- move(X, W), not(been(W)), assert(been(W)), path(W, Y).

Это определение предиката path представляет собой реализацию на языке PROLOG алгоритма, описанного в главе5. Как было указано выше, assert - это встроенный предикат PROLOG, который всегда имеет значение "истина" и попутно помещает свои аргументы в базу данных спецификаций. Предикат been используется для записи посещенных ранее состояний и предотвращения циклов.

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

Как было предложено в главе 3, для отслеживания посещенных состояний и предотвращения циклов при вызове предиката path можно использовать список. Для выявления дублированных состояний (циклов) можно воспользоваться предикатом member. Такой подход позволяет обойти проблему использования глобального утверждения been(W).

618 Часть VI. Языки технологии программирования для искусственного интеллекта

Поиск в глубину с помощью алгоритма с возвратами, описанного в главах 3 и 5, на языке PROLOG может быть реализован следующим образом.

path(Z, Z, L).

path(X, Y, L):- move(X, Z) , not(member(Z, L)), path(Z, Y,[z|L]).

Здесь member - определенный выше предикат.

Третий параметр предиката path - это локальная переменная, представляющая список уже посещенных состояний. При генерации нового состояния (с использованием предиката move) оно помещается в начало списка состояний [ Z | L ] для следующего вызова path, если оно до сих пор не содержалось в списке посещенных состояний not(member(Z, L)).

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

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

Вызов интерпретатора PROLOG для команды path(X, Y, [X] ), где X и Y- это числа из диапазона от 1 до 9, позволяет найти путь из состояния X в состояние Y, если этот путь существует. Третий параметр инициализирует список посещенных состояний начальным состоянием X. Заметим, что в языке PROLOG регистр символов не учитывается. Первые два параметра должны определять любое представление состояний в об­ласти определения задачи, а третий - список состояний. С помощью унификации вы­полняется обобщенная проверка соответствия шаблонам для всех возможных типов дан­ных. Таким образом, path - это общий алгоритм поиска в глубину, который можно использовать для любого графа. В разделе 14.3 он будет применен для реализации продукционной системы решения задачи "о перевозке человека, волка, козы и капусты" с соответствующими спецификациями состояний.

Вернемся к решению задачи "хода конем" на поле 3x3. Полную задачу "хода конем" на поле 8x8 на языке PROLOG читателю предлагается решить самостоятельно (см. упражнения к главам 14 и 15). Для этого пронумеруем обе части алгоритма path.

is path(Z, Z, L).

is path(X, Y, L) :- move(X, Z) , not(member(Z, L)), path(Z, Y,[Z|L]).

?- pathd, 3, [1]) .

Выполним трассировку этой задачи.

Path (1, 3, [1]) attempts to match 1. fail 1?3.

Path (1, 3, [1]) matches 2. X is 1, Y is 3, L is [1]

move(1, Z) matches Z as 6, not (member (6, [1] )) is true, call path(6, 3,[6,1])

Глава 14. Введение в PROLOG 619

path(6, 3, [6,1]) attempts to match 1. fail 6?3.

path(6, 3, [6,1]) matches 2. X is 6, Y is 3, L is [6,1].

move(6,Z) matches Z as 7, not(member(7,[6,1])) is true,

path(7,3,[7,6,1])

path(7,3,[7,6,1]) attempts to match 1. fail 7?3.

path(7,3,[7,6,1]) matches 2. X is 7, Y is 3, L is [7,6,1].

move(7,Z) is Z=6, not(member(6,[7,6,1])) fails, backtrack!

move(7,Z) is Z=2, not(member(2,[7,6,1])) true,

path(2,3, [2,7,6,1] )

path call attempts 1, fail, 2?3.

path matches 2, X is 2, Y is 3, L is [2,7,6,1]

move matches Z as 7, not(member(...)) fails, backtrack!

move matches Z as 9, not(member(...)) true,

path(9,3,[9,2,7,6,1])

path fails 1, 9?3.

path matches 2, X is 9, Y is 3, L is [9,2,7,6,1]

move is Z = 4, not(member(...)) true,

path(4, 3,[4,9,2,7,6,1]) path fails 1, 4?3.

path matches 2, X is 4, Y is 3, L is [4,9,2,7,6,1]

move Z = 3, not(member(...)) true,

path(3, 3, [3,4,9,2,7,6,1])

path attempts 1, true, 3=3, yes

yes

yes

yes

yes

yes

yes

В заключение отметим, что рекурсивный вызов path- это оболочка (shell), или общая управляющая структура для поиска на графе. В path(X, Y, L) X-текущее состояние, Y - целевое. Если X и Y совпадают, рекурсия прекращается. L - список со­стояний в текущем пути к состоянию Y. При обнаружении каждого нового состояния Z с помощью вызова move(X, Z) это состояние помещается в список [Z|L]. Проверка наличия состояния в списке выполняется с помощью вызова not (member (Z, L)). Эта проверка гарантирует отсутствие циклов в найденном пути.

Отличие между списком состояний L в рассмотренном алгоритме поиска пути и замкнутым множеством closed из главы 3 состоит в том, что это множество содержит все посещенные состояния, а в списке L хранится только текущий путь. Желательно расширить запись, создаваемую при вызове path, и хранить все посещенные состояния. Это будет сделано в разделе 14.4.

14.1.5. Использование оператора отсечения для управления поиском в языке PROLOG

Оператор отсечения (cut) представляется символом ! и указывается в качестве целевого утверждения без аргументов. При этом его применение имеет несколько побочных эффектов. Во-первых, этот оператор всегда выполняется при его первом достижении, а во-вторых, если при возврате оказывается невозможным вернуться к предыдущему со-

620 Часть VI. Языки и технологии программирования для искусственного интеллекта

стоянию, то все целевое утверждение, в котором содержится этот оператор, считается ложным. В качестве простого примера использования оператора отсечения рассмотрим реализацию вызова предиката path для поиска двухшагового пути в задаче "хода конем". Можно создать следующий предикат path.2.

path2(X, Y) :- move(X,Z), move(Z,Y).

Между точками Х и Y существует двухшаговый путь, если между ними существует "промежуточная остановка" Z. Предположим, для данного примера существует следующая база данных ходов конем.

move(1,6). move(1,8). move(6,7). move(6,1). move(8,3). move(8,1).

В ответ на запрос о поиске двухшаговых путей из состояния 1 интерпретатор выдаст четыре значения.

?- path2(1,W).

W = 7

W = 1 W = 3 W = 1

no

Если в предикате path2 используется оператор отсечения, то ответов будет только два. path2(X, Y) :- move(X,Z), !, move(Z,Y).

?- path2(l,W).

W = 7

;

W = 1

;

no

Это происходит потому, что переменная Z принимает только одно значение (первое связанное с ней) - 6. Если первая подцель реализуется успешно, то переменная Z связывается со значением 6, и достигается оператор отсечения. Поэтому в дальнейшем возврат к первой подцели не выполняется, и переменная Z не связывается с другими значениями.

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

Глава 14. Введение в PROLOG 621

Во-вторых, оператор отсечения позволяет управлять рекурсией. Например, при вызове предиката path

path(Z, Z, L).

path(X, Z, L) :- move(X, Y), not(member(Y, L)), path(Y, Z,[Y|L]), !.

добавление оператора отсечения означает, что в результате поиска на графе будет найдено только одно решение. Уникальность решения обеспечивается тем, что последующие решения будут найдены после выполнения дизъюнктивного выражения path (Z, Z, L). Если пользователь запрашивает остальные решения, то предикат path(Z, Z, L) принимает значение "ложь" и тем самым инициирует вызов второго предиката path для продолжения поиска (полного перебора) на графе. Если оператор отсечения размещается после рекурсивного вызова path, то этот вызов не может быть повторен (в результате возврата) для продолжения поиска.

Важным побочным эффектом использования оператора отсечения является ускорение работы программы и экономия памяти. Если этот оператор использован внутри пре­диката, то указатели в памяти, необходимые для возврата к предикатам, расположенным слева от оператора отсечения, не создаются. Дело в том, что они никогда не понадобятся. Таким образом, применение оператора отсечения приводит к нахождению желаемого решения только при более эффективном использовании памяти.

Оператор отсечения также можно использовать при реализации рекурсии для повторной инициализации вызова path и продолжения поиска на графе. Эта возможность будет проде­монстрирована в разделе 14.3 при описании общего алгоритма поиска. Для реализации этого алгоритма нам также понадобится разработать несколько абстрактных типов данных.

14.2. Абстрактные типы данных в PROLOG

Эффективность программирования в любой среде можно повысить за счет сокрытия информации и введения процедурных абстракций. Поскольку в алгоритмах поиска на графе, описанных в главах 3-5, используются такие структуры данных, как множество (set), стек (stack), очередь (queue) и приоритетная очередь (priority queue), логично ввести их в языке PROLOG, что и будет сделано в этом разделе.

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

14.2.1. Стек

Стек (stack) - это линейная структура, доступ к которой осуществляется только с одного конца. Следовательно, все элементы добавляются и удаляются из структуры с одного и того же конца. Иногда стек называют структурой данных LIFO (Last-In-FirstOut) - "последним вошел, первым вышел". Примером работы этой структуры может служить алгоритм поиска в глубину из подраздела 3.2.3. Для функционирования стека необходимо определить следующие операции.

Проверка наличия элементов в стеке (проверка пустоты стека).

Добавление элемента в стек.

622 Часть VI. Языки и технологии программирования для искусственного интеллекта