Тогда мы можем получить список всех согласных, упомянутых в этих предложениях, при помощи цели:
?- bagof( Буква, класс( Буква, согл), Буквы).
Буквы = [d, c, d, f]
Если же мы в указанной цели оставим класс букв неопределенным, то, используя автоматический перебор, получим два списка букв, каждый из которых соответствует одному из классов:
?- bagof( Буква, класс( Буква, Класс), Буквы).
Класс = глас
Буквы = [а,e]
Класс =
согл
Буквы = [b, c, d, f]
Если
bagof( X, P, L)
не находит ни одного решения для
P
, то цель
bagof
просто терпит неуспех. Если один и тот же X найден многократно, то все его экземпляры будут занесены в
L
, что приведет к появлению в
L
повторяющихся элементов.
Предикат
setof
работает аналогично предикату
bagof
. Цель
setof( X, P, L)
как и раньше, порождает список L объектов X, удовлетворяющих P. Только на этот раз список L будет упорядочен, а из всех повторяющихся элементов, если таковые есть, в него попадет только один. Упорядочение происходит по алфавиту или по отношению '
<
', если элементы списка — числа. Если элементы списка — структуры, то они упорядочиваются по своим главным функторам. Если же главные функторы совпадают, то решение о порядке таких термов принимается по их первым несовпадающим функторам, расположенным выше и левее других (по дереву). На вид объектов, собираемых в список, ограничения нет. Поэтому можно, например, составить список пар вида
Класс / Буква
при этом гласные будут расположены в списке первыми ("глас" по алфавиту раньше "согл"):
тоже порождает список объектов, удовлетворяющих P. Он отличается от
bagof
тем, что собирает в список все объекты X, не обращая внимание на (возможно) отличающиеся для них конкретизации тех переменных из P, которых нет в X. Это различие видно из следующего примера:
?- findall( Буква, класс( Буква, Класс), Буквы).
Буквы = [a, b, c, d, e, f]
Если не существует ни одного объекта X, удовлетворяющего P, то
findall
все равно имеет успех и выдает
L = []
.
Если в используемой реализации Пролога отсутствует встроенный предикат
findall
, то его легко запрограммировать следующим образом. Все решения для P порождаются искусственно вызываемыми возвратами. Каждое решение, как только оно получено, немедленно добавляется к базе данных, чтобы не потерять его после нахождения следующего решения. После того, как будут получены и сохранены все решения, их нужно собрать в список, а затем удалить из базы данных при помощи
retract
. Весь процесс можно представлять себе как построение очереди из порождаемых решений. Каждое вновь порождаемое решение добавляется в конец этой очереди при помощи
assert
. Когда все решения собраны, очередь расформировывается. Заметим также, что конец очереди надо пометить, например, атомом "дно" (который, конечно, должен отличаться от любого ожидаемого решения). Реализация
findall
в соответствии с описанным методом показана на рис. 7.4.
findall( X, Цель, ХСпис) :-
саll( Цель), % Найти решение
assert(
очередь( X) ), % Добавить егo
fail; % Попытаться найти еще решения
assertz( очередь( дно) ),
% Пометить конец решений
собрать( ХСпис). % Собрать решения в список
собрать( L) :-
retract( очередь(X) ), !,
% Удалить следующее решение
( X == дно, !, L = [];
% Конец решений?
L = [X | Остальные], собрать( Остальные) ).
% Иначе собрать остальные
Рис. 7.4. Реализация отношения findall.
Упражнения
7.8. Используя
bagof
, определите отношение
множподмножеств( Мн, Подмн)
для вычисления множества всех подмножеств данного множества (все множества представлены списками).
7.9. Используя
bagof
, определите отношение
копия( Терм, Копия)
чтобы
Копия
представляла собой
Терм
, в котором все переменные переименованы.
Резюме
• В любой реализации Пролога обычно предусматривается набор встроенных процедур для выполнения различных полезных операций, несуществующих в чистом Прологе. В данной главе мы рассмотрели подобное множество предикатов, имеющееся во многих реализациях.
• Тип терма можно установить при помощи следующих предикатов:
var( X)
X — (неконкретизированная) переменная
nonvar( X)
X — не переменная
atom( X)
X — атом
integer( X)
X — целое
atomic( X)
X — или атом, или целое
• Термы можно синтезировать или разбирать на части:
Терм =.. [Функтор [ СписокАргументов]
functor( Терм, Функтор, Арность)
arg( N, Терм, Аргумент)
name( атом, КодыСимволов)
• Программу на Прологе можно рассматривать как реляционную базу данных, которую можно изменять при помощи следующих процедур:
аssert( Предл)
добавляет предложение
Предл
к программе
аssеrtа( Предл)
добавляет в начало
assertz( Предл)
добавляет в конец
rеtrасt( Предл)
удаляет предложение, сопоставимое с предложением
Предл
• Все объекты, отвечающие некоторому заданному условию, можно собрать в список при помощи предикатов:
bagof( X, P, L)
L — список всех X, удовлетворяющих условию P
setof( X, P, L)
L — отсортированный список всех X, удовлетворяющих условию P
findall( X, P, L)
аналогичен
bagof
•
repeat
— средство управления, позволяющее порождать неограниченное число альтернатив для автоматического перебора.
Глава 8
Стиль и методы программирования
В этой главе мы рассмотрим некоторые общие принципы хорошего программирования и обсудим, в частности, следующие вопросы: "Как представлять себе прологовские программы? Из каких элементов складывается хороший стиль программирования на Прологе? Как отлаживать пролог-программы? Как повысить их эффективность?"