Давайте рассмотрим как определенные ранее определения( аха ) применимы к нашему примеру. Когда мы запускаем запрос
?- edge(a, X).
Пролог просматривает все связанные с edge факты чтобы найти первый факт, который унифицируется с запросом. Выясняется, что в нашей программе почти что самый первый факт edge(a, b) унифицируется с запросом, т.к. подстановка {X = b} унифицирует два атома edge(a, X) и edge(a, b). Подстановка соответствует ответу возвращаемому системой Пролог.
Ранее мы отметили, что для запроса
?- edge(a, X).
Как узел b, так и e могут быть оправданиями (ну, корректными ответами). Пролог возвращает b просто потому что факт edge(a, b) раньше встречается в программе. Что делать с е, если мы всегда получаем b? Вот тут начинает играть механизм бэктрекинга. Когда Когда Пролог возвращает ответ X = b пользователя спрашивают, искать ли другие ответы (нажатием точки с запятой). Взаимодействие между юзером и Прологом выглядит так
?- edge(a, X).
Пролог отвечает
X = b; (введем точку с запятой)
Пролог пробует ответить снова на вопрос и
X = e
Если пользователь продолжит вводить точку с запятой после каждого ответа, возвращенного Прологом, все возможные ответы будут выведены.
конъюнктивные запросы
Давайте узнаем, как конъюнктивные запросы обрабатываются. Это запросы, которые содержат несколько атомов. В случае основных запросов, мы уже обсудили как Пролог будет себя вести. Давайте рассмотрим не основной запрос.
?- edge(a, X),edge(b, Y).
Так как нет общих переменных в запросе, Пролог пытается разрешить каждый атом независимо. Единственной важной частью является то, что атомы раррешаются слева направо. В этом случае, Пролог сначала пробует решить edge(a, X). Как мы только что видели, это унифицируется с фактом edge(a, b) ({X = b}). Далее пытаемся атом edge(b, d). Поиск среди оставшихся фактов связанных с edge приводит к нахождению первого униф. факта edge(b, d) ({Y = d}). Объединяя два унификатора, получаем итоговую подстановку {X = b, Y = d}. Это ответ возвращенный Пролог.
?- edge(a, X), edge(b, Y).
Пролог ответит
X = b, Y = d
Интересным вопросом является “что произойдет, если юзер наберет точку с запятой”. Это приводит к использованию бэктрекинга, порядок в котором он происходит основан на идее “первый пробовался, последний будет забэктречен”. Или можно назвать это “последний пробовался, первым будет забэктречен”. Основная идея состоит в том, что во время бэктрекинга Пролог откатывает последний атом (или наиболее правый) в запросе для которого есть альтернативное решение. Оглядываясь на нашу программу мы можем увидеть, что вдобавок к факту edge(b, d) факт edge(b, c) также унифицируется с атомом edge(b, Y) в запросе с унификатором {Y = c}. Пролог дает такой ответ
X = b, Y = C
как второе решение. Заметьте, что в этом случае первый атом edge(a, X) не откатывается. Далее, предположим, что мы опять нажали точку с запятой, запрашивая еще один бэктрекинг. Снова, это приводит к тому, что edge(b, Y) пытается заново ответиться (:D). Однако, на этот раз нет никакого еще одного ответа (мы исчерпали все возможные решения для edge(b, Y)). Это приводит к тому, что Пролог откатывается на один атом и пробует ответить на edge(a, X). Это приводит к новой привязке {X = E}. На данный момент, Пролог не еще не закончил. Далее он обрабатывает запрос, чтобы снова решить edge(b, Y), давая вот такой ответ
X = e, Y = d
Наконец, еще один запрос на новое решение приводит к
X = e, Y = c
не основные запросы
В случае не основного конъюнктивного запроса, содержащего переменные, которые разделены между атомами в запросе, нам нужно модифицировать наше описание работы Пролога. Предположим есть такой запрос
?- Atom1, Atom2, ..., Atomn.
Порядок в котором атомы “пробуются” остается таким же, слева направо. Однако, каждый раз когда атом унифицируется с фактом программы, унификатор должен быть применен к оставшимся атомам в запросе, перед тем как продолжать. Например, если запрос – это вопрос вида
?- edge(a, X), edge(X, b).
тогда разрешение первого атома edge(a, X) приводит к унификации с фактом edge(a, b) используя унификатор Om = {X = b}. Перед тем как пробовать следующий атом edge(X, b) мы сначала должны применить эту подстановку. Вычисляя edge(X, b)Om мы получаем edge(b, b). Это запрос, который Пролог пытается разрешить следующим. Так как последний атом в запросе для которого есть альтернативное решение – это edge(a, X), он переразрешается, вызывая унификацию с фактом edge(a, e). Новый унификатор Om = {X = e}. И снова, она применяется к атому edge(X, b). Мы имеем edge(X, b)Om = edge(e, b). Это основной терм, который совпадает с фактом edge(e, b) в программе. Получается, что запрос успешен и ответ возвращаемый Прологом
X = e
Программирование в Пролог обеспечивает большую гибкость чем на Scheme or Pascal/C, когда дело касается вычислений, которые могут производить многочисленные (возможно бесконечные) возможные результаты (решения), благодаря механизму бэктрекинга. Это позволяет возвращать множество ответов, а не только один. Однако, это означает, что все что мы можем сделать в других языках – мы можем сделать и в Прологе. Упражнение ниже предлагает решить задачу которая не функциональна: Для заданного ввода могут существовать несколько выводов. Этот тип задач называется реляционным. [Можете ли вы узнать как реализовать функцию в Пролог? Попробуйте стандартный факториал.]
Комментариев нет:
Отправить комментарий