Язык логического программирования Visual Prolog (стр. 7 из 9)

owns (symbol, symbol)

Второй элемент более не является объектом типа symbol. Вместо этого вы можете дать новое определение этого предиката

owns(name, articles)

Доменarticles вразделеdomains можноописатьтак

domains

articles = book(title, author); horse(name)

Точка с запятой читается как "или" В этом случае возможны два варианта книга будет определяться своим заглавием и автором, а лошадь будет распознаваться своим именем Домены title, author и name имеют стандартный тип symbol.

К определению домена легко могут быть добавлены другие варианты.

10. Многоуровневые составные объекты

VisualProlog позволяет конструировать составные объекты на нескольких уровнях. Например:

domains

articles = book(title, author);%Первыйуровень

author= author(first_name, last_name) %Второйуровень

title, first_name, last_name = symbol%Третийуровень

При использовании составных объектов со многими уровнями часто помогает такое "дерево" (рис. 7):

Рис. 7. Дерево многоуровневого составного объекта

Повтор и рекурсия

Компьютеры способны повторять одно и то же действие снова и снова, VisualProlog может выражать повторение как в процедурах, так и в структурах данных. Идея повторяющихся структур данных может показаться странной, но Пролог позволяет создавать структуры данных, размер которых не известен во время создания.

11. Процесс повторения

Программисты на языках Pascal, Basic или С, которые начинают использовать VisualProlog, часто испытывают разочарование, обнаружив, что язык не имеет конструкций for, whileили repeat. В Прологе не существует прямого способа выражения повтора. Пролог обеспечивает только два вида повторения

· откат, с помощью которого осуществляется поиск многих решений в одном запросе,

· и рекурсию, в которой процедура вызывает сама себя.

Однако этот недостаток не снижает мощи Пролога. Фактически, VisualProlog распознает специальный случай рекурсии — хвостовую рекурсию — и компилирует ее в оптимизированную итерационную петлю. Это означает, что хотя программная логика и выражается рекурсивно, скомпилированный код так же эффективен, как если бы программа была написана на Pascal или Basic.

Использование поиска с возвратом для организации повторов

Когда выполняется процедура поиска с возвратом (откат), происходит поиск другого решения целевого утверждения. Это осуществляется путем возврата к последней из проверенных подцелей, имеющей альтернативное решение, использования следующей альтернативы этой подцели и новой попытки движения вперед (см. пример ch06e01). Очень часто для этого используется директива fail.

predicates

country(symbol)

print_countries

clauses

country("England").

country("France").

country("Germany").

country("Denmark").

print_countries:-

country(X),

write(X),% записатьзначениеХ

nl,% начать новую строку

fail.

print_countries.

goal

print__countnes.

Рис. 8. Программа ch06e01.pro

Предварительные и последующие операции

Отметим, что программа, которая находит решения для целевого утверждения, может выполнять какие-либо предварительные или завершающие операции. Например, в нашем примере программа могла бы:

1. Напечатать

Some delightful places to live are... (Некоторые восхитительные места для проживания...).

2. Напечатать все решения для country (X).

3. Завершить печать фразой Andmaybeothers (Могут быть и другие).

Заметьте, что print_countries, определенное в предыдущем примере, уже содержит предложение вывести на печать все решения country (X) и отпечатать завершающее сообщение.

Первое предложение для print_countries соответствует шагу 2 и выводит на печать все решения. Его второе предложение соответствует шагу 3 и просто успешно завершает целевое утверждение (потому что первое предложение всегда в режиме fail — "неудачное завершение").

Можно было бы изменить второе предложение в программе ch06e01.pro.

print_countnes :-

write("And maybe others."), nl.

которое выполнило бы шаг 3, как указано.

А что можно сказать о шаге 1? В нем нет смысла, когда print_countnes содержал только 2 предложения. Но в предикате может быть и три предложения:

print_countries :-

write("Some delightful places to live are"), nl,

fail.

pnnt_countnes :-

country(X),

write(X),nl,

fail.

print_countries :-

write("And maybe others."), nl.

Наличие fail в первом предложении важно, поскольку он обеспечивает после выполнения первого предложения возврат и переход ко второму предложению Кроме того, это важно, потому что предикаты write и nl не образуют альтернатив Строго говоря, первое предложение проверяет все возможные решения перед тем, как завершиться неуспехом.

Такая структура из трех предложений более удобна по сравнению с общепринятым подходом.

Использование отката с петлями

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

repeat

repeat - repeat

Этот прием демонстрирует создание структуры управления Пролога (см листинг на рис. 2.), которая порождает бесконечное множество решений. Цель предиката repeat — допустить бесконечность поиска с возвратом (бесконечное количество откатов)

/* Использование repeat для сохранения введенных символов и печатать их до тех пор, пока пользователь не нажмет Enter (Ввод)*/

predicates

repeat

typewriter

clauses

repeat.

repeat -repeat.

typewriter :-

repeat,

readchar(C),% Читать символ, его значение присвоить С

write(С),

С = '\r',% Символ возврат каретки (Enter)? или неуспех

goal

typewriter (), nl.

Рис. 9. Листинг 13.2. Программа ch06e02.pro

Программа ch06e02 pro показывает, как работает repeat Правило typewriter - описывает процесс приема символов с клавиатуры и отображения их на экране, пока пользователь не нажмет клавишу <Enter> (<Return>)

Правило typewriter работает следующим образом

1 Выполняет repeat (который ничего не делает, но ставит точку отката).

2 Присваивает переменной с значение символа.

3 Отображает С.

4 Проверяет, соответствует ли с коду возврата каретки.

5 Если соответствует, то — завершение. Если нет — возвращается к точке отката и ищет альтернативы, так как ни write, ни readchar не являются альтернативами,

12. Рекурсивные процедуры

Понятие рекурсии

Одним из способов организации повторений — рекурсия. Рекурсивная процедура — это процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы запоминания результатов ее выполнения, потому что любые вычисленные значения можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого предиката.

Логика рекурсии проста для осуществления. Представьте себе ЭВМ, способную "понять":

Найти факториал числа N:

Если N равно 1, то факториал равен 1

Иначе найти факториал N-1 и умножить его на N.

Этот подход означает следующее:

первое («закручиваете» стек), чтобы найти факториал 3, вы должны найти факториал 2, а чтобы найти факториал 2, вы должны вычислить факториал 1. факториал 1 ищется без обращения к другим факториалам, т.к. он равен 1, поэтому повторения не начнутся.

второе («раскручиваете» стек), если у вас есть факториал 1, то умножаете его на 2, чтобы получить факториал 2, а затем умножаете полученное на 3, чтобы получить факториал 3.

Информация хранится в области памяти, называемой стековым фреймом (stackframe) или просто стеком (stack), который создается каждый раз при вызове правила. Когда выполнение правила завершается, занятая его стековым фреймом память освобождается (если это не недетерминированный откат), и выполнение продолжается в стековом фрейме правила-родителя.

Преимущества рекурсии

Рекурсия имеет три основных преимущества:

· она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом;

· она логически проще метода итерации;

· она широко используется в обработке списков.

Рекурсия — хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Например, поиск в дереве (дерево состоит из более мелких деревьев) и рекурсивная сортировка (для сортировки списка, он разделяется на части, часть сортируются и затем объединяются вместе).

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

Пример рекурсивного определения правил

Давайте добавим к программе о родственных связях еще одно отношение - предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет

определять непосредственных (ближайших) предков, а второе - отдаленных. Будем говорить, что некоторый X является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных между собой отношением родитель-ребенок, как показано на рис.1.. В нашем примере на рис. 1. Том - ближайший предок Лиз и отдаленный предок Пат.

Рис. 10. Пример отношения предок:(а) X - ближайший предок Z; (b) X - отдаленный предок Z.

Первое правило простое и его можно сформулировать так:

Для всех X и Z,

X - предок Z, если X - родитель Z.

Это непосредственно переводится на Пролог как

предок( X, Z) :.-родитель( X, Z).

Второе правило сложнее, поскольку построение цепочки отношений родитель может вызвать некоторые трудности. Один из способов определения отдаленных родственников мог бы быть таким, как показано на рис. 2. В соответствии с ним отношение предок определялось бы следующим множеством предложений: