Рекурсивные вычисления в Пролог-программе

Пример.

Переменные в Пролог-программе

Пример.

name (man, "Петр")

Основными называются термы, не содержащие переменных, т.е. факты. Термы, содержащие переменные называются неосновными.

Сложный терм является в Пролог-программе или функтором, или оператором. Определение сложного терма в программе содержит имя, представляющее собой атом, и совокупность аргументов, которые в свою очередь также могут быть простыми и сложными термами.

Переменные в Пролог-программе являются не местом в памяти, а реальным объектом. Место действия одной переменной – одна резольвента. При осуществлении механизма возврата значения всех переменных в резольвенте, через которые осуществляется возврат, очищаются.

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

domains /* раздел данных */

тип фигуры = symbol

выражение для площади = string

predicates

площадь (тип фигуры, выражение для площади)

фигура (тип фигуры, выражение для площади)

goal

площадь (круг, Z).

clauses

площадь (X, Y):- фигура (X, Y), write ("X=", X, "Y=", Y).

фигура (квадрат, "сторона * сторона").

фигура (круг, "pi * радиус * радиус").

фигура (треугольник, "1/2 * основание * высота").

фигура (__, "неизвестно").

Наличие символа «__» означает использование фиктивной переменной. В рассмотренном примере с ее помощью реализован квантор общности.

В разделе данных domains объявлены типы данных пользователя («тип фигуры» и «выражение для площади»), а также указано, что «тип фигуры» эквивалентен стандартному символьному типу (symbol), а тип «выражение для площади» – стандартному строковому типу (string).

Рекурсивное описание правила содержит в своем теле ссылку на заголовок этого же правила. Возможны следующие три варианта рекурсивных правил:

· правая рекурсия − pr 1():- pr 11(), pr 12(),..., pr 1N(), pr 1().

· левая рекурсия − pr 1():- pr 1(1), pr 21(), pr 22(),..., pr 2M().

· обобщенная рекурсия −
pr 1():- pr 11(), pr 12(),..., pr 1N(), pr 1(), pr 21(), pr 22(), …, pr 2M().

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

· заданием в программе альтернативного правила или факта pr 1(), не содержащего рекурсии (выход происходит при успешном выполнении этого правила);

· формированием условия выхода одним из предикатов pr 11(), pr 12()…, - выход происходит если в процессе выполнения правилах хотя бы один из предикатов завершается неуспехом.

Предикаты pr 21(), …, pr 2M() не влияют на выполнение рекурсии, а выполняются только после выхода из нее. Эти предикаты получают значения переменных из стека, в который они помещаются на время выполнения рекурсии. Производимые при этом вычисления называют хвостовыми вычислениями. Идеи реализации рекурсивных вычислений представлены в примере и в табл. 3.1, составленной на основе соответствующей Пролог-программы.

Дата добавления: 2014-12-29