- •Иван Братко Программирование на языке Пролог для искусственного интеллекта
- •От редактора перевода
- •Предисловие
- •Предисловие автора
- •Благодарности
- •Упражнения
- •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.2. Обработка файлов термов
- •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.3. Различные виды равенства
- •7.4. Работа с базой данных
- •Упражнения
- •7.5. Средства управления
- •Упражнения
- •Глава 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 счет добавления вычисленных фактов к базе данных
- •Упражнения
- •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. Двоично-троичные справочники
- •Упражнение
- •Литература
- •Глава 11. Основные стратегии решения задач
- •11.1. Предварительные понятия и примеры
- •11.2. Стратегия поиска в глубину
- •Упражнения
- •11.3. Поиск в ширину
- •11.3.1. Списковое представление множества кандидатов
- •11.3.2. Древовидное представление множества кандидатов
- •Упражнения
- •11.4. Замечания относительно поиска в графах, оптимальности к сложности
- •Литература
- •Глава 12 Поиск с предпочтением: эвристический поиск
- •12.1. Поиск с предпочтением
- •Упражнение
- •12.2. Поиск c предпочтением применительно к головоломке "игра в восемь"
- •Упражнение
- •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. Программа на языке al0 для игры в шахматном эндшпиле
- •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. Заключительные замечания
- •Литература
- •Ответы к некоторым упражнениям Глава 1
- •Глава 2
- •Глава 3
- •Глава 4
- •Глава 5
- •Глава 6
- •Глава 7
- •Глава 8
- •Глава 9
- •Глава 10
- •Глава 11
2.6.3. Сочетание декларативного и процедурного подходов
В предыдущем разделе было показано, что порядок целей и предложений имеет существенное значение. Более того, существуют программы, которые верны в декларативном смысле, но на практике не работают. Такое противоречие между декларативным и процедурным смыслами может вызвать недовольство. Кто-нибудь спросит: "А почему вообще не забыть о декларативном смысле?" Такое пожелание становится особенно сильным, когда рассматриваются предложения типа:
предок( X, Z) :- предок( X, Z).
Это предложение верно в декларативном смысле, но совершенно бесполезно в качестве рабочей программы.
Причина, по которой не следует забывать о декларативном смысле, кроется в том, что прогресс, достигнутый в технологии программирования, получен на пути продвижения от учета всех процедурных деталей к концентрации внимания на декларативных аспектах, которые обычно легче формулировать и понимать. Сама система, а не программист, должна нести бремя заботы о процедурных деталях. В этом Пролог оказывает некоторую помощь, хотя, как мы видели в данном разделе, помощь лишь частичную: иногда он правильно прорабатывает эти процедурные детали, иногда — нет. Многие придерживаются мнения, что лучше иметь хоть какую-то декларативную семантику, чем никакой (отсутствие декларативной семантики характерно для многих других языков программирования). Практическим следствием такого взгляда является тот факт, что часто довольно легко получить работающую программу, имея программу декларативно корректную. Поэтому практичным следует признать такой подход: сосредоточиться на декларативных аспектах задачи, затем пропустить на машине полученную программу и, если она окажется процедурно неправильной, попытаться изменить порядок следования предложений и целей.
2.7. Замечания о взаимосвязи между Прологом и логикой
Пролог восходит к математической логике, поэтому его синтаксис и семантику можно наиболее точно описать при помощи логики. Так часто и поступают при обучении этому языку. Однако такой подход к ознакомлению с Прологом предполагает знание читателем определенных понятий математической логики. С другой стороны, знание этих понятий явно необязательно для того, чтобы понять и использовать Пролог в качестве инструмента для практического программирования, а цель данной книги — научить именно этому. Для тех же читателей, которые особенно заинтересуются взаимосвязями между Прологом и логикой, мы сейчас перечислим основные из них, а также приведем некоторые подходящие источники.
Синтаксис Пролога — это синтаксис предложений логики предикатов первого порядка , записанных в так называемой форме предложений (форме, при которой кванторы не выписываются явно), а точнее, в виде частного случая таких предложений — в виде формул Хорна (предложений, имеющих самое большее один положительный литерал). Клоксин и Меллиш (1981 г.) приводят пролог-программу, которая преобразует предложения исчисления предикатов первого порядка в форму предложений. Процедурный смысл Пролога основывается на принципе резолюций , применяющемся для автоматического доказательства теорем, который был предложен Робинсоном в его классической статье (1965 г.). В Прологе используется особая стратегия доказательства теоремы методом резолюций, носящая название SLD. Введение в исчисление предикатов первого порядка и доказательство теорем, основанное на методе резолюций, можно найти у Нильсона (1981 г.). Математические вопросы, касающиеся свойств процедурной семантики Пролога в их связи с логикой, проанализированы Ллойдом (1984 г.).
Сопоставление в Прологе соответствует некоторому действию в логике, называемому унификацией . Мы, однако, избегаем слова "унификация", так как по соображениям эффективности внести в большинстве пролог-систем сопоставление реализовано таким образом, что оно не полностью соответствует унификации (см. упражнение 2.10). Тем не менее, с практической точки зрения, такая приближенная унификация вполне допустима.
