Prolog: Backtracking
Программы на языке Prolog выполняются не так, как в других языках программирования. Как уже говорилось в предыдущих уроках, задача Prolog программы доказать какое–либо утверждение и для этого используются логические операции, которые были рассмотрены в предыдущем уроке. В этом уроке мы рассмотрим, как Prolog выполняет программы и использует алгоритм поиска с возвратом.
В предыдущем уроке мы изучили предикаты конъюнкции и дизъюнкции. Подумайте, что выведет следующий код:
write('Hello, '), write('Hello, ') ; write('Hexlet!'), write('World!').Как говорилось в предыдущем уроке, конъюнкция – логическое "И", а дизъюнкция – логическое "ИЛИ".
Благодаря конъюнкции первые и последние два оператора были выполнены вместе, а полученные результаты были выведены раздельно. Код выше можно прочитать так:
Выведи строку 'Hello, ' И строку 'Hello, ' ИЛИ выведи строку 'Hexlet!' И выведи строку 'World!'. Предикат write возвращает "ИСТИНУ" (true). Таким образом Prolog нашел два подходящих решения.
А что выведет следующий код?
write(p), (write(q) ; write(r)), write(t).Почему вывод получился именно таким и почему буква 't' вывелась два раза, если в коде только один вывод этой буквы? Все дело в том, как Prolog интерпретирует программу. Фактически программа будет находить все возможные решения, которые в конечном итоге подтвердят утверждение. Для выполнения этой задачи Prolog использует поиск с возвратом (backtracking). Программа перебирает все возможные решения, возвращаясь в разные точки, в которых могло произойти разветвление решения на разные варианты.
Давайте разберем пример выше:
- Prolog выполняет предикат
write(p)и переходит к следующему предикату - Далее Prolog видит предикаты
write(q) ; write(r). Они соединены логическим "ИЛИ", которое разбивает решение на 2 разных. Фактически это означает, что программа может выполнить один предикат "ИЛИ" другой - Далее Prolog видит предикат
write(t)и выполняет его. Программа должна бы завершиться, но мы помним, что у нас был предикат "ИЛИ", который разделил решение на 2 разных - Prolog возвращается в к предикату
;, но выполняет уже следующий предикатwrite(r), а за ним и оставшийся предикатwrite(t)
Совет: вывести все решения сразу можно, дописав в конце
, nl, fail.. Получится такой код:
write(p), (write(q) ; write(r)), write(t), nl, fail.Задание
Расставьте предикаты , и ; так, чтобы программа вывела:
Полезное
Prolog: Backtracking
Программы на языке Prolog выполняются не так, как в других языках программирования. Как уже говорилось в предыдущих уроках, задача Prolog программы доказать какое–либо утверждение и для этого используются логические операции, которые были рассмотрены в предыдущем уроке. В этом уроке мы рассмотрим, как Prolog выполняет программы и использует алгоритм поиска с возвратом.
В предыдущем уроке мы изучили предикаты конъюнкции и дизъюнкции. Подумайте, что выведет следующий код:
write('Hello, '), write('Hello, ') ; write('Hexlet!'), write('World!').Как говорилось в предыдущем уроке, конъюнкция – логическое "И", а дизъюнкция – логическое "ИЛИ".
Благодаря конъюнкции первые и последние два оператора были выполнены вместе, а полученные результаты были выведены раздельно. Код выше можно прочитать так:
Выведи строку 'Hello, ' И строку 'Hello, ' ИЛИ выведи строку 'Hexlet!' И выведи строку 'World!'. Предикат write возвращает "ИСТИНУ" (true). Таким образом Prolog нашел два подходящих решения.
А что выведет следующий код?
write(p), (write(q) ; write(r)), write(t).Почему вывод получился именно таким и почему буква 't' вывелась два раза, если в коде только один вывод этой буквы? Все дело в том, как Prolog интерпретирует программу. Фактически программа будет находить все возможные решения, которые в конечном итоге подтвердят утверждение. Для выполнения этой задачи Prolog использует поиск с возвратом (backtracking). Программа перебирает все возможные решения, возвращаясь в разные точки, в которых могло произойти разветвление решения на разные варианты.
Давайте разберем пример выше:
- Prolog выполняет предикат
write(p)и переходит к следующему предикату - Далее Prolog видит предикаты
write(q) ; write(r). Они соединены логическим "ИЛИ", которое разбивает решение на 2 разных. Фактически это означает, что программа может выполнить один предикат "ИЛИ" другой - Далее Prolog видит предикат
write(t)и выполняет его. Программа должна бы завершиться, но мы помним, что у нас был предикат "ИЛИ", который разделил решение на 2 разных - Prolog возвращается в к предикату
;, но выполняет уже следующий предикатwrite(r), а за ним и оставшийся предикатwrite(t)
Совет: вывести все решения сразу можно, дописав в конце
, nl, fail.. Получится такой код:
write(p), (write(q) ; write(r)), write(t), nl, fail.Задание
Расставьте предикаты , и ; так, чтобы программа вывела:
Полезное
Ваше упражнение проверяется по этим тестам
:- style_check(-singleton).
:- dynamic error_happened/1.
:- assertz(error_happened('OK')).
user:message_hook(Term, error, _Lines) :-
retract(error_happened('OK')),
assertz(error_happened(error)),
fail.
:- include(main).
:- forall(call(writer), (nl, write('true ;'), nl)).
:- begin_tests(backtracking).
test(040, Output == 'a\ntrue ;\nbc\ntrue ;\n') :-
with_output_to(atom(Output), forall(call(writer), (nl, write('true ;'), nl))),
error_happened(X).
:- end_tests(backtracking).Решение учителя откроется через:
20:00
