Программа на прологе состоит из предложений . Предложения трех видов: факты, правила, вопросы. Все предложения строятся из термов.
2.1.1 Константы.
Константы — это поименованные конкретные объекты или отношения.
Атомы — аналогичны атомам или символам в лиспе.
Атомы могут задаваться:
1) Цепочкой букв, цифр и символом подчеркивания ‘_’, начиная со строчной буквы.
2) специальными символами*: ====>
Числа
Целые ( диапазон -32768 32767)
Действительные ( диапазон 1Е-307 1Е+308)
2.1.2 Переменные.
Переменные служат для обозначения объектов, значения которых меняются в ходе выполнения программы.
Имена переменных могут начинаться:
— или с прописной буквы
— или с символа подчеркивания
Eсли значение переменной не интересует, то можно использовать анонимные переменные в виде символа подчеркивания ‘_’.
haschild(X):-parent(X, Y).
Пролог — попытка объяснить без программирования
Здесь значение Y не интересует, можно записaть
Значение анонимной переменной не выводится на печать. Если несколько анонимных переменных, то они все разные. Использование анонимных переменных позволяет не выдумывать имена переменных, когда не надо.
Пусть задано отношение parents для двух родителей.
parents(ann, tom, bob).
Тогда в правиле:
child(X):-parents(_, _, X).
обе анонимные переменные разные.
Одноименные переменные в разных предложениях могут иметь разные значения.
2.1.3 Структуры.
Структура — это единый объект состоящий из совокупности других объектов, называемых компонентами.
Компоненты в свою очередь могут быть также структурами.
Название структуры стоит перед скобками,а компоненты внутри скобок, через запятую.
Название структуры — ФУНКТОР .
Структуры можно изображать в виде деревьев:
data / | 27 april 1992
Структура с компонентами — структурами owns(bob, book(moby_dick, mell_will)).
Структуры можно использовать для представления геометрических фигур. Объекты:
точка Р1=point(1, 1)
точка Р2=point(3, 3)
отрезок seg(P1, P2)
или
seg(point(1, 1), point(3, 3))
треугольник
triangle(point(2, 5), point(2, 8), point(5, 8))
Cтруктуру можно представить в виде дерева
Если точка трехмерного пространства: point3(X, Y, Z)
Можно записать : point(X, Y, Z)
Получается: point(X, Y, Z) и point(X, Y)
Это разные термы, т.к. каждый функтор различается двумя параметрами:
- именем
- арностью — т.е. числом атомов
point/2
point/3
Например,если написано: Отношение point/2 задано .
Это означает, что задано point(_,_) ,
а не point/2(_,_).
. Это типичная ошибка.
Структура программы на ПРОЛОГе
2.1.4 Операторы — тоже функторы.
Некоторые функторы удобнее записывать, как операторы.
Например, можно записать
+ / 1 2
Удобнее записать 1+2 , т.е. в виде оператора. Причем надо понимать, что это не операция сложения, а операторная запись структуры. Такие операторы называются инфиксными .
Аналогично операторная запись
может быть представлена в виде структуры:
Это и производит пролог при трансляции операторных выражений. Надо четко понимать, что операторы — это другая форма записи структуры.
2.2 Арифметика.
В прологе выполняются следующие операции:
+
—
*
/
mod — остаток от целочисленного деления.
X=2+1
т.к. это просто сопоставление переменной и структуры.
Чтобы арифметическое выражение рассчитывалось, необходимо использовать встроенный оператор is , который заставляет выполнять арифметические операции.
?- Y is 2*(5+6).
Y=22
Могут быть переменные, но они должны иметь значение к моменту вычисления.
f(X, Y, Z):-Z is X*X + Y*Y.
R=13
Если определить:
sum(X1, X2, X):-X is X1 + X2.
?- sum(1, 1, X1), sum(X1, X1, X).
4.
2.3 Операции сравнения.
Используются при сравнении чисел
Есть операции
равенство для любых термов
yes
age(mary, 20).
age(ann , 23).
age(bob , 25).
?- age(X , Y), Y>21, Y X=ann ;
2.4 Сопоставление.
Главной операцией в процессе выполнения пролог -программы, является сопоставление (согласование, унификация) термов.
рarent(pam, bob).
Yes
Цель согласуется.
X=bob
Tоже согласуются, но X конкретизируется и принимает значение bob
Но если взять два составных терма -структуры.
a(b, C, d(e, F, g(h, i, J)))
a(B, c, d(E, f, g(H, I, j)))
cогласуются ли они? Что будет с переменными после согласования? Как они будут конкретизированны?
Сопоставление -это процесс, на вход которого подаются два терма, а он проверяет, соответствуют ли эти термы друг другу.
Если термы не сопоставимы, значит сопоставление терпит неудачу.
Если термы сопоставимы, тогда пpоцесс сопоставления находит конкретизацию переменных, делающих эти термы тождественными, и завершается удачей.
Какие же правила определяют сопоставимость двух термов S и Т ?
-
Если S и Т константы , то S и Т cопоставимы, только, если они являются одним и тем же объектом.
т.е.:
2 сопоставляется с 2
bob сопоставляется с bob
data(may, 3, Y).
Сопоставимы, переменные конкретизируются:
М=may
D=3
Y=1992
в обоих термах.
Если сопоставить структуры
a(b, C, d(e, F, g(h, i, J)))
a(B, c, d(E, f, g(H, I, j)))
Рассмотрим более сложный пример:
triangle(point(2, 5), A, point(B, 8)) triangle(X, point(2, 8), point(5, 8))
X=point(2, 5)
A=point(2, 8)
B=5
Еще один пример:
конкретизированная переменная Х=2
! triangle(point(X, 5), point(X, 8), point(5, Z))
неконкретизированная переменная Y=2
! triangle(point(2, 5), point(Y, 8), point(5, A))
Если Y представляет собой неконкретизированную переменную, а переменная X конкретизированную, тоX и Y согласуются и принимает значение Х .
т.е.
Переменные Z и A обе не конкретизированы. Они согласуются и становятся сцепленными .
Если две переменные сцеплены, то при конкретизации одной из них, второй переменной автоматически будет присвоено тоже самое конкретное значение, что и первой. Как это было с X и Y .
2.5 Второе значение операции = в Прологе.
В прологе операция = , кроме сравнения выполняет сопоставление двух термов, с конкретизацией переменных.
Если термы согласуются, то результат истина.
Yes
B=d
X=x
D=3
Аналогично, /= дает истину, если термы не согласуются.
Yes
2.6 Примеры сопоставления структур.
Рассмотрим структуры, описывающие отрезки
Два факта ,описывающие свойство вертикальность
и горизонтальность.
?- horiz(seg(point(1,4),point(2,4))).
Yes
(c) M.N.Morozov, 1999.
Источник: www.mari-el.ru
Структура программы на языке Пролог
2. Лабораторная работа №1. «вычисление целей. Откат»
Откат – это механизм, который Турбо-Пролог использует для нахождения дополнительных фактов и правил, необходимых при вычислении цели, если текущая попытка вычислить цель оказалась неудачной. Турбо-Пролог пытается вычислить цель при помощи сопоставления терма предиката и объектов цели с соответствующими элементами в фактах и головах правил.
Сопоставление выполняется слева направо. Некоторые подцели, вероятно, будут неуспешными при сопоставлении с некоторыми фактами или правилами, поэтому Турбо-Прологу требуется способ «запоминания точек», в которых он может продолжить альтернативные попытки найти решение.
Прежде чем попробовать один из возможных путей решения подцели, Турбо-Пролог фактически помещает в программу «указатель», определяющий точку, в которую может быть выполнен откат, если текущая попытка будет неудачной. По мере того как Турбо-Пролог успешно заканчивает свои попытки вычисления подцелей слева направо, указатели отката расставляются во всех точках, которые могут привести к решению.
Если некоторая подцель оказывается неуспешной, то Турбо-Пролог откатывается влево и останавливается у ближайшего указателя отката. С этой точки Турбо-Пролог начинает попытку найти другое решение для неуспешной цели.
До тех пор, пока следующая цель на данном уровне не будет успешной, Турбо-Пролог будет повторять откат к ближайшему указателю откатаекоторая подцель оказывается неуспешной, то Турбо-Пролог откатывается влево и останавливается у ближайшего указателя отката. п. Эти попытки выполняются внутренними подпрограммами унификации и механизмом отката. Окончательным результатом будет либо успешное, либо неуспешное вычисление цели.
Рассмотрим следующий пример: predicates likes(symbol,symbol) fruit(symbol) color(symbol,symbol) clauses likes(mary,pears). 2 likes(mary,popcorn). 4 likes(mary,apples). likes(beth,X):- likes(mary,X), fruit(X), color(X,red). 1 likes(beth,X):- likes(mary,X), X= popcorn. fruit(pears). fruit(apples). color(pears,yellow). color(oranges,orange). color(apples,yellow). color(apples,red). Целевое утверждение следующее — likes(beth,X).
Для того чтобы ответить на данный вопрос, внутренние унификационные программы Турбо-Пролог ищут факты или голову правила, сопоставимую с этим целевым утверждением. Поиск начинается с первого утверждения для отношения likes, которое содержит три факта о том, что любит Мэри. Турбо-Пролог опробует все утверждения слева направо (сверху вниз).
Сопоставления для всех из них будут неуспешными, так как константаbethнесопоставима с константой mary. Внутренние унификационные подпрограммы Турбо-Пролога переходят к правилу: likes(beth,X):- likes(mary,X), fruit(X), color(X,red). Переменные, как в голове правила, так и в цели неозначены, так что цель и голова правила сопоставимы.
Так как голова (левая часть) первого правила сопоставима с целью, то факты правой части становятся подцелями, которые Турбо-Пролог должен вычислить, обрабатывая их слева направо. Вспомним, что Турбо-Пролог рассматривает термы, разделенные запятыми, как следующие друг за другом, даже если они находятся на разных строках.
Так как другие утверждения для likes следуют за этим правилом, то Турбо-Пролог помещает указатель отката на начало следующего правила для likes. Эта точка отмечена цифрой 1. Первой подцелью является likes(mary,X). Эта новая подцель, поэтому Турбо-Пролог сначала начинает просмотр с вершины списка предикатов дляlikesи находитlikes(mary,pears).
Этот факт сопоставим с подцельюlikes(mary,X), так как все ее термы сопоставимы, поскольку X получила значение pears во время унификации. Теперь подцель likes(mary,X) успешно вычислена, но правило, которое сгенерировало эту подцель, сгенерировало также и другие подцели, которые еще должны быть доказаны. Поэтому внутренние унификационные подпрограммы ставят указатель на следующий факт дляlikes.
Эта точка отмечена цифрой 2. Данный указатель показывает, что существует, по крайней мере, еще одно утверждение дляlikes, которое может быть использовано для вычисления текущей подцели. В случае если следующая подцель окажется неуспешной, механизм отката будет иметь точку для поиска другого кандидата для вычисления цели.
К этому моменту цель likes(beth,X) была сопоставлена с головой правилаlikes(beth,X). Внутренние унификационные подпрограммы установили указатель на голову следующего правилаlikes(beth,X) и начали попытки вычисления утверждений в правой части правила. В результате была сгенерирована подцельlikes(mary,X).
Пытаясь ее вычислить, унификационные подпрограммы обнаружили сопоставимое утверждениеlikes(mary,pears). Теперь X получила значениеpears, а значение подцели сталоlikes(beth,pears). Существуют и другие утверждения, которые могут быть использованы для вычисления подцели, поэтому указатель отката был установлен наlikes(mary,popcorn). Следующая подцель справа есть fruit(X).
Так как сейчас X имеет значение pears, то подцель означает fruit(pears). Внутренние унификационные подпрограммы находят сопоставление с первым утверждением для fruit.
Так как существуют другие утверждения, которые могут быть использованы для вычисления подцели, то создается еще один указатель отката на это утверждение, отмеченный цифрой 3. Теперь два указателя отката отмечают альтернативные пути к решению правила: likes(beth,X):- likes(mary,X), fruit(X), color(X,red). Это точки 2 и 3 (точка 1 – это альтернативный путь к решению основной цели).
Последняя отмеченная точка всегда является точкой, с которой будет начат поиск альтернативного решения. Последняя подцель правила есть color(X,red). Внутренние подпрограммы унификации, всякий раз просматривая утверждения слева направо, пытаются сопоставить подцель с утверждениемcolor(pears,yellow). Тек как X имеет значение pears, то текущая подцель естьcolor(pears,red).
Все попытки вычислить ее неуспешны, поскольку программа не содержит утверждения color(pears,red). Подцель вычислена неуспешно. Внутренние унификационные подпрограммы выполняют откат к последнему указателю, который установлен на fruit(pears). Это сопоставление неуспешно, так что механизм отката повторяет откат к ближайшему предыдущему указателю, который установлен наlikes(mary,popcorn).
Указатель отката, отмеченный цифрой 4, станавливается на следующее утверждение дляlikes. Переменная X имеет значениеpopcorn, так что теперь подцели эквивалентны «Мэри любит кукурузные зерна, и кукурузные зерна – фрукт красного цвета». Подцель fruit(popcorn) не может быть доказана при помощи фактов и правил, имеющихся в программе, так что подцельlikes(mary,X) неуспешна.
Переменная X освобождается, и подцельlikes(mary,X) неуспешна. Переменная X освобождается, и подцель likes(mary,X) в правилеlikes(beth,X) имеет еще один шанс на успех, так как был отмечен для отката еще один факт о том, что любит Мэри. Внутренние унификационные подпрограммы выполняют откат в точку 4. Теперь подцель сопоставляется с likes(mary,apples) и X получает значениеapples.
Выполняется попытка для следующей подцелиfruit(apples). Первое утверждение дляfruitимеет объектpears. Объекты несопоставимы, так что внутренние унификационные подпрограммы переходят к следующему фактуfruit(apples), который сопоставим с подцелью. Наконец, последняя подцель первого правила проверена. Снова делается попытка сопоставить ее с фактом для color. В этот момент подцель есть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, с точки зрения внутренних унификационных подпрограмм выглядит так likes(beth,apples):- likes(mary,apples), fruit(apples), color(apples,red). Выдав сообщение X= apples, Турбо-Пролог показывает, что для цели найдено, по крайней мере, одно решение. Снова используется последняя подцель. Теперь со значением color(apples,red).
Еще раз все утверждения дляcolorпроверяются по очереди для сопоставления с новой подцелью. Сопоставление найдено в последнем утвержденииcolor(apples,red). Теперь все три подцели правила доказаны. Переменная X имеет значениеapples. Следовательно, сейчас голова правила имеет видlikes(beth,apples) и сопоставима с утверждением целиlikes(beth,X), так что цель успешна, и Турбо-Пролог выдает сообщениеX=apples.
Поскольку внешняя цель была использована с программой, являющейся «черным ящиком» для Турбо-Пролога, то он продолжает поиск других решений для цели. Цель была успешной, так что переменная X освобождена и может быть снова означена подпрограммами внутренней унификации. Поиск решений снова начинается с указателя отката, который теперь является последним.
Это указатель точки 1. Указатель точки 2 был удален, так как в конце пути было найдено решение. Теперь внутренние унификационные подпрограммы начинают поиск с правила 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есть константа. Операция сравнения будет неуспешной: pears=popcorn. Термы несопоставимы, поэтому подцель неуспешна и X снова освобождена.
Теперь внутренние унификационные подпрограммы выполняют откат к последнему указателю, с тем, чтобы попробовать альтернативный путь решения. Последний указатель отката установлен на утверждение likes(mary,popcorn). Ранее X была освобождена, поэтому сейчас она получает значение popcorn. Установив указатель отката на следующее утверждениеlikes(mary,apples), внутренние значения термов есть popcorn=popcorn.
Сопоставление успешно, и последняя подцель правила успешно вычислена. Переменная X в голове правила имеет значение popcorn. Таким образом, выведенный факт естьlikes(beth,popcorn). Турбо-Пролог сообщает об этом, выдавая X=popcorn. Теперь найдены два решения, а указатель отката остался на утверждении likes(beth,popcorn). Турбо-Пролог возвращается в указанную точку и пытается найти еще одно решение.
Данный путь является альтернативным для второй подцели второго правила для 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 (два решения).
Ограничение
Для продолжения скачивания необходимо пройти капчу:
Источник: studfile.net
Структура программы на языке Пролог
При программировании на Прологе усилия программиста должны быть направлены на описание логической модели фрагмента предметной области решаемой задачи в терминах объектов предметной области, их свойств и отношений между собой, а не деталей программной реализации. Фактически Пролог представляет собой не столько язык для программирования, сколько язык для описания данных и логики их обработки. Программа на Прологе не является таковой в классическом понимании, поскольку не содержит явных управляющих конструкций типа условных операторов, операторов цикла и т. д. Она представляет собой модель фрагмента предметной области, о котором идет речь в задаче.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФГБОУ ВПО «Уральский государственный экономический университет»
Центр дистанционного образования
по дисциплине: Основы логического программирования______________ __________
по теме: Структура программы на языке Пролог
Структура программы на языке Пролог
При программировании на Прологе усилия программиста должны быть направлены на описание логической модели фрагмента предметной области решаемой задачи в терминах объектов предметной области, их свойств и отношений между собой, а не деталей программной реализации. Фактически Пролог представляет собой не столько язык для программирования, сколько язык для описания данных и логики их обработки. Программа на Прологе не является таковой в классическом понимании, поскольку не содержит явных управляющих конструкций типа условных операторов, операторов цикла и т. д. Она представляет собой модель фрагмента предметной области, о котором идет речь в задаче. И решение задачи записывается не в терминах компьютера, а в терминах предметной области решаемой задачи, в духе модного сейчас объектно-ориентированного программирования.
Пролог очень хорошо подходит для описания взаимоотношений между объектами. Поэтому Пролог называют реляционным языком. Причем «реляционность» Пролога значительно более мощная и развитая, чем «реляционность» языков, используемых для обработки баз данных. Часто Пролог используется для создания систем управления базами данных, где применяются очень сложные запросы, которые довольно легко записать на Прологе.
В Прологе очень компактно, по сравнению с императивными языками, описываются многие алгоритмы. По статистике, строка исходного текста программы на языке Пролог соответствует четырнадцати строкам исходного текста программы на императивном языке, решающем ту же задачу. Пролог-программу, как правило, очень легко писать, понимать и отлаживать. Это приводит к тому, что время разработки приложения на языке Пролог во многих случаях на порядок быстрее, чем на императивных языках. В Прологе легко описывать и обрабатывать сложные структуры данных.
Прологу присущ ряд механизмов, которыми не обладают традиционные языки программирования: сопоставление с образцом, вывод с поиском и возвратом. Еще одно существенное отличие заключается в том, что для хранения данных в Прологе используются списки, а не массивы. В языке отсутствуют операторы присваивания и безусловного перехода, указатели. Естественным и зачастую единственным методом программирования является рекурсия. Поэтому часто оказывается, что люди, имеющие опыт работы на процедурных языках, медленней осваивают декларативные языки, чем те, кто никогда ранее программированием не занимался, так как Пролог требует иного стиля мышления, отказа от стереотипов императивного программирования.
Фразы Хорна (Horn clause) представляют собой подмножество фраз, содержащих только один позитивный литерал. В общем виде фраза Хорна представляется выражением
В языке PROLOG эта же фраза записывается в таком виде:
р :- q1. qn. Такая фраза интерпретируется следующим образом:
«Для всех значений переменных в фразе p истинно, если истинны q1 и . и qn»,
т.е. пара символов «:-» читается как «если», а запятые читаются как «и».
PROLOG — это не совсем обычный язык программирования, в котором программа состоит в основном из логических формул, а процесс выполнения программы представляет собой доказательство теоремы определенного вида.
может рассматриваться в качестве процедуры. Такая процедура предполагает следующий порядок выполнения операций.
(1) Литерал цели сопоставляется с литералом р (унифицируется с р), который называется головой фразы.
(2)Хвост фразы ql, . qn конкретизируется подстановкой значений переменных (или унификаторов), сформированных в результате этого сопоставления.
(3) Конкретизированные термы хвостовой части образуют затем множество подцелей, которые могут быть использованы другими процедурами.
Таким образом, сопоставление (или унификация) играет ту же роль, что и передача параметров функции в других, более привычных языках программирования.
Например, рассмотрим набор фраз языка PROLOG, представленных в листинге 1. Предположим, что a, b и с — какие-то блоки в мире блоков. Две первые фразы утверждают, что а находится на (on) b, a b находится на (on) с. Третья фраза утверждает, что X находится выше (above) Y, если X находится на (on) Y. Четвертая фраза утверждает, что X находится выше (above) Y, если существует какой-то другой блок Z, размещенный на (on) Y, и X находится выше (above) Y.
Листинг 1. Простая программа на языке PROLOG, определяющая отношение
above(X, Y) :- on(X, Y).
above(X, Y) :- on(Z, Y),
Очевидно, что от программы требуется вывести цель above (а, с) из этого множества фраз. Процесс формулировки выражения цели включает обработку двух процедур above и использование двух фраз on. В языке PROLOG используется «интерпретация фраз Хорна для решения проблем» Фундаментальный метод доказательства теорем, на котором базируется PROLOG, называется опровержением резолюций (resolution refutation).
Пролог является языком программирования, который обеспечивает решение задач, выраженных в терминах объектов и отношений между ними.
Отличительные особенности языка Пролог состоят в следующем:
- Для представления знаний используются фразы Хорна.
- Программа описывает логическую модель Предметной Области в виде фактов относительно свойств Предметной Области и отношений между этими свойствами + правила вывода новых свойств и отношений из уже заданных.
- В качестве единообразной структуры данных используется терм.
- Отсутствуют операторы присваивания, ветвлений, безусловных переходов, а также указатели, которые используются при определении динамических структур данных в традиционных процедурно-ориентированных языках.
Написание программы на языке Пролог включает следующие этапы:
- Объявление некоторых фактов об объектах и отношениях между ними.
- Определение некоторых правил, касающихся объектов и отношений между ними.
- Формулировка вопросов об объектах и отношениях между ними.
Для объяснения смысла программы применяются три семантические модели: декларативная, процедурная модели и модель в виде абстрактной машины.
Процедурная трактовка Пролог-программы.
При процедурной трактовке Пролог-программы подчеркивается последовательность шагов, которые выполняет интерпретатор при обработке запроса. Здесь имеет значение порядок следования подцелей в правиле.
Множество фраз, имеющих одно и то же имя и одинаковое количество аргументов, рассматривается как процедура. При этом запрос (или подцель правила) является вызовом процедуры.
Декларативная трактовка Пролог-программы.
При декларативной трактовке Пролог-программы специфицируются истинностные значения конкретных случаев отношений.
Для декларативной модели фразы Пролога являются формулами логики предикатов 1-го порядка, записанными в форме фраз Хорна.
Модель в виде абстрактной машины.
С позиций декларативной модели Пролог-программа есть описание логической структуры. При выполнении запроса интерпретатор применяет по отношению к множеству фраз Пролога некоторую стратегию решения задачи. С точки зрения вычислений эта стратегия может быть описана при помощи некоторой абстрактной машины.
В языке Пролог запрос и множество фраз программы имеет вычислительный смысл. Это проявляется в том, что они вызывают определенное поведение интерпретатора Пролога. Модель в виде абстрактной машины описывает смысл запроса и множества фраз через действия этой машины.
Действия такой абстрактной машины можно рассматривать как применение правила резолюции.
Язык Пролог основывается на языке исчисления предикатов первого порядка и методике автоматического доказательства теорем (метод резолюции с ограничениями для уменьшения пространства поиска). Пролог был разработан в 1972 г. А. Кольмероэ из Марсельского университета. В течение следующего десятилетия язык получил дальнейшее развитие благодаря работам Р. Ковальского и других исследователей. Теперь Пролог применяется в следующих областях:
– общение с ЭВМ на естественном языке;
– интерфейсы реляционных баз данных;
– создание систем автоматического программирования;
– представление и обработка знаний в задачах искусственного интеллекта;
– экспертные системы;
– символические вычисления;
– решение задач в области математической логики;
– написание компиляторов.
К достоинствам языка Пролог относятся:
– сочетание декларативного и процедурного подхода;
–простые и легко понимаемые тексты программ;
– высокая степень модульности, облегчающая модификацию и отладку программ;
– эффективность реализации и доступность транслятора на всех типах ЭВМ.
Программа на языке Пролог описывает знания о некоторой предметной области. Эти знания включают в себя факты, описывающие свойства объектов и отношения между ними, и правила, на основании которых могут быть получены новые знания о свойствах объектов и отношениях между ними. Факт состоит из имени отношения и списка объектов, между которыми это отношение существует. Каждый факт должен заканчиваться точкой. Имена всех объектов и отношений должны начинаться со строчной буквы. Например, факт «Джону нравится Мэри» записывается так:
Выполнение программы инициализируется запросом. Интерпретатор пытается логически вывести запрос, используя знания о предметной области, содержащиеся в программе, которая является своего рода базой данных (БД) об объектах в задаче. Если существует факт, сопоставимый с целью, указанной в запросе, то интерпретатор отвечает утвердительно. В противном случае будет получен отрицательный ответ. Например, пусть БД содержит следующие факты:
Запрос обычно вводится в диалоговом режиме после подсказки «?–» и должен заканчиваться точкой. Например, на эти запросы будут получены следующие ответы:
На второй запрос был получен отрицательный ответ, так как из того, что Джону нравится Мэри, не следует, что Мэри нравится Джон. Остальные отрицательные ответы связаны с ограниченностью БД, в которой не отражаются связи, возможно существующие в действительности. Чтобы узнать все объекты, которые нравятся Джону, нужно указать в запросе вместо имени конкретного объекта переменную. Имя переменной должно начинаться с прописной буквы или символа подчеркивания.
Интерпретатор сопоставляет цель в запросе с фактами в БД, при этом переменная получает значение аргумента отношения, стоящего в соответствующей позиции. Если согласование цели с БД возможно, то значение переменной выводится на экран, и можно ввести символ «;», чтобы получить другой вариант решения. Если вариантов больше нет, то выводится отрицательный ответ. Если альтернативные решения не нужны, то вместо «;» нужно нажать клавишу Enter.
Используя конъюнкцию целей, можно строить более сложные запросы. При этом цели в запросе перечисляются через запятую, а для получения утвердительного ответа необходимо согласование всех целей в запросе. Например, запрос «Существует ли что-либо, что нравится и Джону, и Мэри?» выглядит так:
Если факт – это отношение, которое безусловно истинно, то правило – это отношение, которое является истинным, только если выполняется некоторое условие. Правило состоит из головы, которая определяет новое свойство или отношение объектов, и тела, которое содержит условие. При попытке сопоставления цели в запросе и головы правила выполняется согласование целей в теле правила. Если это согласование успешно, то отношение, задаваемое головой правила, истинно.
Правило должно заканчиваться точкой, а голова от тела правила отделяется обозначением «:–», которое читается как «если». Например, правило «Мэри нравится любой, кому нравится кино» записывается как:
Источник: www.myunivercity.ru