Откат - это механизм, который Пролог использует для нахождения дополнительных фактов и правил, необходимых при вычислении цели, если текущая попытка вычислить цель оказалась неудачной. Пролог использует откат для того, чтобы попробовать новые пути к решению. Пролог использует всю доступную информацию для выбора подходящего направления.

Типичная программа на Прологе содержит факты и правила, основанные на самых различных взаимосвязях предикатов.

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

Цель может состоять из нескольких подцелей.

Переменные могут быть объектами предиката как в утверждениях, так и в подцелях.

Пролог пытается вычислить цель при помощи сопоставления терма предиката и объектов цели с соответствующими элементами в фактах и головах правил. Сопоставление выполняется слева направо. Некоторые подцели, вероятно, будут неуспешными при сопоставлении с некоторыми фактами или правилами, поэтому Прологу требуется способ «запоминания точек», в которых он может продолжить альтернативные попытки найти решение.

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

Если некоторая подцель оказывается неуспешной, то Пролог откатывается влево и останавливается у ближайшего указателя отката. С этой точки Пролог начинает попытку найти другое решение для неуспешной цели.

До тех пор, пока следующая цель на данном уровне не будет успешной, Пролог будет повторять откат к ближайшему указателю отката. Эти попытки выполняются внутренними подпрограммами унификации и механизмом отката. Окончательным результатом будет либо успешное, либо неуспешное вычисление цели.

/* Программа проверки цели: Что любит Бэт?*/
predicates
 
  likes(symbol,symbol)
  fruit(symbol)
  color (symbol,symbol)
 
clauses
 
  likes(mary,pears).    /* Мэри любит персики */
  likes(mary,popcorn).  /* Мэри любит кукурузные зерна */
  likes(mary,apples).   /* Мэри любит яблоки */
 
  likes(beth,X) :-      /* Бет любит то, */
  likes(mary,X),        /* что любит Мэри, */
  fruit(X),             /* если это фрукт, */
  color(X,red).         /* и если он красный */
 
  likes(beth,X) :-      /* Бет любит то, */
  likes(mary,X),        /* что любит Мэри, */
  X=popcorn.            /* если это кукурузные зерна */
 
  fruit(pears).         /* фрукт - персики */
  fruit(apples).        /* фрукт - яблоки */
 
  color(pears,yellow).  /* желтые персики */
  color(oranges,orange)./* оранжевые апельсины */
  color(apples,red).    /* красные яблоки */
  color(apples,yellow). /* желтые яблоки */
 
goal
  /* Ввод цели: "Что любит Бэт?" */
  likes(beth,X),
  write("Beth likes ", X, "."),nl.

Для того, чтобы ответить на вопрос цели, внутренние унификационные подпрограммы Пролога ищут факты или голову правила, сопоставимую с этим целевым утверждением likes(beth,X).

Поиск начинается с первого утверждения для отношения likes, которое содержит три факта о том, что любит Мэри. Пролог опробует все утверждения слева направо (сверху вниз). Сопоставление для всех них будет неуспешным, так как константа beth несопоставима с константой mary.

Внутренние унификационные подпрограммы Пролога переходят к правилу:

likes(beth,X) : likes(mary,X), fruit(X), color(X,red).

Переменные как в голове правила, так и в цели неозначены, так что цель и голова правила сопоставимы. Так как голова (левая часть) первого правила сопоставима с целью, то факты правой части становятся подцелями, которые Пролог должен вычислить, обрабатывая их слева направо.

Так как другие утверждения для likes следуют за этим правилом, то Пролог помещает указатель отката на начало следующего правила для likes:

likes(beth,X) :- likes(mary,X), X=popcorn. /* Второе правило */

Первой подцелью является likes(mary,X). Это новая подцель, поэтому Пролог снова начинает просмотр с вершины списка предикатов для likes (с likes(mary,pears).) и находит likes(mary,X). Этот факт likes(mary,pears). сопоставим с подцелью likes(mary,X), так как все ее термы сопоставимы, поскольку X получила значение pears во время унификации.

Теперь подцель likes(mary,X) успешно вычислена, но правило, которое сгенерировало эту подцель сгенерировало также и другие подцели, которые еще должны быть доказаны. Поэтому внутренние унификационные подпрограммы ставят указатель на следующий факт для likes – на (mary,popcorn). Этот указатель показывает, что существует по крайней мере еще одно утверждение для likes, которое может быть использовано для вычисления текущей подцели. В случае если следующая подцель окажется неуспешной, механизм отката будет иметь точку для поиска другого кандидата для вычисления цели.

Повторим. К этому моменту цель likes(beth,X) была сопоставлена с головой правила likes(beth,X). Внутренние унификационные подпрограммы установили указатель на голову следующего правила likes(beth,X) и начали попытки вычисления утверждений в правой части правила. В результате была сгенерирована подцель likes(mary,X).

Пытаясь вычислить эту подцель, унификационные подпрограммы обнаружили сопоставимое утверждение likes(mary,pears). Теперь X получил значение pears, а значение подцели стало likes(mary,pears). Существуют и другие утверждения, которые могут быть использованы для вычисления подцели, поэтому указатель отката был установлен на likes(mary,popcorn).

Следующая подцель справа есть fruit(X). Так как сейчас X имеет значение pears, то подцель означает fruit(pears). Внутренние унификационные подпрограммы находят сопоставление с первым утверждением для fruit - fruit(pears). Так как существуют другие утверждения, которые могут быть использованы для вычисления подцели, то создается еще один указатель отката на это утверждение – на fruit(apples).

Теперь два указателя отката отмечают альтернативные пути к решению правила:

likes(beth,X) : likes(mary,X), fruit(X), color(X,red).

Последняя подцель правила есть color(X,red). Внутренние подпрограммы унификации, всегда просматривая утверждения слева направо, пытаются сопоставить подцель с утверждением color(pears,yellow). Так как X имеет значение pears, то текущая подцель есть color(pears,red).

Все попытки вычислить эту подцель неуспешны, так как программа не содержит утверждения color(pears,red). Подцель вычислена неуспешно. Переменная X опять становится свободной из-за неуспешного вычисления подцели во время попытки сопоставления с pears.

Это сопоставление неуспешно, так что механизм отката повторяет откат к ближайшему предыдущему указателю, который установлен на likes(mary,popcorn).

В точке, определяемой указателем отката, Пролог находит факт likes(mary,popcorn). Указатель отката устанавливается на следующее утверждение для likes - likes(mary,apples). Переменная X имеет значение popcorn, так что теперь подцели эквивалентны «Мэри любит кукурузные зерна и кукурузные зерна фрукт красного цвета».

Подцель fruit(popcorn) не может быть доказана при помощи фактов и правил, имеющихся в программе (попкорн – не фрукт), так что подцель likes(mary,X) неуспешна. Переменная X освобождается, и подцель likes(mary,X) в правиле likes(beth,X) имеет еще один шанс на успех, так как был отмечен для отката еще один факт, о том что любит Мэри.

Внутренние унификационные подпрограммы выполняют откат в точку likes(mary,apples).

Теперь подцель сопоставляется с likes(mary,apples), и X получает значение apples. Выполняется попытка для следующей подцели fruit(apples). Первое утверждение для fruit имеет объект pears. Объекты не сопоставимы, так что внутренние унификационные подпрограммы переходят к следующему факту fruit(apples), который сопоставим с подцелью.

В этот момент подцель есть color(apples,red). Начав с вершины списка фактов для color, внутренние унификационные подпрограммы пытаются сопоставить эту подцель с фактами color(pears,yellow), color(oranges,orange) и color(apples,red). Во время этой последней попытки объект apples (присвоенный переменной X) сопоставляется с объектом apples в факте, но последние объекты red и yellow не сопоставимы, так что попытка неудачна. Последний факт, связанный с цветом это color(apples,red), который сопоставим с подцелью color(apples,red).

С успешным сопоставлением последней подцели правило доказано. Переменная X, получив значение apples, тем самым доказывает правую часть.

Все правило с переменной X, означенной объектом apples, c точки зрения внутренних унификационных подпрограмм выглядит как

likes(beth,apples) : likes(mary,apples), fruit(apples), color(apples,red).

Выдав сообщение X=apples, Пролог показывает, что для цели найдено, по крайней мере, одно решение.

Поскольку внешняя цель была использована с программой, являющейся «черным ящиком» для Пролога, то он продолжает поиск других решений для цели. Цель была успешной, так что переменная X освобождена и может быть снова означена подпрограммами внутренней унификации. Поиск решений снова начинается с указателя отката, который теперь является последним. Теперь внутренние унификационные подпрограммы начинают поиск с правила

likes(beth,X) : likes(mary,X), X=popcorn.

Снова первая подцель есть likes(mary,X), и внутренние унификационные подпрограммы осуществляют поиск утверждений likes для сопоставления. Утверждение likes(mary,pears) сопоставимо с подцелью, так что X получает значение pears. Указатель для отката устанавливается на следующее утверждение likes(mary,popcorn).

Вычислив текущую подцель и означив X объектом pears, Пролог пытается вычислить оставшуюся подцель, которая есть X=popcorn.

Как было объяснено ранее в этой главе, оператор = работает как оператор сравнения, поскольку значения обоих термов известны: переменная X имеет значение pears, а popcorn есть константа. Операция сравнения будет неуспешной. Термы не сопоставимы, поэтому подцель неуспешна, и X снова освобождена.

Теперь внутренние унификационные подпрограммы выполняют откат к последнему указателю, с тем, чтобы попробовать альтернативный путь решения. Последний указатель отката установлен на утверждение likes(mary,popcorn).

Ранеее X была освобождена, поэтому сейчас она получает значение popcorn. Установив указатель отката на следующее утверждение likes(mary,apples), внутренние унификационные подпрограммы снова пытаются вычислить подцель X=popcorn. Сравнение успешно, и последняя подцель правила успешно вычислена. Переменная X в голове правила имеет значение popcorn. Таким образом, выведенный факт есть likes(beth,popcorn).

Пролог сообщает об этом, выдавая X=popcorn.

Теперь найдены два решения, а указатель отката остался на утверждении likes(mary,apples). Пролог возвращается в указанную точку и пытается найти еще одно решение.

Вспомним, что данный путь является альтернативным для первой подцели второго правила для likes. Следовательно, имеем подцель likes(mary,X).

Так как X снова освобождена, то она получает значение apples и подцель снова успешна. Хотя среди утверждений для likes и не осталось фактов, но еще остались два правила, так что указатель устанавливается на факт likes(mary,apples).

Возвратившись к следующей подцели, Пролог сравнивает X=popcorn или apples=popcorn. Иными словами, подцель неуспешна.

Снова внутренние унификационные подпрограммы выполняют откат к голове правила likes(beth,X). Эта голова правила не сопоставима с подцелью likes(mary,X), управляющей данной попыткой использовать данный альтернативный путь, поэтому унификационный механизм проверяет сопоставимость головы следующего правила.

Эта голова правила также есть likes(beth,X), поэтому снова из-за несопоставимости beth и mary, сопоставление оказывается неудачным. На этот раз правило не смогло дать решение, и цель оказалась неуспешной.

Ранее найдены два решения. Чтобы показать, что на этом процесс завершен, Пролог выдает сообщение Two solutions (Два решения).

Таким образом, Пролог использует откаты для определения альтернативных путей вычисления цели или подцели. Если подцель оказалась неуспешной, а указатели отката были установлены, то для предыдущей подцели будет сделана попытка добиться успеха, начиная с точки отката.

!!Рекомендуем: Семейная Энциклопедия Здоровья ⇒ Что должен знать современный человек? ⇒ Самоанализ. Работа над собой ⇒ Оглавление ⇒ Главная сайта