Бесплатный курс по Prolog. Зарегистрируйтесь для отслеживания прогресса →

Prolog: Backtracking

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

В предыдущем уроке мы изучили предикаты конъюнкции и дизъюнкции. Подумайте, что выведет следующий код:

write('Hello, '), write('Hello, ') ; write('Hexlet!'), write('World!').
  Hello, Hello,
  true ;
  Hexlet!World!
  true.

Как говорилось в предыдущем уроке, конъюнкция – логическое "И", а дизъюнкция – логическое "ИЛИ".
Благодаря конъюнкции первые и последние два оператора были выполнены вместе, а полученные результаты были выведены раздельно. Код выше можно прочитать так:
Выведи строку 'Hello, ' И строку 'Hello, ' ИЛИ выведи строку 'Hexlet!' И выведи строку 'World!'. Предикат write возвращает "ИСТИНУ" (true). Таким образом Prolog нашел два подходящих решения.

А что выведет следующий код?

write(p), (write(q) ; write(r)), write(t).
  pqt
  true ;
  rt
  true.

Почему вывод получился именно таким и почему буква 't' вывелась два раза, если в коде только один вывод этой буквы? Все дело в том, как Prolog интерпретирует программу. Фактически программа будет находить все возможные решения, которые в конечном итоге подтвердят утверждение.
Для выполнения этой задачи Prolog использует поиск с возвратом (backtracking). Программа перебирает все возможные решения, возвращаясь в разные точки, в которых могло произойти разветвление решения на разные варианты.

Давайте разберем пример выше:

  1. Prolog выполняет предикат write(p) и переходит к следующему предикату
  2. Далее Prolog видит предикаты write(q) ; write(r). Они соединены логическим "ИЛИ", которое разбивает решение на 2 разных. Фактически это означает, что программа может выполнить один предикат "ИЛИ" другой
  3. Далее Prolog видит предикат write(t) и выполняет его. Программа должна бы завершиться, но мы помним, что у нас был предикат "ИЛИ", который разделил решение на 2 разных
  4. Prolog возвращается в к предикату ;, но выполняет уже следующий предикат write(r), а за ним и оставшийся предикат write(t)

Совет: вывести все решения сразу можно, дописав в конце , nl, fail.. Получится такой код:

write(p), (write(q) ; write(r)), write(t), nl, fail.

Задание

Расставьте предикаты , и ; так, чтобы программа вывела:

  a
  true ;
  bc
  true.
Упражнение не проходит проверку — что делать? 😶

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

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

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя 🤔

Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно 🙄

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

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

Полезное


Нашли ошибку? Есть что добавить? Пулреквесты приветствуются https://github.com/hexlet-basics
Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе