Так как большинство описанных вариантов заданий предполагает проведение в программе большого перебора при поиске решения, то может возникнуть переполнение памяти, отведенной под стек или кучу. Часто конечной причиной переполнения является неэффективность организации перебора в программе, что требует ее соответствующей перестройки.
Используемый пролог-интерпретатором стек сохраняет, во-первых, всю информацию, необходимую для запоминания точек бэктрекинга, а, во-вторых, информацию, необходимую для выполнения функциональных вызовов и рекурсии (размер стека линейно растет с ростом количества точек бэктрекинга и рекурсивных обращений). Соответственно возможны две основные причины переполнения стека.
В первом случае переполнение стека происходит из-за возникновения неоправданно большого количества точек бэктрекинга. Часто, используя отсечение для сокращения ненужных точек бэктрекинга, можно избежать такого переполнения стека.
Во втором случае переполнение возникает из-за большого количества рекурсивных обращений. Сократить число рекурсивных обращений может преобразование пролог-программы в так называемую хвостовую рекурсию, поскольку для такого вида рекурсии пролог-интерпретатором может быть использован метод, называемый оптимизацией остатка рекурсии [Стерлинг, с.132-133].
Основная идея такой оптимизации состоит в том, что оптимизируемая рекурсивная пролог-процедура выполняется так, как если бы она была итерационной, т.е. без стека. Метод применим далеко не ко всякой рекурсивной пролог-процедуре; чтобы применить его при выполнении предложения
А:- В1, В2,..., В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.
СОДЕРЖАНИЕ
