Е.И. Большакова - Практикум на языке программирования Пролог (1109888), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Во втором случае переполнение возникает из-за большого количества рекурсивных обращений. Сократить число рекурсивных обращений может преобразование пролог-программы в так называемую хвостовую рекурсию, поскольку для такого вида рекурсии пролог-интерпретатором может быть использован метод, называемый оптимизацией остатка рекурсии [Стерлинг, с.132-133].

Основная идея такой оптимизации состоит в том, что оптимизируемая рекурсивная пролог-процедура выполняется так, как если бы она была итерационной, т.е. без стека. Метод применим далеко не ко всякой рекурсивной пролог-процедуре; чтобы применить его при выполнении предложения

А:- В₁, В₂, ..., В_n.

пролог-процедуры А необходимо соблюдение следующих условий :

1. В указанном предложении рекурсивное обращение единственно и стоит в конце правой части, т.е. является последней целью правой части: В_n=А (отсюда произошло название: хвостовая рекурсия).

2. С момента входа в пролог-процедуру до вычисления этого рекурсивного обращения не осталось или не возникало точек бектрекинга, т.е. вычисление конъюнкции всех целей В_i , кроме последней цели В_n, было детерминированным и не осталось иных применимых предложений процедуры А.

Таким образом, при возникновении в ходе вычисления пролог-программы переполнения стека часто полезно провести перестройку рекурсивных процедур пролог-программы (если, конечно, это возможно). Такая перестройка означает перестановку рекурсивных обращений в конец пролог-предложений и вставку перед ними отсечения - тем самым становятся выполнены условия оптимизации.

В практике программирования на языке Пролог иногда необходимы:

• глобальные переменные;

• циклы, управляемые неуспехом.

Глобальные переменные моделируются в Прологе с помощью базы фактов и предикатов assert и retract. Например, запись предикатом assert факта x(Value) может трактоваться как присвоение переменной x значения Value [Стерлинг, с.158].

Циклы, управляемые неуспехом, получили свое название потому, что для порождения шагов цикла используется не рекурсия, а механизм бектрекинга, включаемый предикатом fail [Стерлинг, с.158]. Рассмотрим, к примеру, простой рекурсивный цикл для ввода и вывода символов до «звездочки» (предикат begin служит для входа в цикл):

begin : - readchar (C), while (С).

while (C): - C=’*’.

while (C): - write (C), readchar (Z), while (Z).

Такой цикл можно запрограммировать иначе, если использовать специальный незавершаюшийся предикат repeat без аргументов, который порождает при бектрекинге бесконечные вычисления:

repeat.

repeat :- repeat.

Цикл будет выглядеть так:

begin (X): - repeat, readchar (C), while (C), !.

while (C): - C=’*’ , !.

while (C): - write (C) , fail.

Сам предикат while вычисляется успешно лишь в момент выхода из цикла (применение первого предложения). Отсечение в первом предложении процедуры while предохраняет от незавершающихся вычислений (оно отсекает точку бектрекига, связанную с предикатом while), а отсечение в процедуре begin предотвращает от повторного входа в цикл repeat (оно отсекает точку бектрекинга, возникающую при выполнении цели repeat).

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

ЛИТЕРАТУРА

[Стерлинг] Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог - М.: Мир, 1990.

[Братко] Братко И. Программирование на языке Пролог для искусственого интеллекта - М.: Мир, 1990.

[Клоксин] Клоксин У., Меллиш К. Программирование на языке Пролог - М.: Мир, 1987.

[Ин] Ин Ц., Соломон Д. Использование Турбо-Пролога - М.: Мир, 1993.

[Набебин] Набебин А. А. Логика и Пролог в дискретной математике -

М.: Издательство МЭИ, 1996.

[Уэзерелл] Уэзерелл Ч. Этюды для программистов - М.: Мир, 1982.

СОДЕРЖАНИЕ

Задание 1. Основы программирования на языке Пролог............... 3

Постановка задачи.................................................................. 3

Требования к программе........................................................ 5

Методические указания.......................................................... 7

Задание 2. Пролог для задач искусственного интеллекта............. 12

Постановка задачи.................................................................. 12

Требования к программе........................................................ 12

Варианты задания................................................................... 12

Методические указания.......................................................... 22

Литература.................................................................................... 24

24

Характеристики

Список файлов книги