Чтение онлайн

ЖАНРЫ

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

Братко Иван

Шрифт:

класс( e, глас).

класс( f, согл).

Тогда мы можем получить список всех согласных, упомянутых в этих предложениях, при помощи цели:

?- 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 будет упорядочен, а из всех повторяющихся элементов, если таковые есть, в него попадет только один. Упорядочение происходит по алфавиту или по отношению '

<
', если элементы списка — числа. Если элементы списка — структуры, то они упорядочиваются по своим главным функторам. Если же главные функторы совпадают, то решение о порядке таких термов принимается по их первым несовпадающим функторам, расположенным выше и левее других (по дереву). На вид объектов, собираемых в список, ограничения нет. Поэтому можно, например, составить список пар вида

Класс / Буква

при этом гласные будут расположены в списке первыми ("глас" по алфавиту раньше "согл"):

?- setof( Класс/Буква, класс( Буква, Класс), Спис).

Спис = [глас/а, глас/e, согл/b, согл/с, согл/d, согл/f]

Еще одним предикатом этого семейства, аналогичным

bagof
, является
findall
.

findall( 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

Стиль и методы программирования

В этой главе мы рассмотрим некоторые общие принципы хорошего программирования и обсудим, в частности, следующие вопросы: "Как представлять себе прологовские программы? Из каких элементов складывается хороший стиль программирования на Прологе? Как отлаживать пролог-программы? Как повысить их эффективность?"

Поделиться с друзьями: