Как вы видите, этот факт сопоставим с подцелью. Таким образом, подцель likes(mary,apples) оказывается успешно доказанной. Следовательно, голова правила likes(beth, apples) имеет место. А так как голова правила истинна, то доказана истинность цели likes(beth, apples). Другими словами, цель оказалась успешной. Новый факт был успешно выведен, хотя он нигде в программе явно указан не был.
2.3.3 Результат доказательства цели
Если цель likes(beth, apples) успешно доказана, то Турбо-Пролог информирует об этом, выдавая сообщение True. Если бы целью было likes(beth, oranges), а программа содержала бы те же факты и правила, то эта цель была бы неуспешной, а сообщение было бы False.
На этом примере видно, что манипулирование данными и управление программой определяется фактами и правилами. В Турбо-Прологе факты и правила называются утверждениями. Факт
finds(john, gold). /* Джон нашел золото */
является утверждением. Правило
is(john, rich) if finds(john, gold). /* Джон богат, если */ /* Джон нашел золото */
так же является утверждением. Так как головы утверждений, являющиеся правилами, имеют форму фактов, то правила могут рассматриваться как факты. Но, тем не менее, различия между фактами и правилами весьма существенны, и это обстоятельство используется в данной книге.
В программе на Турбо-Прологе утверждения для одного и того же предиката группируются вместе. Как это происходит, вы увидите в следующей главе.
2.3.4 Связки и другие символы
Часто условия требуют более одной предпосылки. Например, "Джон и Мэри женаты, если Мэри жена Джона и если Джон муж Мэри". На ТурбоПрологе это правило записывается в виде:
married(john, mary) If wife(john, mary) and husband(mary, john).
Данное правило имеет два условия, соединенные словом and
(и). Используя терминологию Пролога, это есть связка двух условий, объединенных словом and. В Прологе вместо слова and часто используется запятая (,). В Турбо-Прологе также используется слово and, однако применение запятой предпочтительнее, т.к. в этом случае чтение программы легче. Кроме того, в Прологе используется так же специальный символ для слова if (если). Это символ :- (двоеточие с последующим тире). Таким образом, если в программе на Турбо-Прологе вам встретиться символ :-, то читайте его как "если", а запятую - как "и". С использованием символов для представления "и" и "если" отношение "женаты" (married) записывается в виде:
married(john, mary) :-
wife(john, mary),
21
husband(mary, john).
Заметим, что символ :- следует за головой утверждения, а оба условия начинаются с абзацного отступа и разделены запятой. Отступы не обязательны, они используются для удобства чтения программы. Как и все утверждения, это утверждение заканчивается точкой.
Точка с запятой (;) используется для представления связки or (или). Как и для связки and (и), Турбо-Пролог допускает использование и слова or (или) и символа ;. Связка or не очень часто используется в правилах и фактах. Она имеет и другие применения, о которых вы узнаете в следующих главах.
В большинстве случаев Турбо-Пролог игнорирует избыточные пробелы и переносы на следующую строку (позже вы узнаете об исключениях из этого правила). Хотя кажется, что предыдущее утверждение читается сверху вниз, Турбо-Пролог читает его как упорядоченную слева направо конструкцию, а переносы на следующую строку игнорируются. Голова правила обычно называется левой частью, а условия, следующие за символом :-, обычно называются правой частью правила. Просмотр слева направо является важным принципом, который необходимо твердо усвоить , так как далее в этой главе будут рассматриваться внутренние процессы Турбо-Пролога.
2.3.5 Цели и подцели
Если вспомнить, что цели, подобно фактам и правилам, строятся из предикатов, то не трудно понять, что цели также могут иметь связки. Цели, имеющие связки, называются целями, имеющими подцели. Подцели утверждения цели разделяются запятыми точно так же, как условия в правилах. Когда цель введена в программу на Турбо-Прологе, то Турбо-Пролог обрабатывает ее подцели слева направо, пытаясь сопоставить подцели с фактами и правилами программы. Если одна из подцелей несопоставима, то вся цель является неуспешной. Если все подцели сопоставимы, то вся цель является успешной.
Пусть, например, программа содержит следующие утверждения:
likes(mary, apples). |
/* Мэри любит яблоки */ |
color(apples, red). |
/* цвет яблок красный */ |
Введем цель
likes(mary, apples),color(apples, red).
Утверждения заканчиваются точками и являются независимыми фактами, а подцели разделены запятыми и точка завершает цель как целое.
Самая левая подцель likes(mary,apples) сопоставима с утверждением likes(mary,apples), так что эта подцель успешна. Следующая подцель справа сопоставима с утверждением color(apples, red), и поэтому вся цель является успешной. Информация, выведенная на экран, уведомит вас, что эта цель истинна. По-русски, цель есть "Мэри любит яблоки и яблоки красные". Либо можно сформулировать цель как вопрос "Любит ли Мэри яблоки, и красные ли эти яблоки?". Факты подтверждают эту цель.
22
В реальной ситуации, вероятно, потребовалось бы подтверждение вопроса, такого как "Любит ли Мэри красные яблоки?". Эта цель отличается от предыдущей. Ранее требовалось, только проверит факты, что Мэри любит яблоки и что эти яблоки красные. Сейчас необходимо знать, любит ли Мэри яблоки, если они красные. Яблоки могут быть и красные, и зеленые, и желтые. Но Мэри может вообще не любить яблоки, либо же она их любит, но они не красные. В таком случае ответ False.
Для того, что бы ввести эти факты в программу, необходимо убрать утверждение
likes(mary, apples).
и добавить правило likes(mary, apples) :-
color(apples, red).
По-русски это правило читается как "Мэри любит яблоки, если они красные". Если вы хотите узнать "Любит ли Мэри яблоки?", то введите цель
likes(mary,apples).
Турбо-Пролог сопоставляет цель с головой правила likes(mary,apples). Но это правило имеет условие color(apples, red).
Поэтому это условие должно быть доказано для того, чтобы цель могла быть успешной.
Даже если цель сама по себе не имеет подцелей, то Турбо-Пролог все равно должен сопоставить правило с условием с соответствующим утверждением. Фактически Турбо-Пролог создает подцель. Для доказательства головы правила, должны быть доказаны условия тела правила точно так же, как если бы целевое утверждение состояло из связки этих подцелей. ТурбоПролог успешно доказывает эту подцель, обнаружив среди утверждений факт color(apples, red). Доказав эту подцель, Турбо-Пролог доказал, что голова правила истинна. Так как голова правила сопоставима с целью, то цель является успешной.
Для того, чтобы понять как Турбо-Пролог генерирует внутренние подцели, можно считать, что условия справа от if (или символа :-) становятся подцелями исходной цели, когда, пытаясь доказать эту цель, ТурбоПролог сопоставляет ее с головой правила.
Для простоты в этом разделе были приведены ясные несложные примеры процесса сопоставления. Эти примеры были упрощены так, чтобы можно было легко увидеть логику управления программой в ТурбоПрологе. Теперь вы должны понимать, что сопоставление является очень важным элементом Турбо-Пролога.
2.4 Внутренние подпрограммы унификации Турбо-Пролога
Турбо-Пролог (как и другие реализации Пролога) имеет внутренние подпрограммы для выполнения сопоставления и связанных с ним процессов. Эти неотъемлемые части языка называются внутренними подпрограммами унификации. Эти подпрограммы выполняют сопоставление целей и подцелей
23
с фактами и головами правил для того, что чтобы доказать (или вычислить) эти цели или подцели. Эти же подпрограммы также определяют, сгенерированы ли новые подцели правой часть правила. Программист в соответствии с логическим синтаксисом Турбо-Пролога объявляет, какие факты и правила дают тот или иной результат при различных подцелях, а внутренние подпрограммы унификации выполняют оставшуюся часть работы.
2.4.1 Представление данных при помощи фактов и правил
В программах на Турбо-Прологе данные представляются при помощи фактов и правил. Хотя факт может быть предикатом, не содержащим объектов, большинство фактов записывается как предикат с одним или более объектами.
Некоторые примеры:
likes(mary,apples). |
/* Мэри любит яблоки */ em- |
ployee(smith,john,1984). |
/* служащий Джон Смит */ |
gender(female). |
/* пол - женский */ |
Если имя объекта начинается со строчной буквы, то этот объект имеет известное значение. Другими словами, объект есть в этом случае константа. Когда Турбо-Пролог пытается сопоставить две константы, то это сопоставление успешно только в том случае, если константы равны. Следовательно, mary никогда не сопоставима с beth.
Пусть программа содержит следующие факты: likes(beth, apples).
likes(mary, pears). likes(mary, oranges). likes(mary, apples).
Теперь предположим, что введена внешняя цель likes(mary,apples).
Как вы понимаете, цель по структуре подобна факту и правилу. Оба объекта в этой цели mary и apples являются константами. Пытаясь выполнить эту цель, Турбо-Пролог просматривает программу слева направо, выполняя поиск предиката с тем же предикатным термом, что и целевой предикат. (Вспомним, что то, что выглядит как "сверху вниз", на самом деле есть "слева направо"). Это первый шаг, выполненный внутренними унификационными подпрограммами.
В этом примере предикатный терм цели есть likes. Первый факт для likes, встречающийся в программе, это likes(beth, apples). Сопоставив предикатный терм в цели и факте, внутренние унификационные подпрограммы теперь пытаются сопоставить первый объект для likes в цели и факте. Так как константа mary не сопоставима с константой beth, то попытка неуспешна. Теперь внутренние унификационные подпрограммы пытаются сопоставить цель со следующим предикатом likes. На этот раз сопоставление успешно, так как константа mary сопоставима с точно такой же константой в правиле. Но для завершения сопоставления внутренние унификационные подпрограммы должны сопоставить следующий объект справа. Константы
24
pears и apples не сопоставимы. Так как и эта попытка неуспешна, то внутренние унификационные подпрограммы опять повторяют попытку для следующего предиката likes.
Каждое возможное сопоставление проверяется слева направо. Очевид-
но, что likes(mary, apples) не сопоставимо с likes(mary, oranges).
Внутренние унификационные подпрограммы просматривают всю программу слева направо, пробуя сопоставить каждый факт или правило с целью. Только предикаты с соответствующими объектами проверяются на сопоставимость с целью. Последний кандидат для сопоставления - это факт likes(mary,apples). Оба объекта в этом факте сопоставимы с соответствующими объектами в предикате цели. Цель успешно доказана. Рассматривая этот пример, следует понять, что механизм внутренней унификации обработал сверху до низу (или слева направо) все подходящие факты и правила. После того как сопоставимый предикат был найден, объекты этого предиката сопоставлялись слева направо, пока это сопоставление не становилось либо успешным, либо неуспешным. Если сопоставление заканчивалось неуспешно, то проверялись следующие факты или правила до тех пор, пока либо одно из сопоставлений заканчивалось успешно, либо все релевантные факты и правила оказывались опробованными и неуспешными.
В случае, когда объектами сопоставления являются две константы, то успешный результат будет лишь тогда, когда они совпадают. Другими словами, константа всегда сопоставима сама с собой.
2.4.2 Обработка правил и фактов во время унификации
Переменные в Турбо-Прологе являются аналогами местоимений в естественном (в частности, русском) языке. В определенный момент переменная может получить некоторое значение. Иногда этого может не произойти. Возможно вы имеете некоторое представление о поведении переменных, основанное на других языках программирования. Если это так, то обратите особое внимание на то, как ведут себя переменные Турбо-Пролога. Вы можете обнаружить некоторые неожиданные отличия.
Следующий пример включает кое-что из того, что вы узнали в предыдущем разделе о внутренних подпрограммах унификации. Данными является факт
likes(mary, apples). |
/* Мэри любит яблоки */ |
Вы хотите сформулировать цель, чтобы узнать, что любит Мэри (если |
|
таковые объекты имеются). Вид этой цели следующий: |
|
likes(mary, What). |
/* Мэри любит Что */ |
Вспомним, что в Турбо-Прологе объект, начинающийся с прописной буквы, есть переменная. Переменная в этой цели есть What (что). Когда внутренние унификационные подпрограммы пытаются сопоставить эту цель с фактами или правилами программы, переменная What не имеет значения. What не равна нулю и не равна пробелу. Эта переменная не имеет даже значения, являющегося "мусором" (какой бы мусор не оказался в памяти, отведенной для переменной).
25