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

введено в гл. 5.

• fail — цель, которая всегда терпит неудачу.

• true — цель, которая всегда успешна.

• not( P) — вид отрицания, который всегда ведет себя в точном соответствии со следующим определением:

not( P) :- P, !, fail; true.

Некоторые проблемы, связанные с отсечением и not детально обсуждались в гл. 5.

• саll( P) активизирует цель P. Обращение к саll имеет успех, если имеет успех P.

• repeat — цель, которая всегда успешна. Ее особое свойство состоит в том, что она недетерминирована, поэтому всякий раз, как до нее доходит перебор, она порождает новую ветвь вычислений. Цель repeat ведет себя так, как если бы она была определена следующим образом:

repeat.
repeat :- repeat.

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

квадраты :-
 repeat,
 read( X),
 ( X = стоп, !;
   Y is X*X, write( Y), fail ).

7.6. bagof, setof и findall

При помощи механизма автоматического перебора можно получить одни за другим все объекты, удовлетворяющие некоторой цели. Всякий раз, как порождается новое решение, предыдущее пропадает и становится с этого момента недоступным. Однако у нас может возникнуть желание получить доступ ко всем порожденным объектам сразу, например собрав их в список. Встроенные предикаты bagof (набор) и setof (множество) обеспечивают такую возможность; вместо них иногда используют предикат findall (найти все).

Цель

bagof( X, P, L)

порождает список L всех объектов X, удовлетворяющих цели P. Обычно bagof имеет смысл применять только тогда, когда X и P содержат общие переменные. Например, допустим, что мы включили в программу следующую группу предложений для разбиения букв (из некоторого множества) на два класса — гласные и согласные:

класс( а, глас).
класс( b, согл).
класс( с, согл).
класс( d, согл).
класс( 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. Когда все решения собраны, очередь расформировывается. Заметим также, что конец очереди надо пометить, например, атомом 'дно' (который, конечно, должен отличаться от любого