Лебедева Н.С. Методическое пособие по программированию на Turbo Prolog
Подождите немного. Документ загружается.
21
point – функтор для точки А;
segment – функтор для отрезка АВ;
tringle – функтор для треугольника СDE;
segment(point(Х1,4), point(Х2,4))
– структура,
представляющая любой отрезок на прямой Y = 4.
Две структуры сопоставимы, если имеют одинаковый главный
функтор и все их соответствующие аргументы сопоставимы.
point(1,1,3)
point(1,2)
Здесь имеем разные структуры, так как эти структуры имеют
разную арность.
22
3. Программирование повторяющихся операций
3.1. Повторение и откат
В программах на Турбо-Прологе повторяющиеся операции
выполняются при помощи правил, которые используют откат и
рекурсию. Правила отката и рекурсии имеют различные алгоритмы и
каждый из них имеет свои преимущества.
Цель программы на Турбо-Прологе может содержать одну или
несколько подцелей. Подцель – это либо факт, либо правило. Факт в
правиле сопоставляется с фактом в программе. Если сопоставление
успешно, то подцель, содержащая данный факт будет успешна. Правило,
состоящее из подцелей будет успешно, если успешны все подцели. Если
подцель правила имеет неуспех, то Турбо-Пролог выполняет откат,
чтобы достичь успеха.
Внутренние унификационные подпрограммы Турбо-Пролога
используют откат для нахождения дополнительных фактов и правил,
необходимых для вычисления текущей подцели, если очередная
попытка вычислить подцель оказалась неудачной. Откат используется
для того, чтобы попробовать новые пути к решению подцели. Прежде,
чем попробовать один из возможных путей решения подцели, Турбо-
Пролог помещает в программу ''указатель''. Указатель определяет точку,
в которую может быть выполнен откат, если текущая попытка была
неуспешной.
Подцели правила вычисляются слева направо, и по мере достижения
подцелей указатели отката расставляются во всех точках, которые могут
привести к решению. Если некоторая подцель оказывается неуспешной, то
происходит откат влево к ближайшему указателю отката. От этого
указателя начинается новая попытка найти решение для неуспешной
подцели. В случае, если решение не будет найдено, т. е. подцель будет
неуспешной, переход к следующей подцели не происходит. Цель,
содержащая неуспешную подцель, будет неуспешной.
Рассмотрим механизм отката на следующем примере:
likes(
'
Nina
'
, pears)
likes(
'
Nina
'
, apples)
likes(
'
Nina
'
, banana)
likes(
'
Katja
'
, orange)
likes(
'
Katja
'
, apples)
likes(
'
Katja
'
, banana)
23
Имеем ряд фактов для отношения likes и имеем целевое
утверждение:
likes(
'
Nina
'
, Х), likes(
'
Katja
'
, Х).
Необходимо определить, что одновременно любят Nina и Katja.
Цель состоит из двух подцелей. Каждая подцель содержит переменную
Х. Необходимо найти значение Х, удовлетворяющее обеим подцелям.
Чтобы вычислить первую подцель likes('Nina', Х) Турбо-Пролог
выполняет следующие действия:
1) поиск в заданной базе данных предиката likes;
2) проверка арности (количества объектов предиката) предиката,
заданного в подцели, с арностью предиката likes в базе данных;
в случае совпадения выполняется следующее действие;
3) сопоставление предикатов по правилу ''сопоставление термов''.
Первый факт из базы данных сопоставим с первой подцелью,
переменная Х получает значение pears и подцель успешно вычисляется.
Значение переменной Х распространяется на все предложение, содержа-
щее целевое утверждение, поэтому имеем likes('Katja', pears). Имеются в
базе данных другие факты для предиката likes, которые могут быть
использованы для вычисления первой подцели. Поэтому
устанавливается указатель отката на предикат likes('Nina', apples). С
этого указателя могут быть продолжены вычисления первой подцели,
если произойдет неуспешное вычисление второй подцели likes('Katja', Х)
со значением Х, равным pears.
Первая подцель likes('Nina', Х) вычислена успешно, необходимо
вычислить вторую подцель likes('Katja', pears), которая представляет собой
факт. Внутренние унификационные подпрограммы просматривают базу
данных в поисках факта, сопоставимого со второй подцелью.
Сопоставимых фактов нет, следовательно, вторая подцель
likes('Katja', pears) неуспешна. После сопоставления переменная Х
становится свободной, Турбо-Пролог возвращается в точку, которая
содержит указатель отката likes('Nina', apples), и начинает вычислять
первую подцель likes('Nina', Х). Факт из базы данных likes('Nina', apples)
сопоставим с первой подцелью likes('Nina', Х). Переменная Х получает
значение apples. Устанавливается указатель отката на предикат likes('Nina',
banana). Первая подцель likes('Nina', Х) успешно выполнена, вычисляется
вторая подцель likes('Katja', apples). Вторая подцель успешно вычисляется,
так как в базе данных имеется факт likes('Katja', apples). Исходное целевое
утверждение, состоящее из двух успешно вычисленных подцелей, также
успешно вычислено. Если целевое утверждение представляет внутреннюю
цель, то процесс вычисления останавливается после первого успешного
24
вычисления. При наличии внешней цели Турбо-Пролог будет продолжать
вычисления до тех пор, пока не будут найдены все решения для данной
цели (если такие имеются).
Механизм отката представляет процесс, автоматически
инициируемый внутренними унификационными подпрограммами
Турбо-Пролога. Повторами, которые реализуются откатами,
можно управлять при помощи встроенных предикатов:
fail(неудача)
cut(отсечение)
Рассмотрим два способа реализации повторов:
1 метод отката после неудачи (ОПН);
2 метод отсечения и отката (ОО).
3.2. Метод отката после неудачи
Метод отката после неудачи использует предикат fail для управле-
ния вычислениями внутренней цели при поиске всех возможных ее
решений. Выполнение предиката fail всегда неуспешно. Использую пре-
дикат fail можно организовать повтор вычислений для внутренней цели.
Рассмотрим как работает программа, которая печатает список
городов.
Пример 3.2.1.
domains
name = symbol
predicates
cities(name)
print_cities
goal
write(“Города Латвии:”), nl, print_cities.
clauses
cities(
'
Рига
'
).
cities(
'
Валмиера
'
).
cities(
'
Даугавпилс
'
).
............................
print_cities: – cities(X),
write(X),
nl,
fail.
print_cities.
Предикат fail делает вычисление правила print_cities неуспешным,
внутренние унификационные подпрограммы выполняют откат к факту
cities(
'
Валмиера
'
)
и процесс печати повторяется до тех пор, пока не будут
25
напечатаны все города. После просмотра всех фактов и неуспешности
правила print_cities алгоритмы поиска приведут к следующему варианту
этого правила, который является простым фактом и приводит к
успешному завершению программы.
Данная программа показывает, что ОПН позволяет извлекать данные
из каждого утверждения базы данных, так как они удовлетворяют цели.
Если подцели правила невозможно выполнить, т. е. какя-либо подцель
будет неуспешна сама по себе, предикат fail не нужен. Предикат fail
включается в правило для того, чтобы вызвать откат, если подцели
правила будут выполнены и все правило окажется успешным.
3.3. Метод отсечения и отката
Метод отсечения и отката позволяет извлекать данные только из
определенных фактов базы данных. Для того, чтобы извлекать данные,
удовлетворяющие некоторым условиям, необходимо иметь средства
управления откатом. Для этих целей используется предикат cut(!) –
предикат отсечения. Вычисление предиката cut всегда успешно.
Предикат cut заставляет внутренние унификационные подпрограммы
''забыть'' все указатели отката, установленные во время попыток
вычислить текущую подцель. Таким образом, устанавливается барьер
для всех других вариантов фактов и правил, встретившихся до
предиката cut. Предикат cut “закрепляет” все решения подцелей,
стоящих в предложении до него.
Подцели, стоящие после предиката cut могут создать новые
указатели отката для поиска новых решений. Область действия преди-
ката cut на них не распространяется.
Рассмотрим правило
р: – А, В, С
правило р состоит из подцелей А, В, С. Подцели выполняются
последовательно одна за другой, а в случае неудачи происходит откат.
Изменим правило:
р: – А, В, !, С
Отсечение повлияет на вычисление правила р следующим образом:
перебор решений будет для подцели А и В, в случае неуспеха подцели С,
альтернативные решения для А и В не рассматриваются.
26
Поставим отсечение в правило программы (п. 3.2.):
print_cities: – cities(X),
write(X), !.
Напечатан будет только один город – Рига, так как все указатели,
поставленные системой “забыты”.
В рассмотренной программе (п. 3.2.) изменим целевое утверждение:
печатаем не весь список городов, а часть списка, где последним городом
будет Даугавпилс. Для этого необходимо изменить правило print_cities:
print_cities: – cities(X),
write(X),
nl,
Х=
'
Даугавпилс
'
!.
Подцель Х = 'Даугавпилс' дает откаты и выборку из базы данных
всех городов списка до Даугавпилса. Когда указанная выше подцель
будет успешна, работа переходит к предикату отсечения cut, который и
прекращает работу правила print_cities.
При вычислении цели Турбо-Пролог проводит перебор вариантов
решения, в соответствии с установленным порядком подцелей. Иногда
для повышения эффективности выполнения программы, требуется
вмешаться в перебор, ограничить его, исключить некоторые цели.
Пример 3.3.1.
/*Определить максимальное число из двух заданных чисел*/
predicates
max(real, real, real) /*Первые два объекта
определяют заданные
числа, третий объект–
максимальное число*/
goal
write(
''
Введите числа
''
), nl, readreal(X),
readreal(Y), max(X, Y, M)
clauses
max(X, Y, X): – X >= Y.
max(X, Y, Y): – X < Y.
Эти два правила являются взаимно исключающимися. Если первое
правило успешно, то второе обязательно неуспешно. Если неуспешно
первое правило, второе правило обязательно успешно. Поэтому нужно
использовать предикат отсечения cut.
max(X, Y, X): – X >= Y, !.
max(X, Y, Y).
27
3.4. Рекурсия
Рекурсия – один из фундаментальных приемов программирования
на Турбо-Прологе. Правило называется рекурсивным, если содержит
само себя в качестве компоненты. Правила, выполняющие рекурсию,
используют самовызов. Для управления рекурсией используется условие
выхода. При рекурсивном вызове новые копии используемых значений
переменных помещаются в стек. Стек – область памяти, которая
используется для передачи значений переменных между правилами. В
стеке данные хранятся до тех пор, пока правило не завершится успешно
или нет. В случае отсутствия условия выхода из рекурсии возникает
бесконечная рекурсия, непрерывно растет число значений переменных,
помещаемых в стек. Возникает переполнение стека и в результате могут
быть утерянными необходимые значения переменных.
Если рекурсивное правило не генерирует указателей отката и
последняя подцель правила является вызовом самого правила, то Турбо-
Пролог устранит дополнительные расходы, вызываемые рекурсией. Этот
процесс называется устранением хвостовой рекурсии.
Рекурсия позволяет в Турбо-Прологе удобно выполнять сложные
алгоритмы обработки данных, особенно для работы со списками и
другими структурами, с которыми практически нет других способов
работы.
Пример 3.4.1.
/*Рекурсивное правило*/
write_char: – /*ввод и печать символов*/
write(
''
Введите символ
''
),
readchar(X),
X <>
''
*
''
/*признак конца ввода–
''
*
''
*/
write(X), nl,
write_char.
Наиболее общая структура рекурсивного правила может быть
представлена в следующем виде:
<имя правила рекурсии>: –
<список предикатов>, (1)
<предикат условия выхода>, (2)
<список предикатов>, (3)
<имя правила рекурсии>, (4)
<список предикатов>. (5)
Данное правило рекурсии имеет пять компонент.
28
Первая компонента – группа предикатов выполняется не влияя на
рекурсию (кроме предиката отсечения, который исключает построение
стека для хранения значений входных аргументов правила).
Вторая компонента – обычно из одного предиката для проверки
условия окончания рекурсии.
Третья компонента – группа предикатов выполняется не влияя на
рекурсию.
Четвертая компонента – имя самого рекурсивного правила,
вызывая его повторно. При этом системой Турбо-Пролога предусмот-
рено заполнение стека памяти (если нет отсечения), где хранятся
значения переменных каждого нового вхождения рекурсивного правила
в само себя (хвост рекурсии).
Пятая компонента – группа предикатов берет значения переменных,
помещенные в стек во время выполнения рекурсии, т. е. после завершения
рекурсии значения из стека последовательно используются этими
предикатами как бы разворачивая ее в обратную сторону.
Правила, построенные данным образом являются обобщенными
правилами рекурсии. Если условие выхода из рекурсии содержится не в
самом рекурсивном правиле, то называется базовым состоянием рекурсии.
Пример 3.4.2.
/*Программа: печать элементов натурального ряда чисел длинной 10 и
нахождение суммы данного ряда*/
domains
number, sum = integer
predicates
write_number(number)
write_sum(number, sum)
goal
write(
''
Элементы натурального ряда чисел:
''
), nl,
write_number(1),
write_sum(10, Sum),
write(
''
S(10)=
''
, Sum), nl.
clauses
write_number(11).
write_number(Number): –
Number < 11,
write(Number), nl,
Next_number = Number + 1,
write_number(Next_number).
write_sum(1, 1).
write_sum(Number, Sum): –
Number > 0,
Next_number = Number – 1,
write_sum(Next_number, Partial_sum),
29
Sum = Number + Partial_sum.
Программа состоит из двух процедур.
Первая процедура для предиката write_number состоит из факта
write_number(11), который называется базовым состоянием рекурсии, и
рекурсивного правила. Условием выхода из рекурсии является значение
переменной Number равное 11.
Печать элементов натурального ряда происходит при выполнении
рекурсии.
Вторая процедура для предиката write_sum состоит из факта
write_sum(1,1), который называется базовым состоянием рекурсии, и
рекурсивного правила. Подцель Number > 0 рекурсивного правила
является условием выполнения рекурсии.
Переменная Partial_sum (частичная сумма) в начале работы
процедуры является неозначенной переменной, она получает значение
равное 1, когда переменная Next_number станет равной 1, т. е. успешно
сопоставится факт write_sum(1, 1). Рекурсивные вызовы закончены, т. к.
переменная Number равна 0, начинает выполнятся подцель
Sum = Number + Partial_sum.
В процессе работы данной процедуры был создан стек, содержащий
все промежуточные значения переменной Number. Теперь эти значения
извлекаются из стека и переменная Sum становится означенной
переменной.
3.5. Метод повтора, определяемый пользователем
Метод повтора, определяемый пользователем (МП) использует
откат и рекурсию. Откат в данном методе выполняется с использова-
нием предиката без аргументов, который определяет пользователь.
Предикат необходимо описать в разделе predicates, а в разделе clauses
необходимо написать процедуру, содержащую факт и рекурсивное
правило. Например, рассмотрим предикат repeat.
predicates
repeat
clauses
repeat.
repeat: –
repeat. /*правило повтора*/
Процедура состоит из факта (repeat), который является всегда
истинным, и рекурсивного правила. Выполнение рекурсивного правила
всегда будет успешным, т. к. для него сразу находится успешный факт
30
repeat. Указатель отката устанавливается на факт (repeat). Так как
правило repeat рекурсивно, то внутренние унификационные подпро-
граммы будут искать много решений, которые имеются при откате. Из-
за отсутствия аргументов у правила repeat их значения не надо заносить
в стек и, следовательно, нет затрат памяти и времени. Правило repeat
удобно использовать в качестве компоненты других правил.
Рассмотрим пример программы, в которой использованы
предикаты fail и cut и метод повтора, определяемый пользователем.
Пример 3.5.1.
/*Программа печатает любые символы, '*' – конец ввода*/
predicates
write_char
repeat
check(char)
goal
write_char.
clauses
repeat.
repeat: – repeat.
write_char: –
repear,
write(
''
Введите символ
''
), nl,
readchar(X),
write(X), nl,
check(X), !.
check(*):– nl, write(
''
Конец работы
''
).
check(_):– fail.
Утверждение repeat в правиле write_char вызывает повторное
выполнение всех следующих за ним компонент, так как в случае неуспеха
правила check идет возврат к указателю, который стоит около него.
Предикат неудачи fail используется для неуспешного завершения правила
check (при вводе любого символа, кроме *). Предикат отсечения cut служит
для прекращения откатов, если введен признак конца ввода – '*'.