Скачать fb2
Prolog

Prolog


    Вперёд >>>

   
    Иван Братко
    Программирование на языке Пролог для искусственного интеллекта
    Перевод с английского.
    Москва, "МИР", 1990      подробнее...
    Электронную версию книги создал Иванов Виктор Михайлович. Книга размещена на сайте http://dstu2204.narod.ru/   ( на этой странице ).

    ОГЛАВЛЕНИЕ
    Обложка
    От редактора перевода
    Предисловие
    Предисловие автора
    ЧАСТЬ 1. ЯЗЫК ПРОЛОГ
    Глава 1.  Общий обзор языка Пролог
    1.1.  Пример программы: родственные отношения
    1.2.  Расширение программы-примера с помощью правил
    1.3.  Рекурсивное определение правил
    1.4.  Как пролог-система отвечает на вопросы
    1.5.  Декларативный и процедурный смысл программ
    Глава 2.  Синтаксис и семантика пролог-программ
    2.1.  Объекты данных
    2.1.1.  Атомы и числа
    2.1.2.  Переменные
    2.1.3.  Структуры
    2.2.  Сопоставление
    2.3.  Декларативный смысл пролог-программ
    2.4.  Процедурная семантика
    2.5.  Пример: обезьяна и банан
    2.6.  Порядок предложений и целей
    2.6.1.  Опасность бесконечного цикла
    2.6.2.  Варианты программы, полученые путем переупорядочивания предложений и целей
    2.6.3.  Сочетание декларативного и процедурного подходов
    2.7.  Замечания о взаимосвязи между Прологом и логикой
    Глава 3.  Списки. Операторы. Арифметика
    3.1.  Представление списков
    3.2.  Некоторые операции над списками
    3.2.1.  Принадлежность к списку
    3.2.2.  Сцепление ( конкатенация)
    3.2.3.  Добавление элемента
    3.2.4.  Удаление элемента
    3.2.5.  Подсписок
    3.2.6.  Перестановки
    3.3.  Операторная запись (нотация)
    3.4.  Арифметические действия
    Глава 4.  Использование структур: примеры
    4.1.  Получение структурированной информации из базы данных
    4.2.  Абстракция данных
    4.3.  Моделирование недетерминированного автомата
    4.4.  Планирование поездки
    4.5.  Задача о восьми ферзях
    4.5.1.  Программа 1
    4.5.2.  Программа 2
    4.5.3.  Программа 3
    4.5.4.  Заключительные замечания
    Глава 5.  Управление перебором
    5.1.  Ограничение перебора
    5.1.1.  Эксперимент 1
    5.1.2.  Эксперимент 2
    5.2.  Примеры, использующие отсечение
    5.2.1.  Вычисление максимума
    5.2.2.  Процедура проверки принадлежности списку, дающая единственное решение
    5.2.3.  Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)
    5.2.4.  Задача классификации объектов
    5.3.  Отрицание как неуспех
    5.4.  Трудности с отсечением и отрицанием
    Глава 6.  Ввод и вывод
    6.1.  Связь с файлами
    6.2.  Обработка файлов термов
    6.2.1.  reаd  и  write
    6.2.2.  Вывод списков
    6.2.3.  Формирование термов
    6.2.4.  Обработка произвольного файла термов
    6.3.  Обработка символов
    6.4.  Создание и декомпозиция атомов
    6.5.  Ввод программ: consult,   reconsult
    Глава 7.  Другие встроенные процедуры
    7.1.  Проверка типов термов
    7.1.1.  Предикаты  var,  nоnvar,  atom,  integer,  atomic
    7.1.2.  Решение числового ребуса с использованием   nonvar
    7.2.  Создание и декомпозиция термов : = ..; functor, arg, name
    7.3.  Различные виды равенства
    7.4.  Работа с базой данных
    7.5.  Средства управления
    7.6. bagof, setof и findall
    Глава 8.  Стиль и методы программирования
    8.1.  Общие принципы хорошего программирования
    8.2.  Как представлять себе программы на Прологе
    8.2.1.  Использование рекурсии
    8.2.2.  Обобщение
    8.2.3.  Использование рисунков
    8.3.  Стиль программирования
    8.3.1.  Некоторые правила хорошего стиля
    8.3.2.  Табличная организация длинных процедур
    8.3.3.  Комментирование
    8.4.  Отладка
    8.5.  Эффективность
    8.5.1.  Повышение эффективности решения задачи о восьми ферзях
    8.5.2.  Повышение эффективности программы раскраски карты
    8.5.3.  Повышение эффективности конкатенации списков за счет совершенствования структуры данных
    8.5.4.  Повышение эффективности зa счет добавления вычисленных фактов к базе данных
    ЧАСТЬ 2. ПРОЛОГ В ИСКУССТВЕННОМ ИНТЕЛЛЕКТЕ
    Глава 9.  Операции над структурами данных
    9.1.  Представление списков. Сортировка
    9.1.1.  Замечания в некоторых альтернативных способах представления списков
    9.1.2.  Сортировка списков
    9.2.  Представление множеств двоичными деревьями
    9.3.  Двоичные справочники: добавление и удаление элемента
    9.4.  Отображение деревьев
    9.5  Графы
    9.5.1.  Представление графов
    9.5.2.  Поиск пути в графе
    9.5.3.  Построение остовного дерева
    Глава 10.   Усовершенствованные методы представления множеств деревьями
    10.1.  Двоично-троичные справочники
    10.2.  AVL-дерево: приближенно сбалансированное дерево
    Глава 11.  Основные стратегии решения задач
    11.1.  Предварительные понятия и примеры
    11.2.  Стратегия поиска в глубину
    11.3.  Поиск в ширину
    11.3.1.  Списковое представление множества кандидатов
    11.3.2.  Древовидное представление множества кандидатов
    11.4.  Замечания относительно поиска в графах, оптимальности и сложности
    Глава 12.  Поиск с предпочтением: эвристический поиск
    12.1.  Поиск с предпочтением
    12.2.  Поиск с предпочтением применительно к головоломке "игра в восемь"
    12.3.  Применение поиска с предпочтением к планированию выполнения задач
    Глава 13.  Сведение задач к подзадачам. И/ИЛИ-графы
    13.1  Представление задач в виде И/ИЛИ-графов
    13.2  Примеры И/ИЛИ-представления задач
    13.2.1.  И / ИЛИ-представление задачи поиска маршрута
    13.2.2.  Задача о ханойской башне
    13.2.3.  Формулировка игровых задач в терминах И / ИЛИ-графов
    13.3.  Базовые процедуры поиска в И/ИЛИ-графах
    13.4.  Поиск с предпочтением в И/ИЛИ-графах
    13.4.1.  Эвристические оценки и алгоритм поиска
    13.4.2.  Программа поиска
    13.4.3.  Пример отношений, определяющих конкретную задачу: поиск маршрута
    Глава 14.  Экспертные системы
    14.1.  Функции, выполняемые экспертной системой
    14.2.  Грубая структура экспертной системы
    14.3.  Правила типа "если-то" для представления знаний
    14.4.  Разработка оболочки
    14.4.1.  Процесс рассуждений
    14.4.2.  Формирование ответа на вопрос "почему"
    14.4.3.  Формирование ответа на вопрос "как"
    14.5.  Реализация
    14.5.1.  Процедура  рассмотреть
    14.5.2.  Процедура  ответпольз
    14.5.3.  Усовершенствование процедуры  ответпольз
    14.5.4.  Процедура  выдать
    14.5.5.  Драйвер верхнего уровня
    14.5.6.  Одно замечание по поводу программы-оболочки
    14.5.7.  Цели с отрицанием
    14.6.  Работа с неопределенностью
    14.6.1.  Степень достоверности
    14.6.2.  Модель Prospector'а
    14.6.3.  Принципы реализации
    14.7.  Заключительные замечания
    Глава 15.  Игры
    15.1.  Игры двух лиц с полной информацией
    15.2.  Минимаксный принцип
    15.3.  Альфа-бета алгоритм: эффективная реализация минимаксного принципа
    15.4.  Минимаксные игровые программы: усовершенствования и ограничения
    15.5.  Знания о типовых ситуациях и механизм "советов"
    15.5.1.  Цели и ограничения на ходы
    15.5.2.  Выполнимость совета
    15.5.3.  Правила и таблицы советов
    15.6.  Программа на языке ALO для игры в шахматном эндшпиле
    15.6.1.  Миниатюрный интерпретатор языка AL0
    15.6.2.  Программа на языке советов для эндшпиля  "король и ладья против короля"
    Глава 16.  Программирование в терминах типовых конфигураций
    16.1.  Архитектура, ориентированная на типовые конфигурации
    16.1.1.  Основные понятия
    16.1.2.  Прологовские программы как системы, управляемые образцами
    16.1.3.  Пример составления программы
    16.2.  Простой интерпретатор программ, управляемых образцами
    16.3.  Простая программа для автоматического доказательства теорем
    16.4.  Заключительные замечания
    Ответы к некоторым упражнениям
    Предметный указатель
    3-я страница обложки

    Вперёд >>>
    Назад | Содержание | Вперёд

    PROLOG
    PROGRAMMING
    FOR ARTIFICIAL
    INTELLIGENCE

    Ivan Bratko
    E. Kardelj University • J. Stefan Institute

    Yugoslavia

    ADDISON-WESLEY
    PUBLISHIHG
    COMPANY

    Wokingham, England • Reading, Massachusetts • Menlo Park,California • Don Mills, Ontario • Amsterdam • Bonn • Sydney • Singapore • Tokyo • Madrid • Bogota • Santiago • San-Juan

    И.  БРАТКО
    ПРОГРАММИРОВАНИЕ
    НА ЯЗЫКЕ ПРОЛОГ
    ДЛЯ ИСКУССТВЕННОГО
    ИНТЕЛЛЕКТА

    Перевод с английского

    А.И. Лупенко и A.M.Степанова
    под редакцией A.M. Степанова

   
    Москва "МИР" 1990


    ББК 22.19

             Б 87

    УДК 519.68
    Братко И.
    Б  87    Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. -М.: Мир, 1990.- 560 с., ил.
    ISBN 5-03-001425-Х
    Книга известного специалиста по программированию (Югославия), содержащая основы языка Пролог и его приложения для решения задач искусственного интеллекта. Изложение отличается методическими достоинствами - книга написана в хорошем стиле, живым языком. Книга дополняет имеющуюся на русском языке литературу по языку Пролог.
    Для программистов разной квалификации, специалистов по искусственному интеллекту, для всех изучающих программирование.

   
                                         ББК 22.19
    Редакция литературы по математическим наукам

    ISBN 5-03-001425-X (русск.)
    ISBN 0-201-14224-4 (англ.)
    (c) 1986 Addison-Wesley Publishing Company, Inc.
    (c) перевод на русский язык, Лупенко А.И., Степанов A.M., 1990

    Электронную версию книги создал Иванов Виктор Михайлович (студент Донского Государственного Технического Университета (ДГТУ), г. Ростов-на-Дону, специальность 2204 "Программное обеспечение АС и ВТ", 5 курс) 2 апреля 2004 года. Книга размещена на сайте http://dstu2204.narod.ru/   ( на этой странице ).
    При создании книги были использованы главы 2-12 из книги в электронном виде в черновом варианте, взятые с этой страницы (что, впрочем, составило не более 15% от всей работы) и бумажный экземпляр книги из библиотеки ДГТУ. Для создания gif-картинок применялся CorelDRAW 12 , для редактирования htm-страниц - MS FrontPage Editor 3.0 . Для графического дизайн-оформления, максимально похожего на исходное, использована hmtl-графика + JavaScript.
    Текст и картинки электронной версии книги проверены на совпадение с оригиналом.
    Улучшения по сравнению с бумажной версией книги:
    Расширено оглавление путём добавления подпунктов (с трёхцифровым кодом).
    Сделан алфавитно-предметный указатель на JavaScript (полностью соответствующий тому, который есть в бумажной книге) на гиперссылках (вместо номеров страниц, как в бумажной книге) с выделением ключевого слова и сбросом выделения через "Обновить" в броузере (F5).
    Сделана система быстрого получения ответов на упражнения по такому же принципу.
    Памяти погибшей Югославии посвящается

   

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд

    ОТ РЕДАКТОРА ПЕРЕВОДА
    По существующей традиции предисловие редактора перевода - это своего рода рецензия, в которой обычно излагается история вопроса, а затем дается обзор содержания книги и оценка ее качества (как правило, рекламного характера). В данном случае моя задача несколько упрощается, так как все это читатель, перевернув страницу, найдет в предисловии известного американского ученого, специалиста по искусственному интеллекту П. Уинстона, а затем - в предисловии автора. Мне остается только присоединиться к авторитетному мнению П. Уинстона, что перед нами прекрасно написанный учебник до Прологу, ориентированный на практическое использование в области искусственного интеллекта. Добавлю также, что для советского читателя потребность в такой книге особенно велика, поскольку в нашей стране Пролог пока еще не получил того распространения, которого он заслуживает.
    Несколько замечаний относительно особенностей перевода. Кроме обычных терминологических трудностей, как правило возникающих при переводе книг по программированию, переводчикам пришлось преодолевать одну дополнительную сложность. Дело в том, что в Прологе идентификаторы (имена переменных, процедур и атомов) несут на себе значительно большую смысловую нагрузку, чем в традиционных языках программирования. Поэтому программные примеры пришлось излагать на некоей условной русской версии Пролога - в противном случае, для читателей, не владеющих английским языком, эти примеры стали бы значительно менее понятными. Мы оставили без перевода все имена встроенных операторов и процедур, все же остальные имена переводились на русский язык. Следует признать, что в ряде случаев русская версия этих имен оказалась менее эстетически привлекательной, чем исходный английский вариант. Пытаясь наиболее точно передать смысл того или иного имени, переводчик нередко оказывался перед нелегким выбором между громоздким идентификатором (иногда из нескольких слов) и неблагозвучной аббревиатурой. Впрочем, все эти проблемы хорошо известны любому "русскоязычному" программисту.
    Главы 1-8 перевел А. И. Лупенко, а предисловия и главы 9-16 - А.М. Степанов. Подготовку оригинала-макета книги на ЭВМ выполнили А.Н. Черных и Н.Г. Черных.
    Эту книгу можно рекомендовать как тем читателям, которые впервые приступают к изучению Пролога и искусственного интеллекта, так и программистам, уже имеющим опыт составления пролог-программ.
    А. М. Степанов

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд

    ПРЕДИСЛОВИЕ
    В средние века знание латинского и греческого языков являлось существенной частью образования любого ученого. Ученый, владеющий только одним языком, неизбежно чувствовал себя неполноценным, поскольку он был лишен той полноты восприятия, которая возникает благодаря возможности посмотреть на мир сразу с двух точек зрения. Таким же неполноценным ощущает себя сегодняшний исследователь в области искусственного интеллекта, если он не обладает основательным знакомством как с Лиспом, так и с Прологом - с этими двумя основополагающими языками искусственного интеллекта, без знания которых невозможен более широкий взгляд на предмет исследования.
    Сам я приверженец Лиспа, так как воспитывался в Массачусетском технологическом институте, где этот язык был изобретен. Тем не менее, я никогда не забуду того волнения, которое я испытал, увидев в действии свою первую программу, написанную в прологовском стиле. Эта программа была частью знаменитой системы Shrdlu Терри Винограда. Решатель задач, встроенный в систему, работал в "мире кубиков" и заставлял руку робота (точнее, ее модель) перемещать кубики на экране дисплея, решая при этом хитроумные задачи, поставленные оператором.
    Решатель задач Винограда был написан на Микропленнере, языке, который, как мы теперь понимаем, был своего рода Прологом в миниатюре. Любой прологоподобный язык заставляет программиста мыслить в терминах целей, поэтому, несмотря на все недостатки Микропленнера, достоинством этой программы было то, что в ее структуре содержались многочисленные явные указания на те или иные цели. Процедуры-цели "схватить", "освободить", "избавиться", "переместить", "отпустить" и т.п. делали программу простой и компактной, а поведение ее казалось поразительно разумным.
    Решатель задач Винограда навсегда изменил мое программистское мышление. Я даже переписал его на Лиспе и привел в своем учебнике по Лиспу в качестве примера - настолько эта программа всегда поражала меня мощью заложенной в ней философии "целевого" программирования, да и само программирование в терминах целей всегда доставляло мне удовольствие.
    Однако учиться целевому программированию на примерах лисповских программ - это все равно, что читать Шекспира на языке, отличном от английского. Какое-то впечатление вы получите, но сила эстетического воздействия будет меньшей, чем при чтении оригинала. Аналогично этому, лучший способ научиться целевому программированию - это читать и писать программы на Прологе, поскольку сама сущность Пролога как раз и состоит в программировании в терминах целей.
    В самом широком смысле слова эволюция языков программирования - это движение от языков низкого уровня, пользуясь которыми, программист описывает, как что-либо следует делать, к языкам высокого уровня, на которых просто указывается, что необходимо сделать. Так, например, появление Фортрана освободило программистов от необходимости разговаривать с машиной на прокрустовом языке адресов и регистров. Теперь они уже могли говорить на своем (или почти на своем) языке, только изредка делая уступки примитивному миру 80-колонных перфокарт.
    Однако Фортран и почти все другие языки программирования все еще остаются языками типа "как". И чемпионом среди этих языков является, пожалуй, современный модернизированный Лисп. Так, скажем, Common Lisp, имея богатейшие выразительные возможности, разрешает программисту описывать наиболее "выразительно" именно то, как что-либо следует делать. В то же время очевидно, что Пролог порывает с традициями языков типа "как", поскольку он определенным образом направляет программистское мышление, заставляя программиста давать определения ситуаций и формулировать задачи вместо того, чтобы во всех деталях описывать способ решения этих задач.
    Отсюда следует, насколько важен вводный курс по Прологу для всех студентов, изучающих вычислительную технику и программирование - просто не существует лучшего способа понять, что из себя представляет программирование типа "что".
    Многие страницы этой книги могут служить хорошей иллюстрацией того различия, которое существует между этими двумя стилями программистского мышления. Например, в первой главе это различие иллюстрируется на задачах, относящихся к семейным отношениям. Прологовский программист дает простое и естественное описание понятия "дедушка": дедушка -это отец родителя. На Прологе это выглядит так:
            дедушка( X, Z) :- отец( X, Y), родитель( Y, Z).
    Как только пролог-система узнала, что такое дедушка, ей можно задать вопрос, например: кто является дедушкой Патрика? В обозначениях Пролога этот вопрос и типичный ответ имеют вид:
            ?-  дедушка( X, патрик).
            X  =  джеймс;

            X  =  карл.
    Каким образом решать эту задачу, как "прочесывать" базу данных, в которой записаны все известные отношения "отец" и "родитель", - это уже забота самой пролог-системы. Программист только сообщает системе то, что ему известно, и задает вопросы. Его в большей степени интересуют знания и в меньшей - алгоритмы, при помощи которых из этих знаний извлекается нужная информация.
    Поняв, что очень важно научиться Прологу, естественно задать себе следующий вопрос - как это сделать. Я убежден, что изучение языка программирования во многом сходно с изучением естественного языка. Так, например, в первом случае может пригодиться инструкция по программированию точно так же, как во втором - словарь. Но никто не изучает язык при помощи словаря, так как слова - это только часть знаний, необходимых для овладения языком. Изучающий язык должен кроме того узнать те соглашения, следуя которым, можно получать осмысленные сочетания слов, а затем научиться у мастеров слова искусству литературного стиля.
    Точно так же, никто не изучает язык программирования, пользуясь только инструкцией по программированию, так как в инструкциях очень мало или вообще ничего не говорится о том, как хорошие программисты используют элементарные конструкции языка. Поэтому необходим учебник, причем лучшие учебники обычно предлагают читателю богатый набор примеров. Ведь в хороших примерах сконцентрирован опыт лучших программистов, а именно на опыте мы, в основном, и учимся.
    В этой книге первый пример появляется уже на первой странице, а далее на читателя как из рога изобилия обрушивается поток примеров прологовских программ, написанных программистом-энтузиастом, горячим приверженцем прологовской идеологии программирования. После тщательного изучения этих примеров читатель не только узнает, как "работает" Пролог, но и станет обладателем личной коллекции программ-прецедентов, готовых к употреблению: он может разбирать эти программы на части, приспосабливать каждую часть к своей задаче, а затем снова собирать их вместе, получая при этом новые программы. Такое усвоение предшествующего опыта можно считать первым шагом на пути от новичка к программисту-мастеру.
    Изучение хороших программных примеров дает, как правило, один полезный побочный эффект: мы узнаем из них не только очень многое о самом программировании, но и кое-что - о какой-нибудь интересной научной области. В данной книге такой научной областью, стоящей за большинством примеров, является искусственный интеллект. Читатель узнает о таких идеях в области автоматического решения задач, как сведение задач к подзадачам, прямое и обратное построение цепочки рассуждений, ответы на вопросы "как" и "почему", а также разнообразные методы поиска.
    Одним из замечательных свойств Пролога является то, что это достаточно простой язык, и студенты могли бы использовать его непосредственно в процессе изучения вводного курса по искусственному интеллекту. Я не сомневаюсь, что многие преподаватели включат эту книгу в свои курсы искусственного интеллекта с тем, чтобы студенты смогли увидеть, как при помощи Пролога абстрактные идеи приобретают конкретные и действенные формы.
    Полагаю, что среди учебников по Прологу эта книга окажется особенно популярной, и не только из-за своих хороших примеров, но также из-за целого ряда других своих привлекательных черт:
    тщательно составленные резюме появляются на всем протяжении книги;
    все вводимые понятия подкрепляются многочисленными упражнениями;
    процедуры выборки элементов структур подводят нас к понятию абстракции данных;
    обсуждение вопросов стиля и методологии программирования занимает целую главу;
    автор не только показывает приятные свойства языка, но и со всей откровенностью обращает наше внимание на трудные проблемы, возникающие при программировании на Прологе.
    Все это говорит о том, что перед нами прекрасно написанная, увлекательная и полезная книга.
    Патрик Г. Уинстон
    Кеймбридж, Массачусетс

    Январь 1986

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд

    Посвящается Бранке, Андрею и Тадею
    ПРЕДИСЛОВИЕ АВТОРА
    Язык программирования Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов, древовидное представление структур данных и автоматический возврат. Этот небольшой набор образует удивительно мощный и гибкий программный аппарат. Пролог особенно хорошо приспособлен для решения задач, в которых фигурируют объекты (в частности, структуры) и отношения между ними. Например, в качестве легкого упражнения, можно попробовать выразить на Прологе пространственные отношения между объектами, изображенными на обложке этой книги. Пример такого отношения: верхний шар расположен дальше, чем левый шар. Нетрудно также сформулировать и более общее положение в виде следующего правила: если X ближе к наблюдателю, чем Y, a Y - ближе, чем Z, то объект X находится ближе, чем Z. Пользуясь правилами и фактами, пролог-система может проводить рассуждения относительно имеющихся пространственных отношений и, в частности, проверить, насколько они согласуются с вышеуказанным общим правилом. Все эти возможности придают Прологу черты мощного языка для решения задач искусственного интеллекта, а также любых задач, требующих нечислового программирования.
    Само название Пролог есть сокращение, означающее программирование в терминах логики. Идея использовать логику в качестве языка программирования возникла впервые в начале 70-х годов. Первыми исследователями, разрабатывавшими эту идею, были Роберт Ковальский из Эдинбурга (теоретические аспекты), Маартен ван Эмден из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ из Марселя (реализация). Сегодняшней своей популярности Пролог во многом обязан эффективной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном в середине 70-х годов.
    Поскольку Пролог уходит своими корнями в математическую логику, его преподавание часто начинают с изложения логики. Однако такое введение в Пролог, насыщенное математическими понятиями, приносит мало пользы в том случае, когда Пролог изучается в качестве практического инструмента программирования. Поэтому в данной книге мы не будем заниматься математическими аспектами этого языка, вместо этого мы сосредоточим свое внимание на навыках использования базовых механизмов Пролога, для решения целого ряда содержательных задач. В то время, как традиционные языки программирования являются процедурно-ориентированными, Пролог основан на описательной или декларативной точке зрения на программирование. Это свойство Пролога коренным образом меняет программистское мышление и делает обучение программированию на Прологе увлекательным занятием, требующим определенных интеллектуальных усилий.
    В первой части книги содержится введение в Пролог, в ней показано, как составлять программы на Прологе. Во второй части демонстрируется, как мощные средства языка применяются в некоторых областях искусственного интеллекта, таких как, например, решение задач, эвристический поиск, экспертные системы, машинные игры и системы, управляемые образцами. В этой части излагаются фундаментальные методы в области искусственного интеллекта. Далее они прорабатываются достаточно глубоко для того, чтобы реализовать их на Прологе и получить готовые программы. Эти программы можно использовать в качестве "кирпичиков" для построения сложных прикладных систем. В книге рассматриваются также вопросы обработки таких сложных структур данных, как графы и деревья, хотя эти вопросы, строго говоря, и не имеют прямого отношения к искусственному интеллекту. В программах искусственного интеллекта методы обработки структур применяются довольно часто, и, реализуя их, читатель приобретет самые общие навыки программирования на Прологе. В книге особое внимание уделяется простоте и ясности составляемых программ. Повсеместно мы стремились избегать программистских "хитростей", повышающих эффективность за счет учета особенностей конкретной реализации Пролога.
    Эта книга предназначена для тех, кто изучает Пролог и искусственный интеллект. Материал книги можно использовать в курсе лекций по искусственному интеллекту, ориентированном на прологовскую реализацию. Предполагается, что читатель имеет общее представление о вычислительных машинах, но предварительные знания в области искусственного интеллекта необязательны. От читателя не требуется также какого-либо программистского опыта. Дело в том, что богатый программистский опыт вместе с приверженностью к традиционному процедурному программированию (например, на Паскале) может стать помехой при изучении Пролога, требующего свежего программистского мышления.
    Среди различных диалектов Пролога наиболее широко распространен так называемый эдинбургский синтаксис (или синтаксис DEC-10), который мы я принимаем в данной книге. Для того, чтобы обеспечить совместимость с различными реализациями Пролога, мы используем в книге сравнительно небольшое подмножество встроенных средств, имеющихся во многих вариантах Пролога.
    Как читать эту книгу? В первой части порядок чтения естественным образом совпадает с порядком изложения, принятым в книге. Впрочем, часть разд. 2.4, в которой дается более формальное описание процедурной семантики Пролога, можно опустить. В главе 4 приводятся примеры программ, которые можно читать только выборочно. Вторая часть книги допускает более гибкий порядок чтения, поскольку различные главы этой части предполагаются взаимно независимыми. Однако некоторые из тем было бы естественным прочесть раньше других - это относится к основным понятиям, связанным со структурами данных (гл. 9), и к базовым стратегиям поиска (гл. 11 и 13). В приведенной ниже диаграмме показана наиболее естественная последовательность чтения глав.
   
    Существует целый ряд исторически сложившихся и противоречащих друг другу взглядов на Пролог. Пролог быстро завоевал популярность в Европе как практический инструмент программирования. В Японии Пролог оказался в центре разработки компьютеров пятого поколения. С другой стороны, в связи с определенными историческими факторами, в США Пролог получил признание несколько позднее. Один из этих факторов был связан с предварительным знакомством с Микропленнером, языком, близким к логическому программированию, но реализованным не эффективно. Этот отрицательный опыт, относящийся к Микропленнеру, был неоправданно распространен и на Пролог, но позднее, после появления эффективной реализации, предложенной Дэвидом Уорреном, это предубеждение было убедительно снято. Определенная сдержанность по отношению к Прологу объяснялась также существованием "ортодоксальной школы" логического программирования, сторонники которой настаивали на использовании чистой логики, не запятнанной добавлением практически полезных внелогических средств. Практикам в области применения Пролога удалось изменить эту бескомпромиссную позицию и принять более прагматический подход, позволивший удачно сочетать декларативный принцип с традиционным - процедурным. И наконец, третьим фактором, приведшим к задержке признания Пролога, явилось то обстоятельство, что в США в течение долгого времени Лисп не имел серьезных конкурентов среди языков искусственного интеллекта. Понятно поэтому, что в исследовательских центрах с сильными лисповскими традициями возникало естественное противодействие Прологу. Но со временем соперничество между Прологом и Лиспом потеряло свою остроту, и в настоящее время многие считают, что оптимальный подход состоит в сочетании идей, лежащих в основе этих двух языков.
    Благодарности
    Интерес к Прологу впервые возник у меня под влиянием Дональда Мики. Я благодарен также Лоренсу Берду, Фернандо Перейра и Дэвиду Г. Уоррену, входившим в свое время в эдинбургскую группу разработчиков Пролога, за их советы по составлению программ и многочисленные дискуссии. Чрезвычайно полезными были замечания и предложения, высказанные Эндрью Макгеттриком и Патриком Уинстоном. Среди прочитавших рукопись книги и сделавших ценные замечания были также Игорь Кононенко, Таня Маярон, Игорь Мозетик, Тимоти Ниблетт и Фрэнк Зердин. Мне бы хотелось также поблагодарить Дебру Майсон-Этерингтон и Саймона Пламтри из издательства Эддисон-Уэсли за труд, вложенный в издание этой книги. И наконец, эта книга не могла бы появиться на свет без стимулирующего влияния творческой деятельности всего международного сообщества специалистов по логическому программированию.
    Иван Братко
    Институт Тьюринга, Глазго

    Январь 1986

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд


    Часть 1
    ЯЗЫК ПРОЛОГ

   


    Глава 1
    ОБЩИЙ ОБЗОР ЯЗЫКА ПРОЛОГ
    В этой главе на примере конкретной программы рассматриваются основные механизмы Пролога. Несмотря на то, что материал излагается в основном неформально, здесь вводятся многие важные понятия.
    1. 1.    Пример программы: родственные отношения
    Пролог - это язык программирования, предназначенный для обработки символьной нечисловой информации. Особенно хорошо он приспособлен для решения задач, в которых фигурируют объекты и отношения между ними. На рис. 1.1 представлен пример - родственные отношения. Тот факт, что Том является родителем Боба, можно записать на Прологе так:
            родитель( том, боб).
    Здесь мы выбрали родитель в качестве имени отношения, том и боб - в качестве аргументов этого отношения. По причинам, которые станут понятны позднее, мы записываем такие имена, как том, начиная со строчной буквы. Все дерево родственных отношений рис. 1.1 описывается следующей пролог-программой:
            родитель( пам, боб).

            родитель( том, боб).

            родитель( том, лиз).

            родитель( боб, энн).

            родитель( боб, пат).

            родитель( пам, джим).

   
    Рис. 1. 1.  Дерево родственных
    отношений.
    Эта программа содержит шесть предложений. Каждое предложение объявляет об одном факте наличия отношения родитель.
    После ввода такой программы в пролог-систему последней можно будет задавать вопросы, касающиеся отношения родитель. Например, является ли Боб родителем Пат? Этот вопрос можно передать пролог-системе, набрав на клавиатуре терминала:
            ?-  родитель( боб, пат).
    Найдя этот факт в программе, система ответит
            yes            (да)
    Другим вопросом мог бы быть такой:
            ?-  родитель( лиз, пат).
    Система ответит
            no             (нет),
    поскольку в программе ничего не говорится о том, является ли Лиз родителем Пат. Программа ответит "нет" и на вопрос
            ?-  родитель( том, бен).
    потому, что имя Бен в программе даже не упоминается.
    Можно задавать и более интересные вопросы. Например:"Кто является родителем Лиз?"
           ?-  родитель( X, лиз).
    На этот раз система ответит не просто "да" или "нет". Она скажет нам, каким должно быть значение X (ранее неизвестное), чтобы вышеприведенное утверждение было истинным. Поэтому мы получим ответ:
            X  =  том
    Вопрос "Кто дети Боба?" можно передать пролог-системе в такой форме:
            ?-  родитель( боб, X).
    В этом случае возможно несколько ответов. Сначала система сообщит первое решение:
            X  =  энн
    Возможно, мы захотим увидеть и другие решения. О нашем желании мы можем сообщить системе (во многих реализациях для этого надо набрать точку с запятой), и она найдет другой ответ:
            X  =  пат
    Если мы потребуем дальнейших решений, система ответит "нет", поскольку все решения исчерпаны.
    Нашей программе можно задавать и более общие вопросы: "Кто чей родитель?" Приведем другую формулировку этого вопроса:
            Найти X и Y такие, что X - родитель Y.
    На Прологе это записывается так:
            ?-  родитель( X, Y).
    Система будет по очереди находить все пары вида "родитель-ребенок". По мере того, как мы будем требовать от системы новых решений, они будут выводиться на экран одно за другим до тех пор, пока все они не будут найдены. Ответы выводятся следующим образом:
            X  =  пам

            Y  =  боб;
            X  =  том

            Y  =  боб;
            X  =  том

            Y  =  лиз;
            .  .  .
    Мы можем остановить поток решений, набрав, например, точку вместо точки с запятой (выбор конкретного символа зависит от реализации).
    Нашей программе можно задавать и еще более сложные вопросы, скажем, кто является родителем родителя Джима? Поскольку в нашей программе прямо не сказано, что представляет собой отношение родительродителя, такой вопрос следует задавать в два этапа, как это показано на рис. 1.2.
            (1)    Кто родитель Джима?   Предположим, что это некоторый Y.
            (2)    Кто родитель Y?   Предположим, что это некоторый X.
    Такой составной вопрос на Прологе записывается в виде последовательности двух простых вопросов:
            ?-  родитель( Y, джим), родитель( X, Y).
    Ответ будет:
            X  =  боб

            Y  =  пат
   

    Рис. 1. 2.   Отношение родительродителя, выраженное через композицию двух отношений родитель.

    Наш составной вопрос можно интерпретировать и так: "Найти X и Y, удовлетворяющие следующим двум требованиям":
            родитель ( Y, джим)  и   родитель( X, У)
    Если мы поменяем порядок этих двух требований, то логический смысл останется прежним:
            родитель ( X, Y)   и   родитель ( Y, джим)
    Этот вопрос можно задать нашей пролог-системе и в такой форме:
            ?-  родитель( X, Y), родитель( Y, джим).
    При этом результат будет тем же. Таким же образом можно спросить: "Кто внуки Тома?"
            ?-  родитель( том, X), родитель( X, Y).
    Система ответит так:
            X  =  боб

            Y  =  энн;
            X  =  боб

            Y  =  пат
    Следующим вопросом мог бы быть такой: "Есть ли у Энн и Пат общий родитель?" Его тоже можно выразить в два этапа:
            (1)    Какой X является родителем Энн?

            (2)    Является ли (тот же) X родителем Пат?
    Соответствующий запрос к пролог-системе будет тогда выглядеть так:
            ?-  родитель( X, энн), родитель( X, пат).
    Ответ:
            X  =  боб
    Наша программа-пример помогла проиллюстрировать некоторые важные моменты:
    На Прологе легко определить отношение, подобное отношению родитель, указав n-ку объектов, для которых это отношение выполняется.
    Пользователь может легко задавать пролог-системе вопросы, касающиеся отношений, определенных в программе.
    Пролог-программа состоит из предложений. Каждое предложение заканчивается точкой.
    Аргументы отношения могут быть (среди прочего): конкретными объектами, или константами (такими, как том и энн), или
    абстрактными объектами, такими, как
    X
    и
    Y
    . Объекты первого типа называются
    атомами
    . Объекты второго типа -
    переменными
    .
    Вопросы к системе состоят из одного или более целевых утверждений (или кратко целей). Последовательность целей, такая как


            родитель( X, энн), родитель( X, пат)


    означает конъюнкцию этих целевых утверждений:


            X  -  родитель Энн   и

            X  -  родитель Пат.


    Пролог-система рассматривает вопросы как цели, к достижению которых нужно стремиться.

    Ответ на вопрос может оказаться или положительным или отрицательным в зависимости от того, может ли быть соответствующая цель достигнута или нет. В случае положительного ответа мы говорим, что соответствующая цель достижима и успешна. В противном случае цель   недостижима,   имеет неуспех   или   терпит неудачу.
    Если на вопрос существует несколько ответов, пролог-система найдет столько из них, сколько пожелает пользователь.
    Упражнения
    1. 1.    Считая, что отношение родитель определено так же, как и раньше в данном разделе (см. рис. 1.1), найдите, какими будут ответы пролог-системы на следующие вопросы:
            (a)        ?   -  родитель ( джим, X).
            (b)        ?   -  родитель( X, джим).
            (c)        ?   -  родитель( пам,Х), родитель( Х, пат).
            (d)        ?   -  родитель( пам, X), родитель( Х, Y),

                            родитель( Y, джим).
    Посмотреть ответ
    1. 2.    Сформулируйте на Прологе следующие вопросы об отношении родитель:
            (a)        Кто родитель Пат?
            (b)        Есть ли у Лиз ребенок?
            (c)        Кто является родителем родителя Пат?
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    1. 2.    Расширение программы-примера с помощью правил
    Нашу программу-пример можно легко расширить многими интересными способами. Давайте сперва добавим информацию о том, каков пол людей, участвующих в отношении родитель. Это можно сделать, просто добавив в нее следующие факты:
            женщина( пам).

            мужчина( том).

            мужчина( боб).

            женщина( лиз).

            женщина( пат).

            женщина( энн).

            мужчина( джим).
    Мы ввели здесь два новых отношения - мужчина и женщина. Эти отношения - унарные (или одноместные). Бинарное отношение, такое как родитель, определяет отношение между двумя объектами; унарные же можно использовать для объявления наличия (отсутствия) простых свойств у объектов. Первое из приведенных выше предложений читается так: Пам - женщина. Можно было бы выразить информацию, представляемую этими двумя унарными отношениями (мужчина и женщина), по-другому - с помощью одного бинарного отношения пол. Тогда новый фрагмент нашей программы выглядел бы так:
            пол( пам, женский).

            пол( том, мужской).

            пол( боб, мужской).

            .  .  .
    В качестве дальнейшего расширения нашей программы-примера давайте введем отношение отпрыск, которое обратно отношению родитель. Можно было бы определить отпрыск тем же способом, что и родитель, т.е. представив список простых фактов наличия этого отношения для конкретных пар объектов, таких, что один является отпрыском другого. Например:
           отпрыск( лиз, том).
    Однако это отношение можно определить значительно элегантнее, использовав тот факт, что оно обратно отношению родитель, которое уже определено. Такой альтернативный способ основывается на следующем логическом утверждении:
            Для всех X и Y

                    Y является отпрыском X, если

                    X является родителем Y.
    Эта формулировка уже близка к формализму, принятому в Прологе. Вот соответствующее прологовское предложение, имеющее тот же смысл:
           отпрыск( Y, X) :- родитель( X, Y).
    Это предложение можно прочитать еще и так:
            Для всех X и Y,

                    если X - родитель Y, то

                    Y - отпрыск X.
    Такие предложения Пролога, как
            отпрыск( Y, X) :- родитель( X, Y).
    называются правилами. Есть существенное различие между фактами и правилами. Факт, подобный факту
           родитель( том, лиз).
    это нечто такое, что всегда, безусловно истинно. Напротив, правила описывают утверждения, которые могут быть истинными, только если выполнено некоторое условие. Поэтому можно сказать, что правила имеют
    условную часть (правая половина правила) и
    часть вывода (левая половина правила).
    Вывод называют также головой предложения, а условную часть - его телом. Например:
            отпрыск( Y, X) :- родитель( X, Y).

                    голова                         тело
    Если условие родитель( X, Y) выполняется (оно истинно), то логическим следствием из него является утверждение отпрыск( Y, X).
    На приведенном ниже примере проследим, как в действительности правила используются Прологом. Спросим нашу программу, является ли Лиз отпрыском Тома:
           ?  -  отпрыск( лиз, том).
    В программе нет фактов об отпрысках, поэтому единственный способ ответить на такой вопрос - это применить правило о них. Правило универсально в том смысле, что оно применимо к любым объектам X и Y, следовательно, его можно применить и к таким конкретным объектам, как лиз и том. Чтобы это сделать, нужно вместо Y подставить в него лиз, а вместо X - том. В этом случае мы будем говорить, что переменные X и Y конкретизируются:
           X  =  том    и   Y  =  лиз
    После конкретизации мы получаем частный случай нашего общего правила. Вот он:
           отпрыск( лиз, том) :- родитель( том, лиз).
    Условная часть приняла вид:
           родитель( том, лиз)
    Теперь пролог-система попытается выяснить, выполняется ли это условие (является ли оно истинным). Для этого исходная цель
            отпрыск( лиз, том)
    заменяется подцелью
            родитель( том, лиз)
    Эта (новая) цель достигается тривиально, поскольку такой факт можно найти в нашей программе. Это означает, что утверждение, содержащееся в выводе правила, также истинно, и система ответит на вопрос yes (да).
    Добавим теперь в нашу программу-пример еще несколько родственных отношений. Определение отношения мать может быть основано на следующем логическом утверждении:
            Для всех X и Y

                    X является матерью Y, если

                    X является родителем Y и

                    Х - женщина.
    На Пролог это переводится в виде такого правила:
            мать( X, Y) :- родитель( X, Y), женщина( X).
    Запятая между двумя условиями указывает ка конъюнкцию условий. Это означает, что они должны быть выполнены оба одновременно.
   
    Рис. 1. 3.  Графы отношений родительродителя, мать и отпрыск,

    определенных через другие отношения.
    Такие отношения как родитель, отпрыск и мать можно изобразить в виде диаграмм, приведенных на рис. 1.3. Они нарисованы с учетом следующих соглашений. Вершины графа соответствуют объектам, т.е. аргументам отношений. Дуги между вершинами соответствуют бинарным (двуместным) отношениям. Дуги направлены от первого аргумента к второму. Унарные отношения на диаграмме изображаются просто пометкой соответствующих объектов именем отношения. Отношения, определяемые через другие отношения, представлены штриховыми дугами. Таким образом, любую диаграмму следует понимать так: если выполнены отношения, изображенные сплошными дугами, тогда и отношение, изображенное штриховой дугой, тоже выполнено. В соответствии с рис. 1.3, отношение родительродителя можно сразу записать на Прологе:
            родительродителя( X, Z) :- родитель( X, Y),

                                                            родитель( Y, Z).
    Здесь уместно сделать несколько замечаний о внешнем виде нашей программы. Пролог дает почти полную свободу расположения текста на листе. Так что можно вставлять пробелы и переходить к новой строке в любом месте текста по вкусу. Вообще мы хотим сделать так, чтобы наша программа имела красивый и аккуратный вид, а самое главное, легко читалась. Для этого мы часто будем помещать голову предложения и каждую цель на отдельной строке. При этом цели мы будем писать с отступом, чтобы сделать разницу между головой и целями более заметной. Например, правило родительродителя в соответствии с этими соглашениями запишется так:
            родительродителя( X, Z) :-

                    родитель( X, Y),

                    родитель( Y, Z).
    На рис. 1.4 показано отношение сестра:
        Для любых X и Y

             X является сестрой Y, если

             (1)        у X и Y есть общий родитель, и

             (2)        X - женщина.
   
    Рис. 1. 4.  Определение отношения сестра.
    Граф на рис. 1.4 можно перевести на Пролог так:
            сестра( X, Y) :-

                    родитель( Z, X),

                    родитель( Z, Y),

                    женщина( X).
    Обратите внимание на способ, с помощью которого выражается требование "у X и Y есть общий родитель". Была использована следующая логическая формулировка: "некоторый Z должен быть родителем X и этот же самый Z должен быть родителем Y". По-другому, менее красиво, можно было бы сказать так: "Z1 - родитель X, Z2 - родитель Y и Z1 равен Z2".
    Теперь можно спросить:
           ?-  сестра( энн, пат).
    Как и ожидается, ответ будет "yes" (да) (см. рис. 1.1). Мы могли бы заключить отсюда, что определенное нами отношение сестра работает правильно. Тем не менее в нашей программе есть маленькое упущение, которое обнаружится, если задать вопрос: "Кто является сестрой Пат?"
           ?-  сестра( X, пат).
    Система найдет два ответа, один из которых может показаться неожиданным:
            X  =  энн;

            X  =  пат
    Получается, что Пат - сестра себе самой?! Наверное, когда мы определяли отношение сестра, мы не имели этого ввиду. Однако ответ Пролога совершенно логичен, поскольку он руководствовался нашим правилом, а это правило ничего не говорит о том, что, если X - сестра Y, то X и Y не должны совпадать. Пролог (с полным правом) считает, что X и Y могут быть одним и тем же объектом и в качестве следствия из этого делает вывод, что любая женщина, имеющая родителя, является сестрой самой себе.
    Чтобы исправить наше правило о сестрах, его нужно дополнить утверждением, что X и Y должны различаться. В следующих главах мы увидим, как это можно сделать, в данный же момент мы предположим, что отношение различны уже известно пролог-системе и что цель
           различны( X, Y)
    достигается тогда и только тогда, когда X и Y не равны. Усовершенствованное правило для отношения сестра примет тогда следующий вид:
           сестра( X, Y) :-

                    родитель( Z, X),

                    родители( Z, Y),

                    женщина( X),

                    различны( X, Y).
    Некоторые важные моменты этого раздела:
    Пролог-программы можно расширять, добавляя в них новые предложения.
    Прологовские предложения бывают трех типов:
    факты
    ,
    правила
    и
    вопросы
    .
    Факты содержат утверждения, которые
    являются всегда, безусловно верными.
    Правила содержат утверждения, истинность которых зависит от некоторых условий.
    С помощью вопросов пользователь может спрашивать систему о том, какие утверждения являются
    истинными
    .
    Предложения Пролога состоят из
    головы
    и
    тела
    .
    Тело
    - это список
    целей
    , разделенных запятыми. Запятая понимается как конъюнкция.
    Факты - это предложения, имеющие пустое тело. Вопросы имеют только тело. Правила имеют голову и (непустое) тело.
    По ходу вычислений вместо переменной может быть подставлен другой объект. Мы говорим в этом случае, что переменная конкретизирована.
    Предполагается, что на переменные действует квантор всеобщности, читаемый как "для всех...". Однако для переменных, появляющихся только в теле, возможны и другие формулировки. Например,


            имеетребенка( X) :- родитель( X, Y).


    можно прочитать двумя способами:


    (а)        Для всех X и Y,

                если X - отец Y, то

                X имеет ребенка.


    (б)        Для всех X,

                X имеет ребенка, если

                существует некоторый Y, такой, что

                X - родитель Y.
    Упражнения
    1. 3.    Оттранслируйте следующие утверждения в правила на Прологе:
    (a)    Всякий, кто имеет ребенка, - счастлив (введите одноаргументное отношение счастлив).
    (b)    Всякий X, имеющий ребенка, у которого есть сестра, имеет двух детей (введите новое отношение иметьдвухдетей).
    Посмотреть ответ
    1. 4.    Определите отношение внук, используя отношение родитель. Указание: оно будет похоже на отношение родительродителя (см. рис. 1.3).
    Посмотреть ответ
    1. 5.    Определите отношение тетя( X, Y) через отношение родитель и сестра. Для облегчения работы можно сначала изобразить отношение тетя в виде диаграммы по типу тех, что изображены на рис. 1.3.
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    1. 3.    Рекурсивное определение правил
    Давайте добавим к нашей программе о родственных связях еще одно отношение - предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных (ближайших) предков, а второе - отдаленных. Будем говорить, что некоторый является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных
   
    Рис. 1. 5.  Пример отношения предок:

    (а)    X - ближайший предок Z;     (b)    X - отдаленный предок Z.
    между собой отношением родитель-ребенок, как показано на рис.1.5. В нашем примере на рис. 1.1   Том - ближайший предок Лиз и отдаленный предок Пат.
    Первое правило простое и его можно сформулировать так:
        Для всех X и Z,

              X - предок Z, если

              X - родитель Z.
    Это непосредственно переводится на Пролог как
        предок( X, Z) :-

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

                    родитель( X, Z).
            предок( X, Z) :-

                     родитель( X, Y),

                     родитель( Y, Z).
            предок( X, Z) :-

                     родитель( X, Y1),

                     родитель( Yl, Y2),

                     родитель( Y2, Z).
            предок( X, Z) :-

                     родитель( X, Y1),

                     родитель( Y1, Y2),

                     родитель( Y2, Y3),

                     родитель( Y3, Z).
            .  .  .

   
    Рис. 1. 6.  Пары предок-потомок, разделенных разным числом поколений.
    Эта программа длинна и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения.
    Существует, однако, корректная и элегантная формулировка отношения предок - корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь - определить отношение предок через него самого. Рис 1.7 иллюстрирует эту идею:
            Для всех X и Z,

                  X - предок Z, если

                   существует Y, такой, что

                   (1)    X - родитель Y и

                   (2)    Y - предок Z.
    Предложение Пролога, имеющее тот же смысл, записывается так:
           предок( X, Z) :-

                    родитель( X, Y),

                    предок( Y, Z).
    Теперь мы построили полную программу для отношения предок, содержащую два правила: одно для ближайших предков и другое для отдаленных предков. Здесь приводятся они оба вместе:
           предок( X, Z) :-

                    родитель( X, Z).
            предок( X, Z) :-

                    родитель( X, Y),

                    предок( Y, Z).
   
    Рис 1. 7.  Рекурсивная формулировка отношения предок.
    Ключевым моментом в данной формулировке было использование самого отношения предок в его определении. Такое определение может озадачить - допустимо ли при определении какого-либо понятия использовать его же, ведь оно определено еще не полностью. Такие определения называются рекурсивными. Логически они совершенно корректны и понятны; интуитивно это ясно, если посмотреть на рис. 1.7. Но будет ли в состоянии пролог-система использовать рекурсивные правила? Оказывается, что пролог-система очень легко может обрабатывать рекурсивные определения. На самом деле, рекурсия - один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.
    Возвращаясь к нашей программе, можно теперь задать системе вопрос: "Кто потомки Пам?" То есть: "Кто тот человек, чьим предком является Пам ?"
           ?-  предок( пам, X).
            X  =  боб;

            X  =  энн;

            X  =  пат;

            X  =  джим
    Ответы системы, конечно, правильны, и они логически вытекают из наших определений отношений предок и родитель. Возникает, однако, довольно важный вопрос: "Как в действительности система использует программу для отыскания этих ответов?"
    Неформальное объяснение того, как система это делает, приведено в следующем разделе. Но сначала давайте объединим все фрагменты нашей программы о родственных отношениях, которая постепенно расширялась по мере того, как мы вводили в нее новые факты и правила. Окончательный вид программы показан на рис. 1.8.
    При рассмотрении рис. 1.8 следует учесть два новых момента: первый касается понятия "процедура", второй - комментариев в программах. Программа, приведенная на рис. 1.8, определяет несколько отношений - родитель, мужчина, женщина, предок и т.д. Отношение предок, например, определено с помощью двух предложений. Будем говорить, что эти два предложения входят в состав отношения
    родитель( пам, боб).                 % Пам - родитель Боба

    родитель( том, боб).

    родитель( том, лиз).

    родитель( бoб, энн).

    родитель( боб, пат).

    родитель( пат, джим).
    женщина( пам).                        % Пам - женщина

    мужчина( том).                         % Том - мужчина

    мужчина( боб).

    женщина( лиз).

    женщина( энн).

    женщина( пат).

    мужчина( джим).
    отпрыск( Y, X) :-                      % Y - отпрыск X, если

          родитель( X, Y).                  % X - родитель Y
        мать( X, Y) :-                         % X - мать Y, если

                родитель( X, Y),            % X - родитель Y и

                женщина( X).                % X - женщина
    родительродителя( X, Z) :-

                                        % X - родитель родителя Z, если

                родитель( X, Y),            % X - родитель Y и

                родитель( Y, Z).            % Y - родитель Z
        сестра( X, Y) :-                       % X - сестра Y

                родитель( Z, X),

                родитель( Z, Y)

                                % X и Y имеют общего родителя

                женщина( X, Y),            % X - женщина и

                различны( X, Y).           % X отличается от Y
    предок( X, Z) :-                          % Правило пр1:  X - предок Z

                 родитель( X, Z).
    предок( X, Z) :-                          % Правило пр2:  X - предок Z

            родитель( X, Y),

            предок( Y, Z).
    Рис. 1. 8.   Программа о родственных отношениях.
    предок. Иногда бывает удобно рассматривать в целом все множество предложений, входящих в состав одного отношения. Такое множество называется процедурой.
    На рис. 1.8 два предложения, входящие в состав отношения предок, выделены именами "пр1" и "пр2", добавленными в программу в виде комментариев. Эти имена будут использоваться в дальнейшем для ссылок на соответствующие правила. Вообще говоря, комментарии пролог-системой игнорируются. Они нужны лишь человеку, который читает программу. В Прологе комментарии отделяются от остального текста программы специальными скобками "/*" и "*/". Таким образом, прологовский комментарий выглядит так
    /*    Это комментарий    */
    Другой способ, более практичный для коротких комментариев, использует символ процента %. Все, что находится между % и концом строки, расценивается как комментарии:
    %    Это тоже комментарий
    Упражнение
    1. 6.    Рассмотрим другой вариант отношения предок:
        предок( X, Z) :-

               родитель( X, Z).
        предок( X, Z) :-

               родитель( Y, Z).

               предок( X, Y).
    Верно ли и такое определение? Сможете ли Вы изменить диаграмму на рис. 1.7 таким образом, чтобы она соответствовала новому определению?
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    1. 4.    Как пролог-система отвечает на вопросы
    В данном разделе приводится неформальное объяснение того, как пролог-система отвечает на вопросы.
    Вопрос к системе - это всегда последовательность, состоящая из одной или нескольких целей. Для того, чтобы ответить на вопрос, система пытается достичь всех целей. Что значит достичь цели? Достичь цели - это значит показать, что утверждения, содержащиеся в вопросе, истинны в предположении, что все отношения программы истинны. Другими словами, достичь цели - это значит показать, что она логически следует из фактов и правил программы. Если вопрос содержит переменные, система должна к тому же найти конкретные объекты, которые (будучи подставленными вместо переменных) обеспечивают достижение цели. Найденные конкретизации сообщаются пользователю. Если для некоторой конкретизации система не в состоянии вывести цель из остальных предложений программы, то ее ответом на вопрос будет "нет".
    Таким образом, подходящей интерпретацией пролог-программы в математических терминах будет следующая: пролог-система рассматривает факты и правила в качестве множества аксиом, а вопрос пользователя - как теорему; затем она пытается доказать эту теорему, т.е. показать, что ее можно логически вывести из аксиом.
    Проиллюстрируем этот подход на классическом примере. Пусть имеются следующие аксиомы:
            Все люди смертны.

            Сократ - человек.
    Теорема, логически вытекающая из этих двух аксиом:
            Сократ смертен.
    Первую из вышеуказанных аксиом можно переписать так:
            Для всех X, если X - человек, то X смертен.
    Соответственно наш пример можно перевести на Пролог следующим образом:
           смертен( X) :- человек( X).                    % Все люди смертны

           человек( сократ).                                     % Сократ - человек

           ?-  смертен( сократ).                                % Сократ смертен?

           yes                   (да)
    Более сложный пример из программы о родственных отношениях, приведенной на рис. 1.8:
           ?-  предок( том, пат)
    Мы знаем, что родитель( боб, пат) - это факт. Используя этот факт и правило пр1, мы можем сделать вывод, что утверждение предок( боб, пат) истинно. Этот факт получен в результате вывода - его нельзя найти непосредственно в программе, но можно вывести, пользуясь содержащимися в ней фактами и правилами. Подобный шаг вывода можно коротко записать
           родитель( боб, пат) ==> предок( боб, пат)
    Эту запись можно прочитать так: из родитель( боб, пат) следует предок( боб, пат) на основании правила пр1. Далее, нам известен факт родитель( том, боб). На основании этого факта и выведенного факта предок( боб, пат) можно заключить, что, в силу правила пр2, наше целевое утверждение предок( том, пат) истинно. Весь процесс вывода, состоящий из двух шагов, можно записать так:
           родитель(боб, пат) ==> предок( боб, пат)
            родитель(том, боб)  и   предок( боб, пат)    ==>

                   предок( том, пат)
    Таким образом, мы показали, какой может быть последовательность шагов для достижения цели, т.е. для демонстрации истинности целевого утверждения. Назовем такую последовательность цепочкой доказательства. Однако мы еще не показали как пролог-система в действительности строит такую цепочку.
    Пролог-система строит цепочку доказательства в порядке, обратном по отношению к тому, которым мы только что воспользовались. Вместо того, чтобы начинать с простых фактов, приведенных в программе, система начинает с целей и, применяя правила, подменяет текущие цели новыми, до тех пор, пока эти новые цели не окажутся простыми фактами. Если задан вопрос
           ?-  предок( том, пат).
    система попытается достичь этой цели. Для того, чтобы это сделать, она пробует найти такое предложение в программе, из которого немедленно следует упомянутая цель. Очевидно, единственными подходящими для этого предложениями являются пр1 и пр2.
   
    Рис. 1. 9.  Первый шаг вычислений. Верхняя цель истинна, если истинна нижняя.
    Это правила, входящие в отношение предок. Будем говорить, что головы этих правил сопоставимы с целью.
    Два предложения пр1 и пр2 описывают два варианта продолжения рассуждений для пролог-системы. Вначале система пробует предложение, стоящее в программе первым:
           предок( X, Z) :- родитель( X, Z).
    Поскольку цель - предок( том, пат), значения переменным должны быть приписаны следующим образом:
           X  =  том,  Z  =   пат
    Тогда исходная цель предок( том, пат) заменяется новой целью:
           родитель( том, пат)
    Такое действие по замене одной цели на другую на основании некоторого правила показано на рис. 1.9. В программе нет правила, голова которого была бы сопоставима с целью родитель(том, пат), поэтому такая цель оказывается неуспешной. Теперь система делает возврат к исходной цели, чтобы попробовать второй вариант вывода цели верхнего уровня предок( том, пат). То есть, пробуется правило пр2:
           предок( X, Z) :-

                   родитель( X, Y),

                   предок( Y, Z).
    Как и раньше, переменным X и Z приписываются значения:
           X  =  том,   Z   =  пат
    В этот момент переменной Y еще не приписано никакого значения. Верхняя цель предок( том, пат) заменяется двумя целями:
           родитель( том, Y),

            предок( Y, пат)
    Этот шаг вычислений показан на рис. 1.10, который представляет развитие ситуации, изображенной на рис. 1.9.
   
    Рис. 1. 10.  Продолжение процесса вычислений, показанного на рис. 1.9.
    Имея теперь перед
    собой
    две
    цели, система пытается достичь их в том порядке, каком они
    записаны. Достичь первой из них легко, поскольку она
    соответствует
    факту из программы. Процесс установления соответствия - сопоставление (унификация) вызывает приписывание переменной Y значения
    боб
    . Тем самым достигается первая цель, а оставшаяся превращается в
           предок( боб, пат)
    Для достижения этой цели вновь применяется правило пр1. Заметим, - что это (второе) применение правила никак не связано с его первым применением. Поэтому система использует новое множество переменных правила всякий раз, как оно применяется. Чтобы указать это, мы переименуем переменные правила пр1 для нового его применения следующим образом:
           предок( X ', Z ') :-

                   родитель( X ', Z ').
    Голова этого правила должна соответствовать нашей текущей цели предок( боб, пат). Поэтому
           X '  =  боб,   Z '   =  пат
    Текущая цель заменяется на
           родитель( боб, пат)
    Такая цель немедленно достигается, поскольку встречается в программе в качестве факта. Этот шаг завершает вычисление, что графически показано на рис. 1.11.
   
    Рис. 1. 11.  Все шаги достижения цели предок( том, пат). Правая

    ветвь демонстрирует, что цель достижима.
    Графическое представление шагов вычисления на рис. 1.11 имеет форму дерева. Вершины дерева соответствуют целям или спискам целей, которые требуется достичь. Дуги между вершинами соответствуют применению (альтернативных) предложений программы, которые преобразуют цель, соответствующую одной вершине, в цель, соответствующую другой вершине. Корневая (верхняя) цель достигается тогда, когда находится путь от корня дерева (верхней вершины) к его листу, помеченному меткой "да". Лист помечается меткой "да", если он представляет собой простой факт. Выполнение пролог-программы состоит в поиске таких путей. В процессе такого поиска система может входить и в ветви, приводящие к неуспеху. В тот момент, когда она обнаруживает, что ветвь не приводит к успеху, происходит автоматический возврат к предыдущей вершине, и далее следует попытка применить к ней альтернативное предложение.
    Упражнение
    1. 7.    Постарайтесь понять, как пролог-система, используя программу, приведенную на рис. 1.8, выводит ответы на указанные ниже вопросы. Попытайтесь нарисовать соответствующие диаграммы вывода по типу тех, что изображены на рис.1.9 -1.11. Будут ли встречаться возвраты при выводе ответов на какие-либо из этих вопросов?
        (a)        ?-   родитель( пам, боб).
        (b)        ?-  мать( пам, боб).
        (с)        ?-   родительродителя( пам, энн).
        (d)        ?-   родительродителя( боб, джим).
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    1. 5.    Декларативный и процедурный смысл программ
    До сих пор во всех наших примерах всегда можно было понять результаты работы программы, точно не зная, как система в действительности их нашла. Поэтому стоит различать два уровня смысла программы на Прологе, а именно:
    декларативный смысл и
    процедурный смысл.
    Декларативный смысл касается только отношений, определенных в программе. Таким образом, декларативный смысл определяет, что должно быть результатом работы программы. С другой стороны, процедурный смысл определяет еще и как этот результат был получен, т. е. как отношения реально обрабатываются пролог-системой.
    Способность пролог-системы прорабатывать многие процедурные детали самостоятельно считается одним из специфических преимуществ Пролога. Это свойство побуждает программиста рассматривать декларативный смысл программы относительно независимо от ее процедурного смысла. Поскольку результаты работы программы в принципе определяются ее декларативным смыслом, последнего (Опять же в принципе) достаточно для написания программ. Этот факт имеет практическое значение, поскольку декларативные аспекты программы являются, обычно, более легкими для понимания, нежели процедурные детали. Чтобы извлечь из этого обстоятельства наибольшую пользу, программисту следует сосредоточиться главным образом на декларативном смысле и по возможности не отвлекаться на детали процесса вычислений. Последние следует в возможно большей мере предоставить самой пролог-системе.
    Такой декларативный подход и в самом деле часто делает программирование на Прологе более легким, чем на таких типичных процедурно-ориентированных языках, как Паскаль. К сожалению, однако, декларативного подхода не всегда оказывается, достаточно. Далее станет ясно, что, особенно в больших программах, программист не может полностью игнорировать процедурные аспекты по соображениям эффективности вычислений. Тем не менее следует поощрять декларативный стиль мышления при написании пролог-программ, а процедурные аспекты игнорировать в тех пределах, которые устанавливаются практическими ограничениями.
    Резюме
    Программирование на Прологе состоит в определении отношений и в постановке вопросов, касающихся этих отношений.
    Программа состоит из предложений. Предложения бывают трех типов: факты, правила и вопросы.
    Отношение может определяться фактами, перечисляющими n-ки объектов, для которых это отношение выполняется, или же оно может определяться правилами.
    Процедура - это множество предложений об одном и том же отношении.
    Вопросы напоминают запросы к некоторой базе данных. Ответ системы на вопрос представляет собой множество объектов, которые удовлетворяют запросу.
    Процесс, в результате которого пролог-система устанавливает, удовлетворяет ли объект запросу, часто довольно сложен и включает в себя логический вывод, исследование различных вариантов и, возможно, возвраты. Все это делается автоматически самой пролог-системой и по большей части скрыто от пользователя.
    Различают два типа смысла пролог-программ: декларативный и процедурный. Декларативный подход предпочтительнее с точки зрения программирования. Тем не менее, программист должен часто учитывать также и процедурные детали.
    В данной главе были введены следующие понятия:


        предложение, факт, правило, вопрос

        голова предложения, тело предложения

        рекурсивное правило

        рекурсивное определение

        процедура

        атом, переменная

        конкретизация переменной

        цель

        цель достижима, цель успешна

        цель недостижима,

        цель имеет неуспех, цель терпит неудачу

        возврат

        декларативный смысл, процедурный смысл.
    Литература
    Различные реализации Пролога используют разные синтаксические соглашения. В данной книге мы применяем так называемый Эдинбургский синтаксис (его называют также синтаксисом DEC-10, поскольку он принят в известной реализации Пролога для машины DEC-10; см. Pereira и др. 1978), он используется во многих популярных пролог-системах, таких как Quintus Prolog, Poplog, CProlog, Arity/ Prolog, Prolog-2 и т.д.
    Bowen D. L. (1981). DECsystem-10 Prolog User's Manual. University of Edinburgh: Department of Artificial Intelligence.
    Mellish С. and Hardy S. (1984). Integrating Prolog in the POPLOG environment. Implementations of Prolog (J. A. Campbell, ed.). Ellis Horwood.
    Pereira F. (1982). C-Prolog User's Manual. University of Edinburgh: Department of Computer-Aided Architectural Design.
    Pereira L. M., Pereira F., Warren D. H. D. (1978). User's Guide to DECsystem-10 Prolog. University of Edinburgh: Department of Artificial Intelligence.
    Quintus Prolog User's Guide and Reference Manual. Palo Alto: Quintus Computer System Inc. (1985).
    The Arity/Prolog Programming Language. Concord, Massachusetts: Arity Corporation (1986).

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд

    Глава 2
    СИНТАКСИС И СЕМАНТИКА ПРОЛОГ ПРОГРАММ
    В данной главе дается систематическое изложение синтаксиса и семантики основных понятий Пролога, а также вводятся структурные объекты данных. Рассматриваются следующие темы:
    простые объекты данных (атомы, числа, переменные)
    структурные объекты
    сопоставление как основная операция над объектами
    декларативная (или непроцедурная) семантика программ
    взаимосвязь между декларативным и процедурным смыслами программ
    изменение процедурного смысла путем изменения порядка следования предложений и целей
    Большая часть этих тем уже была затронута в гл. 1. Теперь их изложение будет более формальным и детализированным.
    2. 1.    Объекты данных
    На рис. 2.1 приведена классификация объектов данных Пролога. Пролог-система распознает тип объекта по его синтаксической форме в тексте программы. Это возможно благодаря тому, что синтаксис Пролога
   
    Рис. 2. 1.  Обьекты данных Пролога.
    предписывает различные формы записи для различных типов объектов данных. В гл. 1 мы уже видели способ, с помощью которого можно отличить атомы от переменных: переменные начинаются с прописной буквы, тогда как атомы - со строчной. Для того, чтобы пролог-система распознала тип объекта, ей не требуется сообщать больше никакой дополнительной информации (такой, например, как объявление типа данных).

    2. 1. 1.    Атомы и числа
    В гл. 1 мы уже видели несколько простых примеров атомов и переменных. Вообще же они могут принимать более сложные формы, а именно представлять собой цепочки следующих символов:
    прописные буквы А, В, ..., Z
    строчные буквы а, b, ..., z
    цифры 0, 1, 2, ..., 9
    специальные символы, такие как

            +  -  *  /   =  :  .  &  _  ~
    Атомы можно создавать тремя способами:
    (1)    из цепочки букв, цифр и символа подчеркивания _, начиная такую цепочку со строчной буквы:
           анна

            nil

            х25

            х_25

            х_25AB

            х_

            х__у

            альфа_бета_процедура

            мисс_Джонс

            сара_джонс
    (2)    из специальных символов:
           <--->

            ======>

            ...

             .

            ...

            : : =
    Пользуясь атомами такой формы, следует соблюдать некоторую осторожность, поскольку часть цепочек специальных символов имеют в Прологе заранее определенный смысл. Примером может служить :-  .
    (3)    из цепочки символов, заключенной в одинарные кавычки. Это удобно, если мы хотим, например, иметь атом, начинающийся с прописной буквы. Заключая его в кавычки, мы делаем его отличным от переменной:
            'Том'

            ' Южная_Америка'

            'Сара Джонс'
    Числа в Прологе бывают целыми и вещественными. Синтаксис целых чисел прост, как это видно из следующих примеров: 1, 1313, 0, -97. Не все целые числа могут быть представлены в машине, поэтому диапазон целых чисел ограничен интервалом между некоторыми минимальным и максимальным числами, определяемыми конкретной реализацией Пролога. Обычно реализация допускает диапазон хотя бы от -16 383 до 16 383, а часто, и значительно более широкий.
    Синтаксис вещественных чисел зависит от реализации. Мы будем придерживаться простых правил, видных из следующих примеров: 3.14, -0.0035, 100.2. При обычном программировании на Прологе вещественные числа используются редко. Причина этого кроется в том, что Пролог - это язык, предназначенный в первую очередь для обработки символьной, а не числовой информации, в противоположность языкам типа Фортрана, ориентированным на числовую обработку. При символьной обработке часто используются целые числа, например, для подсчета количества элементов списка; нужда же в вещественных числах невелика.
    Кроме отсутствия необходимости в использовании вещественных чисел в обычных применениях Пролога, существует и другая причина избегать их. Мы всегда стремимся поддерживать наши программы в таком виде, чтобы их смысл был предельно ясен. Введение вещественных чисел в некоторой степени нарушает эту ясность из-за ошибок вычислений, связанных с округлением во время выполнения арифметических действий. Например, результатом вычисления выражения 10000 + 0.0001 - 10000 может оказаться 0 вместо правильного значения 0.0001.

    2. 1. 2.    Переменные
    Переменные - это цепочки, состоящие из букв, цифр и символов подчеркивания. Они начинаются с прописной буквы или с символа подчеркивания:
            Х

            Результат

            Объект2

            Список_участников

            СписокПокупок

            _х23

            _23
    Если переменная встречается в предложения только один раз, то нет необходимости изобретать ей имя. Можно использовать так называемую "анонимную" переменную, которая записывается в виде одного символа подчеркивания. Рассмотрим, например, следующее правило:
            имеетребенка( X) :- родитель( X, Y).
    Это правило гласит: "Для всех X,  Х имеет ребенка, если X является родителем некоторого Y". Здесь мы определяем свойство имеетребенка таким образом, что оно не зависит от имени ребенка. Следовательно, это как раз тот случай, когда уместно использовать анонимную переменную. Поэтому вышеприведенное правило можно переписать так:
            имеетребенка( X) :- родитель( X, _ ).
    Всякий раз, когда в предложения появляется одиночный символ подчеркивания, он обозначает новую анонимную переменную. Например, можно сказать, что существует некто, кто имеет ребенка, если существуют два объекта, такие, что один из них является родителем другого:
            некто_имеет_ребенка :- родитель( _, _ ).
    Это предложение эквивалентно следующему:
            некто_имеет_ребенка :- родитель( X, Y).
    Однако оно имеет совершенно другой смысл, нежели
           некто_имеет_ребенка :- родитель( X, X).
    Если анонимная переменная встречается в вопросе, то ее значение не выводится при ответе системы на этот вопрос. Если нас интересуют люди, имеющие детей, но не имена этих детей, мы можем просто спросить:
            ?-  родитель( X, _ ).
    Лексический диапазон имени - одно предложение. Это значит, что если, например, имя Х15 встречается в двух предложениях, то оно обозначает две разные переменные. Однако внутри одного предложения каждое его появлений обозначает одну и ту же переменную. Для констант ситуация другая: один и тот же атом обозначает один и тот же объект в любом предложении, иначе говоря, - во всей программе.

    2. 1. 3.    Структуры
    Структурные объекты (или просто структуры) - это объекты, которые состоят из нескольких компонент. Эти компоненты, в свою очередь, могут быть структурами. Например, дату можно рассматривать как структуру, состоящую из трех компонент: день, месяц, год. Хотя они и составлены из нескольких компонент, структуры в программе ведут себя как единые объекты. Для того, чтобы объединить компоненты в структуру, требуется выбрать функтор. Для нашего примера подойдет функтор дата. Тогда дату 1-е мая 1983 г. можно записать так:
           дата( 1, май, 1983)
    (см. рис. 2.2).
    Все компоненты в данном примере являются константами (две компоненты - целые числа и одна - атом). Компоненты могут быть также переменными или структурами. Произвольный день в мае можно представить структурой:
           дата( День, май, 1983)
    Заметим, что День является переменной и ей можно приписать произвольное значение на некотором более позднем этапе вычислений.
    Такой метод структурирования данных прост и эффективен. Это является одной из причин того, почему Пролог естественно использовать для решения задач обработки символьной информации.
    Синтаксически все объекты данных в Прологе представляют собой термы. Например,
           май
    и
           дата( 1, май, 1983)
    суть термы.
    Все структурные объекты можно изображать в виде деревьев (пример см. на рис. 2.2). Корнем дерева служит функтор, ветвями, выходящими из него, - компоненты. Если некоторая компонента тоже является структурой, тогда ей соответствует поддерево в дереве, изображающем весь структурный объект.
    Наш следующий пример показывает, как можно использовать структуры для представления геометрических объектов (см. рис. 2.3). Точка в двумерном пространстве определяется двумя координатами; отрезок определяется двумя точками, а треугольник можно задать тремя точками. Введем следующие функторы:
           точка                            для точек

           отрезок                         для отрезков и

           треугольник                для треугольников.
   
    Рис. 2. 2.  Дата - пример структурного объекта:

    (а)    его представление в виде дерева;     (б)    запись на Прологе.
    Тогда объекты, приведенные на рис. 2.3, можно представить следующими прологовскими термами:
           Р1 = точка( 1, 1)

                P2 = точка( 2, 3)
                S = отрезок( P1, P2) =

                        отрезок( точка( 1, 1), точка( 2, 3) )
                Т = треугольник( точка( 4, 2), точка( 6, 4),

                                                 точка( 7, 1) )
   
    Рис. 2. 3.  Простые геометрические объекты.
    Соответствующее представление этих объектов в виде деревьев приводится на рис. 2.4. Функтор, служащий
   
    Рис. 2. 4.  Представление объектов с рис. 2.3  в виде деревьев.
    корнем дерева, называется главным функтором терма.
    Если бы в такой же программе фигурировали точки трехмерного пространства, то можно было бы для их представления использовать другой функтор, скажем точка3:
           точка3( X, Y, Z)
    Можно, однако, воспользоваться одним и тем же именем точка одновременно и для точек двумерного и трехмерного пространств и написать, например, так:
           точка( XI, Y1)  и   точка ( X, Y, Z)
    Если одно и то же имя появляется в программе в двух различных смыслах, как в вышеупомянутом примере с точкой, то пролог-система будет различать их по числу аргументов и интерпретировать это имя как два функтора: один - двухаргументный; второй - трех. Это возможно потому, что каждый функтор определяется двумя параметрами:
    (1)    именем, синтаксис которого совпадает с синтаксисом атомов;
    (2)    арностью - т. е. числом аргументов.
    Как уже объяснялось, все структурные объекты в Прологе - это деревья, представленные в программе термами. Рассмотрим еще два примера, чтобы показать, насколько удобно сложные объекты данных представляются с помощью прологовских термов. На рис. 2.5 показана древовидная структура, соответствующая арифметическому выражению
           (а + в)*(с - 5)
    В соответствии с введенным к настоящему моменту синтаксисом, такое выражение, используя символы *,  +  и  -  в качестве функторов, можно записать следующим образом:
           *( +( а, в), -( с, 5) )
   
    Рис. 2. 5.  Древовидная структура, соответствующая арифметическому

    выражению (а + w)*(s - 5).
    Это, конечно, совершенно правильный прологовский терм, однако это не та форма, которую нам хотелось бы иметь, при записи арифметических выражений. Хотелось бы применять обычную инфиксную запись, принятую в математике. На самом деле Пролог допускает использование инфиксной нотации, при которой символы *,  +   и  -  записываются как инфиксные операторы. Детали того, как программист может определять свои собственные операторы, мы приведем в гл. 3.
    В качестве последнего примера рассмотрим некоторые простые электрические цепи, изображенные на рис. 2.6. В правой части рисунка помещены древовидные представления этих цепей. Атомы r1, r2, r3 и r4 - имена резисторов. Функторы пар и посл обозначают соответственно параллельное и последовательное соединение резисторов. Вот соответствующие прологовские термы:
           посл( r1, r2)

            пар( r1, r2)

            паp( rl, пap( r2, r3) )

            пар( r1, посл( пар( r2, r3), r4) )
     
   
    Рис. 2. 6.  Некоторые простые электрические цепи и их представление: (а) последовательное соединение резисторов rl и r2; (b) параллельное соединение двух резисторов; (с) параллельное соединение трех резисторов; (d) параллельное соединение r1 и еще одной цепи.
    Упражнения
    2. 1.    Какие из следующих выражений представляют собой правильные объекты в смысле Пролога? Что это за объекты (атомы, числа, переменные, структуры)?
        (а)        Диана

        (b)        диана

        (с)        'Диана'

        (d)        _диана

        (e)        'Диана едет на юг'

        (f)        едет( диана, юг)

        (g)        45

        (h)        5( X, Y)

        (i)        +( север, запад)

        (j)        три( Черные( Кошки) )
    Посмотреть ответ
    2. 2.    Предложите представление для прямоугольников, квадратов и окружностей в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 2.4. Например, прямоугольник можно представить четырьмя точками (а может быть, только тремя точками). Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    2. 2.    Сопоставление
    В предыдущем разделе мы видели, как используются термы для представления сложных объектов данных. Наиболее важной операцией над термами является сопоставление. Сопоставление само по себе может производить содержательные вычисления.
    Пусть даны два терма. Будем говорить, что они сопоставимы, если:
    (1)    они идентичны или
    (2)    переменным в обоих термах можно приписать в качестве значений объекты (т.е. конкретизировать их) таким образом, чтобы после подстановки этих объектов в термы вместо переменных, последние стали идентичными.
    Например, термы дата( Д, М, 1983) и дата( Д1, май, Y1) сопоставимы. Одной из конкретизации, которая делает эти термы идентичными, является следующая:
    Д   заменяется на   Д1
    М   заменяется на   май
    Y1   заменяется на   1983
    Более компактно такая подстановка записывается в привычной форме, т. е. в той, в которой пролог-система выводит результаты:
           Д  =  Д1

           М  =  май

           Y1  =  1983
    С другой стороны, дата( Д, М, 1983) и дата( Д1, Ml, 1944) не сопоставимы, как и термы дата( X, Y, Z) и точка( X, Y, Z).
    Сопоставление - это процесс, на вход которого подаются два терма, а он проверяет, соответствуют ли эти термы друг другу. Если термы не сопоставимы, будем говорить, что этот процесс терпит неуспех. Если же они сопоставимы, тогда процесс находит конкретизацию переменных, делающую эти термы тождественными, и завершается успешно.
    Рассмотрим еще раз сопоставление двух дат. Запрос на проведение такой операции можно передать системе, использовав оператор '=':
           ?-  дата( Д, М, 1983)  =   дата( Д1, май, Y1).
    Мы уже упоминали конкретизацию Д = Д1, М = май, Y1 = 1983, на которой достигается сопоставление. Существуют, однако, и другие конкретизации, делающие оба терма идентичными. Вот две из них:
           Д  =  1

           Д1  =  1

           М  =  май

           Y1  =  1983
           Д  =  третий

           Д1  =  третий

           М  =  май

           Y1  =  1983
    Говорят, что эти конкретизации являются менее общими по сравнению с первой, поскольку они ограничивают значения переменных Д и Д1 в большей степени, чем это необходимо. Для того, чтобы сделать оба терма нашего примера идентичными, важно лишь, чтобы Д и Д1 имели одно и то же значение, однако
    само это значение может быть произвольным.
    Сопоставление в Прологе всегда дает
    наиболее общую конкретизацию
    . Таковой является конкретизация, которая ограничивает переменные в наименьшей степени, оставляя им, тем самым, наибольшую свободу для дальнейших конкретизаций, если потребуются новые сопоставления. В качестве примера рассмотрим следующий вопрос:
           ?-  дата( Д, М, 1983)  =   дата( Д1, май, Y1),

                 дата( Д, М, 1983)  =  дата( 15, М, Y).
    Для достижения первой цели система припишет переменным такие значения:
            Д  = Д1

            М  =  май

            Y1  =  1983
    После достижения второй цели, значения переменных станут более конкретными, а именно:
            Д  =  15

            Д1  =  15

            М  =  май

            Y1  =  1983

            Y  =  1983
    Этот пример иллюстрирует также и тот факт, что переменным по мере вычисления последовательности целей приписываются обычно все более и более конкретные значения.
    Общие правила выяснения, сопоставимы ли два терма S и Т, таковы:
    (1)    Если S и Т - константы, то S и Т сопоставимы, только если они являются одним и тем же объектом.
    (2)    Если S - переменная, а Т - произвольный объект, то они сопоставимы, и S приписывается значение Т. Наоборот, если Т -переменная, а S -произвольный объект, то Т приписывается значение S.
    (3)    Если S и Т - структуры, то они сопоставимы, только если
    (а)    S и Т имеют одинаковый главный функтор

            и

    (б)    все их соответствующие компоненты сопоставимы.
            Результирующая конкретизация определяется сопоставлением компонент.
    Последнее из этих правил можно наглядно представить себе, рассмотрев древовидное изображение термов, такое, например, как на рис. 2.7. Процесс сопоставления начинается от корня (главных функторов). Поскольку оба функтора сопоставимы, процесс продолжается и сопоставляет соответствующие пары аргументов. Таким образом, можно представить себе, что весь процесс сопоставления состоит из следующей последовательности (более простых) операций сопоставления:
            треугольник  =   треугольник,

            точка( 1, 1)  =  X,

            А  =  точка( 4, Y),

            точка( 2, 3)  =  точка( 2, Z).
    Весь процесс сопоставления успешен, поскольку все сопоставления в этой последовательности успешны. Результирующая конкретизация такова:
            Х  =  точка( 1, 1)

            А  =  точка( 4, Y)

            Z  =  3
    В приведенном ниже примере показано, как сопоставление само по себе можно использовать для содержательных вычислений. Давайте вернемся к простым геометрическим объектам с рис. 2.4 и напишем фрагмент программы для распознавания горизонтальных и вертикальных отрезков. "Вертикальность" - это свойство отрезка, поэтому его можно формализовать в Прологе в виде унарного отношения. Рис. 2.8 помогает сформулировать это отношение. Отрезок
   
    Рис.  2. 7.    Сопоставление треугольник(( точка( 1, 1), А, точка( 2, 3)) = треугольник( Х, точка( 4, Y),

    точка( 2, Z))
    является вертикальным, если x-координаты его точек-концов совпадают; никаких других ограничений на отрезок не накладывается. Свойство "горизонтальности" формулируется аналогично, нужно только в этой формулировке х и y поменять местами. Следующая программа, содержащая два факта, реализует эти формулировки:
            верт( отр( точка( Х, Y), точка( Х, Y1) ) ).

            гор( отр( точка( Х, Y), точка( Х1, Y) ) ).
    С этой программой возможен такой диалог:
            ?-  верт( отр( точка( 1, 1), точка( 1, 2) ) ).

            да
            ?-  верт( отр( точка( 1, 1), точка( 2, Y) ) ).

            нет
            ?-  гор( отр( точка( 1, 1), точка( 2, Y) ) ).

            Y  =  1
    На первый вопрос система ответила "да", потому. что цель, поставленная в вопросе, сопоставима с одним из фактов программы. Для второго вопроса сопоставимых фактов не нашлось. Во время ответа на третий вопрос при сопоставлении с фактом о горизонтальных отрезках Y получил значение 1.
   
    Рис. 2. 8.  Пример вертикальных и горизонтальных отрезков прямых.
    Сформулируем более общий вопрос к программе: "Существуют ли какие-либо вертикальные отрезки, начало которых лежит в точке (2,3)?"
            ?-  верт( отр( точка( 2, 3), Р) ).

            Р  =  точка( 2, Y)
    Такой ответ означает: "Да, это любой отрезок, с концом в точке (2,Y), т. е. в произвольной точке вертикальной прямой х = 2". Следует заметить, что ответ пролог-системы возможно будет выглядеть не так красиво, как только что описано, а (в зависимости от реализации) приблизительно следующим образом:
            Р  =  точка( 2, _136)
    Впрочем, разница здесь чисто внешняя. В данном случае _136 - это неинициализированная переменная. Имя _136 - законное имя прологовской переменной, которое система построила сама во время вычислений. Ей приходится генерировать новые имена, для того чтобы переименовывать введенные пользователем переменные в программе. Это необходимо по двум причинам: первая - одинаковые имена обозначают в разных предложениях разные переменные; и вторая - при последовательном применении одного и того же предложения используется каждый раз его "копия" с новым набором переменных.
    Другим содержательным вопросом к нашей программe является следующий: "Существует ли отрезок, который одновременно и горизонтален в вертикален?"
            ?-  верт( S), гор( S).

            S  =  отр( точка( Х, Y), точка( Х, Y) )
    Такой ответ пролог-системы следует, понимать так: "да, любой отрезок, выродившийся в точку, обладает как свойством вертикальности, так и свойством горизонтальности одновременно". Этот ответ снова получен лишь из сопоставления. Как и раньше, в ответе вместо Х и Y могут появиться некоторые имена, сгенерированные системой.
    Упражнения
    2. 3.    Будут ли следующие операции сопоставления успешными или неуспешными? Если они будут успешными, то какова будет результирующая конкретизация переменных?
        (а)        точка( А, В) = точка( 1, 2)

        (b)        точка( А, В) = точка( X, Y, Z)

        (c)        плюс( 2, 2) = 4

        (d)        +( 2, D)= +( Е, 2)

        (е)        треугольник( точка( -1, 0), Р2, Р3) =

                     треугольник( Р1, точка( 1, 0), точка( 0, Y)
    Результирующая конкретизация определяет семейство треугольников. Как бы Вы описали это семейство?
    Посмотреть ответ
    2. 4    Используя представление отрезков, применявшееся в данной разделе, напишите терм, соответствующий любому отрезку на вертикальной прямой x = 5.
    Посмотреть ответ
    2. 5.    Предположим, что прямоугольник представлен термом прямоугольник( P1, P2, P3, Р4), где Р - вершины прямоугольника, положительно упорядоченные. Определите отношение
            регулярный( R)
    которое имеет место, если R - прямоугольник с вертикальными и горизонтальными сторонами.
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    2. 3.    Декларативный смысл пролог-программ
    В главе 1 мы уже видели, что пролог-программу можно понимать по-разному: с декларативной и процедурной точек зрения. В этом и следующем разделах мы рассмотрим более формальное определение декларативного и процедурного смыслов программ базисного Пролога. Но сначала давайте еще раз взглянем на различия между этими двумя семантиками.
    Рассмотрим предложение
            Р :- Q,  R.
    где Р, Q и R имеют синтаксис термов. Приведем некоторые способы декларативной интерпретации этого предложения:
            Р  -  истинно, если  Q  и  R   истинны.

            Из  Q  и  R  следует  Р.
    А вот два варианта его "процедурного" прочтения:
            Чтобы решить задачу  Р,  сначала реши подзадачу

            Q,  а затем - подзадачу  R.

            Чтобы достичь  Р,  сначала достигни  Q,  а затем  R.
    Таким образом, различие между "декларативным" и "процедурным" прочтениями заключается в том, что последнее определяет не только логические связи между головой предложения и целями в его теле, но еще и порядок, в котором эти цели обрабатываются.
    Формализуем теперь декларативный смысл.
    Декларативный смысл программы определяет, является ли данная цель истинной (достижимой) и, если да, при каких значениях переменных она достигается. Для точного определения декларативного смысла нам потребуется понятие конкретизации предложения. Конкретизацией предложения С называется результат подстановки в него на место каждой переменной некоторого терма. Вариантом предложения С называется такая конкретизация С, при которой каждая переменная заменена на другую переменную. Например, рассмотрим предложение:
           имеетребенка( X) :- родитель( X, Y).
    Приведем два варианта этого предложения:
            имеетребенка( А) :- родитель( А, В).

            имеетребенка( X1) :- родитель( X1, Х2).
    Примеры конкретизаций этого же предложения:
            имеетребенка( питер) :- родитель( питер, Z).

            имеетребенка( барри) :- родитель( барри,

                                                          маленькая( каролина) ).
    Пусть дана некоторая программа и цель G, тогда, в соответствии с декларативной семантикой, можно утверждать, что
    Цель  G  истинна (т.е. достижима или логически следует из программы) тогда и только тогда, когда
    (1)    в программе существует предложение  С, такое, что
    (2)    существует такая его  (С)   конкретизация  I,  что
            (a)    голова   I  совпадает с  G  и

            (б)    все цели в теле  I  истинны.
    Это определение можно распространить на вопросы следующим образом. В общем случае вопрос к пролог-системе представляет собой список целей, разделенных запятыми. Список целей называется истинным (достижимым), если все цели в этом списке истинны (достижимы) при одинаковых конкретизациях переменных. Значения переменных получаются из наиболее общей конкретизации.
    Таким образом, запятая между целями обозначает конъюнкцию целей: они все должны быть истинными. Однако в Прологе возможна и дизъюнкция целей: должна быть истинной, по крайней мере одна из целей. Дизъюнкция обозначается точкой с запятой. Например:
            Р   :-   Q;  R.
    читается так:  Р  -  истинно, если истинно   Q   или истинно  R.  То есть смысл такого предложения тот же, что и смысл следующей пары предложений:
            Р   :-   Q.

            Р   :-   R.
    Запятая связывает (цели) сильнее, чем точка с запятой. Таким образом, предложение
            Р   :-   Q,  R;  S,  Т,   U.
    понимается как:
            Р   :-   ( Q,  R);  (S,   Т,  U).
    и имеет тот же смысл, что и два предложения
            Р   :-   Q,  R.

            Р   :-   S,  T,  U.
    Упражнения
    2. 6.    Рассмотрим следующую программу:
        f( 1, один).

        f( s(1), два).

        f(    s(s(1)),    три).

        f( s(s(s(X))),  N) :-

                   f(X,   N).
    Как пролог-система ответит на следующие вопросы? Там, где возможны несколько ответов, приведите по крайней мере два.
        (a)        ?- f( s( 1), A).

        (b)        ?- f( s(s(1)), два).

        (c)        ?- f(   s(s(s(s(s(s(1)))))), С).

        (d)        ?- f( D, три).
    Посмотреть ответ
    2. 7.    В следующей программе говорится, что два человека являются родственниками, если
        (a)        один является предком другого, или

        (b)        у них есть общий предок, или

        (c)        у них есть общий потомок.
        родственники( X, Y) :-

              предок( X, Y).
        родственники( X, Y) :-

              предок( Y, X).
        родственники( X, Y) :-

                          % X и Y имеют общего предка

              предок( Z, X),

              предок( Z, Y).
        родственники( X, Y) :-

                          % X и Y имеют общего потомка

              предок( X, Z),

              предок( Y, Z).
    Сможете ли вы сократить эту программу, используя запись с точками с запятой?
    Посмотреть ответ
    2. 8.    Перепишите следующую программу, не пользуясь точками с запятой.
        преобразовать( Число, Слово) :-

              Число = 1,  Слово = один;

              Число = 2,  Слово = два;

              Число = 3,  Слово = три.
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    2. 4.    Процедурная семантика
    Процедурная семантика определяет, как пролог-система отвечает на вопросы. Ответить на вопрос - это значит удовлетворить список целей. Этого можно добиться, приписав встречающимся переменным значения таким образом, чтобы
    цели логически следовали из программы. Можно
    сказать, что процедурная семантика Пролога - это
    процедура вычисления списка целей
    с учетом заданной программы. "Вычислить цели" это значит попытаться достичь их.
    Назовем эту процедуру вычислить. Как показано на рис. 2.9, входом и выходом этой процедуры являются:
        входом - программа и список целей,

        выходом - признак успех/неуспех и подстановка переменных.
   
    Рис. 2. 9.  Входы и выходы процедуры вычисления списка целей.
    Смысл двух составляющих выхода такой:
    (1)    Признак успех/неуспех принимает значение "да", если цели достижимы, и "нет" - в противном случае. Будем говорить, что "да" сигнализирует об успешном завершении и "нет" - о неуспехе.
    (2)    Подстановка переменных порождается только в случае успешного завершения; в случае неуспеха подстановка отсутствует.
    ПРОГРАММА
    большой( медведь).                % Предложение 1

    большой( слон).                       % Предложение 2

    маленький( кот).                    % Предложение 3

    коричневый ( медведь).        % Предложение 4

    черный ( кот).                         % Предложение 5

    серый( слон).                           % Предложение 6
    темный( Z) :-                           % Предложение 7:

               черный( Z).                   % любой черный

                                                       % объект является темным

    темный( Z) :-                           % Предложение 8:

               коричневый( Z).           % Любой коричневый

                                                        % объект является темным
    ВОПРОС
    ?-  темный( X), большой( X)    % Кто одновременно темный

                                                         % и большой?
    ШАГИ  ВЫЧИСЛЕНИЯ
    (1)    Исходный список целевых утверждений:
                темный( X),  большой( X).
    (2)    Просмотр всей программы от начала к концу и поиск предложения, у которого голова сопоставима с первым целевым утверждением
                темный( X).
            Найдена формула 7:
                темный( Z) :- черный( Z).
    Замена первого целевого утверждения конкретизированным телом предложения 7 - порождение нового списка целевых утверждений.
                черный( X),  большой( X)
    (3)    Просмотр программы для нахождения предложения, сопоставимого с черный( X). Найдено предложение 5: черный ( кот). У этого предложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до
                большой( кот)
    (4)    Просмотр программы в поисках цели большой( кот). Ни одно предложение не найдено. Поэтому происходит возврат к шагу (3) и отмена конкретизации Х = кот. Список целей теперь снова
                черный( X),  большой( X)
    Продолжение просмотра программы ниже предложения 5. Ни одно предложение не найдено. Поэтому возврат к шагу (2) и продолжение просмотра ниже предложения 7. Найдено предложение (8):
               темный( Z) :- коричневый( Z).
    Замена первой цели в списке на коричневый( Х), что дает
               коричневый( X), большой( X)
    (5)    Просмотр программы для обнаружения предложения, сопоставимого коричневый( X). Найдено предложение коричневый( медведь). У этого предложения нет тела, поэтому список целей уменьшается до
                большой( медведь)
    (6)    Просмотр программы и обнаружение предложения большой( медведь). У него нет тела, поэтому список целей становится пустым. Это указывает на успешное завершение, а соответствующая конкретизация переменных такова:
    Рис. 2. 10.  Пример, иллюстрирующий процедурную семантику

          Пролога: шаги вычислений, выполняемых процедурой вычислить.
    В главе 1 в разд. "Как пролог-система отвечает на вопросы" мы уже фактически рассмотрели, что делает процедура вычислить. В оставшейся части данного раздела приводится несколько более формальное и систематическое описание этого процесса, которое можно пропустить без серьезного ущерба для понимания остального материала книги.
    Конкретные операции, выполняемые в процессе вычисления целевых утверждений, показаны на рис. 2.10. Возможно, следует изучить этот рисунок прежде, чем знакомиться с последующим общим описанием.
    Чтобы вычислить список целевых утверждений
            G1, G2, ..., Gm
    процедура вычислить делает следующее:
    Если список целей пуст - завершает работу успешно.
    Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'.
    ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.

   

    Если С найдено и имеет вид

   

            Н   :-   B1,  ...,   Вn.

   

    то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком  G1,   ...,  Gm. Пусть С' - это

   

            Н'   :-   B1',  ...,   Вn'.

   

    Сопоставляется  G1  с  H';  пусть  S  - результирующая конкретизация переменных.  В списке целей  G1,  G2,  ....  Gm, цель  G1   заменяется на список  В1',  ..,  Вn',   что порождает новый список целей:

   

            В1',  ...,  Вn', G2,  ...,   Gm

   

    (Заметим, что, если  С  - факт, тогда  n=0,   и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а следовательно, - привести к успешному завершению.)

   

    Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация  S,  что порождает еще один список целей

   

            В1'',  ....  Вn", G2',   ...,  Gm'

   
    Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением  С   (С  -  предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.
    Более компактная запись этой процедуры в обозначениях, близких к Паскалю, приведена на рис. 2.11.
    Здесь следует сделать несколько дополнительных замечаний, касающихся процедуры вычислить в том виде, в котором она приводится. Во-первых, в ней явно не указано, как порождается окончательная результирующая конкретизация переменных. Речь идет о конкретизации S, которая приводит к успешному завершению и которая, возможно, уточнялась последующими конкретизациями во время вложенных рекурсивных вызовов вычислить.
    procedure вычислить (Прогр, СписокЦелей, Успех)
    Входные параметры:
            Прогр:   список предложений

            СписокЦелей:   список целей
    Выходной параметр:
            Успех:          истинностное значение; Успех принимает значение

                                   истина, если список целевых утверждений

                                   (их конъюнкция) истиннен с точки зрения Прогр
    Локальные переменные:
            Цель:  цель

            ДругиеЦели:  список целей

            Достигнуты:   истинностное значение

            Сопоставились:   истинностное значение

            Конкрет:   конкретизация переменных

                    Н,   Н',  B1,  B1',  ...,  Вn ,  Вn':   цели
    Вспомогательные функции:
            пycтой( L):   возвращает истину, если L - пустой список
            голoвa( L):   возвращает первый элемент списка L
            хвост( L):   возвращает остальную часть списка L
            конкат( L1, L2):   создает конкатенацию списков - присоединяет

                    список L2 к концу списка L1
            сопоставление( T1, T2, Сопоставились, Конкрет): пытается

                    сопоставить термы Т1 и T2; если они сопоставимы, то

                    Сопоставились - истина, а Конкрет представляет

                    собой конкретизацию переменных
            подставить( Конкрет, Цели): производит подстановку переменных

                    в Цели согласно Конкрет
    begin

        if пустой( СписокЦелей) then Успех : = истина

        else

            begin

                Цель : = голова( СписокЦелей);

                ДругиеЦели : = хвост( СписокЦелей);

                Достигнута : = ложь;

                while not Достигнута and

                    "в программе есть еще предложения" do

                    begin

                        Пусть следующее предложение в Прогр есть

                                Н    :-   B1,  ....  Вn.

                        Создать вариант этого предложения

                                Н'    :-   В1',  ....  Вn'.

                        сопоставление( Цель, Н',

                                                        Сопоставились, Конкрет)

                        if Сопоставились then

                            begin

                                НовыеЦели : =

                                    конкат( [В1', ..., Вn' ], Другие Цели);

                                НовыеЦели : =

                                    подставить( Конкрет, НовыеЦели);

                                вычислить( Прогр, НовыеЦели, Достигнуты)

                            end

                        end;

                Успех : = Достигнуты

            end

    end;
    Рис. 2. 11.  Вычисление целевых утверждений Пролога.
    Всякий раз, как рекурсивный вызов процедуры вычислить приводят к неуспеху, процесс вычислений возвращается к ПРОСМОТРУ и продолжается с того предложения  С,  которое использовалось последним. Поскольку применение предложения  С  не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности
    система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет
    возврат
    в ту точку (предложение  С),  в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки, аннулируются. Такой порядок обеспечивает систематическую проверку пролог-системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.
    Мы уже знаем, что даже после успешного завершения пользователь может заставить систему совершить возврат для поиска новых решений. В нашем описании процедуры вычислить эта деталь была опущена.
    Конечно, в настоящих реализациях Пролога в процедуру вычислить добавлены и еще некоторые усовершенствования. Одно из них - сокращение работы по просмотрам программы с целью повышения эффективности. Поэтому на практике пролог-система не просматривает все предложения программы, а вместо этого рассматривает только те из них, которые касаются текущего целевого утверждения.
    Упражнение
    2. 9.    Рассмотрите программу на рис. 2.10 и по типу того, как это сделано на рис. 2.10, проследите процесс вычисления пролог-системой вопроса
            ?-  большой( X),   темный( X).
    Сравните свое описание шагов вычисления с описанием на рис. 2.10, где вычислялся, по существу, тот же вопрос, но с другой последовательностью целей:
            ?-  темный( X),   большой( X).
    В каком из этих двух случаев системе приходится производить большую работу для нахождения ответа?
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    2. 5.    Пример: обезьяна и банан
    Задача об обезьяне и банане часто используется в качестве простого примера задачи из области искуственного интеллекта. Наша пролог-программа, способная ее решить, показывает, как механизмы сопоставления и автоматических возвратов могут применяться для подобных целей. Мы сначала составим программу, не принимая во внимание процедурную семантику, а затем детально изучим ее процедурное поведение. Программа будет компактной и наглядной.
    Рассмотрим следующий вариант данной задачи. Возле двери комнаты стоит обезьяна. В середине этой комнаты к потолку подвешен банан. Обезьяна голодна и хочет съесть банан, однако она не может дотянуться до него, находясь на полу. Около окна этой же комнаты на полу лежит ящик, которым обезьяна может воспользоваться. Обезьяна может предпринимать следующие действия: ходить по полу, залезать на ящик, двигать ящик (если она уже находится около него) и схватить банан, если она стоит на ящике прямо под бананом. Может ли обезьяна добраться до банана?
    Одна из важных проблем при программировании состоит в выборе (адекватного) представления решаемой задачи в терминах понятий используемого языка программирования. В нашем случае мы можем считать, что "обезьяний мир" всегда находится в некотором состоянии, и оно может изменяться со временем. Текущее состояние определяется взаиморасположением объектов. Например, исходное состояние мира определяется так:
    (1)        Обезьяна у двери.

    (2)        Обезьяна на полу.

    (3)        Ящик у окна.

    (4)        Обезьяна не имеет банана.
    Удобно объединить все эти четыре информационных фрагмента в один структурный объект. Давайте в качестве такого объединяющего функтора выберем слово "состояние". На рис. 2.12 в виде структурного объекта изображено исходное состояние.
    Нашу задачу можно рассматривать как игру для одного игрока. Давайте, формализуем правила этой игры. Первое, целью игры является ситуация, в которой обезьяна имеет банан, т. е. любое состояние, у которого в качестве четвертой компоненты стоит "имеет":
            состояние( -, -, -, имеет)
    Второе, каковы разрешенные ходы, переводящие мир из одного состояния в другое? Существуют четыре типа ходов:
    (1)        схватить банан,

    (2)        залезть на ящик,

    (3)        подвинуть ящик,

    (4)        перейти в другое место.
   
    Рис. 2. 12.  Исходное состояние обезьяньего мира, представленное в виде структурного объекта. Его четыре компоненты суть горизонтальная позиция обезьяны, вертикальная позиция обезьяны, позиция ящика, наличие или отсутствие у обезьяны банана.
    Не всякий ход допустим при всех возможных состояниях мира. Например, ход "схватить" допустим, только если обезьяна стоит на ящике прямо под бананом (т.е. в середине комнаты) и еще не имеет банана. Эти правила можно формализовать в Прологе в виде трехместного отношения ход:
            ход( Состояние1, М, Состояние2)
    Три аргумента этого отношения определяют ход, следующим образом:
            Состояние1 --------> Состояние2

                                        М
    Состояние1 это состояние до хода, М - выполняемый ход, и Состояние2 - состояние после хода.
    Ход "схватить", вместе с необходимыми ограничениями на состояние перед этим ходом, можно выразить такой формулой:
    ход( состояние( середина, наящике, середина, неимеет),

                                                               % Перед ходом

            схватить,                                 % Ход

            состояние( середина, наящике, середина, имеет) ).

                                                             % После хода
    В этом факте говорится о том, что после хода у обезьяны уже есть банан и что она осталась на ящике в середине комнаты.
    Таким же способом можно выразить и тот факт, что обезьяна, находясь на полу, может перейти из любой горизонтальной позиции Р1 в любую позицию Р2. Обезьяна может это сделать независимо от позиции ящика, а также независимо от того, есть у нее банан или нет. Все это можно записать в виде следующего прологовского факта:
            ход( состояние( Р1, наполу, В, Н),

                    перейти( Р1, Р2),             % Перейти из Р1 в Р2

                    состояние( Р2, наполу, В, Н) ).
    Заметим, что в этом предложении делается много утверждений и, в частности:
    выполненный ход состоял в том, чтобы "перейти из некоторой позиции Р1 в некоторую позицию Р2";
    обезьяна находится на полу, как до, так и после хода;
    ящик находится в некоторой точке В, которая осталась неизменной после хода;
    состояние "имеет банан" остается неизменным после хода.
   
    Рис. 2. 13.  Рекурсивная формулировка отношения можетзавладетъ.
    Данное предложение на самом деле определяет все множество возможных ходов указанного типа, так как оно применимо к любой ситуации, сопоставимой с состоянием, имеющим место перед входом. Поэтому такое предложение иногда называют схемой хода. Благодаря понятию переменной, имеющемуся в Прологе, такие схемы легко на нем запрограммировать.
    Два других типа ходов: "подвинуть" и "залезть" - легко определить аналогичным способом.
    Главный вопрос, на который должна ответить наша программа, это вопрос: "Может ли обезьяна, находясь в некотором начальном состоянии  S,   завладеть бананом?" Его можно сформулировать в виде предиката
            можетзавладеть( S)
    где аргумент  S  -  состояние обезьяньего мира. Программа для можетзавладеть может основываться на двух наблюдениях:
    (1)    Для любого состояния  S,  в которой обезьяна уже имеет банан, предикат можетзавладеть должен, конечно, быть истинным; в этом случае никаких ходов не требуется. Вот соответствующий прологовский факт:
            можетзавладеть( состояние( -, -, -, имеет) ).
    (2)    В остальных случаях требуется один или более ходов. Обезьяна может завладеть бананом в любом состоянии S1, если для него существует ход из состояния Р1 в некоторое состояние S2, такое, что, попав в него, обезьяна уже сможет завладеть бананом (за нуль или более ходов). Этот принцип показан на рис. 2.13. Прологовская формула, соответствующая этому правилу, такова:
            можетзавладеть( S1) :-

                    ход( S1, М, S2),

                    можетзавладеть( S2).
    Теперь мы полностью завершили нашу программу, показанную на рис. 2.14.
    Формулировка можетзавладеть рекурсивна и совершенно аналогична формулировке отношения предок из гл. 1 (ср. рис. 2.13 и 1.7). Этот принцип используется в Прологе повсеместно.
    Мы создали нашу программу "непроцедурным" способом. Давайте теперь изучим ее процедурное поведение, рассмотрев следующий вопрос к программе:
            ?-   можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).
    Ответом пролог-системы будет "да". Процесс, выполняемый ею при этом, обрабатывает, в соответствии с процедурной семантикой Пролога, последовательность списков целей. Для этого требуется некоторый перебор ходов, для отыскания верного из нескольких альтернативных. В некоторых точках при таком переборе будет сделан неверный ход, ведущий в тупиковую ветвь процесса вычислений. На этом этапе автоматический возврат позволит исправить положение. На рис. 2.15 изображен процесс перебора.
    % Разрешенные ходы
    ход( состояние( середина, на ящике, середина, неимеет),

            схватить,                                 % Схватить банан

            состояние( середина, наящике, середина, имеет)).
    ход( состояние( Р, наполу, Р, Н),

            залезть,                                     % Залезть на ящик

            состояние( Р, наящике, Р, Н) ).
    ход( состояние( Р1, наполу, Р1, Н),

            подвинуть( Р1, Р2),             % Подвинуть ящик с Р1 на Р2

            состояние( Р2, наполу, Р2, Н) ).
    ход( состояние( Р1, наполу, В, Н),

            перейти( Р1, Р2),                     % Перейти с Р1 на Р2

            состояние( Р2, наполу, В, Н) ).
        % можетзавладеть(Состояние): обезьяна может завладеть

        % бананом, находясь в состоянии Состояние
    можетзавладеть( состояние( -, -, -, имеет) ).
        % может 1:  обезьяна уже его имеет
    можетзавладеть( Состояние1) :-
        % может 2:  Сделать что-нибудь, чтобы завладеть им
            ход( Состояние1, Ход, Состояние2),
        % сделать что-нибудь
            можетзавладеть( Состояние2).
        % теперь может завладеть
    Рис. 2. 14.  Программа для задачи об обезьяне и банане.
    Для ответа на наш вопрос системе пришлось сделать лишь один возврат. Верная последовательность ходов была найдена почти сразу. Причина такой эффективности программы кроется в том порядке, в
   
    Рис. 2. 15.  Поиск банана обезьяной. Перебор начинается в верхнем узле и распространяется вниз, как показано. Альтернативные ходы перебираются слева направо. Возврат произошел только один раз.
    котором в ней расположены предложения, касающиеся отношения ход. В нашем случае этот порядок (к счастью) оказался весьма подходящим. Однако возможен и менее удачный порядок. По правилам игры обезьяна могла бы с легкостью ходить туда-сюда, даже не касаясь ящика, или бесцельно двигать ящик в разные стороны. Как будет видно из следующего раздела, более тщательное исследование обнаруживает, что порядок предложений в нашей программе является, на самом деле, критическим моментом для успешного решения задачи.

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    2. 6.    Порядок предложений и целей

    2. 6. 1.    Опасность бесконечного цикла
    Рассмотрим следующее предложение:
            р   :-   р.
    В нем говорится: "р истинно, если р истинно". С точки зрения декларативного смысла это совершенно корректно, однако в процедурном смысле оно бесполезно. Более того, для пролог-системы такое предложение может породить серьезную проблему. Рассмотрим вопрос:
            ?-  р.
    При использовании вышеприведенного предложения цель р будет заменена на ту же самую цель р; она в свою очередь будет заменена снова на р и т.д. В этом случае система войдет в бесконечный цикл, не замечая, что никакого продвижения в вычислениях не происходит.
    Данный пример демонстрирует простой способ ввести пролог-систему в бесконечный цикл. Однако подобное зацикливание могло встретиться и в некоторых наших предыдущих программах, если бы мы изменили порядок предложений, или же порядок целей в них. Будет полезно рассмотреть несколько примеров.
    В программе об обезьяне и банане предложения, касающиеся отношения ход, были упорядочены следующим образом: схватить, залезть, подвинуть, перейти (возможно, для полноты следует добавить еще "слезть"). В этих предложениях говорится, что можно схватить, можно залезть и т.д. В соответствии с процедурной семантикой Пролога порядок предложений указывает на то, что обезьяна предпочитает схватывание залезанию, залезание - передвиганию и т.д. Такой порядок предпочтений на самом деле помогает обезьяне решить задачу. Но что могло случиться. если бы этот порядок был другим? Предположим, что предложение с "перейти" оказалось бы первым. Процесс вычисления нашей исходной цели из предыдущего раздела
            ?- можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).
    протекал бы на этот раз так. Первые четыре списка целей (с соответствующим образом переименованными переменными) остались бы такими же, как и раньше:
    (1)    можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).
    Применение второго предложения из можетзавладеть ("может2") породило бы
    (2)    ход( состояние( удвери, наполу, уокна, неимеет), М', S2'),

                    можетзавладеть( S2')
    С помощью хода перейти( уокна, Р2') получилось бы
    (3)    можетзавладеть( состояние( Р2', наполу, уокна, неимеет) )
    Повторное использование предложения "может2" превратило бы список целей в
    (4)    ход( состояние(Р2', наполу, уокна, неимеет), М'', S2''),

                    можетзавладеть( S2")
    С этого момента начались бы отличия. Первым предложением, голова которого сопоставима с первой целью из этого списка, было бы теперь "перейти" (а не "залезть", как раньше). Конкретизация стала бы следующей:
            S2" = состояние( Р2", наполу, уокна, неимеет).
    Поэтому список целей стал бы таким:
    (5)    можетзавладеть( состояние( Р2'', наполу, уокна, неимеет) )
    Применение предложения "может2" дало бы
    (6)    ход( cocтояниe( P2", наполу, yoкнa, неимeeт), M" ', S2'' '),

                    можетзавладеть( S2" ')
    Снова первый было бы попробовано "перейти" и получилось бы
    (7)    можетзавладеть( состояние( Р2" ', наполу, уокна, неимеет) )
    Сравним теперь цели  (3),  (5)  и  (7).   Они похожи и отличаются лишь одной переменной, которая по очереди имела имена  Р',   Р''  и  P" '.  Как мы знаем, успешность цели не зависит от конкретных имен переменных в ней. Это означает, что, начиная со списка целей (3), процесс вычислений никуда не продвинулся. Фактически мы замечаем, что по очереди многократно используются одни и те же два предложения: "может2" и "перейти". Обезьяна перемещается, даже не пытаясь воспользоваться ящиком. Поскольку продвижения нет, такая ситуация продолжалась бы (теоретически) бесконечно: пролог-система не сумела бы осознать, что работать в этой направлении нет смысла.
    Данный пример показывает, как пролог-система может пытаться решить задачу таким способом, при котором решение никогда не будет достигнуто, хотя оно существует. Такая ситуация не является редкостью при программировании на Прологе. Да и при программировании на других языках бесконечные циклы не такая уж редкость. Что действительно необычно при сравнении Пролога с другими языками, так это то, что декларативная семантика пролог-программы может быть правильной, но в то же самое время ее процедурная семантика может быть ошибочной в том смысле, что с помощью такой программы нельзя получить правильный ответ на вопрос. В таких случаях система не способна достичь цели потому, что она пытается добраться до ответа, но выбирает при этом неверный путь.
    Теперь уместно спросить: "Не можем ли мы внести какое-либо более существенное изменение в нашу программу, так чтобы полностью исключить опасность зацикливания? Или же нам всегда придется рассчитывать на удачный порядок предложений и целей?" Как оказывается, программы, в особенности большие, были бы чересчур ненадежными, если бы можно было рассчитывать лишь на некоторый удачный порядок. Существует несколько других методов, позволяющих избежать зацикливания и являющихся более общими и надежными, чем сам по себе метод упорядочивания. Такие методы будут систематически использоваться дальше в книге, в особенности в тех главах, в которых пойдет речь о нахождении путей (в графах), о решения интеллектуальных задач и о переборе.

    2. 6. 2.    Варианты программы, полученые путем переупорядочивания предложений и целей
    Уже в примерах программ гл. 1 существовала скрытая опасность зацикливания. Определение отношения предок в этой главе было таким:
            предок( X, Z) :-

                    родитель( X, Z).
            предок( X, Z) :-

                    родитель( X, Y),

                    предок( Y, Z).
    Проанализируем некоторые варианты этой программы. Ясно, что все варианты будут иметь одинаковую декларативную семантику, но разные процедурные семантики.
    В соответствии с декларативной семантикой Пролога мы можем, не меняя декларативного смысла, изменить
    (1)        порядок предложений в программе и
    (2)        порядок целей в телах предложений.
    Процедура предок состоит из двух предложений, и одно из них содержит в своем теле две цели. Возможны, поэтому, четыре варианта данной программы, все с одинаковым декларативным смыслом. Эти четыре варианта можно получить, если
    (1)        поменять местами оба предложения и

    (2)        поменять местами цели в каждом из этих двух последовательностей предложений.
    Соответствующие процедуры, названные пред1, пред2, пред3 и пред4, показаны на рис. 2.16.
    Есть существенная разница в поведении этих четырех декларативно эквивалентных процедур. Чтобы это продемонстрировать, будем считать, отношение родитель определенным так, как показано на рис. 1.1 гл. 1. и посмотрим, что произойдет, если мы спросим, является ли Том предком Пат, используя все четыре варианта отношения предок:
            ?-  пред1( том, пат).

            да
            ?-  пред2( том, пат).

            да
            ?-  пред3( том, пат).

            да
            ?-  пред4( том, пат).
    %  Четыре версии программы предок

    %  Исходная версия
    пред1( X, Z) :-

           родитель( X, Z).
    пред1( X, Z) :-

           родитель( X, Y),

           пред1( Y, Z).
    %  Вариант  а:  изменение порядка предложений в исходной версии
    пред2( X, Z) :-

           родитель( X, Y),

           пред2( Y, Z).
    пред2( X, Z) :-

           родитель( X, Z).
    %  Вариант  b:  изменение порядка целей во втором предложении

    %  исходной версии
    пред3( X, Z) :-

           родитель( X, Z).
    пред3( X, Z) :-

           пред3( X, Y),

           родитель( Y, Z).
    %  Вариант  с:  изменение порядка предложений и целей в исходной

    %  версии
    пред4( X, Z) :-

           пред4( X, Y),

           родитель( Y, Z).
    пред4( X, Z):-

           родитель( X, Z).
    Рис. 2. 16.  Четыре версии программы предок.
    В последнем случае пролог-система не сможет найти ответа. И выведет на терминал сообщение: "Не хватает памяти".
    На рис. 1.11 гл. 1 были показаны все шаги вычислений по пред1 (в главе 1 она называлась предок), предпринятые для ответа на этот вопрос. На рис 2.17 показаны соответствующие вычисления по пред2, пред3 и пред4. На рис. 2.17 (с) ясно видно, что работа пред4 - бесперспективна, а рис. 2.17(а) показывает, что пред2 довольно неэффективна по сравнению с пред1: пред2 производит значительно больший перебор и делает больше возвратов по фамильному дереву.
    Такое сравнение должно напомнить нам об общем практическом правиле при решении задач: обычно бывает полезным прежде всего попробовать самое простое соображение. В нашем случае все версии отношения предок основаны на двух соображениях:
    более простое - нужно проверить, не удовлетворяют ли два аргумента отношения предок отношению родитель;
    более сложное - найти кого-либо "между" этими двумя людьми (кого-либо, кто связан с ними отношениями родитель и предок).
    Из всех четырех вариантов отношения предок, пред1 использует наиболее простое соображение в первую очередь. В противоположность этому пред4 всегда сначала пробует использовать самое сложное. Пред2 и пред3 находятся между этими двумя крайностями. Даже без детального изучения процессов вычислений ясно, что пред1 следует предпочесть просто на основании правила "самое простое пробуй в первую очередь".
    Наши четыре варианта процедуры предок можно далее сравнить, рассмотрев вопрос: "На какие типы вопросов может отвечать тот или иной конкретный вариант и на какие не может?" Оказывается, пред1 и пред2 оба способны найти ответ на любой вид вопроса относительно предков; пред4 никогда не находит ответа, а пред3 иногда может найти, иногда нет. Вот пример вопроса, на который пред4 ответить не может:
            ?-  пред3( лиз, джим).
    Такой вопрос тоже вводит систему в бесконечную рекурсию. Следовательно и пред3 нельзя признать верным с точки зрения процедурного смысла.
   
    Рис. 2. 17.  Поведение трех вариантов формулировки отношения

    предок при ответе на вопрос, является ли Том предком Пат?

    2. 6. 3.    Сочетание декларативного и процедурного подходов
    В предыдущем разделе было показано, что порядок целей и предложений имеет существенное значение. Более того, существуют программы, которые верны в декларативном смысле, но на практике не работают. Такое противоречие между декларативным и процедурным смыслами может вызвать недовольство. Кто-нибудь спросит: "А почему вообще не забыть о декларативном смысле?" Такое пожелание становится особенно сильным, когда рассматриваются предложения типа:
            предок( X, Z) :- предок( X, Z).
    Это предложение верно в декларативном смысле, но совершенно бесполезно в качестве рабочей программы.
    Причина, по которой не следует забывать о декларативном смысле, кроется в том, что прогресс, достигнутый в технологии программирования, получен на пути продвижения от учета всех процедурных деталей к концентрации внимания на декларативных аспектах, которые обычно легче формулировать и понимать. Сама система, а не программист, должна нести бремя заботы о процедурных деталях. В этом Пролог оказывает некоторую помощь, хотя, как мы видели в данном разделе, помощь лишь частичную: иногда он правильно прорабатывает эти процедурные детали, иногда - нет. Многие придерживаются мнения, что лучше иметь хоть какую-то декларативную семантику, чем никакой (отсутствие декларативной семантики характерно для многих других языков программирования). Практическим следствием такого взгляда является тот факт, что часто довольно легко получить работающую программу, имея программу декларативно корректную. Поэтому практичным следует признать такой подход: сосредоточиться на декларативных аспектах задачи, затем пропустить на машине полученную программу и, если она окажется процедурно неправильной, попытаться изменить порядок следования предложений и целей.

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    2. 7.    Замечания о взаимосвязи между Прологом и логикой
    Пролог восходит к математической логике, поэтому его синтаксис и семантику можно наиболее точно описать при помощи логики. Так часто и поступают при обучении этому языку. Однако такой подход к ознакомлению с Прологом предполагает знание читателем определенных понятий математической логики. С другой стороны, знание этих понятий явно необязательно для того, чтобы понять и использовать Пролог в качестве инструмента для практического программирования, а цель данной книги - научить именно этому. Для тех же читателей, которые особенно заинтересуются взаимосвязями между Прологом и логикой, мы сейчас перечислим основные из них, а также приведем некоторые подходящие источники
    .
    Синтаксис Пролога - это синтаксис предложений логики предикатов первого порядка, записанных в так называемой форме предложений (форме, при которой кванторы не выписываются
    явно), а точнее, в виде частного случая таких предложений - в виде
    формул Хорна
    (предложений, имеющих самое большее один положительный литерал). Клоксин и Меллиш (1981 г.) приводят пролог-программу, которая преобразует предложения исчисления предикатов
    первого порядка в форму предложений. Процедурный смысл Пролога основывается на
    принципе резолюций
    , применяющемся для автоматического доказательства теорем, который был предложен Робинсоном в его классической статье (1965 г.). В Прологе используется особая стратегия доказательства теоремы методом резолюций, носящая название SLD. Введение в исчисление предикатов первого порядка и доказательство теорем, основанное на методе резолюций, можно найти у Нильсона (1981 г.). Математические вопросы, касающиеся свойств процедурной семантики Пролога в их связи с логикой, проанализированы Ллойдом (1984 г.)
    .
    Сопоставление в Прологе соответствует некоторому действию в логике, называемому унификацией. Мы, однако, избегаем слова "унификация", так как по соображениям эффективности внести в большинстве пролог-систем сопоставление реализовано таким образом, что оно не полностью соответствует унификации (см. упражнение 2.10). Тем не менее, с практической точки зрения, такая приближенная унификация вполне допустима.
    Упражнение
    2. 10.    Что будет, если пролог-системе задать такой вопрос:
            ?-   Х  =  f( X).
    Успешным или неуспешным будет здесь сопоставление? По определению унификации в логике, сопоставление должно быть неуспешным, а что будет в соответствии с нашим определением сопоставления из раздела 2.2? Попробуйте объяснить, почему многие реализации Пролога отвечают на вышеприведенный вопрос так:
            X  =   f(f(f(f(f(f(f(f(f(f(f(f(f(f(f( ...
    Посмотреть ответ
    Резюме
    К настоящему моменту мы изучили нечто вроде базового Пролога, который называют еще "чистый Пролог". Он "чист", потому что довольно точно соответствует формальной логике. Расширения, преследующие цель приспособить язык к некоторым практическим нуждам, будут изучены дальше (гл. 3, 5, 6. 7). Важными моментами данной главы являются следующие:
    Простые объекты в Прологе - это атомы, переменные и числа. Структурные объекты, или структуры, используются для представления объектов, которые состоят из нескольких компонент.
    Структуры строятся посредством функторов. Каждый функтор определяется своими именем и арностью.
    Тип объекта распознается исключительно по его синтаксической форме.
    Область известности (лексический диапазон) переменных - одно предложение. Поэтому одно и то же имя в двух предложениях обозначает две разные переменные.
    Структуры могут быть естественным образом изображены в виде деревьев. Пролог можно рассматривать как язык обработки деревьев.
    Операция сопоставление берет два терма и пытается сделать их идентичными, подбирая соответствующую конкретизацию переменных в обоих термах.
    Сопоставление, если оно завершается успешно, в качестве результата выдает наиболее общую конкретизацию переменных.
    Декларативная семантика Пролога определяет, является ли целевое утверждение истинным, исходя из данной программы, и если оно истинно, то для какой конкретизации переменных.
    Запятая между целями означает их конъюнкцию. Точка с запятой между целями означает их дизъюнкцию.
    Процедурная семантика Пролога - это процедура достижения списка целей в контексте данной программы. Процедура выдает истинность или ложность списка целей и соответствующую конкретизацию переменных. Процедура осуществляет автоматический возврат для перебора различных вариантов.
    Декларативный смысл программ на "чистом Прологе" не зависит от порядка предложений и от порядка целей в предложениях.
    Процедурный смысл существенно зависит от порядка целей и предложений. Поэтому порядок может повлиять на эффективность программы; неудачный порядок может даже привести к бесконечным рекурсивным вызовам.
    Имея декларативно правильную программу, можно улучшить ее эффективность путем изменения порядка предложений и целей при сохранении ее декларативной правильности. Переупорядочивание - один из методов предотвращения зацикливания.
    Кроме переупорядочивания существуют и другие, более общие методы предотвращения зацикливания, способствующие получению процедурно правильных программ.
    В данной главе обсуждались следующие понятия:


    объекты данных:

            атом, число, переменная, структура

    терм

    функтор, арность функтора

    главный функтор терма

    сопоставление термов

    наиболее общая конкретизация

    декларативная семантика

    конкретизация предложений,

            вариант предложения

    процедурная семантика

    вычисление целевого утверждения Литература
    Clocksin W. F. and Mellish С. S. (1981). Programming in Prolog. Springer-Verlag. [Имеется перевод: Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987.]
    Lloyd J. W. (1984). Foundations of Logic Programming. Springer-Verlag.
    Nilsson N. J. (1981). Principies of Artificial Intelligence. Tioga; Springer-Verlag.
    Robinson A. J. (1965). A machine-oriented logic based on the resolution principle. JACM 12: 23-41. [Имеется перевод: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции.- В кн. Кибернетический сборник, вып. 7, 1970, с. 194-218.]

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд

    Глава 3
    СПИСКИ, ОПЕРАТОРЫ, АРИФМЕТИКА
    В этой главе мы будем изучать специальные способы представления списков. Список - один из самых простых и полезных типов структур. Мы рассмотрим также некоторые программы для выполнения типовых операций над списками и, кроме того, покажем, как можно просто записывать арифметические выражения и операторы, что во многих случаях позволит улучшить "читабельность" программ. Базовый Пролог (глава 2), расширенный этими тремя добавлениями, станет удобной основой для составления интересных программ.
    3. 1.    Представление списков
    Список - это простая структура данных, широко используемая в нечисловом программировании. Список - это последовательность, составленная из произвольного числа элементов, например энн, теннис, том, лыжи. На Прологе это записывается так:
            [ энн, теннис, том, лыжи ]
    Однако таково лишь внешнее представление списков. Как мы уже видели в гл. 2, все структурные объекты Пролога - это деревья. Списки не являются исключением из этого правила.
    Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом  [ ].  Во втором случае список следует рассматривать как структуру состоящую из двух частей:
    (1)    первый элемент, называемый головой списка;
    (2)    остальная часть списка, называемая хвостом.
    Например, для списка
            [ энн, теннис, том, лыжи ]
    энн - это голова, а хвостом является список
            [ теннис, том, лыжи ]
    В общем случае, головой может быть что угодно (любой прологовский объект, например, дерево или переменная); хвост же должен быть списком. Голова соединяется с хвостом при помощи специального функтора. Выбор этого функтора зависит от конкретной реализации Пролога; мы будем считать, что это точка:
            .( Голова, Хвост)
    Поскольку Хвост - это список, он либо пуст, либо имеет свои собственную голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. Наш список представляется следующим образом:
            .( энн, .( теннис, .( том, .( лыжи, [ ] ) ) ) )
    На рис. 3.1 изображена соответствующая древовидная структура. Заметим, что показанный выше пример содержит пустой список [ ]. Дело в том, что самый последний хвост является одноэлементным списком:
            [ лыжи ]
    Хвост этого списка пуст
            [ лыжи ] = .( лыжи, [ ] )
    Рассмотренный пример показывает, как общий принцип структуризации объектов данных можно применить к спискам любой длины. Из нашего примера также видно, что такой примитивный способ представления в случае большой глубины вложенности подэлементов в хвостовой части списка может привести к довольно запутанным выражениям. Вот почему в Прологе предусматривается более лаконичный способ изображения списков, при котором они записываются как последовательности элементов, заключенные в квадратные скобки. Программист может использовать оба способа, но представление с квадратными скобками, конечно, в большинстве случаев пользуется предпочтением. Мы, однако, всегда будем помнить, что это всего лишь косметическое улучшение и что во внутреннем представлении наши списки выглядят как деревья. При выводе же они автоматически преобразуются в более лаконичную форму представления. Так, например, возможен следующий диалог:
            ?-  Список1 = [а, b, с],

                 Список2 = (a,  .(b,  .(c,[ ]) ) ).
            Список1 = [а, b, с]

            Список2 = [а, b, с]
            ?-  Увлечения1 = .( теннис, .(музыка, [ ] ) ),

                 Увлечения2 = [лыжи, еда],

                 L = [энн, Увлечения1, том, Увлечения2].
            Увлечения1 = [теннис, музыка]

            Увлечения2 = [лыжи, еда]

            L = [энн, [теннис, музыка], том, [лыжи, еда]]
   
    Рис. 3. 1.  Представление списка [энн, теннис, том, лыжи] в виде дерева.
    Приведенный пример также напоминает вам о том, что элементами списка могут быть любые объекты, в частности тоже списки.
    На практике часто бывает удобным трактовать хвост списка как самостоятельный объект. Например, пусть
            L = [а, b, с]
    Тогда можно написать:
            Хвост = [b, с] и L = .(а, Хвост)
    Для того, чтобы выразить это при помощи квадратных скобок, в Прологе предусмотрено еще одно расширение нотации для представления списка, а именно вертикальная черта, отделяющая голову от хвоста:
            L = [а | Хвост]
    На самом деле вертикальная черта имеет более общий смысл: мы можем перечислить любое количество элементов списка, затем поставить символ " | ", а после этого - список остальных элементов. Так, только что рассмотренный пример можно представить следующими различными способами:
            [а, b, с] = [а | [b, с]] = [a, b | [c]] = [a, b, c | [ ]]
    Подытожим:
    Список - это структура данных, которая либо пуста, либо состоит из двух частей: головы и хвоста. Хвост в свою очередь сам является списком.
    Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде


            [ Элемент1, Элемент2, ... ]


    или


            [ Голова | Хвост ]


    или


            [ Элемент1, Элемент2, ... | Остальные]

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    3. 2.    Некоторые операции над списками
    Списки можно применять для представления множеств, хотя и существует некоторое различие между этими понятиями: порядок элементов множества не существенен, в то время как для списка этот порядок имеет значение; кроме того, один н тот же объект может встретиться в списке несколько раз. Однако наиболее часто используемые операции над списками аналогичны операциям над множествами. Среди них
    проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;
    конкатенация (сцепление) двух списков, что соответствует объединению множеств;
    добавление нового объекта в список или удаление некоторого объекта из него.
    В оставшейся части раздела мы покажем программы, реализующие эти и некоторые другие операции над списками.

    3. 2. 1.    Принадлежность к списку
    Мы представим отношение принадлежности как
            принадлежит( X, L)
    где Х - объект, а L - список. Цель принадлежит( X, L) истинна, если элемент Х встречается в L. Например, верно что
            принадлежит( b, [а, b, с] )
    и, наоборот, не верно, что
            принадлежит b, [а, [b, с] ] )
    но
            принадлежит [b, с], [а, [b, с]] )
    истинно. Составление программы для отношения принадлежности может быть основано на следующих соображениях:
        (1)        Х есть голова L, либо
        (2)        Х принадлежит хвосту L.
    Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе - правило:
            принадлежит( X, [X | Хвост ] ).
            принадлежит ( X, [Голова | Хвост ] ) :-

                    принадлежит( X, Хвост).

    3. 2. 2.    Сцепление ( конкатенация)
    Для сцепления списков мы определим отношение
            конк( L1, L2, L3)
    Здесь L1 и L2 - два списка, a L3 - список, получаемый при их сцеплении. Например,
            конк( [а, b], [c, d], [a, b, c, d] )
    истинно, а
            конк( [а, b], [c, d], [a, b, a, c, d] )
    ложно. Определение отношения конк, как и раньше, содержит два случая в зависимости от вида первого аргумента L1:
    (1)        Если первый аргумент пуст, тогда второй и третий аргументы представляют собой один и тот же список (назовем его L), что выражается в виде следующего прологовского факта:
            конк( [ ], L, L ).
    (2)        Если первый аргумент отношения конк не пуст, то он имеет голову и хвост в выглядит так:
            [X | L1]
    На рис. 3.2 показано, как производится сцепление списка [X | L1] с произвольным списком L2. Результат сцепления - список [X | L3], где L3 получен после сцепления списков L1 и L2. На прологе это можно записать следующим образом:
            конк( [X | L1, L2, [X | L3]):-

                  конк( L1, L2, L3).
   
    Рис. 3. 2.  Конкатенация списков.
    Составленную программу можно теперь использовать для сцепления заданных списков, например:
            ?- конк( [a, b, с], [1, 2, 3], L ).

            L = [a, b, c, 1, 2, 3]
            ?- конк( [а, [b, с], d], [а, [ ], b], L ).

            L = [a, [b, c], d, а, [ ], b]
    Хотя программа для конк выглядит довольно просто, она обладает большой гибкостью и ее можно использовать многими другими способами. Например, ее можно применять как бы в обратном направлении для разбиения заданного списка на две части:
            ?- конк( L1, L2, [а, b, с] ).
            L1 = [ ]

            L2 = [а, b, c];
            L1 = [а]

            L2 = [b, с];
            L1 = [а, b]

            L2 = [c];
            L1 = [а, b, с]

            L2 = [ ];
            no             (нет)
    Список  [а, b, с]  разбивается на два списка четырьмя способами, и все они были обнаружены нашей программой при помощи механизма автоматического перебора.
    Нашу программу можно также применить для поиска в списке комбинации элементов, отвечающей некоторому условию, задаваемому в виде шаблона или образца. Например, можно найти все месяцы, предшествующие данному, и все месяцы, следующие за ним, сформулировав такую цель:
            ?- конк( До, [май | После ],

                      [янв, фев, март, апр, май, июнь,

                            июль, авг, сент, окт, ноябрь, дек]).
            До = [янв, фев, март, апр]
            После = [июнь, июль, авг, сент, окт, ноябрь, дек].
    Далее мы сможем найти месяц, непосредственно предшествующий маю, и месяц, непосредственно следующий за ним, задав вопрос:
            ?- конк( _, [Месяц1, май, Месяц2 | _ ],

                       [янв, февр, март, апр, май, июнь,

                            июль, авг, сент, окт, ноябрь, дек]).
            Месяц1 = апр

            Месяц2 = июнь
    Более того, мы сможем, например, удалить из некоторого списка L1 все, что следует за тремя последовательными вхождениями элемента z в L1 вместе с этими тремя z. Например, это можно сделать так:
            ?- L1 = [a, b, z, z, c, z, z, z, d, e],

                конк( L2, [z, z, z | _ ], L1).
            L1 = [a, b, z, z, c, z, z, z, d, e]

            L2 = [a, b, z, z, c]
    Мы уже запрограммировали отношение принадлежности. Однако, используя конк, можно было бы определить это отношение следующим эквивалентным способом:
        принадлежит1( X, L) :-

               конк( L1, [X | L2], L).
   
    Рис. 3. 3.  Процедура принадлежит1 находит элемент в заданном

    списке, производя по нему последовательный поиск.
    В этом предложении сказано: "X принадлежит L, если список L можно разбить на два списка таким образом, чтобы элемент Х являлся головой второго из них. Разумеется, принадлежит1 определяет то же самое отношение, что и принадлежит. Мы использовали другое имя только для того, чтобы различать таким образом две разные реализации этого отношения, Заметим, что, используя анонимную переменную, можно записать вышеприведенное предложение так:
            принадлежит1( X, L) :-

                   конк( _, [X | _ ], L).
    Интересно сравнить между собой эти две реализации отношения принадлежности. Принадлежит имеет довольно очевидный процедурный смысл:
        Для проверки, является ли Х элементом списка L, нужно
        (1)    сначала проверить, не совпадает ли голова списка L с X, а затем
        (2)    проверить, не принадлежит ли Х хвосту списка L.
    С другой стороны, принадлежит1, наоборот, имеет очевидный декларативный смысл, но его процедурный смысл не столь очевиден.
    Интересным упражнением было бы следующее: выяснить, как в действительности принадлежит1 что-либо вычисляет. Некоторое представление об этом мы получим, рассмотрев запись всех шагов вычисления ответа на вопрос:
            ?-  принадлежит1( b, [а, b, с] ).
    На рис. 3.3 приведена эта запись. Из нее можно заключить, что принадлежит1 ведет себя точно так же, как и принадлежит. Он просматривает список элемент за элементом до тех пор, пока не найдет нужный или пока не кончится список.
    Упражнения
    3. 1.    (а)    Используя отношение конк, напишите цель, соответствующую вычеркиванию трех последних элементов списка L, результат - новый список L1. Указание: L - конкатенация L1 и трехэлементного списка.
    (b)    Напишите последовательность целей для порождения списка L2, получающегося из списка L вычеркиванием его трех первых и трех последних элементов.
    Посмотреть ответ
    3. 2.    Определите отношение
            последний( Элемент, Список)
    так, чтобы Элемент являлся последним элементом списка Список. Напишите два варианта определения:    (а)    с использованием отношения конк,     (b)    без использования этого отношения.
    Посмотреть ответ

    3. 2. 3.    Добавление элемента
    Наиболее простой способ добавить элемент в список - это вставить его в самое начало так, чтобы он стал его новой головой. Если Х - это новый элемент, а список, в который Х добавляется - L, тогда результирующий список - это просто
            [X | L]
    Таким образом, для того, чтобы добавить новый элемент в начало списка, не надо использовать никакой процедуры. Тем не менее, если мы хотим определить такую процедуру в явном виде, то ее можно представить в форме такого факта:
            добавить( X, L, [X | L] ).

    3. 2. 4.    Удаление элемента
    Удаление элемента Х из списка L можно запрограммировать в виде отношения
            удалить( X, L, L1)
    где L1 совпадает со списком L, у которого удален элемент X. Отношение удалить можно определить аналогично отношению принадлежности. Имеем снова два случая:
    (1)        Если Х является головой списка, тогда результатом удаления будет хвост этого списка.
    (2)        Если Х находится в хвосте списка, тогда его нужно удалить оттуда.
            удалить( X, [X | Хвост], Хвост).
            удалить( X, [Y | Хвост], [ Y | Хвост1]  ) :-

                   удалить( X, Хвост, Хвост1).
    как и принадлежит, отношение удалить по природе своей недетерминировано. Если в списке встречается несколько вхождений элемента X, то удалить сможет исключить их все при помощи возвратов. Конечно, вычисление по каждой альтернативе будет удалять лишь одно вхождение X, оставляя остальные в неприкосновенности. Например:
            ?- удалить( а, [а, b, а, а], L].
            L = [b, а, а];

            L = [а, b, а];

            L = [а, b, а];
            nо                 (нет)
    При попытке исключить элемент, не содержащийся в списке, отношение удалить потерпит неудачу.
    Отношение удалить можно использовать в обратном направлении для того, чтобы добавлять элементы в список, вставляя их в произвольные места. Например, если мы хотим во все возможные места списка [1, 2, 3]  вставить атом а,  то мы можем это сделать, задав вопрос: "Каким должен быть список L, чтобы после удаления из него элемента а   получился список  [1, 2, 3]?"
            ?- удалить( а, L, [1, 2, 3] ).
            L = [а, 1, 2, 3];

            L = [1, а, 2, 3];

            L = [1, 2, а, 3];

            L = [1, 2, 3, а];
            nо                     (нет)
    Вообще операция по внесению Х в произвольное место некоторого списка Список, дающее в результате БольшийСписок, может быть определена предложением:
            внести( X, Список, БольшийСписок) :-

                  удалить( X, БольшийСписок, Список).
    В принадлежит1 мы изящно реализовали отношение принадлежности через конк. Для проверки на принадлежность можно также использовать и удалить. Идея простая: некоторый Х принадлежит списку Список, если Х можно из него удалить:
            принадлежит2( X, Список) :-

                   удалить( X, Список, _ ).

    3. 2. 5.    Подсписок
    Рассмотрим теперь отношение подсписок. Это отношение имеет два аргумента - список L и список S, такой, что S содержится в L в качестве подсписка. Так отношение
            подсписок( [c, d, e], [a, b, c, d, e, f] )
    имеет место, а отношение
            подсписок( [c, e], [a, b, c, d, e, f] )
    нет. Пролог-программа для отношения подсписок может основываться на той же идее, что и принадлежит1, только на этот раз отношение более общо (см. рис. 3.4).
   
    Рис. 3. 4.  Отношения принадлежит и подсписок.
    Его можно сформулировать так:
        S является подсписком L, если
        (1)        L можно разбить на два списка L1 и L2 и
        (2)        L2 можно разбить на два списка S и L3.
    Как мы видели раньше, отношение конк можно использовать для разбиения списков. Поэтому вышеприведенную формулировку можно выразить на Прологе так:
            подсписок( S, L) :-

                     конк( L1, L2, L),

                     конк( S, L3, L2).
    Ясно, что процедуру подсписок можно гибко использовать различными способами. Хотя она предназначалась для проверки, является ли какой-либо список подсписком другого, ее можно использовать, например, для нахождения всех подсписков данного списка:
            ?-  подсписок( S, [а, b, с] ).
            S = [ ];

            S = [a];

            S = [а, b];

            S = [а, b, с];

            S = [b];

            . . .

    3. 2. 6.    Перестановки
    Иногда бывает полезно построить все перестановки некоторого заданного списка. Для этого мы определим отношение перестановка с двумя аргументами. Аргументы - это два списка, один из которых является перестановкой другого. Мы намереваемся порождать перестановки списка с помощью механизма автоматического перебора, используя процедуру перестановка, подобно тому, как это делается в следующем примере:
            ?- перестановка( [а, b, с], Р).
            Р = [а, b, с];

            Р = [а, с, b];

            Р = [b, а, с];

            . . .
   
    Рис. 3. 5.  Один из способов построения перестановки списка [X | L].
    Программа для отношения перестановка в свою очередь опять может основываться на рассмотрении двух случаев в зависимости от вида первого списка:
    (1)        Если первый список пуст, то и второй список должен быть пустым.
    (2)        Если первый список не пуст, тогда он имеет вид [Х | L], и перестановку такого списка можно построить так, как Это показано на рис. 3.5: вначале получить список L1 - перестановку L, а затем внести Х в произвольную позицию L1.
    Два прологовских предложения, соответствующих этим двум случаям, таковы:
            перестановка( [ ], [ ]).
            перестановка( [X | L ], Р) :-

                  перестановка( L, L1),

                  внести( X, L1, Р).
    Другой вариант этой программы мог бы предусматривать удаление элемента Х из первого списка, перестановку оставшейся его части - получение списка Р, а затем добавление Х в начало списка Р. Соответствующая программа такова:
            перестановка2( [ ], [ ]).
            перестановка2( L, [X | Р] ) :-

                  удалить( X, L, L1),

                  перестановка2( L1, Р).
    Поучительно проделать несколько экспериментов с нашей программой перестановки. Ее нормальное использование могло бы быть примерно таким:
            ?-  перестановка( [красный, голубой, зеленый], Р).
    Как и предполагалось, будут построены все шесть перестановок:
            Р = [ красный, голубой, зеленый];

            Р = [ красный, зеленый, голубой];

            Р = [ голубой, красный, зеленый];

            Р = [ голубой, зеленый, красный];

            Р = [ зеленый, красный, голубой];

            Р = [ зеленый, голубой, красный];
            nо                   (нет)
    Приведем другой вариант использования процедуры перестановка:
            ?-  перестановка( L, [а, b, с] ).
    Наша первая версия, перестановка, произведет успешную конкретизацию L всеми шестью перестановками. Если пользователь потребует новых решений, он никогда не получит ответ "нет", поскольку программа войдет в бесконечный цикл, пытаясь отыскать новые несуществующие перестановки. Вторая версия, перестановка2, в этой ситуации найдет только первую (идентичную) перестановку, а затем сразу зациклится. Следовательно, при использовании этих отношений требуется соблюдать осторожность.
    Упражнения
    3. 3.    Определите два предиката
            четнаядлина( Список)    и    нечетнаядлина( Список)
    таким образом, чтобы они были истинными, если их аргументом является список четной или нечетной длины соответственно. Например, список [а, b, с, d] имеет четную длину, a [a, b, c] - нечетную.
    Посмотреть ответ
    3. 4.    Определите отношение
            обращение( Список, ОбращенныйСписок),
    которое обращает списки. Например,
            обращение( [a, b, c, d], [d, c, b, a] ).
    Посмотреть ответ
    3. 5.    Определите предикат
            палиндром( Список).
    Список называется палиндромом, если он читается одинаково, как слева направо, так и справа налево. Например,  [м, а, д, а, м].
    Посмотреть ответ
    3. 6.    Определите отношение
            сдвиг( Список1, Список2)
    таким образом, чтобы Список2 представлял собой Список1, "циклически сдвинутый" влево на один символ. Например,
            ?-  сдвиг( [1, 2, 3, 4, 5], L1),

                 сдвиг1( LI, L2)
    дает
            L1 = [2, 3, 4, 5, 1]

            L2 = [3, 4, 5, 1, 2]
    Посмотреть ответ
    3. 7.    Определите отношение
            перевод( Список1, Список2)
    для перевода списка чисел от 0 до 9 в список соответствующих слов. Например,
            перевод( [3, 5, 1, 3], [три, пять, один, три] )
    Используйте в качестве вспомогательных следующие отношения:
            означает( 0, нуль).

            означает( 1, один).

            означает( 2, два).

            . . .
    Посмотреть ответ
    3. 8.        Определите отношение
            подмножество( Множество, Подмножество)
    где Множество и Подмножество - два списка представляющие два множества. Желательно иметь возможность использовать это отношение не только для проверки включения одного множества в другое, но и для порождения всех возможных подмножеств заданного множества. Например:
            ?-  подмножество( [а, b, с], S ).
            S = [a, b, c];

            S = [b, c];

            S = [c];

            S = [ ];

            S = [a, c];

            S = [a];

            . . .
    Посмотреть ответ
    3. 9.    Определите отношение
            разбиениесписка( Список, Список1, Список2)
    так, чтобы оно распределяло элементы списка между двумя списками Список1 и Список2 и чтобы эти списки были примерно одинаковой длины. Например:
            разбиениесписка( [а, b, с, d, e], [a, с, е], [b, d]).
    Посмотреть ответ
    3. 10.    Перепишите программу об обезьяне и бананах из главы 2 таким образом, чтобы отношение
            можетзавладеть( Состояние, Действия)
    давало не только положительный или отрицательный ответ, но и порождало последовательность действий обезьяны, приводящую ее к успеху. Пусть Действия будет такой последовательностью, представленной в виде списка ходов:
            Действия = [ перейти( дверь, окно),

                                   передвинуть( окно, середина),

                                   залезть, схватить ]
    Посмотреть ответ
    3. 11.    Определите отношение
            линеаризация( Список, ЛинейныйСписок)
    где Список может быть списком списков, а ЛинейныйСписок - это тот же список, но "выровненный" таким образом, что элементы его подсписков составляют один линейный список. Например:
            ? - линеаризация( [а, d, [с, d], [ ], [[[е]]], f, L).
            L = [a, b, c, d, e, f]
    Посмотреть ответ

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    3. 3.    Операторная запись (нотация)
    В математике мы привыкли записывать выражения в таком виде:
            2*a  +  b*с
    где  +  и  *  - это операторы, а    2,   а,   b,    с   - аргументы. В частности,  +   и  *  называют инфиксными операторами, поскольку они появляются между своими аргументами. Такие выражения могут быть
    представлены в виде деревьев, как это сделано на рис. 3.6, и
    записаны как прологовские термы
    с
    +
      и
    *
      в качестве функторов:
            +( *( 2, а), *( b, с) )
   
    Рис. 3. 6.  Представление выражения  2*а+b*с  в виде дерева.
    Поскольку мы обычно предпочитаем записывать такие выражения в привычной инфиксной форме операторов, Пролог обеспечивает такое удобство. Поэтому наше выражение, записанное просто как
            2*а  +  b*с
    будет воспринято правильно. Однако это лишь внешнее представление объекта, которое будет автоматически преобразовано в обычную форму прологовских термов. Такой терм выводится пользователю снова в своей внешней инфиксной форме.
    Выражения рассматриваются Прологом просто как дополнительный способ записи, при котором не вводятся какие-либо новые принципы структуризации объектов данных. Если мы напишем   а  +  b,  Пролог поймет эту запись, как если бы написали +(а, b). Для того, чтобы Пролог правильно воспринимал выражения типа а + b*с, он должен знать, что * связывает сильнее, чем +. Будем говорить, что + имеет более низкий приоритет, чем *. Поэтому верная интерпретация выражений зависит от приоритетов операторов. Например, выражение а  +  b*с, в принципе можно понимать и как
            +( а, *( b, с) )
    и как
            *( +( а, b), с
    )
    Общее правило состоит в том, что оператор с самым низким приоритетом расценивается как главный функтор терма. Если мы хотим, чтобы выражения, содержащие  +  и  *,   понимались в соответствии с обычными соглашениями, то  + должен иметь более низкий приоритет, чем  *.  Тогда выражение а  +   b*с означает то же, что и а  +  (b*с). Если имеется в виду другая интерпретация, то это надо указать явно с помощью скобок, например ( а+b)*с.
    Программист может вводить свои собственные операторы. Так, например, можно определить атомы имеет и поддерживает в качестве инфиксных операторов, а затем записывать в программе факты вида:
            питер имеет информацию.

            пол поддерживает стол.
    Эти факты в точности эквивалентны следующим:
            имеет( питер, информацию).

            поддерживает( пол, стол).
    Программист определяет новые операторы, вводя в программу особый вид предложений, которые иногда называют директивами. Такие предложения играют роль определений новых операторов. Определение оператора должно появиться в программе раньше, чем любое выражение, использующее этот оператор. Например, оператор имеет можно определить директивой
            :- ор( 600, xfx, имеет).
    Такая запись сообщит Прологу, что мы хотим использовать "имеет" в качестве оператора с приоритетом 600 и типом 'xfx', обозначающий одну из разновидностей инфиксного оператора. Форма спецификатора 'xfx' указывает на то, что оператор, обозначенный через 'f', располагается между аргументами, обозначенными через 'х'.
    Обратите внимание на то, что определения операторов не содержат описания каких-либо операций или действий. В соответствии с принципами языка ни с одним оператором не связывается каких-либо операций над данными (за исключением особых, редких случаев). Операторы обычно используются так же, как и функторы, только для объединения объектов в структуры и не вызывают действия над данными, хотя само слово "оператор", казалось бы, должно подразумевать какое-то действие.
    Имена операторов это атомы, а их приоритеты - точнее, номера их приоритетов -  должны находиться в некотором диапазоне, зависящем от реализации. Мы будем считать, что этот диапазон располагается в пределах от 1 до 1200.(Чем выше приоритет, тем меньше его номер.  -  Прим. перев
    .)
    Существуют три группы типов операторов, обозначаемые спецификаторами, похожими на xfx:
    (1)        инфиксные операторы трех типов:
                xfx     xfy    yfx
    (2)        префиксные операторы двух типов:
                fx     fy
    (3)        постфиксные операторы двух типов:
                хf     yf
    Спецификаторы выбраны с таким расчетом, чтобы нагляднее отразить структуру выражения, в котором 'f' соответствует оператору, а 'х' и 'у' представляют его аргументы. Расположение 'f' между аргументами указывает на то, что оператор инфиксный. Префиксные и постфиксные спецификаторы содержат только один аргумент, который, соответственно, либо следует за оператором, либо предшествует ему.
   
    Рис. 3. 7.  Две интерпретации выражения а-b-с в предположении, что '-' имеет приоритет 500. Если тип '-' есть yfx, то интерпретация 2 неверна, так как приоритет b-с не выше, чем приоритет '-'.
    Между 'х' и 'у' есть разница. Для ее объяснения нам потребуется ввести понятие приоритета аргумента. Если аргумент заключен в скобки или не имеет структуры (является простым объектом), тогда его приоритет равен 0; если же он структурный, тогда его приоритет равен приоритету его главного функтора. С помощью 'х' обозначается аргумент, чей приоритет должен быть строго выше приоритета оператора (т. е. его номер строго меньше номера приоритета оператора); с помощью 'у' обозначается аргумент, чей приоритет выше или равен приоритету оператора.
    Такие правила помогают избежать неоднозначности при обработке выражений, в которых встречаются операторы с одинаковым приоритетом. Например, выражение
            а-b-с
    обычно понимается как (а-b)-с , а не как а-(b-с). Чтобы обеспечить такую обычную интерпретацию, оператор '-' следует определять как yfx. На рис. 3.7 показано, каким образом исключается вторая интерпретация.
    В качестве еще одного примера рассмотрим оператор not (логическое отрицание "не"). Если not oпределён как fy, тогда выражение
            not  not  р
    записано верно; однако, если not определен как fx, оно некорректно, потому что аргументом первого not является структура not p, которая имеет тот же приоритет, что и not. В этом случае выражение следует писать со скобками:
            not  (not  р)
    :- ор( 1200, xfx, ':-').
    :- ор( 1200, fx, [:-, ?-] ).
    :- op( 1100, xfy, ';').
    :- ор( 1000, xfy, ',').
    :- op( 700, xfx, [=, is, <, >, =<, >=, ==, =\=, \==, =:=]).
    :- op( 500, yfx, [+, -] ).
    :- op( 500, fx, [+, -, not] ).
    :- op( 400, yfx, [*, /, div] ).
    :- op( 300, xfx, mod).
    Рис. 3. 8.  Множество предопределенных операторов
    .
    Для удобства некоторые операторы в пролог-системах определены заранее, чтобы ими можно было пользоваться сразу, без какого-либо определения их в программе. Набор таких операторов и их приоритеты зависят от реализации. Мы будем предполагать, что множество этих "стандартных" операторов ведет себя так, как если бы оно было определено с помощью предложений, приведенных на рис. 3.8. Как видно из того же рисунка, несколько операторов могут быть определены в одном предложении, если только они все имеют одинаковый приоритет и тип. В этом случае имена операторов записываются в виде списка. Использование операторов может значительно повысить наглядность, "читабельность" программы. Для примера предположим, что мы пишем программу для обработки булевских выражений. В такой программе мы, возможно, захотим записать утверждение одной из теорем де Моргана, которое в математических обозначениях записывается так:
            ~ (А & В)  <===>   ~А  v  ~В
    Приведем один из способов записи этого утверждения в виде прологовского предложения:
            эквивалентно( not( и( А, В)), или( not( A, not( B))).
    Однако хорошим стилем программирования было бы попытаться сохранить по возможности больше сходства между видом записи исходной задачи и видом, используемом в программе ее решения. В нашем примере этого можно достичь почти в полной мере, применив операторы. Подходящее множество операторов для наших целей можно определить так:
            :- ор( 800, xfx, <===>).
            :- ор( 700, xfy, v).
            :- ор( 600, хfу, &).
            :- ор( 500, fy, ~).
    Теперь правило де Моргана можно записать в виде следующего факта:
            ~(А & В)  <===>   ~А  v  ~В.
    В соответствии с нашими определениями операторов этот терм понимается так, как это показано на рис. 3.9.
   
    Рис. 3. 9.  Интерпретация терма ~(А  &  В)  <===> ~A  v  ~В
    Подытожим:
    Наглядность программы часто можно улучшить, использовав операторную нотацию. Операторы бывают инфиксные, префиксные и постфиксные.
    В принципе, с оператором не связываются никакие действия над данными, за исключением особых случаев. Определение оператора не содержит описания каких-либо действий, оно лишь вводит новый способ записи. Операторы, как и функторы, лишь связывают компоненты в единую структуру.
    Программист может вводить свои собственные операторы. Каждый оператор определяется своим именем, приоритетом и типом.
    Номер приоритета - это целое число из некоторого диапазона, скажем, между 1 и 1200. Оператор с самым больший номером приоритета соответствует главному функтору выражения, в котором этот оператор встретился. Операторы с меньшими номерами приоритетов связывают свои аргументы сильнее других операторов.
    Тип оператора зависит от двух условий:     (1)    его расположения относительно своих аргументов,    (2)     приоритета его аргументов по сравнению с его собственным. В спецификаторах, таких, как xfyх   обозначает аргумент, чей номер приоритета строго меньше номера приоритета оператора;  у   - аргумент с номером приоритета, меньшим или равным номеру приоритета оператора.
    Упражнения
    3. 12.    Если принять такие определения
            :- ор( 300, xfy, играет_в).

            :- ор( 200, xfy, и).
    то два следующих терма представляют собой синтаксически правильные объекты:
            Tepмl = джимми играет_в футбол и сквош

            Терм1 = сьюзан играет_в теннис и баскетбол и волейбол
    Как эти термы интерпретируются пролог-системой? Каковы их главные функторы и какова их структура?
    Посмотреть ответ
    3. 13.    Предложите подходящее определение операторов ("работает", "в", "нашем"), чтобы можно было писать предложения типа:
            диана работает секретарем в нашем отделе.
    а затем спрашивать:
            ?- Кто работает секретарем в нашем отделе.

            Кто = диана
            ?- диана работает Кем.

            Кем = секретарем в нашем отдела
    Посмотреть ответ
    3. 14.    Рассмотрим программу:
            t( 0+1, 1+0).
            t( X+0+1, X+1+0).
            t( X+1+1, Z) :-

                t( X+1, X1),

                t( X1+1, Z).
    Как данная программа будет отвечать на ниже перечисленные вопросы, если '+' "- это (как обычно) инфиксный оператор типа yfx?
    (a)    ?- t( 0+1, А).
    (b)    ?- t( 0+1+1, В).
    (с)    ?- t( 1+0+1+1+1, С).
    (d)    ?- t( D, 1+1+1+0).
    Посмотреть ответ
    3. 15.    В предыдущем разделе отношения между списка ми мы записывали так:
            принадлежит( Элемент, Список),

            конк( Список1, Список2, Список3),

            удалить( Элемент, Список, НовыйСписок),   . . .
    Предположим, что более предпочтительной для нас является следующая форма записи:
            Элемент входит_в Список,

            конкатенация_списков Список1 и Список2

                  дает Список3,

            удаление_элемента Элемент из_списка Список

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

    Назад | Содержание | Вперёд
    Назад | Содержание | Вперёд
    3. 4.    Арифметические действия
    Пролог рассчитан главным образом на обработку символьной информации, при которой потребность в арифметических вычислениях относительно мала. Поэтому и средства для таких вычислений довольно просты. Для осуществления основных арифметических действий можно воспользоваться
    несколькими предопределенными
    операторами
    .
            +    сложение

            -    вычитание

            *    умножение

            /    деление

            mod     модуль, остаток от целочисленного деления
    Заметьте, что это как раз тот исключительный случай. когда оператор может и в самом деле произвести некоторую операцию. Но даже и в этом случае требуется дополнительное указание на выполнение действия. Пролог-система знает, как выполнять вычисления, предписываемые такими операторами, но этого недостаточно для их непосредственного использования. Следующий вопрос - наивная попытка произвести арифметическое действие:
            ?-  Х = 1 + 2.
    Пролог-система "спокойно" ответит
                 Х = 1 + 2
    а не  X = 3,  как, возможно, ожидалось. Причина этого проста: выражение  1 + 2   обозначает лишь прологовский терм, в котором   +  является функтором, а  1  и  2  - его аргументами.
    В вышеприведенной цели нет ничего, что могло бы заставить
    систему выполнить операцию сложения.
    Для этого в Прологе
    существует
    специальный оператор
    is
      (есть). Этот оператор заставит систему выполнить вычисление. Таким образом, чтобы правильно активизировать арифметическую операцию, надо написать:
            ?-  Х  is  1 + 2.
    Вот теперь ответ будет
                 Х = 3
    Сложение здесь выполняется специальной процедурой, связанной с оператором   +.    Мы будем называть такие процедуры встроенными.
    В Прологе не существует общепринятой нотации для записи арифметических действий, поэтому в разных реализациях она может слегка различаться. Например, оператор  '/'  может в одних реализациях обозначать целочисленное деление, а в других - вещественное. В данной книге под  '/'   мы подразумеваем вещественное деление, для целочисленного же будем использовать оператор div.   В соответствии с этим, на вопрос
            ?- Х  is  3/2,

                Y  is  3 div 2.
    ответ должен быть такой:
                Х = 1.5

                Y = 1
    Левым аргументом оператора  is   является простой объект. Правый аргумент - арифметическое выражение, составленное с помощью арифметических операторов, чисел и переменных. Поскольку оператор  is   запускает арифметические вычисления, к моменту начала вычисления этой цели все ее переменные должны быть уже конкретизированы какими-либо числами. Приоритеты этих предопределенных арифметических операторов (см. рис. 3.8) выбраны с таким расчетом, чтобы операторы применялись к аргументам в том порядке, который принят в математике. Чтобы изменить обычный порядок вычислений, применяются скобки (тоже, как в математике). Заметьте, что  +,  -,  *,    /  и  div  определены, как   yfx,  что определяет порядок их выполнения слева направо. Например,
            Х  is  5 - 2 - 1
    понимается как
            X  is  (5 - 2) - 1
    Арифметические операции используются также и при сравнении числовых величин. Мы можем, например, проверить, что больше - 10000 или результат умножения 277 на 37, с помощью цели
            ?-  277 * 37 > 10000.

            yes             (да)
    Заметьте, что точно так же, как и is,   оператор  '>'  вызывает выполнение вычислений.
    Предположим, у нас есть программа, в которую входит отношение рожд, связывающее имя человека с годом его рождения. Тогда имена людей, родившихся между 1950 и 1960 годами включительно, можно получить при помощи такого вопроса:
            ?-  рожд( Имя, Год),

                 Год >= 1950,

   
    Год <= 1960.
    Ниже перечислены операторы с