Prolog — cut (отсечение) и fail

      Комментарии к записи Prolog — cut (отсечение) и fail отключены

Помечено: ,

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 4 мес. назад.

  • Автор
    Сообщения
  • #2604

    Konstantin_S
    Участник

    Помогите разобраться с применением в прологе cut и fail, для того, чтобы контролировать вывод результата.

  • #2605

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

    1. введение в логическое программирование — дано короткое описание поведения оператора cut. Кроме того, там можно посмотреть чем отличается предикат от правила, например;
    2. принципы построения Prolog-программ — приведены несколько примеров с использованием отсечения, при этом показываются деревья логического вывода (в которые преобразуется программа). По деревьям проще отследить как выполняется поиск решений интерпретатором и, следовательно, изменения, которые оператор cut в этот поиск вносит.

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

    dump_db:-
      edge(From, To),
      write([From, To]), nl,
      fail.
    dump_db.

    Для этого примера, дерево логического вывода будет следующим:

    prolog_fail_operator

    Предикат dump_db состоит из двух правил, первое выбирает дугу, выводит ее на экран и выполняет fail. Оператор fail завершается неудачей, в связи с чем выполняется откат (попытка получить другие решения от ранее вычисленных целей).
    Сначала управление вернется функции write, однако она является детерминированной (всегда дает только одно решение), поэтому получить других решений с нее нельзя и откат продолжится — фокус управления получит предикат edge.
    До этого, предикат edge вернул нам первую запись базы данных (дугу a->b), но он может вернуть и другие решения, поэтому переменные From и To связываются теперь с дугой (a->c).
    Выполняется вывод этой дуги и опять оператор fail. Процесс повторится столько раз, сколько дуг записано в базе данных. После вывода последней дуги откат к предикату edge не сможет дать новых решений и первое правило предиката dump_db завершится неудачей. В связи с этим будет выполнен переход ко второму правилу (ведь они соединены оператором точка, т.е. логическим ИЛИ). Второе правило не содержит кода и всегда завершается успешно.
    Таким образом предикат dump_db может вывести на экран все содержимое базы данных и завершиться успешно.

    Сочетание операторов отсечения и fail используется в случаях, когда нужно остановить поиск с возвратами и при этом завершить выполнение неудачей. Из примеров, приведенных выше было видно, что обычный вызов fail не даст такого эффекта, т.к. будет запущен поиск альтернативных решений, который нужно предварительно запретив оператором cut. Такое сочетание используется достаточно часто, например:

    1. при обработке ошибок. Если на вход функции поданы данные, обработка которых может привести к ошибкам (например зацикливанию) — нужно их отдельно обработать до запуска основных вычислений. Один из способов (не лучший, но применяется) — в отдельном правиле проверить корректность данных и в случае ошибки выполнить !, fail чтобы запретить переход к основной части вычислений. Такой подход использовался например в функции генерации списка случайных чисел, а также в функции between, выполняющей перебор чисел в диапазоне для устранения зацикливания;
    2. может являться частью логики функции. Если задача функции — выполнять какую-либо проверку и завершаться успешно лишь на некоторых наборах данных, то комбинация отсечение, fail используется для реализации этой логики. Примеры: при раскраске плоской карты (графа) выполняется проверка корректности раскраски, которая должна завершаться неудачей если в графе есть смежные вершины одного цвета; в лексикографическом сравнении строк комбинация !, fail используется дважды.

Для ответа в этой теме необходимо авторизоваться.