Поиск с возвратом для внутреннего целевого утверждения
Вот еще один, слегка усложненный пример, иллюстрирующий, как в Про-
логе происходит поиск с возвратом.
/* Program CH05EX05.PRO */
predicates
type(symbol, symbol)
is_a(symbol, symbol)
lives(symbol, symbol)
can_swim(symbol)
goal
can_swim(What) ,
write("A ", What, " can swim.").
clauses
type(ungulate, animal).
type(fish, animal).
is_a(zebra, ungulate).
is_a(herring, fish).
is_a(shark, fish).
lives(zebra, on_land).
lives(frog, on_land).
lives(frog, in_water).
lives(shark, in_water).
can_swim(Y) :-
type(X, animal) ,
is_a(Y, X) ,
lives(Y, in_water).
Данный пример программы использует внутреннее целевое утверждение, с
тем чтобы приллюстрировать, как работает поиск с возвратом. После того
как программма скомпилирована и запущена, Турбо Пролог автоматически нач-
нет выполнение целевого утверждения, пытаясь согласовать все подцели в
разделе программы goal.
1. Турбо Пролог обращается к предикату can_swim со свободной пере-
менной What. Пытаясь выполнить это обращение, Турбо Пролог просмат-
ривает программу в поисках соответствия. Он обнаруживает соответст-
вие с предложением, определяющим can_swim, и переменная What унифи-
цируется с переменной Y.
2. Затем Турбо Пролог пытается согласовать тело правила. При этом
Турбо Пролог обращается к первой подцели в теле правила, type(X,
animal) , и ищет соответствие для этого обращения. Он обнаруживает
соответствие с первым фактом, определяющим отношение type.
3. В этот момент Х связывается с ungulate. Поскольку здесь налицо
более, чем одно возможное решение, Турбо Пролог проставляет точку
возврата возле факта type(ungulate, animal).
4. Имея Х, связанным с ungulate, Турбо Пролог производит обращение
ко второй подцели в правиле ( is_a(Y,ungulate) ) и снова ищет соот-
ветствие. Он находит его с первым фактом, is_a(zebra, ungulate). Y
связывается с zebra, и Пролог выставляет точку возврата около
is_a(zebra, ungulate).
5. Теперь, имея Х, связанным с ungulate, и Y - с zebra, Пролог пыта-
ется согласовать последнюю подцель, lives(zebra, in_water). Пролог
проверяет каждое предложение lives, но в программе нет предложения
lives(zebra, in_water), поэтому обращение завершается неудачно и
Пролог начинает поиск с возвратом другого решения.
6. Когда Турбо Пролог совершает обратный ход, процесс возвращается к
последней позиции, где была помещена точка возврата. В данном случае
последняя точка возврата была поставлена у второй подцели в правиле,
на факте is_a (zebra, ungulate).
7. При достижении точки возврата Турбо Пролог освобождает перемен-
ные, которым были присвоены новые значения после последней точки
возврата, и пытается найти другое решение для обрабатываемого обра-
щения. В данном случае обращение было is_a (Y, ungulate).
8. Tурбо Пролог продолжает спуск по предложениям в поиске другого
соответствующего предложения, начиная с того места, где поиск был
прекращен. Так как в программе больше нет соответствующих предложе-
ний, обращение завершается неудачно, и Турбо Пролог вновь ведет по-
иск с возвратом в попытке решить исходное целевое утверждение.
9. Для теперешней позиции последней точкой возврата является
type(ungulate, animal).
10.Турбо Пролог освобождает переменные, использованные в исходном
обращении, и пытается найти другое решение для обращения type(X,
animal). Поиск начинается после точки возврата. Турбо Пролог находит
соответствие со следующим фактом type в программе
(type(fish,animal)); X связывается с fish, и новая точка возврата
ставится возле этого факта.
11.Теперь Турбо Пролог продвигается вниз, к следующей подцели в пра-
виле; поскольку это уже новое обращение, поиск начинается с вершины
программы для is_a(Y,fish).
12.Турбо Пролог находит соответствие для этого обращения, и Y стано-
вится связанным с herring.
13.Tак как Y теперь связан с herring, следующая подцель, к которой
происходит обращение, суть lives(herring,in_water) Это опять-таки
новое обращение, и поиск начинается с вершины программы.
14.Турбо Пролог исследует каждый факт lives, но не находит соответс-
твия, и подцель не выполняется.
15.Теперь Турбо Пролог возвращается к последней точке возврата is _a
(herring, fish).
16.Переменные, которые были связаны этим сопоставлением, не освобож-
дены. Начиная с того места, где процесс был прекращен, Турбо Пролог
теперь ищет новое решение для обращения is_a(Y, fish).
17. Турбо Пролог находит соответствие со следующим предложением
is_a, Y становится связанным с идентификатором shark.
18.Турбо Пролог опять исследует последнюю подцель, имея переменную
Y, связанную с shark. Он выполняет обращение lives(shark, in_water);
поиск начинается с вершины программы, так как это уже новое обраще-
ние. Он обнаруживает соответствие, и последняя для правила подцель
выполняется.
19.К этому моменту тело правила can_swim(Y) согласовано. Турбо Про-
лог возвращает Y обращению can_swim(What). Tак как What связана с Y,
a Y связан с shark, отныне в целевом утверждении What связана с
shark.
20.Турбо Пролог продолжает процесс с того места в разделе goal, где
он был остановлен, и обращается ко второй подцели в целевом утверж-
дении.
21.Турбо Пролог завершает программу выводом:
A shark can swim.
Программа закончена успешно.
|------------------------------------|
| ПРАВИЛО: can_swim(What) :- | What унифицировано с Y.
| type(X,animal), |
| is_a(What,X), |
| lives(What,in_water). |
|------------------------------------|
|-------------------------------------|
* | ОБРАЩЕНИЕ : type(X,animal) | Х связан с ungulate
: | СООТВЕТСТВИЕ: type(ungulate,animal) |
: |---------------------------------|---|
: |
: v
: |-------------------------------------|
: * | ОБРАЩЕНИЕ : is_a(Y,ungulate) | Y связан с zebra
: : | СООТВЕТСТВИЕ: is_a(zebra,ungulate) |
: : |---------------------------------|---|
: : |
: : v
: : |-----------------------------------|
: : | ОБРАЩЕНИЕ : lives(zebra,in_water) | Не согласуется
: : | НЕУДАЧА : lives(zebra,in_water) |
: : |--|--------------------------------|
: : |
: : |
: : v
: : |-----------------------------------|
: :.| ЕЩЕ РАЗ : is_a(Y,ungulate) | Больше нет фактов,
: | НЕУДАЧА : is_a(Y,ungulate) | соответствующих
: |--|--------------------------------| обращению
: |
: |
: v
: |-------------------------------------|
:.| ЕЩЕ РАЗ : type(X,animal) |Х теперь связан с fish
| СООТВЕТСТВИЕ: type(fish,animal) |
|---------------------------------|---|
|
v
|-----------------------------------|
* | ОБРАЩЕНИЕ : is_a(Y,fish) | Y теперь связан с
: | СООТВЕТСТВИЕ: is_a(herring,fish) | herring
: |---------------------------------|-|
: |
: v
: |-------------------------------------|
: | ОБРАЩЕНИЕ : lives(herring,in_water) | Не согласуется
: | НЕУДАЧА : lives(herring,in_water) |
: |--|----------------------------------|
: |
: |
: v
: |-----------------------------------|
:.| ЕЩЕ РАЗ : is_a(Y,fish) | Теперь Y связан с
| СООТВЕТСТВИЕ: is_a(shark,fish) | shark
|---------------------------------|-|
|
v
|--------------------------------------|
| ОБРАЩЕНИЕ : lives(shark,in_water) | What связано
| СООТВЕТСТВИЕ : lives(zebra,in_water) | с shark
|--------------------------------------|
Рис. 5.1 : Как работает программа can_swim
- Руководство пользователя турбо пролог 2.0.
- Часть 1: Введение в Турбо Пролог 2.0 18
- Часть 2. Изучение турбо пролога 2.0 44
- Глава 3. Основы пролога 44
- Глава 4. Программы турбо пролога 65
- Глава 5. Унификация и поиск с возвратом. 84
- Глава 6. Простые и составные объекты 116
- Глава 7. Повтор и рекурсия 132
- Глава 8. Списки и рекурсия 160
- Глава 9. Внутренняя база данных турбо пролога 180
- Глава 10. Трассировка и отладка 189
- Часть 3. Описание турбо пролога 2.0 203
- Глава 11. Арифметические вычисления и сравнения 203
- Глава 12. Запись, чтение и файлы 215
- Глава 13. Обработка строк в турбо прологе 240
- Глава 14. Окна в ваших программах 249
- Глава 15. Система внешних баз данных 269
- Глава 16. Программирование на системном уровне 298
- Глава 17. Графический интерфейс borland 309
- Глава 18. Примеры программ 347
- Глава 19. Сложные приемы программирования 365
- Введение
- О Прологе
- Для чего может быть использован Турбо Пролог?
- Чем Турбо Пролог отличается от других языков?
- Минимальные требования к системе
- Поддерживаемое оборудование
- О руководствах по Турбо Пролог 2.0
- Том I: Руководство пользователя
- Рекомендуемая литература
- Используемые шрифты
- Торговые марки.
- Как связаться с фирмой Borland.
- Часть 1 введение в турбо пролог 2.0 глава 1. Установка турбо пролога 2.0
- Что хранится на ваших дисках
- Теперь сделаем резервные копии
- Установка Турбо Пролога на вашу систему
- Установка на систему с гибкими магнитными дисками
- Установка на жесткий диск
- Использование данного руководства
- Глава 2. Начало
- Загрузка Турбо Пролога
- Краткое руководство по меню и "горячим" клавишам.
- Главное меню
- Спускающиеся меню
- "Горячие" клавиши и командные клавиши
- "Горячие" клавиши главного меню
- Командные клавиши редактора
- Командные клавиши компиляции
- Стирание текста
- Манипулирование текстовыми блоками
- Ваша первая программа на Турбо Прологе
- Ввод вашей программы в редактор
- Корректирование ввода
- Просмотр в редакторе
- Запуск вашей программы
- Что происходит, когда вы делаете синтаксическую ошибку
- Сохранение вашей программы на диске
- Просмотр файлов на диске
- Трассирование вашей программы
- Пользователям с гибкими магнитными дисками: создание автономных программ.
- Контроль установки системы
- Часть 2. Изучение турбо пролога 2.0 глава 3. Основы пролога
- ПрОграммирование в лоГике
- Предложения: Факты и Правила.
- Факты: То что известно
- Правила: То что вы можете получить из заданных фактов
- Запросы
- Совместное задание фактов, правил и запросов
- Переменные: основные положения
- Упражнения
- Из естественного языка в программы на Прологе
- Упражнения
- Предикаты (связи)
- Переменные (обобщенные предложения)
- Как переменные получают свои значения
- Анонимные переменные
- Цели (запросы)
- Составные цели: Конъюнкция и Дизъюнкция
- Комментарии
- Что такое Сопоставление?
- Глава 4. Программы турбо пролога
- Основные секции программы на Турбо Прологе
- Секция предложений
- Секция предикатов
- Как объявить предикат пользователя
- Имена предикатов
- Аргументы предикатов
- Секция доменов
- Примеры.
- Секция цели
- Подробнее о декларациях и правилах
- Задание типов аргументов при декларации предикатов
- Упражнения
- Арность (размерность)
- Синтаксис правил
- Ключевое слово Пролога "if" и "if" в других языках
- Автоматическое преобразование типов
- Другие секции программы
- Секция базы данных
- Секция констант
- Глобальные секции
- Директивы компилятора
- Директива include
- Директивы trace и shorttrace
- Глава 10 подробно объясняет трассирование, однако еще до того, как
- Глава 5. Унификация и поиск с возвратом.
- Сопоставление и унификация
- Поиск с возвратом.
- Поиск всех решений
- Упражнение на поиск с возвратом.
- Детальный обзор поиска с возвратом.
- Четыре основных принципа поиска с возвратом.
- Поиск с возвратом для внутреннего целевого утверждения
- Управление поиском решений.
- Использование предиката fail.
- Упражнения.
- Прерывание поиска с возвратом: отсечение.
- Как использовать отсечение.
- Предотвращение поиска с возвратом к предыдущей подцели в правиле.
- Предотвращение поиска с возвратом к следующему предложению.
- Детерминизм и отсечение.
- Пример, использующий отсечение
- Предикат not.
- Упражнения.
- Пролог с процедурной точки зрения.
- Как представлять факты и правила в качестве процедур
- Использование правил для условного ветвления (case).
- Представление проверки в правиле.
- Отсечение как goto.
- Возврат вычисленного значения.
- Глава 6. Простые и составные объекты
- Простые объекты данных.
- Переменные как объекты данных.
- Константы как объекты данных.
- Литеры.
- Составные объекты данных и функторы
- Унификация составных объектов.
- Использование знака равенства для унификации составных объектов.
- Рассмотрение нескольких значений как единое целое.
- Примеры использования функторов.
- Пример использования составных объектов.
- Упражнение.
- Объявление доменов составных объектов.
- Запись определений доменов: Обзор.
- Многоуровневые составные объекты.
- Пример, иллюстрирующий структуру предложения.
- Упражнения.
- Определения составных смешанных доменов.
- Аргументы множественных типов.
- Сравнение составных объектов.
- Глава 7. Повтор и рекурсия
- Процесс повторения
- Снова поиск с возвратом
- Упражнение
- Предварительные и последующие операции
- Упражнение
- Использование поиска с возвратом в замкнутых системах
- Упражнения
- Рекурсивные процедуры
- Что же все-таки делает компьютер?
- Преимущества рекурсии
- Оптимизация хвостовой рекурсии
- Как задать хвостовую рекурсию
- Упражение
- Как избежать хвостовой рекурсии
- На помощь приходит команда "cut"
- Использование аргументов в качестве переменных цикла
- Упражнения
- Рекурсивные структуры данных
- Деревья - как типы данных
- Обход дерева
- Создание дерева
- Бинарные поисковые деревья
- Сортировка на основе дерева
- Упражнения
- Глава 8. Списки и рекурсия
- Что такое списки?
- Объявление списков
- Голова и хвост списка
- Работа со списками
- Использование списков
- Печать списков
- Упражнение
- Подсчет элементов списка
- Упражнение
- Хвостовая рекурсия
- Упражнение
- Другой пример - изменения в списках
- Снова о хвостовой рекурсии
- Еще об изменении списков
- Принадлежность к списку
- Упражнение
- Объединение одного списка с другим: декларативное и процедурное программирование
- Рекурсии с процедурной точки зрения
- Упражнение
- Один предикат может иметь несколько вариантов использования
- Упражнение
- Немедленный поиск всех решений
- Составные списки
- Упражнение
- Грамматический разбор списков
- Заключение
- Глава 9. Внутренняя база данных турбо пролога
- Использование внутренней базы данных
- Объявление внутренней базы данных
- Обновление внутренней базы данных
- Занесение фактов во время исполнения
- Удаление фактов во время выполнения программы
- Удаление нескольких фактов сразу
- Считывание новых фактов из файла во время выполнения программы
- Сохранение базы данных с фактами во время работы программы
- Примеры
- Глава 10. Трассировка и отладка
- Синтаксическая проверка
- Трассировка
- Директива трассировки
- Пример использования директивы trace
- Трассировка в режиме оптимизации: shorttrace
- Трассировка указанных предикатов
- Пример использования директивы shorttrace
- Сохранение результатов трассировки
- Предикат trace
- Пример использования предиката trace
- Диалоговое управление трассировкой
- Состояние ( Status )
- Окно Трассировки ( Trace Window )
- Окно Редактора ( Edit Window )
- Предикаты, с особым значением в режиме трассировки
- Упражнение по трассировке
- Директивы компилятора, используемые для отладки
- Директивы check_determ и nondeterm
- Упражнение
- Директива diagnostics
- Директива nowarnings
- Собщения об ошибках во время выполнения программы
- Опции компилятора из меню
- Integer Overflow Check (Проверка целого)
- Stack Check (Проверка стека)
- Часть 3. Описание турбо пролога 2.0 глава 11. Арифметические вычисления и сравнения
- Арифметические выражения
- Операции
- Порядок вычислений
- Функции и предикаты
- Генератор случайных чисел
- Предикат random/1
- Предикат random/2
- Целочисленная и вещественная арифметика
- Равенство и предикат равенства
- Упражнения
- Сравнение символов, строк и идентификаторов
- Символы
- Идентификаторы
- Примеры, демонстрирующие предикат write
- Упражнение
- Предикат writef/*
- Турбо Пролог распознает следующие спецификаторы формата поля f:
- Примеры форматного вывода
- Предикат readln/1
- Предикаты readint/1, readreal/1 и readchar/1
- Предикат readterm/2
- Предикат file_str/2
- Предикат inkey/1
- Предикат keypressed/0
- Предикат unreadchar/1
- Примеры
- Упражнение
- Открытие и закрытие файлов
- Предикат openread/2
- Предикат readdevice/1
- Предикат writedevice/1
- Примеры
- Работа с файлами
- Примеры
- Предикат eof/1
- Предикат flush/1
- Предикат existfile/1
- Предикат deletefile/1
- Предикат renamefile/2
- Предикат disk/1
- Расширение базы данных с помощью файлов
- Работа с фактами, как с термами
- Примеры
- Глава 13. Обработка строк в турбо прологе
- Обработка строк
- Основные предикаты управления строкой
- Frontchar/3
- Fronttoken/3
- Frontstr/4
- Concat/3
- Str_lеn/2
- Str_char/2
- Str_int/2
- Str_real/2
- Upper_lower/2
- Примеры.
- Глава 14. Окна в ваших программах
- Основные операторы управления окном.
- Задание атрибутов экрана дисплея.
- Черно-белый дисплей.
- Цветной дисплей.
- Makewindow/8
- Пример.
- Shiftwindow/1
- Clearwindow/0
- Removewindow/0
- Cursor/2
- Пример.
- Игра в угадывание слов с использованием окон.
- Усовершенствованные предикаты обработки окон.
- Textmode/2
- Makewindow/11
- Existwindow/1
- Gotowindow/1
- Removewindow/2
- Resizewindow/0
- Resizewindow/4
- Пример.
- Framewindow/1
- Framewindow/4
- Colorsetup/1
- Scr_char/3
- Scr_attr/3
- Field_str/4
- Field_attr/4
- Window_str/1
- Window_attr/1
- Простая игра.
- Использование редактора и dir из программы.
- Editmsg/8
- Edit/2 и edit/13
- Аргументы предиката edit.
- Display/1
- Пример доступа к редактору и каталогу.
- Заключение.
- Глава 15. Система внешних баз данных
- Внешние базы данных в Турбо Прологе.
- Обзор: что такое внешние базы данных?
- Соглашения об именовании.
- Селекторы внешних баз данных.
- Домены, связанные с внешними базами данных.
- Указатели базы данных.
- Домен ref.
- Обработка целых баз.
- Db_create/3
- Db_open/3
- Db_copy/3
- Db_openinvalid/3
- Db_flush/1
- Db_close/1
- Db_delete/1
- Db_garbagecollect/1
- Db_btrees/2
- Db_chains/2
- Db_statistics/5
- Обработка цепочек.
- Chain_inserta/5 и chain_insertz/5
- Chain_insertafter/5
- Term_replace/4
- Term_delete/3
- Ref_term/4
- Пример полной программы.
- B-деревья.
- Страницы, порядок и длина ключа.
- Двойные ключи.
- Множественный просмотр.
- Стандартные предикаты для b-деревьев
- Bt_create/5
- Bt_open/3
- Bt_clost/2 и bt_delete/2
- Bt_statistics/8
- Key_insert/4 и key_delete/4
- Key_first/3, key_last/3 и key_search/4
- Key_next/3 и key_prev/3
- Key_current/4
- Пример: Доступ к базе данных через b-деревья
- Программирование внешних баз данных
- Просмотр базы данных
- Вывод содержания базы данных
- Создание защищенной базы данных
- Обновление базы данных
- Использование внутреннего указателя b-дерева.
- Использование key-search с дублируемыми ключами
- Изменение структуры базы данных.
- Глава 16. Программирование на системном уровне
- Доступ к операционной системе
- System/1
- System/3
- Пример:
- Envsymbol/2
- Date/3 и time/4
- Пример.
- Comline/1
- Операции на уровне бит
- Bitnot/2
- Bitand/3
- Bitor/3
- Bitxor/3
- Bitleft/3
- Bitright/3
- Упражнение:
- Доступ к аппаратуре: поддержка низкого уровня.
- Bios/3 и bios/4
- Ptr_dword/3
- Membyte/3 и memword/3
- Port_byte/2
- Примеры:
- Глава 17. Графический интерфейс borland
- Что такое bgi?
- Несколько слов о видео режимах.
- Несколько слов о полях вывода (графических окнах).
- Файл grapdecl.Pro
- Как начинать
- Инициализация и выключение системы bgi
- Предикаты
- Initgraph/5
- Detectgraph/2
- Getgraphmode/1
- Getmaxmode/1
- Graphdefaults/0
- Closegraph/0
- Restorecrtmode/0
- Текущая позиция (тп)
- Getlinesettings/3
- Окружности
- Circle/3
- Getarccoords/6
- Прямоугольники, многоугольники и полосы.
- Rectangle/4
- Bar3d/6
- Drawpoly/1
- Fillpoly/1
- Setfillpattern/2
- Getfillpattern
- Floodfill/3
- Пример заполнения области.
- Управление цветом.
- Палитра
- Цвет фона и цвет рисования.
- Управление цветом в cga.
- Низкое разрешение cga.
- Высокое разрешение cga.
- Предикаты палитры cga.
- Управление цветом в ega.
- Управление цветом в дисплеях системы rgb.
- Предикаты
- Шрифты: загружать или компоновать
- Предикаты
- Settstyle/3
- Setusercharsize/4
- Пример использования различных видов текста
- Экраны и поля вывода.
- Предикаты.
- Setviewport/5
- Getviesettings/5
- Управление пикселами и образами
- Предикаты
- Ограничения на использование драйвера 8514.
- Использование bgi
- Графические драйверы и символьные шрифты.
- Программа, загружающая драйверы
- Построение и запуск загружаемых .Exe файлов
- Сообщения bgi об ошибках
- Новые драйверы bgi
- Задача выбора кратчайшего пути
- Приключения в опасной пещере
- Моделирование элементов аппаратуры
- Ханойские башни.
- Деление слов на слоги
- Проблема расстановки n ферзей
- Использование клавиатуры.
- Чтение и распознавание клавиш
- Простой редактор полей
- Применение предиката inkey
- Глава 19. Сложные приемы программирования
- Ошибки, исключительные ситуации и прерывания
- Обработка исключительных ситуаций, связанных с ошибками
- Exit/o и exit/1
- Errorsg/4
- Обработка ошибок при чтении термов
- Consulterror/3
- Readtermerror/2
- Управление режимом break
- Break/1
- Breakpressed/0
- Углубленный контроль ошибок в .Exe файлах
- Criticalerror/4
- Fileerror/2
- Анализ потока параметров
- Контроль потока параметров
- Ссылочные типы
- Объявление ссылочных типов
- Ссылочные типы и массив trail
- Применение ссылочного типа
- Динамическое отсечение
- Примеры
- Применение ссылочных типов при реализации бинарных деревьев
- Сортировка с помощью ссылочных типов
- Стиль программирования
- Определение1
- Определение 2
- Определение 3.
- Использование предиката fail
- Детерминизм и отсечение