|
p align="left"> На языке Пролог это выглядит следующим образом: birthday(person("Leo","Jensen"),date("Apr",14,1960)) 7. Унификация составных объектовСоставной объект может быть унифицирован с простой переменной или с составным объектом (возможно, содержащим переменные в качестве частей во внутренней структуре), который ему соответствует. Это означает, что составной объект можно использовать для того, чтобы передавать целый набор значений как единый объект, и затем применять унификацию для их разделения. Например:date("April",14,I960) сопоставляется с X и присваивает X значение date ("April", 14,1960). Также date("April",14,I960) сопоставляется с date (Mo, Da, Yr) и присваивает переменным Мо = "April", Da=14 и Yr = 1960. 8. Использование нескольких значений как единого целогоСоставные объекты могут рассматриваться в предложениях Пролога как единые объекты, что сильно упрощает написание программ. Рассмотрим, например, факт:owns(john, book(“From Here to Eternity", "James Jones")). в котором утверждается, что у Джона есть книга "From Here to Eternity" (Отсюда в вечность), написанная James Jones (Джеймсом Джонсом). Аналогично можно записать: owns (john, horse (blacky) ) . что означает: John owns a horse named blacky.(У Джона есть лошадь Блеки.) Если вместо этого описать только два факта: owns (john, "From Here to Eternity"), owns(john, blacky). то нельзя было бы определить, является ли blacky названием книги или именем лошади. 9. Объявление составных доменовРассмотрим, как определяются составные домены. После компиляции программы, которая содержит следующие отношения:owns(john, book("From Here to Eternity", "James Jones")). и owns (John, horse (blacky) ). вы можете послать системе запрос в следующем виде: owns (John, X) Переменная Х может быть связана с различными типами объектов: книга, лошадь и, возможно, другими объектами, которые вы определите. Отметим, что теперь вы не можете более использовать старое определение предиката owns: owns (symbol, symbol) Второй элемент более не является объектом типа symbol. Вместо этого вы можете дать новое определение этого предиката owns(name, articles) Домен articles в разделе domains можно описать так domains articles = book(title, author); horse(name) Точка с запятой читается как "или" В этом случае возможны два варианта книга будет определяться своим заглавием и автором, а лошадь будет распознаваться своим именем Домены title, author и name имеют стандартный тип symbol. К определению домена легко могут быть добавлены другие варианты. 10. Многоуровневые составные объектыVisual Prolog позволяет конструировать составные объекты на нескольких уровнях. Например:domains articles = book(title, author);%Первый уровень author= author(first_name, last_name) %Второй уровень title, first_name, last_name = symbol%Третий уровень При использовании составных объектов со многими уровнями часто помогает такое "дерево" (рис. 7): Дерево многоуровневого составного объекта Повтор и рекурсия Компьютеры способны повторять одно и то же действие снова и снова, Visual Prolog может выражать повторение как в процедурах, так и в структурах данных. Идея повторяющихся структур данных может показаться странной, но Пролог позволяет создавать структуры данных, размер которых не известен во время создания. 11. Процесс повторенияПрограммисты на языках Pascal, Basic или С, которые начинают использовать Visual Prolog, часто испытывают разочарование, обнаружив, что язык не имеет конструкций for, while или repeat. В Прологе не существует прямого способа выражения повтора. Пролог обеспечивает только два вида повторения · откат, с помощью которого осуществляется поиск многих решений в одном запросе, · и рекурсию, в которой процедура вызывает сама себя.Однако этот недостаток не снижает мощи Пролога. Фактически, Visual Prolog распознает специальный случай рекурсии -- хвостовую рекурсию -- и компилирует ее в оптимизированную итерационную петлю. Это означает, что хотя программная логика и выражается рекурсивно, скомпилированный код так же эффективен, как если бы программа была написана на 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. Программа ch06e01.pro Предварительные и последующие операцииОтметим, что программа, которая находит решения для целевого утверждения, может выполнять какие-либо предварительные или завершающие операции. Например, в нашем примере программа могла бы:1. Напечатать Some delightful places to live are... (Некоторые восхитительные места для проживания...).2. Напечатать все решения для country (X).3. Завершить печать фразой And maybe others (Могут быть и другие).Заметьте, что 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. Листинг 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. Информация хранится в области памяти, называемой стековым фреймом (stack frame) или просто стеком (stack), который создается каждый раз при вызове правила. Когда выполнение правила завершается, занятая его стековым фреймом память освобождается (если это не недетерминированный откат), и выполнение продолжается в стековом фрейме правила-родителя. Преимущества рекурсииРекурсия имеет три основных преимущества:· она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом;· она логически проще метода итерации;· она широко используется в обработке списков.Рекурсия -- хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Например, поиск в дереве (дерево состоит из более мелких деревьев) и рекурсивная сортировка (для сортировки списка, он разделяется на части, часть сортируются и затем объединяются вместе).Логически рекурсивным алгоритмам присуща структура индуктивного математического доказательства. Приведенная выше рекурсивная программа вычисления факториала описывает бесконечное множество различных вычислений с помощью всего лишь двух предложений. Это позволяет легко увидеть правильность этих предложений. Кроме того, правильность каждого предложения может быть изучена независимо от другого.Пример рекурсивного определения правилДавайте добавим к программе о родственных связях еще одно отношение - предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных (ближайших) предков, а второе - отдаленных. Будем говорить, что некоторый X является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных между собой отношением родитель-ребенок, как показано на рис.1.. В нашем примере на рис. 1. Том - ближайший предок Лиз и отдаленный предок Пат.Пример отношения предок:(а) X - ближайший предок Z; (b) X - отдаленный предок Z. Первое правило простое и его можно сформулировать так: Для всех X и Z, X - предок Z, если X - родитель Z. Это непосредственно переводится на Пролог как предок( X, Z) :.-родитель( X, Z). Второе правило сложнее, поскольку построение цепочки отношений родитель может вызвать некоторые трудности. Один из способов определения отдаленных родственников мог бы быть таким, как показано на рис. 2. В соответствии с ним отношение предок определялось бы следующим множеством предложений: предок( X, Z) :- родитель( X, Z).
Страницы: 1, 2, 3, 4, 5, 6, 7
|
