Управление перебором. Отсечение

3.3. Предикат findall и конструкция [… || …]

Предикат findall/3 собирает значения параметра в список. Его первый аргумент — это вычисляемый параметр, второй — предикат, из которого он находится, третий — имя переменной, которая обозначает список значений параметра. Обобщением этой конструкции является конструкция [… || …]. Данная конструкция соответствует в математике заданию множества с помощью определяющего свойства, например, в виде $$\{x|x\in M~ или ~x\in N\}$$, где $$M$$ и $$N$$ — некоторые множества. Ниже приведены примеры использования предиката findall и конструкции [… || …].

List = [tuple(X, Y) || male(X), female(Y)].

В объявлении доменов термов с функторами tuple, которые могут иметь от 2 до 12 аргументов, нет необходимости, они объявлены в классе core. Напомним, что функтор состоит из имени и арности, поэтому функторы с одинаковым именем и разной арностью являются разными функторами. Само слово "tuple" в литературе используется для обозначения кортежа, или n-ки, например, термин 4-tuple означает "четверку" — упорядоченный набор из четырех элементов.

Упражнение 1.

Найдите результат вызова последней цели (декартово произведение), если набор фактов имеет вид:

male("Иван").
male("Павел").
male("Петр").

female("Мария").
female("Анна").

Обратите внимание на порядок следования элементов в списке List.

3.4. Режимы детерминизма предикатов

Для того чтобы компилятор языка Visual Prolog проводил более быстрые вычисления, при объявлении предикатов указывается режим детерминизма.

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

Режим детерминизма определяется количеством возможных решений при вызове предиката (т. е. тем, нужен ли откат) и тем, может ли он быть неуспешным. Ключевые слова, с помощью которых указываются режимы детерминизма, перечислены в табл. 3.1.

Компилятор Visual Prolog автоматически вычисляет режим детерминизма предиката с помощью его определения в программе и сообщает пользователю об ошибке, если объявленный режим детерминизма предиката не соответствует фактическому определению предиката. Иногда он ограничивается предупреждением.

Предикат succeed() является примером предиката с режимом procedure, предикат fail имеет режим failure.

Предикаты с режимом детерминизма procedure, называют процедурами. Если предикат не может порождать более одного решения, то он называются детерминированным, а если может, то недетерминированным.

По умолчанию используется режим procedure, если предикат объявляется в разделе (class) predicates, и режим nondeterm, если предикат объявляется в разделе (class) facts.

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

В объявлении предиката требуется указывать не только режим детерминизма, но и поток параметров (flow pattern). В нем описывается, какие аргументы предиката при его вызове являются входными, а какие выходными. Используется обозначение (i) для входного аргумента и обозначение (o) для выходного. Произвольный поток параметров обозначается с помощью ключевого слова anyflow. По умолчанию все аргументы предиката являются входными. Поток параметров указывается в виде последовательности (i,o,o,…) символов i или o, соответствующих аргументам предиката, либо с помощью слова [out], которое ставится после имени домена аргумента предиката (см. листинг 3.1).

Один и тот же предикат может иметь разные потоки параметров и режимы детерминизма. В этом случае они перечисляются последовательно. Например,

parent: (string, string) nondeterm (o,o) (i,o) (o,i) determ.

Следующие две программы посвящены решению логических задач.

Пример 1. "Кино". Аня, Боря, Витя, Гриша и Даша решают, пойти ли им в кино. Ситуация описывается следующими высказываниями:

Нужно определить, кто пойдет в кино.

class predicates
    proposition: (integer, integer, integer) nondeterm.
    indicator: (integer Индикатор [out]) multi.
    solution: (integer, integer, integer, integer, integer)
        nondeterm (o,o,o,o,o).
clauses
    indicator(0).     % не пойдет
    indicator(1).      % пойдет

    % если А пойдет, то и Б пойдет
    proposition(1, А, Б):- А = 1, Б = 1; А = 0.
    % хотя бы кто-то из В и Г пойдет
    proposition(2, В, Г):- В = 1; Г = 1.
    % пойдет либо Б, либо Д, но не оба вместе
    proposition(3, Б, Д):- Б = 1, Д = 0; Б = 0, Д = 1.
    % В и Д либо оба пойдут, либо оба не пойдут
    proposition(4, В, Д):- В = 1, Д = 1; В = 0, Д = 0.

    solution(А, Б, В, Г, Д):-
        indicator(А), indicator(Б),
        proposition(1, А, Б),
        indicator(В), indicator(Г),
        proposition(2, В, Г),
        indicator(Д),
        proposition(3, Б, Д),
        proposition(4, В, Д),
        proposition(1, Г, А),
        proposition(1, Г, В).

    run():-
        solution(А, Б, В, Г, Д),
            write("Aня=", А, ", Боря=", Б, ", Витя=", В, ", Гриша=", Г,
                ", Даша=", Д), nl,
        fail;
        _ = readLine().

Упражнение 2. Выразите условия, которым должны удовлетворять значения переменных (см. листинг 3.1), одним равенством или неравенством для каждого высказывания. Например, условие "если А = 1, то Б = 1" для А, Б $$\in$$ {0, 1} равносильно любому из условий:

А * Б = А или Б >= А.

После этого упростите программу, удалив предикат proposition.

Пример 2. "Шкатулки". Перед претендентом на руку Порции находятся три шкатулки — золотая, серебряная и свинцовая. Претендент должен угадать, не открывая шкатулок, в какой из них лежит ее портрет. На крышке каждой из шкатулок имеются два высказывания. На золотой шкатулке:

На серебряной шкатулке:

На свинцовой шкатулке:

На одной из шкатулок оба высказывания истинны, на другой оба ложны, на третьей одно истинно, другое ложно. В какой шкатулке находится портрет?

class predicates
    box: (symbol Color) multi (o).
    proposition: (symbol, integer, symbol) determ.
    statement:  (symbol, integer, symbol, integer Истинность)
        nondeterm (i,i,i,o) determ.
    solution: (symbol ЦветШкатулкиСПортретом) nondeterm (o).
clauses
    box("золото").
    box("серебро").
    box("свинец").

    proposition("золото", 1, PortraitBoxColor):- 
        PortraitBoxColor <> "золото".
    proposition("золото", 2, "серебро").

    proposition("серебро", 1, PortraitBoxColor):- 
        PortraitBoxColor <> "золото".
    proposition("серебро", 2, "свинец").

    proposition("свинец", 1, PortraitBoxColor):- 
        PortraitBoxColor <> "свинец".
    proposition("свинец", 2, "золото").

    statement(Box, Number, PortraitBoxColor, 1):-
        proposition(Box, Number, PortraitBoxColor).
    statement(Box, Number, PortraitBoxColor, 0):-
        not(proposition(Box, Number, PortraitBoxColor)).

    solution(PortraitBoxColor):-
        box(PortraitBoxColor),
        box(Color1),
        statement(Color1, 1, PortraitBoxColor, 1),
        statement(Color1, 2, PortraitBoxColor, 1),
        box(Color2), Color2 <> Color1,
        statement(Color2, 1, PortraitBoxColor, 0),
        statement(Color2, 2, PortraitBoxColor, 0),
        box(Color3), Color3 <> Color1, Color3 <> Color2,
        statement(Color3, 1, PortraitBoxColor, X),
        statement(Color3, 2, PortraitBoxColor, 1 - X).

    run():-
        solution(PortraitBoxColor),
            write("Портрет в шкатулке цвета: ", PortraitBoxColor),
        fail;
        _ = readLine().

Упражнение 3. Измените программу так, чтобы кроме решения она выводила цвет шкатулки, на которых оба высказывания истинны, цвет шкатулки, на которой оба высказывания ложны, и цвет шкатулки, на которой одно высказывание истинно, а другое ложно.

В приведенной ниже программе описываются сведения, полученные в процессе расследования убийства [2, 7, 16]. Не рекомендуется запускать программу без ее предварительного изучения.

domains
    sex = m; f.

class facts
    person: (symbol Name, integer Age, sex, symbol Occupation).
    had_affair: (symbol Name, symbol Name).
    killed_with: (symbol Name, symbol Object).
    killed: (symbol Name).
    motive: (symbol Vice).
    smeared_in: (symbol Name, symbol Substance).
    owns: (symbol Name, symbol Object).
    operates_identically: (symbol Object, symbol Object).

class predicates
    owns_probably: (symbol Name, symbol Object) nondeterm.
    suspect: (symbol Name) nondeterm.
    killer: (symbol Name) nondeterm (o).

% Facts about the murder
clauses
    person("Allan", 25, m, "football player").
    person("Allain", 35, m, "butcher").
    person("John", 30, m, "pickpocket").
    person("Bert", 55, m, "carpenter").
    person("Barbara", 30, f, "hairdresser").

    had_affair("Barbara", "John").
    had_affair("Barbara", "Bert").
    had_affair("Susan", "John").

    killed_with("Susan", "club").

    killed("Susan").

    motive("money").
    motive("jealousy").
    motive("righteousness").

    smeared_in("Susan", "blood").
    smeared_in("Allan", "mud").
    smeared_in("Allain", "blood").
    smeared_in("John", "chocolate").
    smeared_in("Barbara", "chocolate").
    smeared_in("Bert", "blood").

    owns("Bert", "wooden leg").
    owns("John", "pistol").

% Background knowledge
    operates_identically("wooden leg", "club").
    operates_identically("bar", "club").
    operates_identically("pair of scissors", "knife").
    operates_identically("football boot", "club").

    owns_probably(X, "football boot"):-
        person(X, _, _, "football player").
    owns_probably(X, "pair of scissors"):-
        person(X, _, _, "hairdresser").
    owns_probably(X, "knife"):-
        person(X, _, _, "butcher").
    owns_probably(X, Object):-
        owns(X, Object).

% Suspect all those who own a weapon
% with which Susan could have been killed.
    suspect(X):-
        killed(Woman),
        killed_with(Woman, Weapon),
        operates_identically(Object, Weapon),
        owns_probably(X, Object).

% Suspect men who have had an affair with Susan.
    suspect(X):-
        motive("jealousy"),
        person(X, _, m, _),
        killed(Woman),
        had_affair(Woman, X).

% Suspect females who have had an affair
% with someone that Susan knew.
    suspect(X):-
        motive("jealousy"),
        person(X, _, f, _),
        had_affair(X, Man),
        killed(Woman),
        had_affair(Woman, Man).

% Suspect pickpockets whose motive could be money.
    suspect(X):-
        motive("money"),
        person(X, _, _, "pickpocket").

    killer(Killer):-
        person(Killer, _, _, _),
        killed(Killed),
        Killed <> Killer,  % It is not a suicide
        suspect(Killer),
        smeared_in(Killer, Goo),
        smeared_in(Killed, Goo).

    run():-
        killer(Killer),
            write("Killer is ", Killer), nl,
        fail;
        _ = readLine().

Упражнение 4. Прочитайте программу "Кто убийца?" (см. листинг 3.3), опишите сюжет драмы и, не запуская программу, для каждого участника описанных событий выясните, является ли он убийцей. Ответ подробно обоснуйте.

Ниже рассматриваются три способа определения максимума двух чисел: без отсечений, с зеленым отсечением и с красным отсечением (см. листинг 3.4). На рис. 3.1 (a) и (b) показаны деревья поиска для предиката maximum1, в определении которого нет отсечений.

Дерево поиска для предиката maximum2, в определении которого используется зеленое отсечение, сокращается в случае, когда значение первого аргумента не меньше, чем значение второго (рис. 3.2 (a)). Дерево поиска для предиката maximum, в определении которого имеется красное отсечение, сокращается и в случае, когда значение первого аргумента меньше значения второго (рис. 3.2 (b)).

На практике обычно используется красное отсечение, которое позволяет существенно сократить вычисления.

class predicates
    maximum1: (integer, integer, integer [out]) nondeterm.
    maximum2: (integer, integer, integer [out]) determ.
    maximum: (integer, integer, integer [out]).
clauses
    maximum1(X, Y, X):- X >= Y. % вариант без отсечений
    maximum1(X, Y, Y):- X < Y.

    maximum2(X, Y, X):- X >= Y, !. % зеленое отсечение
    maximum2(X, Y, Y):- X < Y.

    maximum(X, Y, X):-  X >= Y, !. % красное отсечение
    maximum(_, Y, Y).

    run():-
        maximum1(3, 7, M),  % maximum1(7, 3, M),
            write(M), nl,
        fail;
        maximum2(3, 7, M),
        write(M), nl,
        fail;
        maximum(3, 7, M),
        write(M),
    _ = readLine().

Упражнение 5. Используя предикат maximum/3 (см. листинг 3.4), определите предикат maximum/4, вычисляющий максимальное из трех чисел.

Следующая программа посвящена решению квадратных уравнений с действительными коэффициентами в действительных числах. Коэффициенты уравнения вводятся пользователем с клавиатуры. Решением является список корней уравнения. В предикат solution, который находит решение уравнения по его коэффициентам, добавлен еще один аргумент — метка. С помощью метки определяется предикат print, который печатает результат.

class predicates
    solution: (real A, real B, real C, real* [out], integer Mark [out]).
    roots: (real A, real B, real D, real* Решение [out]).
    print: (integer, real* Решение).
clauses
    solution(0, 0, 0, [], -1):- !.
    solution(0, 0, _, [], 0):- !.
    solution(0, B, C, [-C/B], 1):- !.
    solution(A, B, C, L, 2):-
        roots(A, B, B^2 - 4 * A * C, L).

    roots(A, B, 0, [-B/(2 * A)]):- !.
    roots(_, _, D, []):- D < 0, !.
    roots(A, B, D, [(-B + Q)/(2 * A), (-B - Q)/(2 * A)]):-
        Q = math::sqrt(D * 1).

    print(-1, _):- !, write("Решение - любое число").
    print(0, _):- !, write("Уравнение линейное, решений нет.").
    print(1, [X]):- !, write("X = ", X).
    print(2, [X]):- !, write("X1 = X2 = ", X).
    print(2, [X1, X2]):- !, write("X1 = ", X1, ", X2 = ", X2).
    print(_, _):- write("Решений нет.").

    run():-
        write("Введите коэффициенты уравнения "
            "A*X^2 + B*X + C = 0\nA = "),
        A = read(), clearInput(),
        write("B = "),
        B = read(), clearInput(),
        write("C = "),
        C = read(), clearInput(),
        solution(A, B, C, L, Mark),
        print(Mark, L),
        _ = readLine().

Предикат read считывает терм любого домена. При этом буфер ввода полностью не очищается, для этого вызывается предикат clearInput. Предикат sqrt/1 возвращает квадратный корень из неотрицательного числа (ureal). Умножение дискриминанта на единицу в выражении Q = math::sqrt(D * 1) используется для преобразования типа: значение переменной D принадлежит домену real, а значение аргумента предиката sqrt должно принадлежать домену math::ureal. Выполнение операции умножения на единицу вынуждает компилятор искать нужный тип для результата.

Для преобразования типов предназначены предикаты сonvert и tryConvert. Первый из них всегда успешен. Если преобразование невозможно, то возбуждается исключение. Второй предикат детерминированный. В случае невозможности преобразоваия он принимает значение ложь.

Можно заменить строку Q = math::sqrt(D * 1) в программе парой строк:

D1 = convert(math::ureal, D),
Q = math::sqrt(D1).

Упражнение 6. Напишите программу, которая решает линейные уравнения. Коэффициенты вводятся пользователем с клавиатуры.

В программе, приведенной ниже, генерируются все двузначные числа. Кроме этого, с помощью конструкции […||…] четные двузначные числа собираются в список.

class facts
    digit: (integer).

class predicates
    twoDigitNumber: (integer) nondeterm (o).
clauses
    digit(0).    digit(1).    digit(2).    digit(3).    digit(4).
    digit(5).    digit(6).    digit(7).    digit(8).    digit(9).

    twoDigitNumber(10 * A + B):-
        digit(A),
            A > 0,
            digit(B).

    run():-
        twoDigitNumber(X),
            write(X), nl,
        fail;
        write("Список четных двузначных чисел:\n"),
        L = [10 * A + B || digit(A), A > 0, digit(B), B mod 2 = 0],
        write(L),
        _ = readLine().

Упражнение 7.

Упражнения

Кто из сестер месил тесто, кто готовил начинку, а кто выпекал пирог?

Определите, кто из них кем был на самом деле.

упорядочение(X, Y, Min, Max);
упорядочение(X, Y, Z, Min, Ave, Max).