Bagof , setof и findall

bagof , setof и findall

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

Цель

bagof( X, P, L)

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

        класс( а, глас).
        класс( b, согл).
        класс( с, согл).
        класс( d, согл).
        класс( е, глас).
        класс( f, согл).

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

?- bagof( Буква, класс( Буква, согл), Буквы).

Буквы = [d, c, d, f]

Если же мы в указанной цели оставим класс букв неопределенным, то, используя автоматический перебор, получим два списка букв, каждый из которых соответствует одному из классов:

?- bagof( Буква, класс( Буква, Класс), Буквы).

Класс = глас
Буквы = [а,е]

Класс = согл
Буквы = [b, c, d, f]

Если bagof( X, Р, L) не находит ни одного решения для Р, то цель bagof просто терпит неуспех. Если один и тот же Х найден многократно, то все его экземпляры будут занесены в L, что приведет к появлению в L повторяющихся элементов .

Предикат setof работает аналогично предикату bagof. Цель

setof( X, P, L)

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

Класс / Буква

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

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

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

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

findall( X, P, L)

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

?- findall( Буква, класс( Буква, Класс), Буквы).

Буквы= [a, b, c, d, e, f]

Если не существует ни одного объекта X, удовлетворяющего P, то findall все равно имеет успех и выдает L = [ ].

Если в используемой реализации Пролога отсутствует встроенный предикат findall, то его легко запрограммировать следующим образом. Все решения для Р порождаются искусственно вызываемыми возвратами. Каждое решение, как только оно получено, немедленно добавляется к базе данных, чтобы не потерять его после нахождения следующего решения. После того, как будут получены и сохранены все решения, их нужно собрать в список, а затем удалить из базы данных при помощи retract. Весь процесс можно представлять себе как построение очереди из порождаемых решений. Каждое вновь порождаемое решение добавляется в конец этой очереди при помощи assert. Когда все решения собраны, очередь расформировывается. Заметим также, что конец очереди надо пометить, например, атомом "дно" (который, конечно, должен отличаться от любого ожидаемого решения). Реализация findall в соответствии с описанным методом показана на рис. 7.4.

line();

findall( X, Цель, ХСпис) :-
    саll( Цель),                                 % Найти решение
    assert( очередь( X) ),                % Добавить егo
    fail;                 % Попытаться найти еще решения
    assertz( очередь( дно) ),
                         % Пометить конец решений
    собрать( ХСпис).                     % Собрать решения в список

собрать( L) :-
     retract( очередь(Х) ), !,
                         % Удалить следующее решение
    ( Х == дно, !, L = [ ];
                         % Конец решений?
    L = [X | Остальные], собрать( Остальные) ).
                         % Иначе собрать остальные

line();

Другие встроенные процедуры

Глава 7. ДРУГИЕ ВСТРОЕННЫЕ ПРОЦЕДУРЫ

В данной главе мы изучим некоторые другие, не упоминавшиеся ранее встроенные процедуры, предназначенные для более серьезного программирования на Прологе. Эта новые процедуры дают возможность запрограммировать операции, которые известными нам средствами запрограммировать невозможно. Один набор таких процедур касается обработки термов: эти процедуры проверяют, была ли некоторая переменная конкретизирована целым числом, они разбирают термы на части, конструируют новые термы и т.д. Другой полезный набор процедур работает с "базой данных": процедуры из этого набора добавляют новые отношения в программу или удаляют из нее существующие.

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

double_line();

Поразрядное сложение. Отношения в показанном i-м

разряде такие: D3i = (C1 + D1i + D2i) mod 10; C = (C1 + D1i + D2i)
div 10 (div - целочисленное деление, mod - остаток от деления).

Для определения отношения сумма над списками цифр нам нужно запрограммировать реальные правила суммирования в десятичной системе счисления. Суммирование производится цифра за цифрой, начиная с младших цифр в сторону старших, всякий раз учитывая цифру переноса справа. Необходимо также сохранять множество допустимых цифр, т.е. цифр, которые еще не были использованы для конкретизации уже встретившихся переменных. Поэтому, вообще говоря, кроме трех чисел Nl, N2 и N в рассмотрении должна участвовать некоторая дополнительная информация, как показано на рис. 7.1: перенос перед сложением перенос после сложения множество цифр, доступных перед сложением оставшиеся цифры, не использованные при сложении

Для формулировки отношения сумма мы снова воспользуемся принципом обобщения задачи: введем вспомогательное, более общее отношение сумма1. Это отношение будет иметь несколько дополнительных аргументов, соответствующих той дополнительной информации, о которой говорилось выше:

сумма1( Nl, N2, N, C1, С, Цифры1, Цифры)

Здесь Nl, N2 и N - наши три числа, как и в отношении сумма, С1 - перенос справа (до сложения Nl и N2), а С - перенос влево (после сложения). Пример:

        ?- сумма1( [H, E], [6, E], [U, S], l, l,
                            [1, 3, 4, 7, 8, 9], Цифры ).
        Н = 8
        Е = 3
        S = 7
        U = 4
        Цифры = [1, 9]

Если Nl и N удовлетворяют отношению сумма, то, как показано на рис. 7.1, С1 и С должны быть равны 0. Цифры1 - список цифр, которые не были использованы для конкретизации переменных. Поскольку мы допускаем использование в отношении сумма любых цифр, ее определение в терминах отношения сумма1 выглядит так:

сумма( Nl, N2, N) :-
cyммa1( Nl, N2, N, 0, 0, [0, l, 2, 3, 4, 5, 6, 7, 8, 9], _ ).

Бремя решения задачи переложено теперь на отношение сумма1. Но это отношение является уже достаточно общим, чтобы можно было определить его рекурсивно. Без ограничения общности мы предположим, что все три списка, представляющие три числа, имеют одинаковую длину. Наш пример, конечно, удовлетворяет этому условию, но если это не так, то всегда можно приписать слева нужное количество нулей к более "короткому" числу.

Определение отношения сумма1 можно разбить на два случая:

(1) Все три числа представляются пустыми списками. Тогда

сумма1( [ ], [ ], [ ], 0, 0, Циф, Циф).

(2) Все три числа имеют какую-то самую левую цифру и справа от нее - остальные цифры. То есть, они имеют вид:

[D1 | Nl], [D2 | N2], [D | N]

В этом случае должны выполняться два условия:

(а) Оставшиеся цифры, рассматриваемые как три числа Nl, N2 и N, сами должны удовлетворять отношению сумма1, выдавая влево некоторый перенос С2 и оставляя некоторое подмножество неиспользованных цифр Циф2.

(b) Крайние левые цифры D1, D2 и D, а также перенос С2 должны удовлетворять отношению, показанному на рис. 7.1: С2, D1 и D2 складываются, давая в результате D и перенос влево. Это условие в нашей программе формулируется в виде отношения суммацифр.

Переводя это на Пролог, получаем:

        сумма1( [D1 | N1], [D2 | N2], [D | N], С1, С, Циф1, Циф) :-
                сумма1( Nl, N2, N, С1, С2, Циф1, Циф2),
                суммацифр( D1, D2, С2, D, С, Циф2, Циф).

Осталось только описать на Прологе отношение суммацифр. В его определении есть одна тонкая деталь, касающаяся применения металогического предиката nonvar. D1, D2 и D должны быть десятичными цифрами. Если хоть одна из этих переменных еще не конкретизирована, ее нужно конкретизировать какой-нибудь цифрой из списка Циф2. Как только такая конкретизация произошла, эту цифру нужно удалить из множества доступных цифр. Если D1, D2 и D уже конкретизированы, тогда, конечно, ни одна из доступных цифр "потрачена" не будет. В программе эти действия реализуются при помощи недетерминированного вычеркивания элемента списка. Если этот элемент - не переменная, ничего не вычеркивается (конкретизации не было). Вот эта программа:

удалить( Элемент, Список, Список) :-
nonvar( Элемент), !.

удалить( Элемент, [Элемент | Список ], Список).

удалить(Элемент, [А | Список], [А | Список1]) :-
удалить( Элемент, Список, Список1).

Полная программа для решения арифметических ребусов приводится на рис. 7.2. В программу включены также определения двух ребусов. Вопрос к пролог-системе для ребуса про DONALD'a, GERALD'a и ROBERT'a с использованием этой программы выглядит так:

?- ребус1( N1, N2, N), сумма( N1, N2, N).

line();

% Решение числовых ребусов

сумма( N1, N2, N) :-
                            % Числа представлены в виде списков цифр
сумма1( N1, N2, N,
                0, 0,
                            % Перенос справа и перенос влево равны 0
                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], _ ).
                            % Все цифры доступны

сумма1( [ ], [ ], [ ], 0, 0, Цифры, Цифры).

сумма1( [D1 | N1], [D2 | N2], [D | N], C1, С, Циф1, Циф) :-
сумма1( Nl, N2, N, C1, C2, Циф1, Циф2),
суммацифр( Dl, D2, C2, С, Циф2, Циф).

суммацифр( Dl, D2, C1, D, С, Циф1, Циф) :-
        удалить( D1, Циф1, Циф2),
                                    % Выбор доступной цифры для D1
        удалить( D2, Циф2, Циф3),
                                    % Выбор доступной цифры для D2
        удалить( D, Циф3, Циф),
                                    % Выбор доступной цифры для D
        S is D1 + D2 + C1,
        D is S mod 10,
        С is S div 10.

удалить( A, L, L) :-
nonvar( A), !.
% Переменная А уже конкретизирована

удалить( А, [А | L], L).

удалить( А, [В | L], [В | L1]) :-
удалить( A, L, L1).

% Примеры ребусов

ребус1( [D, O, N, A, L, D],
[G, E, R, A, L, D],
[R, O, B, E, R, T].

ребус2( [0, S, E, N, D],
[0, M, O, R, E],
[M, O, N, E, Y].

line();

Процедура подстановки в терм вместо одного из его

Процедура подстановки в терм вместо одного из его

подтермов некоторого другого подтерма.

зависимости от ее текущей конкретизации, может по своей синтаксической форме не подойти в качестве цели. Эту трудность можно обойти при помощи еще одного встроенного предиката call (вызов), чьим аргументом является цель, подлежащая вычислению. В соответствий с этим предыдущий пример должен быть переписан так:

        . . .
        Цель = [Функтор | Списарг],
        саll( Цель)

Иногда нужно извлечь из терма только его главный функтор или один из аргументов. В этом случае можно, конечно, воспользоваться отношением '=..' Но более аккуратным и практичным, а также и более эффективным способом будет применение одной из двух новых встроенных процедур: functor и аrg. Вот их смысл: цель

functor( Терм, F, N)

истинна, если F - главный функтор Tepм'a, а N -арность F. Цель

arg( N, Терм, А)

истинна, если А - N-й аргумент в Терм'е, в предположении, что нумерация аргументов идет слева направо и начинается с 1. Примеры для иллюстрации:

?- functor( t( f( x), X, t), Фун, Арность).

Фун = t
Арность = 3

?- аrg( 2, f( X, t( a), t( b) ), Y).

Y = t( a)

        ?- functor( D, дата, 3),
                arg( 1, D, 29),
                arg( 2, D, июнь),
                arg( 3, D, 1982).

D = дата( 29, июнь, 1982)

Последний пример иллюстрирует особый случай применения предиката functor. Цель functor( D, дата, 3) создает "обобщенный" терм с главным функтором дата и тремя аргументами. Этот терм обобщенный, так как все три его аргумента - не конкретизированные переменные, чья имена генерируются пролог - системой. Например:

D = дата( _5, _6, _7)

Затем эти три переменные конкретизируются при помощи трех целей аrg.

К рассматриваемому множеству встроенных предикатов относится также и введенный в гл. 6 предикат name, предназначенный для синтеза и декомпозиция атомов. Для полноты изложения мы здесь напомним его смысл. Цель

name( A, L)

истинна, если L - список кодов (в кодировке ASCII) символов, входящих в состав атома А.

Программа для арифметических ребусов.

Иногда этот ребус упрощают, сообщая часть решения в виде дополнительного ограничения, например D равно 5. В такой форме ребус можно передать пролог-системе при помощи сумма1:

        ? - сумма1( [5, O, N, A, L, 5],
                              [G, E, R, A, L, 5],
                              [R, O, B, E, R, T],
                              0, 0, [0, 1, 2, 3, 4, 6, 7, 8, 9], _ ).

Интересно, что в обоих случаях существует только одно решение, т.е. только один способ заменить буквы цифрами.

Проверка типов термов

    Проверка типов термов

    Предикаты   var, nоnvar, atom, integer, atomic
1.    Предикаты   var, nоnvar, atom, integer, atomic

Термы бывают разных типов: переменные, целые числа, атомы и т.д. Если терм - переменная, то в некоторый момент выполнения программы он может оказаться конкретизированным или не конкретизированным. Далее, если он конкретизирован, то его значение может быть атомом, структурой и т. п. Иногда бывает полезно узнать, каков тип этого значения. Например, пусть мы хотим сложить значения двух переменных Х и Y:

Z is X + Y

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

Для этого следует воспользоваться встроенным предикатом integer (целое). Предикат integer( X) принимает значение истина, если Х - целое или если Х - переменная, имеющая целое значение. Будем говорить в этом случае, что Х "обозначает" целое. Цель для сложения Х и Y можно тогда "защитить" такой проверкой переменных Х и Y:

. . ., integer( X), integer( Y), Z is X + Y, . . .

Если неверно, что X и Y оба являются целыми, то система и не будет пытаться их сложить. Таким образом, цели integer "охраняют" цель Z is Х + Y от бессмысленного вычисления.

Встроенные предикаты этого типа таковы: var (переменная), nonvar (непеременная), atom (атом), integer (целое), atomic (атомарный). Они имеют следующий смысл :

var( X)

Эта цель успешна, если Х в текущий момент - не конкретизированная переменная .

nonvar( X)

Эта цель успешна, если Х - терм, отличный от переменной, или если Х - уже конкретизированная переменная.

atom( X)

Эта цель истинна, если Х обозначает атом.

integer( X)

Цель истинна, если Х обозначает целое .

atomic( X)

Цель истинна, если Х обозначает целое или атом.

Следующие примеры вопросов к пролог-системе иллюстрируют применение этих встроенных предикатов:

?- var( Z), Z = 2.
Z = 2

?- Z = 2, var( Z).
no

?- integer( Z), Z = 2.
no

?- Z = 2, integer( Z), nonvar( Z).
Z = 2

?- atom( 22).
no

?- atomic( 22).
yes

?- atom( ==>).
yes

?- atom( p( 1) ).
no

Необходимость в предикате atom продемонстрируем на следующем примере. Пусть мы хотим подсчитать, сколько раз заданный атом встречается в некоторой списке объектов. Для этого мы определим процедуру

счетчик( А, L, N)

где А - атом, L - список и N - количество вхождений этого атома. В качестве первой попытки можно было бы определить счетчик так:

счетчик( _, [ ], 0).

        счетчик( A, [A | L], N) :- !,
                счетчик( A, L, N1),
                                    % N1 - число вхождений атома в хвост
                N is N1 + 1.

счетчик( А, [ _ | L], N) :-
счетчик( A, L, N).

Теперь на нескольких примерах посмотрим, как эта процедура работает:

?- счетчик( а, [а, b, а, а], N).
N = 3

        ?- счетчик( a, [a, b, X, Y], Na).
        Na = 3
        . . .

        ?- счетчик( b, [a, b, X, Y], Nb).
        Nb = 3
        . . .

        ?- L=[a, b, Х, Y], счетчик( а, L, Na), счетчик( b, L, Nb).
        Na = 3
        Nb = 1
        X = a
        Y = a
        . . .

В последнем примере как X, так и Y после конкретизации получили значение а, и поэтому Nb оказалось равным только 1, однако мы хотели не этого. Нас интересовало количество реальных появлений конкретного атома, а вовсе не число термов, сопоставимых с этим атомом. В соответствии с этим более точным определением отношения счетчик мы должны теперь проверять, является ли голова списка атомом. Усовершенствованная программа выглядит так:

счетчик( _, [ ], 0).

        счетчик( А, [В | L], N) :-
                atom( В), А = В, !,                       % B равно атому А?
                счетчик( A, L, N1),                     % Подсчет в хвосте
                N is N1 + 1;
                счетчик( А, L, N).
                                % Иначе - подсчитать только в хвосте

В следующем более сложном упражнении по программированию числовых ребусов используется предикат nonvar.

Решение числового ребуса с использованием nonvar
2. Решение числового ребуса с использованием nonvar

Известным примером числового ребуса является

+	D O N A L D
G E R A L D
	R O B E R T

Задача состоит в том. чтобы заменить буквы D, О, N и т.д. на цифры таким образом, чтобы вышеприведенная сумма была правильной. Разным буквам должны соответствовать разные цифры, иначе возможно тривиальное решение, например, все буквы можно заменить на нули.

Определим отношение

сумма( Nl, N2, N)

где Nl, N2 и N представляют три числа данного ребуса. Цель cyммa(Nl, N2, N) достигается, если существует такая замена букв цифрами, что N1+N2 = N.

Первым шагом к решению будет выбор представления чисел Nl, N2 и N в программе. Один из способов - представить каждое число в виде списка его цифр. Например, число 255 будет тогда представляться списком [2, 2, 5]. Поскольку значения цифр нам не известны заранее, каждая цифра будет обозначаться соответствующей неинициализированной переменной. Используя это представление, мы можем сформулировать задачу так:

        [ D, O, N, A, L, D ]
+    [ G, E, R, A, L, D ]
=    [ R, О, B, E, R, T ]

Теперь задача состоит в том. чтобы найти такую конкретизацию переменных D, О, N и т.д., для которой сумма верна. После того, как отношение сумма будет запрограммировано, задание для пролог-системы на решение ребуса будет иметь вид

?- сумма( [D, O, N, A, L, D], [G, E, R, A, L, D],
[R, O, В, Е, R, T ).

Работа с базой данных

Реляционная модель предполагает, что база данных - это описание некоторого множества отношений. Пролог-программу можно рассматривать как именно такую базу данных: описание отношений частично присутствует в ней в явном виде (факты), а частично - в неявном (правила). Более того, встроенные предикаты дают возможность корректировать эту базу данных в процессе выполнения программ. Это делается добавлением к программе (в процессе вычисления) новых предложений или же вычеркиванием из нее уже существующих. Предикаты, используемые для этой цели, таковы: assert (добавить), asserta, assertz и retract (удалить).

Цель

assert( С)

всегда успешна, а в качестве своего побочного эффекта вызывает "констатацию" предложения С, т. е. добавление его к базе данных. Цель

retract( С)

приводит к противоположному эффекту: удаляет предложение, сопоставимое с С. Следующий диалог иллюстрирует их работу:

?- кризис.
no

? - assert( кризис).
yes

?- кризис.
yes

? - retract( кризис).
yes

?- кризис.
no

Предложения, добавленные к программе таким способом, ведут себя точно так же, как и те, что были в "оригинале" программы. Следующий пример показывает, как с помощью assert и retract можно работать в условиях изменяющейся обстановки. Предположим, что у нас есть такая программа о погоде:

хорошая :-
солнечно, not дождь.

необычная :-
солнечно, дождь.

отвратительная :-
дождь, туман.

дождь.

туман.

Ниже приводится пример диалога с этой программой, во время которого база данных постепенно изменяется:

?- хорошая.
no

?- отвратительная.
yes

?- retract( туман).
yes

?- отвратительная.
no

?- assert( солнечно).
yes

?- необычная.
yes

?- retract( дождь).
уes

?- хорошая.
yes

Добавлять и удалять можно предложения любой формы. Следующий пример показывает, что, кроме того, retract может работать недетерминировано: используя механизм возвратов с помощью только одной цели retract можно удалить целое множество предложений. Предположим, что в программе, с которой мы "консультируемся", есть такие факты:

        быстр( энн).
        медл( том).
        медл( пат).

К этой программе можно добавить правило:

        ?- assert(
                         ( быстрее( X, Y) :-
                              быстр( X), медл( Y) ) ).

yes

        ?- быстрее( А, В).
        А = энн
        В = том

        ?- retract( медл( X) ).
        Х = том;
        X = пат;
        nо

?- быстрее( энн, _ ).
nо

Заметьте, что при добавлении нового правила синтаксис требует, чтобы оно (как аргумент assert) было заключено в скобки.

При добавлении нового предложения может возникнуть желание указать, на какое место в базе данных его следует поместить. Такую возможность обеспечивают предикаты asserta и assertz. Цель

asserta( С)

помещает С в начале базы данных. Цель

assertz( С)

- в конце. Вот пример, иллюстрирующий работу этих предикатов:

?- assеrt( р( a)), assertz( р( b) ), asserta( p( c) ).

yes

?- p( X).

        Х = с;
        Х = а;
        Х = b

Между consult и assertz существует связь. Обращение к файлу при помощи consult можно в терминах assertz определить так: считать все термы (предложения) файла и добавить их в конец базы данных.

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

решить( Задача, Решение)

Мы можем теперь задать вопрос и потребовать, чтобы ответ на него был запомнен, с тем чтобы облегчить получение ответов на будущие вопросы:

?- решить( задача1, решение),
asserta( решить( Задача1, Решение) ).

Если в первой из приведенных целей будет успех, ответ ( Решение) будет сохранен, а затем использован так же, как и любое другое предложение, при ответе на дальнейшие вопросы. Преимущество такого "запоминания" состоит в том, что на дальнейшие вопросы, сопоставимые с добавленным фактом, ответ будет получен, как правило, значительно быстрее, чем в первый раз. Ответ будет теперь получен как факт, а не как результат вычислений, требующих, возможно, длительного времени.

Развитие этой идеи состоит в использовании assert для порождения всех решений в виде таблицы фактов. Например, создать таблицу произведений всех чисел от 0 до 9 можно так: породить пару чисел Х и Y, вычислить Z, равное Х * Y, добавить эти три числа в виде строки в таблицу произведений, а затем создать искусственно неуспех. Неуспех вызовет возврат, в результате которого будет найдена новая пара чисел, и в таблицу добавится новая строка и т.д. Эта идея реализована в процедуре

        таблица :-
                L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
                принадлежит( X, L),            % Выбрать первый сомножитель
                принадлежит( Y, L),            % Выбрать второй сомножитель
                Z is X*Y,
                assert( произв( X,Y,Z) ),
                fail.

Вопрос

?- таблица.

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

?- произв( А, В, 8).

А = 1
В = 8;

А = 2
В = 4;

. . .

Здесь следует сделать одно замечание, относящееся к стилю программирования. Приведенные примеры показали некоторые явно полезные применения assert и retract. Однако использование этих отношений требует особой внимательности. Не рекомендуется применять их слишком часто и без должной осторожности - это плохой стиль программирования. Ведь добавляя и удаляя предложения, мы фактически изменяем программу. Поэтому отношения, выполнявшиеся в некоторой ее точке, могут оказаться неверными в другой. В разные моменты времени ответы на одни и те же вопросы будут различными. Таким образом, большое количество обращений к assert и retract может затемнить смысл программы и станет трудно разобрать, что истинно, а что - нет. В результате поведение программы может стать непонятным, трудно объяснимым, и вряд ли можно будет ей доверять.

Различные виды равенства

В каких случаях мы считаем, что два терма равны? До сих пор мы рассматривали три вида равенства в Прологе. Первый был связан с сопоставлением и записывался так:

Х = Y

Это равенство верно, если Х и Y сопоставимы. Следующий вид равенства записывался в виде

Х is E

Такое равенство выполняется, если Х сопоставим со значением арифметического выражения E. Мы также рассматривали равенства вида

Е1 =:= Е2

которые верны, если равны значения арифметических выражений Е1 и Е2. Наоборот, если значения двух арифметических выражений не равны, мы пишем

Е1 =/= Е2

Иногда нам может понадобиться более строгий вид равенства - буквальное равенство двух термов. Этот вид реализован еще одним встроенным предикатом, записываемым как инфиксный оператор '==':

Т1 == Т2

Это равенство выполняется, если термы Т1 и Т2 идентичны, т. е. имеют в точности одинаковую структуру, причем все соответствующие компоненты совпадают. В частности, должны совпадать и имена переменных. Отношение "не идентичны", дополнительное к данному, записывается так:

Tl \== T2

Приведем несколько примеров:

?- f( a, b) == f( а, b).
yes

?- f( a, b) == f( a, X).
nо

?- f( a, X) == f( a, Y).
no

?- X \== Y.
yes

?- t( X, f( a, Y) ) == t( X, f( a, Y) ).
yes

Давайте в качестве примера переопределим отношение

счетчик( Терм, Список, N)

из разд. 7.1. Пусть на этот раз N будет числом буквальных вхождений Терм'а в Список:

счетчик( _, [ ], 0).

        счетчик( Терм, [Голова | L], N) :-
                Терм == Голова, !,
                счетчик( Терм, L, N1),
                N is N1 + 1;
                счетчик( Терм, L, N).

В любой реализации Пролога обычно

Резюме

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

        var( X)                     Х - (неконкретизированная) переменная
        nonvar( X)               Х - не переменная
        atom( X)                  Х - атом
        integer( X)               Х - целое
        atomic( X)               Х - или атом, или целое
Термы можно синтезировать или разбирать на части:

        Терм =.. [Функтор [ СписокАргументов]
        functor( Терм, Функтор, Арность)
        arg( N, Терм, Аргумент)
        name( атом, КодыСимволов)
Программу на Прологе можно рассматривать как реляционную базу данных, которую можно изменять при помощи следующих процедур:

        аssert( Предл)                 добавляет предложение Предл к программе
        аssегtа( Предл)               добавляет в начало
        asserfz( Предл)               добавляет в конец
        rеtrасt( Предл)                удаляет предложение,
                                                  сопоставимое с предложением Предл
Все объекты, отвечающие некоторому заданному условию, можно собрать в список при помощи предикатов:

        bagof( X, Р, L)         L - список всех X, удовлетворяющих условию Р

        setof( X, Р, L)          L - отсортированный список всех X,
                                         удовлетворяющих условию Р

        findall( X, Р, L)        аналогичен bagof
repeat - средство управления, позволяющее порождать неограниченное число альтернатив для автоматического перебора.

Создание и декомпозиция термов: =.., functor, arg, name

Имеются три встроенные предиката для декомпозиции и синтеза термов: functor, arg и =.. . Рассмотрим сначала отношение =.. , которое записывается как инфиксный оператор. Цель

Терм =.. L

истинна, если L - список, начинающийся с главного функтора терма Терм, вслед за которым идут его аргументы. Вот примеры:

?- f( а, b) =.. L.
L = [f, а, b]

?- Т =.. [прямоугольник, 3, 5].
Т = прямоугольник( 3, 5)

?- Z =.. [р, X, f( X,Y) ].
Z = p( X, f( X,Y) )

Зачем может понадобиться разбирать терм на составляющие компоненты - функтор и его аргументы? Зачем создавать новый терм из заданного функтора и аргументов? Следующий пример показывает, что это действительно нужно.

Рассмотрим программу, которая манипулирует геометрическими фигурами. Фигуры - это квадраты, прямоугольники, треугольники, окружности в т.д. В программе их можно представлять в виде термов, функтор которых указывает на тип фигуры, а аргументы задают ее размеры:

        квадрат( Сторона)
        треугольник( Сторона1, Сторона2, Сторона3)
        окружность( R)

Одной из операций над такими фигурами может быть увеличение. Его можно реализовать в виде трехаргументного отношения

увел( Фиг, Коэффициент, Фиг1)

где Фиг и Фиг1 - геометрические фигуры одного типа (с одним в тем же функтором), причем параметры Фиг1 равны параметрам Фиг, умноженным на Коэффициент. Для простоты будем считать, что все параметры Фиг, а также Коэффициент уже известны, т. е. конкретизированы числами. Один из способов программирования отношения увел таков:

увел( квадрат( A), F, квадрат( А1) ) :-
A1 is F*A

увел( окружность( R), F, окружность( R1) ) :-
R1 is F*R1

увел( прямоугольник( А, В), F, прямоугольник( А1, В1)) :-
A1 is F*A, B1 is F*B.

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

Ниже приводится программа, в которой делается попытка (неудачная) справиться для начала хотя бы со всеми однопараметрическими фигурами при помощи одного предложения:

увел( Тип( Пар), F, Тип( Пар1) ):-
Пар1 is F*Пар.

Однако в Прологе подобные конструкции, как правило, запрещены, поскольку функтор должен быть атомом, и, следовательно, переменная Тип синтаксически не будет воспринята как функтор. Правильный метод - воспользоваться предикатом '=..' . Тогда процедура увел будет иметь обобщенную формулировку, пригодную для фигур любых типов:

        увел( Фиг, F, Фиг1):-
                Фиг =.. [Тип | Параметры],
                умножспис( Параметры, F, Параметры1),
                Фиг1 =.. [Тип | Параметры)].

умножспис( [ ], _, [ ]).

умножспис( [X | L], F, [X1 | L1] ) :-
X1 is F*X, умножспис( L, F, L1).

Наш следующий пример использования предиката '=..' связан с обработкой символьных выражений (формул), где часто приходится подставлять вместо некоторого подвыражения другое выражение. Мы определим отношение

подставить( Подтерм, Терм, Подтерм1, Терм1)

следующим образом: если все вхождения Подтерм'а в Терм заменить на Подтерм1, то получится Терм1. Например:

?- подставить( sin( x), 2*sin( x)*f( sin( x)), t, F ).
F = 2*t*f( t)

Под "вхождением" Подтерм'а в Терм мы будем понимать такой элемент Терм'а, который сопоставим с Подтерм'ом. Вхождения будем искать сверху вниз. Поэтому цель

?- подставить( а+b, f( а, А+В), v, F).

даст результат

        F = f( а, v)                                                 F = f( a, v+v)
        А = а                         а не                         А = а+b
        В = b                                                         В = а+b

При определении отношения подставить нам нужно рассмотреть несколько случаев и для каждого принять свое решение:

        если Подтерм = Терм, то Терм1 = Подтерм1;
        иначе если Терм - "атомарный" (не структура),
                    то Терм1 = Терм (подставлять нечего),
                    иначе подстановку нужно выполнить над
                                аргументами Tерм'a.

Эти правила можно превратить в программу, показанную на рис. 7.3.

Термы, полученные при помощи предиката '=..', разумеется, можно использовать и в качестве целей. Это дает возможность программе в процессе вычислений самой порождать и вычислять цели, структура которых не обязательно была известна заранее в момент написания программы. Последовательность целей, иллюстрирующая этот прием, могла бы выглядеть примерно так:

        получить( Функтор),
        вычислить( Списарг),
        Цель =.. [Функтор | Списарг],
        Цель

Здесь получить и вычислить - некоторые определенные пользователем процедуры, предназначенные для вычисления компонент цели. После этого цель порождается предикатом '=..', а затем активизируется при помощи простого указания ее имени Цель.

Некоторые реализации Пролога могут содержать требование, чтобы все цели, появляющиеся в программе, по своей синтаксической форме были либо атомами, либо структурами с атомом в качестве главного функтора. Поэтому переменная, вне

line();

%    Отношение
%
%    подставить( Подтерм, Терм, Подтерм1, Терм1)
%
%    состоит в следующем: если все вхождения Подтерм'а в Терм
%    заменить на Подтерм1, то получится Терм1.

% Случай 1: Заменить весь терм

подставить( Терм, Терм, Терм1, Терм1) :- !.

% Случай 2: нечего подставлять

подставить( _, Терм, _, Терм) :-
atomic( Терм), !.

% Случай 3: Проделать подстановку в аргументах

        подставить( Под, Терм, Под1, Терм1) :-
                Терм =.. [F | Арги],
                                        % Выделить аргументы
        подспис( Под, Арги, Под1, Арги1),
                                        % Выполнить над ними подстановку
        Терм1 =.. [F | Арги1].

        подспис( Под, [Терм | Термы], Под1, [Терм1 | Термы1]) :-
                 подставить( Под, Терм, Под1, Терм1),
                 подспис( Под, Термы, Под1, Термы1).

line();

Средства управления

К настоящему моменту мы познакомились с большинством дополнительных средств управления, за исключением repeat (повторение). Здесь мы для полноты приводим список всех таких средств. отсечение, записывается как '!', предотвращает перебор, введено в гл. 5. fail - цель, которая всегда терпит неудачу. true - цель, которая всегда успешна. not( P) - вид отрицания, который всегда ведет себя в точном соответствии со следующим определением:

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

Некоторые проблемы, связанные с отсечением и not детально обсуждались в гл. 5. саll( P) активизирует цель Р. Обращение к саll имеет успех, если имеет успех Р. repeat - цель, которая всегда успешна. Ее особое свойство состоит в том, что она недетерминирована, поэтому всякий раз, как до нее доходит перебор, она порождает новую ветвь вычислений. Цель repeat ведет себя так, как если бы она была определена следующим образом:

        repeat.
        repeat :- repeat.

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

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

Пусть эта процедура переупорядочивает слагаемые

Упражнения

    Напишите процедуру упростить для упрощения алгебраических сумм, в которых участвуют числа и символы (строчные буквы). Пусть эта процедура переупорядочивает слагаемые так, чтобы символы предшествовали числам. Вот примеры ее использования:
        ?- упростить( 1 + 1 + а, Е).
        Е = а + 2
        ?- упростить( l + a + 4 + 2 + b + с, E).
        Е = а + b + с + 7
        ?- упростить( 3 + х + х, Е).
        Е = 2*х + 3
Определите процедуру
        добавить( Элемент, Список)
для добавления нового элемента в список. Предполагается, что все элементы, хранящиеся в списке, - атомы. Список состоит из всех хранящихся в нем элементов, а за ними следует хвост, который не конкретизирован и служит для принятия новых элементов. Пусть, например, в списке уже хранятся а, b и с, тогда
        Список = [а, b, с | Хвост]
где Хвост - переменная. Цель
        добавить( d, Список)
вызовет конкретизацию
        Xвoст = [d | НовыйХвост] и
        Список = [а, b, с, d | НовыйХвост]
Таким способом структура может наращиваться, включая в себя новые элементы. Определите также соответствующее отношение принадлежности.
Посмотреть ответ

чтобы он принимал значение истина,

Упражнения

    Определите предикат конкрет(Терм) так, чтобы он принимал значение истина, когда в Tepм'e нет ни одной неконкретизированной переменной.
    Процедура подставить из данного раздела производит, при наличии разных вариантов, лишь самую "внешнюю" подстановку.
Модифицируйте эту процедуру так, чтобы она находила все возможные варианты при помощи автоматического перебора. Например:
        ?- подставить( a+b, f( A+B), новый, НовыйТерм).
        А = а
        В = b
        НовыйТерм = f( новый);
        А = а+b
        В = а+b
        НовыйТерм = f( новый + новый)
Наша исходная версия нашла бы только первый из этих двух ответов.
    Определите отношение
        включает( Tepмl, Терм2)
которое выполняется, если Терм1 является более общим, чем Терм2. Например:
        ?- включает( X, с).
        yes
        ?- включает( g( X), g( t( Y))).
        yes
        ?- включает f( X,X), f( a,b)).
        no

который удаляет из базы данных

Упражнения

   (а)         Напишите вопрос к пролог-системе, который удаляет из базы данных всю таблицу произв.
           (b)         Измените этот вопрос так, чтобы он удалил из таблицы только те строки, в которых произведение равно 0.
        Определите отношение
        копия( Терм, Копия)
которое порождает такую копию Терм'а Копия, в которой все переменные переименованы. Это легко сделать, используя assert и retract.

для вычисления множества всех подмножеств

Упражнения

Используя bagof, определите отношение
        множподмножеств( Мн, Подмн)
для вычисления множества всех подмножеств данного множества (все множества представлены списками).
    Используя bagof, определите отношение
        копия( Терм, Копия)
чтобы Копия представляла собой Терм, в котором все переменные переименованы.