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.