Методические указания. Так как большинство описанных вариантов заданий предполагает проведение в программе большого перебора при поиске решения

 

Так как большинство описанных вариантов заданий предполагает проведение в программе большого перебора при поиске решения, то может возникнуть переполнение памяти, отведенной под стек или кучу. Часто конечной причиной переполнения является неэффективность организации перебора в программе, что требует ее соответствующей перестройки.

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

В первом случае переполнение стека происходит из-за возникновения неоправданно большого количества точек бэктрекинга. Часто, используя отсечение для сокращения ненужных точек бэктрекинга, можно избежать такого переполнения стека.

Во втором случае переполнение возникает из-за большого количества рекурсивных обращений. Сократить число рекурсивных обращений может преобразование пролог-программы в так называемую хвостовую рекурсию, поскольку для такого вида рекурсии пролог-интерпретатором может быть использован метод, называемый оптимизацией остатка рекурсии [Стерлинг, с.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.

 

СОДЕРЖАНИЕ