Сопоставление и унификация
ПРОграммирование в ЛОГике
Пролог является результатом многолетней исследовательской работы. Первая официальная версия Пролога была разработана Аланом Кольмероэ в Марсельском университете во Франции в 1972 году как инструмент для ПРОграммирования ЛОГики. Первоначально Пролог разрабатывался как язык для решения задач искусственного интеллекта, он и сейчас очень хорошо подходит для создания экспертных систем и программирования других задач этой области. Но нынешний Visual Prolog – это язык, способный решать практически любые задачи современного программирования.
В Прологе решение задачи получается логическим выводом из ранее известных положений. Программа на Прологе представляет собой набор фактов и правил, обеспечивающих получение заключений на основе этих фактов. Поэтому Пролог известен как декларативный язык.
Пролог включает механизм вывода, который основан на сопоставлении образцов. С помощью подбора ответов на запросы он извлекает хранящуюся (известную) информацию. Пролог пытается проверить истинность гипотезы (другими словами – ответить на вопрос), запрашивая для этого информацию, о которой уже известно, что она истинна. Прологовское знание о мире – это ограниченный набор фактов и правил, заданных в программе.
Одной из важнейших особенностей Пролога является тот факт, что в дополнение к логическому поиску ответов на поставленные вопросы он может иметь дело с альтернативами и находить все возможные решения. Вместо обычной работы от начала программы до ее конца Пролог может возвращаться назад и просматривать более одного «пути» при решении всех составляющих задачу частей.
Пример 1. (слайд 1)
«В одном небольшом кафе в смене работали пять человек: администратор, повар, кондитер, кассир и дворник. Одновременно на работу выходили Голубева, Иванова, Васин, Смирнов и Азаров. При этом было известно, что:
повар – холостяк (A);
кассир и администратор жили в одной комнате, когда учились в колледже (B);
Азаров и Иванова встречаются только на работе (C);
жена Васина заболела, когда муж сказал ей, что администратор отказал ему в отгуле на субботний вечер (D);
Смирнов собирается быть свидетелем на свадьбе у кассира и кондитера (E).
Кто на какой должности в этом кафе?»
Этот пример в дальнейшей нашей работе будет неоднократно использоваться. В данный момент мы обратим внимание на способ записи предложений на естественном языке в стиле синтаксиса логики предикатов. Курсивом выделим несущественные слова. (слайд 2)
Таблица 1.
| Предложения на естественном языке | Синтаксис логики предикатов |
| В одном небольшом кафе в смене работали пять человек: администратор, повар, кондитер, кассир и дворник. | профессия(администратор). профессия(повар). профессия(кондитер). профессия(кассир). профессия(дворник). |
| Одновременно на работу выходили Голубева, Иванова, Васин, Смирнов и Азаров | сотрудник(голубева, жен). сотрудник(иванова, жен). сотрудник(васин, муж). сотрудник(смирнов, муж). сотрудник(азаров, муж). |
n
Факты и правила
При составлении программы на языке Пролог необходимо описать объекты (objects) и отношения (relations), а затем – правила (rules), при условии соблюдения которых эти отношения являются истинными. Программа на языке Пролог состоит из предложений (clauses), которые могут быть отнесены к одному из двух типов фраз: факты и правила.
Отношение в Прологе называется предикатом. Аргументы – это объекты, которые связываются этим отношением. Предикаты могут не иметь аргументов, но использование таких предикатов ограничено.
Предложение: «Одновременно на работу выходили Голубева, Иванова, Васин, Смирнов и Азаров» позволяет установить, что объектами являются Голубева, Иванова, Васин, Смирнов и Азаров. Каждый из которых обладает свойством принадлежности к определенному полу человека. Факты относительно этой принадлежности обеспечиваются двухместным предикатом сотрудник.
Факты
Отношение между объектами называется фактом. Факты– это отношения или свойства, о которых известно, что они имеют значение «истина». Факт самодостаточен. Прологу не требуется дополнительных сведений для подтверждения факта, и факт может быть использован как основа для логического вывода. Отношение состоит из имени отношения и объекта или объектов, заключенных в круглые скобки. Как и предложение, факт заканчивается точкой.
сотрудник(голубева, жен).
сотрудник(смирнов, муж).
Факты помимо отношений могут выражать и свойства:
профессия(администратор).
профессия(повар).
Правила
Правила позволяют вывести один факт из других фактов. Правило – это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными. Правила – это связанные отношения. Они позволяют Прологу логически выводить одну порцию информации из другой. Правило принимает значение «истина», если доказано, что заданный набор условий является истинным.
(слайд 3)
Символ «: -» имеет смысл «если», и служит для разделения двух частей правила: заголовка и тела.
Заголовок – это факт, который был бы истинным, если бы были бы истинными несколько условий.
Тело – это ряд условий, которые должны быть истинными, чтобы Пролог мог доказать, что заголовок правила истинен.
Правило может рассматриваться как процедура. С этой (процедурной) точки зрения правила могут предписывать выполнение каких-либо действий, отличных от доказательств фактов (вывести что-нибудь на экран или создать файл).
В качестве предикатов, составляющих тело правила, могут выступать:
ü предикаты, фигурирующие в базе фактов;
ü предикаты, совпадающие с заголовком других правил;
ü встроенные предикаты систем программирования Пролог.
Пример 2.
На основании высказывания B из примера 1 можно сформулировать правило, которое может выглядеть так:
Кассир и администратор являются людьми одного пола.
По этому правилу получается, что в том случае, когда в примере 1 будет устанавливаться профессия каждого из работников кафе, то необходимо описать правило, в котором осуществляется проверка совпадения полов.
На Прологе синтаксис у правил будет таким:
работа(Имя,Должность,Пол):-
сотрудник(Имя,Пол), профессия(Должность), … .
условие_пола(X1,Y1,Z1,X2,Y2,Z2):-
работа(X1,Y1,Z1), работа(X2,Y2,Z2),
Y1=кассир, Y2=администратор, Z1=Z2.
условие_пола(X1,Y1,Z1,X2,Y2,Z2):-
работа(X1,Y1,Z1), работа(X2,Y2,Z2),
Y1=администратор, Y2=кассир, Z1=Z2.
В примере 2 заголовками являются:
работа(Имя,Должность,Пол); условие_пола(X1,Y1,Z1,X2,Y2,Z2).
Телом первого правила является:
сотрудник(Имя,Пол), профессия(Должность), …
Здесь многоточие означает, что формулировка правила не приводится до конца, так как на этом этапе мы еще не учли всех фактов, изложенных в условии.
n
Запросы (цели)
Однократная запись фактов в программе позволяет нам задавать вопросы, касающиеся отношений между ними. Этот процесс называется запросом (query) системы языка Пролог. Пролог всегда ищет ответ на запрос, начиная с первого факта, и перебирает все факты, пока они не закончатся.
Запросы (цели) могут быть простыми или сложными. Сложными называются цели, состоящие из двух или более частей. А каждая часть сложной цели – подцелью. Возможно использование конъюнктивной и дизъюнктивной формы объединения подцелей. В качестве разделителей используются знаки«,»и«;»соответственно.
Составные цели можно использовать для поиска решения, в котором:
ü обе подцели A и B истинны (конъюнкция), разделяя подцели запятой:
ü истинна либо подцель A, либо подцель B (дизъюнкция), разделяя подцели точкой с запятой.
Пример 3. (слайд 4)
- профессия(администратор).
- профессия(врач).
- сотрудник(Кто,жен).
Каждая из приведенных записей может быть сформулирована в разделе программы, определяющем запросы. Первая и вторая требуют ответа «да» или «нет». В соответствии с фактами, представленными в примере 1, на первый запрос получим ответ «да», а на второй – «нет». В третьем случае первый объект Кто – начинается с большой буквы, тогда как второй объект (жен) со строчной. Это объясняется тем, что жен – фиксированный, постоянный объект, известная величина, а Кто – переменная. Получив запрос о том, кто из объектов является мужчиной, Пролог ответит:
Кто = голубева.
Кто = иванова.
2 Solutions. n
Переменные
Переменные в Прологе всегда начинаются с заглавной буквы или символа подчеркивания. Пролог не имеет оператора присваивания, но обеспечивает связывание переменной с конкретным значением при сопоставлении с константами в фактах или правилах. Переменные в Прологе инициализируются (или конкретизируются). До инициализации переменная свободна. После получения ею значения, она становится связанной. Конкретизация переменной обеспечивает возврат искомых значений переменных по запросам.
Переменная остается связанной только то время, которое необходимо для получения решения по запросу. Затем Пролог освобождает ее и ищет другое решение.
Нельзя сохранить информацию, присвоив значение переменной. Переменные используются как часть процесса поиска решения, а не как хранилище информации.
Пример 4. (слайд 5)
Рассмотрим совокупность фактов:
увлечение(лена, чтение).
увлечение(иван, компьютеры).
увлечение(илья, баскетбол).
увлечение(леонид, баскетбол).
увлечение(юра, плавание).
увлечение(юра, чтение).
По запросу
увлечение(Кто,чтение), увлечение(Кто,плавание).
Пролог среди фактов первоначально выделяет тот, у которого второй аргумент – чтение. В результате чего переменная Person первоначально связывается со значением лена и по списку фактов ищет факт, соответствующий второй части запроса: увлечение(лена,плавание).
Поскольку такого факта нет, то Пролог освобождает переменную Person и среди фактов выделяет следующий, у которого второй аргумент – чтение, то есть увлечение(юра,чтение) и переменная Person связывается со значением юра. Далее по списку фактов ищет факт, соответствующий второй части запроса: увлечение(юра,плавание). И, поскольку данный факт имеет место, то Пролог выдает ответ:
Кто = юра
1 Solutions.
Если бы среди множества фактов имелись в наличии следующие:
увлечение(маша, плавание).
увлечение(маша, чтение).
то при соответствующих настройках проекта, Пролог, выдав решение (Кто = юра), освободил бы переменную Person, затем связал бы ее со значением маша, и, действуя аналогично, нашел бы второе решение (Кто = маша). n
Анонимные переменные
Переменные данного вида используются в том случае, когда необходимо использовать не полную, а определенную информацию из запроса, проигнорировав ненужные значения. Обозначаются такие переменные символом подчеркивания и сопоставляются с любыми данными.
Пример 5. (слайд 6)
Рассмотрим совокупность фактов:
сотрудник(голубева, жен).
сотрудник(иванова, жен).
сотрудник(васин, муж).
сотрудник(смирнов, муж).
сотрудник(азаров, муж).
На запрос
сотрудник(Кто,_).
Пролог ответит:
Кто = голубева
Кто = иванова
Кто = васин
Кто = смирнов
Кто = азаров
5 Solutions. n
Анонимные переменные могут использоваться и в фактах Пролога. Например, факты:
есть(_,нос). дышать(_).
могут быть выражены средствами естественного языка:
«У каждого есть нос». «Все дышат».
4. Комментарии (слайд 7)
Многострочные комментарии должны начинаться с символов «/*» и заканчиваться символами «*/». Однострочные комментарии можно начинать с символа «%».
5. Основные разделы программ (слайд 8)
ü раздел DOMAINS (доменов);
ü раздел PREDICATES (предикатов);
ü раздел CLAUSES(предложений);
ü раздел GOAL (целей).
Раздел целей аналогичен телу правила и представляет собой список подцелей, представленных в виде запроса. Цель отличается от правила тем, что за ключевым словом GOAL не следует знак «:-» и при запуске программы Visual Prolog автоматически выполняет цель.
Раздел предложений. Все предложения (и факты, и правила) для каждого предиката в данном разделе должны располагаться вместе. Последовательность предложений, описывающих один предикат, называется процедурой.
Раздел предикатов. Здесь перечисляются все предикаты, отличные от стандартных (встроенных в Visual Prolog) и используемые в программе. Предикаты должны быть перечислены с указанием типов (доменов) их аргументов.
Объявление предиката содержит:
1) имя предиката – последовательность латинских букв, цифр и символа подчеркивания, начинающаяся с прописной буквы. Длина имени не может быть больше 250 символов. В именах запрещено использовать такие символы, как «пробел», «-», «*» и т.п.;
2) список доменов (типов) аргументов предиката, заключенный в круглые скобки.
Арность предиката – это количество аргументов, которые он принимает. В программе можно использовать два предиката с одним и тем же именем, но отличающиеся арностью.
Объявление предиката не заканчивается точкой. Доменами (типами) аргументов могут быть либо стандартные домены, либо домены, объявленные в разделе domains.
Например,
увлечение(человек, действие)
color(symbol)
мой_предикат(integer, symbol)
Раздел доменов. Домены позволяют задавать разные имена различным видам данных.
Например, если в разделе описания предикатов объявлен предикат
увлечение(человек, действие)
то выше надо описать в разделе доменов
DOMAINS
человек, действие = symbol
Одно из преимуществ объявления собственных доменов заключается в том, что компилятор может отслеживать ошибки типов (слайд 9):
DOMAINS
имя, пол = symbol
возраст = integer
PREDICATES
человек(имя, пол, возраст)
ровесник(X, Y) :- человек(X, Pol, Let), человек(Pol, Y, Let).
Здесь переменная Pol указана в одном правиле при обращении к разным типам данных. Отсюда мы делаем однозначный вывод: если переменная в предложении используется более чем в одном предикате, она должна быть одинаково объявлена в каждом из них.
Стандартные домены
Таблица 2.
| Домен | Описание | Значение |
| short | короткое, знаковое, количественное | -32 768 .. 32 767 |
| ushort | короткое, беззнаковое, количественное | 0 .. 65 535 |
| long | длинное, знаковое, количественное | -2 млрд. .. 2 млрд. |
| ulong | длинное, беззнаковое, количественное | 0 .. 4 млрд. |
| integer | знаковое, количественное | или -32 768 .. 32 767 или -2 млрд. .. 2 млрд. |
| unsigned | беззнаковое, количественное | или 0 .. 65 535 или 0 .. 4 млрд. |
| byte | 0 .. 255 | |
| word | 0 .. 65 535 | |
| dword | 0 .. 4 млрд. | |
| char | символ, заключенный в апострофы | |
| real | число с плавающей десятичной точкой (эквивалентен типу double в C) в интервале: 10-307 .. 10308 | |
| string | 1) последовательность символов, заключенных в кавычки 2) последовательность букв, цифр и символов подчеркивания, начинающаяся со строчной буквы | |
| symbol | то же, что и string |
Сопоставление и унификация
Все предложения Пролога строятся из термов (фактов и правил). Терм является синтаксической единицей программы. Главной операцией в процессе выполнения Пролог-программы, является сопоставление термов.
Сопоставление – это процесс, на вход которого подаются два терма, а он проверяет, соответствуют ли эти термы друг другу. Операция сопоставления берет два терма и пытается сделать их идентичными, подбирая соответствующую конкретизацию переменных в обоих термах. Если термы не сопоставимы, значит сопоставление терпит неудачу. Если термы сопоставимы, тогда процесс сопоставления находит конкретизацию переменных, делающих эти термы тождественными, и завершается удачей.
Получив запрос, состоящий из нескольких предикатов, интерпретатор выбирает первый в последовательности запроса предикат и делает попытку (если этот предикат не встроенный) согласовать его с утверждениями, составляющими базы фактов и правил. Для этого выполняется сопоставление этого предиката со всеми фактами и заголовками всех правил в простом линейном порядке до тех пор, пока оно не даст положительного результата. Если этого не происходит, ответом на запрос будет «нет». Если в ходе просмотра произошло сравнение с заголовком правила, то тело правила рекурсивно рассматривается в качестве нового целевого утверждения, доказательство которого реализуется с помощью рассматриваемой здесь процедуры.
Удовлетворив один предикат (подцель) запроса, интерпретатор переходит к соседнему справа, обрабатывая его аналогичным образом. При этом Пролог выполняет поиск от начала программы и до ее конца. Обнаружив предложение, соответствующее целевому утверждению, Visual Prolog присваивает значения свободным переменным таким образом, что целевое утверждение и предложение становятся идентичными. В этом случае говорят, что утверждение унифицируется с предложением. Такая операция сопоставления называется унификацией.
Унификация – это сопоставление двух произвольных термов, содержащих переменные, с целью определения того, можно ли присвоить этим переменным такие значения, чтобы получились два одинаковых терма.
Например(слайд 10) , унификация термов f(X, 2) и f(1, Y), где X, Y - переменные, выдаст подстановку: X=1, Y=2. Унификация термов f(X) и Х пройдет безуспешно.
Свободная переменная может быть унифицирована с любым другим аргументом и даже с другой свободной переменной.
Пример 6. (слайд 11)
Рассмотрим совокупность фактов:
профессия(администратор).
профессия(повар).
профессия(кондитер).
профессия(кассир).
профессия(дворник).
сотрудник(голубева, жен).
сотрудник(иванова, жен).
сотрудник(васин, муж).
сотрудник(смирнов, муж).
сотрудник(азаров, муж).
По запросу
GOAL
профессия(кондитер).
пройдет сопоставление термов, и Пролог среди предложений выделит группу тех, которые связаны с одноместным предикатом профессия. Затем Visual Prolog проведет унификацию целевого утверждения и каждого из выбранных предложений. На третьем шаге сопоставление установит идентичность термов. Процесс закончится успешно, а Пролог выдаст «yes» в качестве результата.
По запросу
GOAL
профессия(коcмонавт).
процесс сопоставления термов будет организован аналогично, но закончится он неуспешно, и Пролог выдаст «no» в качестве результата.
По запросу
GOAL
сотрудник(Кто, муж).
пройдет сопоставление целевого утверждения и каждого из предложений группы термов, связанных с двухместным предикатом сотрудник. Уже на третьем шаге сопоставление установит идентичность термов, при условии, что переменная Кто будет конкретизирована и примет значение васин. Пролог сообщит об этом записью Кто=васин, а затем продолжит труд над согласованием целевого утверждения с оставшимися предложениями, освободив переменную Кто для дальнейшей работы. Уже в следующей попытке будет установлена идентичность термов, а значение Кто конкретизировано. Visual Prolog сообщит об этом так: Кто = смирнов. Аналогично будет найдено решение Кто = азаров, и Пролог выдаст 3 Solutions в качестве результата. n
Поиск с возвратом
Часто при решении какой-либо задачи мы придерживаемся определенной стратегии. Если полученный результат не дает искомого ответа, мы должны выбрать другой путь. Пролог при поиске решения задачи использует именно такой метод проб и возвращений назад. Этот метод называется поиск в возвратом. Если, начиная поиск решения (или согласования целевого утверждения) задачи, Пролог должен выбрать между альтернативными путями, то он ставит маркер у места ветвления (называемого точкой отката) и выбирает первую подцель, которую и станет проверять. Если данная подцель не выполнится (что эквивалентно достижению тупика в лабиринте), то Visual Prolog вернется к точке отката и попробует проверить другую подцель.
Попытка согласования целевого утверждения начинается с вершины программы. Если соответствие обнаружено, то инициируется процесс конкретизации переменных.
В том случае, когда в программе существует более чем один возможный ответ на некоторое обращение, ставится точка возврата после соответствующего факта. Эта точка указывает на то место, откуда начнется поиск следующего возможного согласования для некоторого предложения. Механизм возврата запускается тогда, когда в программе не обнаруживается соответствующих предложений. Когда Пролог отступает к точке поиска с возвратом, он освобождает все переменные, связанные после этой точки, и ищет другое решение для исходного обращения.