ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.01.2024
Просмотров: 303
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
domains
thing = misc_thing(whatever);
book(author,title); record(artist,album,type) person, whatever, author, title, artist, album, type = symbol
predicates
owns (person, thing)
clauses
owns ("Иванов", misc_thing("Piano")).
owns ("Петров", book("J.R.R. Tolkien", "Return of the Ring")).
owns ("Сидоров", record("Elton John", "Ice Fair", "popular")).
1 2 3 4 5 6 7 8 9
ТЕМА 2.5 ОРГАНИЗАЦИЯ ПОВТОРЕНИЙ В ЯЗЫКЕ PROLOG
План лекции:
2.5.1 Метод отката после неудачи
2.5.2 Метод отсечения и отката
2.5.3 Простая рекурсия
2.5.4 Метод обобщенного правила рекурсии (ОПР)
2.5.1 Метод отката после неудачи
Очень часто в программах необходимо выполнить одну и ту же задачу несколько раз. Существуют два способа реализации правил, выполняющих одну и ту же задачу многократно. Первый их них мы будем называть повторением, а второй — рекурсией. Правила Turbo-Prolog, выполняющие повторения, используют откат, а правила, выполняющие рекурсию, используют самовызов.
Вид правила, выполняющего повторение, следующий:
repetitive_rule :- /* правило повторения */
<предикаты и правила>,
fail.
/* неудача */
Конструкция <предикаты и правила> в теле этого правила обозначает предикаты, содержащие несколько утверждений, а также правила, определенные в программе. Встроенный предикат fail («неудача») вызывает откат, так что предикаты и правила выполняются еще раз.
Вид правила, выполняющего рекурсию, следующий:
recursive_rule :-
/* правило рекурсии */
<предикаты и правила>, recursive_rule.
Заметим, что последним в теле данного правила является само же правило recursive_rule. Это и есть рекурсия: тело правила содержит вызов самого себя.
Правила повтора и рекурсии могут обеспечивать одинаковый результат, хотя алгоритмы их выполнения не одинаковы. Каждый из них в конкретной ситуации имеет свои преимущества. Рекурсия, например, может требовать больше системных ресурсов, поскольку всякий раз при рекурсивном вызове новые копии используемых значений помещаются в стек — особую область памяти, используемую в основном для передачи значений между правилами. Эти значения сохраняются, пока правило не завершится успешно или неуспешно. В некоторых ситуациях такое использование стека может быть оправдано, если промежуточные значения должны храниться в определенном порядке для дальнейшего использования.
Метод отката после неудачи (ОПН) может быть использован для управления вычислением внутренней цели при поиске всех возможных ее решений. Метод ОПН использует предикат fail, который вызывает неуспешное завершение правила. При его срабатывании внутренние унификационные подпрограммы выполняют откат в точку возврата, и процесс повторяется до тех пор, пока последнее утверждение не будет обработано.
Использование метода ОПН позволяет извлекать данные из каждого утверждения базы данных. Добавив же дополнительные условия на значения объектов для одной или более переменных предиката, можно извлекать данные только из определенных утверждений.
Пример 1. Пусть в базе данных в виде набора фактов хранятся сведения о нескольких городах (название города и название реки, протекающей через город). Цель — получить на экране полный список городов.
/* Демонстрация метода отката после неудачи */ predicates city
(symbol, symbol) all_cities
clauses
city ("Самара","Волга"). city ("Саратов","Волга"). city
("Ростов","Дон"). city ("Москва","Москва").
city ("Волгоград","Волга").
/*правило для получения полного списка городов*/ all-cities:-city (C,_),
write (C), nl,
fail.
goal write ("Полный список городов:"),nl,
all_cities.
Пример 2. Пусть в базе данных в виде набора фактов хранятся сведения о нескольких городах (название города и название реки, протекающей через город). Цель — получить на экране список городов, стоящих на указанной реке.
predicates
city (symbol, symbol) search (symbol)
clauses
city
("Самара","Волга"). city
("Саратов","Волга"). city
("Ростов","Дон"). city ("Москва","Москва"). city ("Волгоград","Волга").
/*правило для поиска*/ search (R):- city (C,R),
write (C), nl,
fail.
goal
write ("Укажите название реки: "), readln (River), nl,
write ("Города, стоящие на реке", River,":"), nl, search (River).
2.5.2 Метод отсечения и отката
В некоторых ситуациях необходимо иметь доступ только к определенной части данных. Метод отсечения и отката (ОО) может быть использован для фильтрации данных, выбираемых из утверждений базы данных. Задавая условие на окончание просмотра базы данных, можно получить только требуемую часть информации.
Для этих целей Prolog имеет встроенный предикат cut («отсечение»), который обозначается символом восклицательного знака (!). Этот предикат, вычисление которого всегда завершается успешно, заставляет внутренние
унификационные подпрограммы
«забыть» все указатели отката, установленные во время попыток вычислить текущую подцель. Другими словами, предикат cut «устанавливает барьер», запрещающий выполнить откат ко всем альтернативным решениям текущей подцели. Однако последующие подцели могут создать новые указатели отката и тем самым создать условия для поиска новых решений, на которые область действия предиката cut уже не распространяется. Но если все более поздние цели окажутся неуспешными, то барьер, установленный предикатом cut, заставит механизм отката отсечь все решения в области действия cut путем немедленного отката к другим возможным решениям вне области действия предиката cut. Тем самым метод отсечения и отката имитирует неуспешное вычисление и выполняет последующий откат до тех пор, пока не будет обнаружено определенное условие, а предикат cut служит для устранения всех последующих откатов.
Пример. Пусть имеется база данных, которая содержит несколько имен детей. Цель — выдать список этих имен до имени Diana включительно.
/* Демонстрация метода отката и отсечения */ predicates
name (symbol) choice
clauses name ("Mary"). name ("Bob"). name ("Diana"). name ("John"). name ("Peter"). /*правило для поиска*/ choice:- name (N),
write (N), nl, N="Diana",!.
goal write ("Список имен до Diana: "), nl, choice.
2.5.3 Простая рекурсия
Правило, содержащее само себя в качестве компонента, называется правилом рекурсии.
Пример. Программа «Эхо» — ввод с клавиатуры строк и вывод их на экран; признак окончания ввода данных — пустая строка.
«забыть» все указатели отката, установленные во время попыток вычислить текущую подцель. Другими словами, предикат cut «устанавливает барьер», запрещающий выполнить откат ко всем альтернативным решениям текущей подцели. Однако последующие подцели могут создать новые указатели отката и тем самым создать условия для поиска новых решений, на которые область действия предиката cut уже не распространяется. Но если все более поздние цели окажутся неуспешными, то барьер, установленный предикатом cut, заставит механизм отката отсечь все решения в области действия cut путем немедленного отката к другим возможным решениям вне области действия предиката cut. Тем самым метод отсечения и отката имитирует неуспешное вычисление и выполняет последующий откат до тех пор, пока не будет обнаружено определенное условие, а предикат cut служит для устранения всех последующих откатов.
Пример. Пусть имеется база данных, которая содержит несколько имен детей. Цель — выдать список этих имен до имени Diana включительно.
/* Демонстрация метода отката и отсечения */ predicates
name (symbol) choice
clauses name ("Mary"). name ("Bob"). name ("Diana"). name ("John"). name ("Peter"). /*правило для поиска*/ choice:- name (N),
write (N), nl, N="Diana",!.
goal write ("Список имен до Diana: "), nl, choice.
2.5.3 Простая рекурсия
Правило, содержащее само себя в качестве компонента, называется правилом рекурсии.
Пример. Программа «Эхо» — ввод с клавиатуры строк и вывод их на экран; признак окончания ввода данных — пустая строка.
/* Демонстрация рекурсии на примере программы "Эхо" */ predicates
echo
clauses
echo :- readln (String), String<>"", write (String), nl, echo.
goal
echo.
2.5.4 Метод обобщенного правила рекурсии (ОПР)
Обобщенное правило рекурсии содержит в теле правила само себя.
Рекурсия будет конечной, если в правило включено условие выхода, гарантирующее окончание его работы. Тело правила состоит из утверждений и правил, определяющих задачи, которые должны быть выполнены. Общий вид правила рекурсии в символическом виде:
<имя правила рекурсии> :-
<список предикатов>, (1) <предикат условия выхода>, (2) <список
предикатов>, (3) <имя правила рекурсии>, (4)
<список предикатов>.
(5)
Данное правило рекурсии имеет пять компонентов. Первый — это группа предикатов, которые всегда истинны и на рекурсию не влияют.
Второй компонент — это предикат условия выхода. Успех этого предиката позволяет продолжить рекурсию, а неудача вызывает ее остановку
(рекурсивное правило возвращает «Ложь»). Третий компонент — список других предикатов, которые также всегда истинны и на рекурсию тоже не оказывает влияния. Четвертая группа — само рекурсивное правило, успех которого и вызывает рекурсию. Наконец, пятая группа — это список предикатов, которые тоже всегда успешны и опять-таки не влияют на рекурсию. Пятая группа также получает значения (если они имеются), помещенные в стек во время выполнения рекурсии.
Напомним, что правило рекурсии обязательно должно содержать условие выхода. В противном случае рекурсия будет бесконечной, а такое правило — бесполезным. Ответственность за обеспечение завершаемости правила рекурсии возлагается на программиста. Правила, построенные указанным образом, являются обобщенными правилами рекурсиии (ОПР), а сам метод называется ОПР-методом.
Пример. Правило генерации всех целых чисел, начиная с 1 и заканчивая 7.
Пусть имя правила будет write_number(Number).
Для этого примера первый компонент структуры общего правила рекурсии не используется. Вторым компонентом, т. е. предикатом выхода, является условие Number < 8: когда значение Number равно 8, правило будет успешным, а программа завершится. Третий компонент правила оперирует с числами: число выдается на экран, а затем увеличивается на 1. Для увеличенного числа будет использоваться новая переменная Next_Number.
Четвертый компонент
— вызов самого правила рекурсии write_number(Next_number). Пятый компонент, представленный в общем случае, здесь не используется.
Таким образом, программа генерации ряда чисел будет использовать следующее правило рекурсии:
write_number(8).
write_number(Number) :Number < 8, write(Number), nl, Next_Number =
Number + 1,
write_number(Next_number).
Рассмотрим ход выполнения этой программы. Она начинается с попытки вычислить подцель write_number(1). Сначала программа сопоставляет подцель с первым правилом write_number(8). Так как 1 не равно
8, то это сопоставление неуспешно. Тогда программа вновь пытается сопоставить подцель, но уже с головой правила write_number (Number). На
этот раз сопоставление успешно, так как переменной Number присвоено значение 1. Теперь программа сравнивает это значение с 8 (условие выхода).
Так как 1 меньше 8, то данное подправило успешно. Следующий предикат выдает значение, присвоенное Number. Переменная Next_Number получает значение 2, а значение Number увеличивается на 1.
Так как 1 меньше 8, то данное подправило успешно. Следующий предикат выдает значение, присвоенное Number. Переменная Next_Number получает значение 2, а значение Number увеличивается на 1.
ТЕМА 2.6 СПИСКИ В ЯЗЫКЕ PROLOG
Prolog также поддерживает связанные объекты, называемые списками.
Список — это упорядоченный набор объектов, следующих друг за другом.
Составляющие списка внутренне связаны между собой, поэтому с ними можно работать и как с группой (списком в целом), и как с индивидуальными объектами (элементами списка).
Рассмотрим структуру, организацию и представление списков.
Список является набором объектов одного и того же доменного типа.
Объектами списка могут быть целые числа, действительные числа, символы, символьные строки и структуры. Порядок расположения элементов является отличительной чертой списка; те же самые элементы, упорядоченные иным способом, представляют уже совсем другой список, поскольку порядок играет важную роль в процессе сопоставления.
Prolog допускает списки, элементами которых являются структуры.
Если структуры принадлежат к альтернативному домену, то элементы списка могут иметь разный тип. Такие списки используются для специальных целей.
Совокупность элементов списка заключается в квадратные скобки —
[], а друг от друга элементы списка отделяются запятыми.
Примеры:
[1,2,3,6,9,3,4]
[3.2,4.6,1.1,2.64,100.2]
["YESTERDAY","TODAY","TOMORROW"]
Элементами первого списка являются целые числа, элементами второго
— действительные числа, а третьего — символьные строки.
Количество элементов в списке называется его длиной. Например, длина списка ["MADONNA","AND","CHILD"] равна 3, а длина списка [4.50,
3.50, 6.25, 2.9, 100.15] равна 5. Список может также содержать всего один элемент или даже не содержать элементов вовсе, например, ["summer"] или
[]. Список, не содержащий элементов, называется пустым, или нулевым списком.
Непустой список можно рассматривать как состоящий из двух частей: первый элемент списка — его голова (1), а остальная часть списка — хвост
(2). Голова является одним из элементов списка, а хвост — это список сам по себе. Голова списка представляет собой отдельное неделимое значение; хвост же — это список, составленный из того, что осталось от исходного списка в результате «усекновения головы». Если, например, список состоит из одного-единственного элемента, то его можно разделить на голову, которой будет этот самый единственный элемент, и хвост, являющийся пустым списком.
Примеры:
Список
Голова
Хвост
[1,2,3,4,5]
1
[2,3,4,5]
['s','k','y']
's'
['k','y']
[cat]
cat
[]
[]
не определена не определен
Чтобы использовать в программе список, необходимо описать предикат списка.
Примеры:
num
([1,2,3,6,9,3,4]) realnum
([3.2,4.6,1.1,2.64,100.2]) time
(["YESTERDAY","TODAY","TOMORROW"])
Введение списков в программу необходимо отразить в трех ее разделах. Домен списка должен быть описан в разделе domains, работающий со списком предикат — в разделе predicates и, наконец, надо задать сам список в разделе clauses или goal.