Материал: Терёхин В. В. Turbo Prolog

Переменная What не имеет значения, так как она неозначена, или неинициализирована. Эти два термина используются как взаимозаменяемые. Неозначенные переменные еще называются свободными переменными. Когда свободная переменная цели What сопоставляется с соответствующим объектом apples, значением What становится apples. Теперь переменная What означена (или инициализирована) объектом apples. Другими словами, эта переменная более не свободна (связана).

Пока What имеет значение apples, эта переменная для Турбо-Пролога "означает" apples. Фактически всякий раз, когда неозначенная переменная сопоставляется с константой, она получает значение этой константы. Тур- бо-Пролог выдает на экран, что What=apples , и, что внутренняя подпрограмма унификации нашла все (единственный) объекты, сопоставимые с целью.

Теперь предположим, что программа содержит следующие факты:

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

Может показаться, что переменная What получает значения apples, pears и popcorn в одно и тоже время, но это не так. Подпрограммы внутренней унификации присваивают переменной конкретное значение только во время сопоставления. Переменная становится вновь свободной, когда сопоставление оказывается неуспешным или цель оказывается успешно вычисленной.

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

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

26

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

Пример использования оператора = поможет лучше понять процесс означивания переменой. В языке программирования, таком как Бэйсик, оператор = может означать "Сделать два терма равными", например в выражении X=6. Здесь оператор = является оператором присвоения значения. Его действие состоит в том, чтобы сделать X равным 6, т. е. присвоить значение 6 переменной X. Но в Бейсике оператор = имеет еще и другой смысл - проверить равенство двух термов. Такое использование символа = встречается в условных выражениях, таких как IF X=6 GOSUB 3010. Оператор = , использованный таким образом, выражает следующее: "Два терма, между которыми я нахожусь, должны быть равными для того, чтобы весь оператор был истинным". Оператор = интерпретируется как оператор присваивания или как оператор проверки равенства в зависимости от контекста. (Но некоторые языки для присваивания и равенства используют различные символы ).

Турбо-Пролог также использует оператор = , но используется ли он как оператор сравнения или как оператор присваивания определяется в зависимости от того, являются ли значения термов свободными или означенными.

Рассмотрим, например, выражение apples = apples .

Это выражение может быть подцелью, сгенерированной внутри ТурбоПролога. Так как оба значения известны, то оператор = является оператором сравнения. В этом случае равенство истинно, и подцель является успешной.

Рассмотрим выражение apples = oranges .

Так как эти два терма имеют различные значения, то равенство ложно. Рассмотрим пример, в котором используется переменная:

X = apples .

Это выражение так же могло бы быть подцелью, сгенерированной внутри Турбо-Пролога во время попытки вычислить цель. Но здесь знак равенства не обязательно является оператором присваивания. Эта подцель присваивает значение apples переменной X (означивает эту переменную) только в том случае, если X еще не была означена. Но если X уже имеет значение, то оно известно внутренним подпрограммам унификации и сравнивается с константой apples. Если эти два значения одинаковы, то подцель успешна; если они различны, то подцель неуспешна.

Интерпретация Турбо-Прологом оператора = зависит от того, известны ли оба значения или нет. Если оба значения известны, то оператор интерпретируется как оператор сравнения, даже если оба терма переменные.

Если известно только одно из значений, то это известное значение будет присвоено другому. Для Турбо-Пролога несущественно, известно ли значение справа или слева от = ; в любом случае неизвестное получит значение из-

27

вестного. Например, предположим, что переменная Fruit (фрукт) неозначена. Подцель apples=Fruit вызовет присвоение значения apples переменной Fruit. Теперь предположим, что подцель Fruit=X непосредственно следует за предыдущей, и что X свободная переменная. Результат попытки выполнить эту подцель состоит в присваивании переменной X значения apples. Вы видите, что даже если оба терма Fruit и X переменные, Турбо-Пролог присваивает (означивает) неозначенной переменной известное значение. Во многих языках программирования присваивание встречается только в форме присваивания правого терма левому. Но в Турбо-Прологе присваивание может иметь место в обоих направлениях. В качестве последнего примера рассмотрим подцель X=oranges.

Переменная X получила значение apples в результате предыдущей инициализации. Константа oranges (апельсины) также имеет известное значение. Так как обо значения известны, то Турбо-Пролог проверяет их равенство. Результирующее выражение apples=oranges ложно. Следовательно, эта подцель неуспешна и цель также неуспешна. После этого неуспешного доказательства цели переменные Fruit и X становятся неозначенными. Изучение поведения оператора = при выполнении сравнения и присваивания весьма полезно по двум причинам. Во-первых, оператор = широко используется при программировании на Турбо-Прологе. Во-вторых, что более важно, оператор = ведет себя точно так же, как ведут себя внутренние унификационные подпрограммы при сопоставлении целей и подцелей с фактами или правилами программы. Переменным могут быть присвоены значения во время попыток выполнить цели, и они же могут сравниваться для проверки равенства. Результаты означивания передаются дальше другим подцелям, которые используют соответствующие объекты во время присваивания значений или сравнения значений. Если некоторая подцель оказывается неуспешной или последующие подцели не используют значений означенных переменных, то эти переменные становятся неозначенными, т.е.

они становятся снова свободными.

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

2.4.3 Откат

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

После того, как вы свернете с автострады и повернете направо на первом перекрестке, вы не найдете входа в парк. Поэтому вы вернетесь (выполните откат) к перекрестку и продолжите первоначальное движение до следующего

28

перекрестка. Здесь вы опять повернете направо и поищите вход в парк. Если вам вновь неудастся найти вход в парк, вы еще раз вернетесь назад (выполните откат) и сделаете попытку на следующем перекрестке. Вы будете повторять этот процесс до тех пор, пока вам не удастся достичь вашей цели найти дом, или же вы потерпите полную неудачу и откажитесь от этой затеи.

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

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

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

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

С некоторыми небольшими дополнениями факты и правила о Мэри, Бет и яблоках могут быть использованы для иллюстрации отката и внутренней унификации. Данный пример содержит переменные, а также факты и правила, которые обрабатываются подпрограммой внутренней унификации при выполнении операций сопоставления.

Факты для отношения likes:

Заметьте, что эти предикаты сами по себе не образуют законченной программы на Турбо-Прологе. В следующей главе вы узнаете об остальных необходимых частях программы.

Ниже дано целевое утверждение, которое используется для выборки информации из приведенных утверждений:

likes(beth, X).

Эта цель означает "Что любит Beth?". Для того, чтобы ответить на данный вопрос, внутренние унификационные подпрограммы Турбо-Пролога ищут факты или голову правила, сопоставимую с этим целевым утверждением. Поиск начинается с первого утверждения для отношения likes, которое содержит три факта о том, что любит Мэри. Турбо-Пролог опробует все утверждения слева направо (сверху вниз). Сопоставление для всех них будет неуспешным, так как константа beth несопоставима с константой mary.

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

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

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

30