Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Основы языка Пролог (стандарт)
Особенности языка
Пролог имеет два главных отличия от процедурных языков: 1) Программирование на Прологе по-преимуществу является символьным. Данные в этом языке – это символы, которые никак не интерпретируются, и числа. (исключение – числа). 2) Так как Пролог относится к парадигме декларативного программирования, алгоритмы решения задач не задаются. Формулируется лишь условие задачи, после чего она решается с помощью встроенного (в интерпретатор) универсального алгоритма логического вывода, основанного, как уже упоминалось, на входной линейной резолюции. Программа на Прологе состоит из описания предметной области и вопроса. Предметная область задается описанием объектов и отношений между ними с помощью фактов и правил. Факты и правила представляются хорновскими дизъюнктами: факты – унитарными позитивными дизъюнктами, правила – точными дизъюнктами. При этом с помощью фактов указываются тождественно истинные утверждения – представленные предикатами со значениями аргументов (термов), при которых они являются истинными. С помощью правил задаются средства установления новых фактов. Каждое правило интерпретируется так: если истинными являются все предикаты, представленные негативными литерами, то истинным считается и предикат, представленный позитивной литерой. Вопросы указывают на необходимость установить наличие в БЗ указанных в них фактов или попытаться вывести эти факты в качестве новых. Вопросы представляются негативными дизъюнктами. Характерными чертами языка Пролог считаются: 1) наличие алгоритма вывода с поиском и возвратом, который осуществляется с помощью стековой памяти и используется для перебора всех возможных вариантов вывода; возврат часто называется откатом, а перебор вариантов с откатом выполняется процедурой, называемой бэктрекингом. 2) наличие встроенного механизма сравнения с образцом (для реализации процедуры унификации); 3) простые синтаксис и структура данных. Синтаксис языка. Синтаксическими элементами языка являются: Термы: константы, переменные, сложные термы. Константы: целые и вещественные числа, атомы (любые цепочки символов, не начинающиеся с заглавных букв или любые цепочки символов в кавычках).
Целые числа представляются последовательностями цифр с возможным знаком «+» или «-». Вещественные числа представляются в двух форматах: 1) В виде десятичной дроби, например: 10.12, -0.25, +35.1234. В некоторых случаях целые числа могут интерпретироваться как десятичные дроби – это зависит от контекста, в котором находится число. 2) В виде мантиссы и десятичного порядка: <десятичная дробь>Е<целое>, например: 1.012E1, -0.95Е+3, 125Е-2. Как видно из примеров, перед вещественными числами могут находиться знаки «+» или «-» Переменные: цепочки букв, цифр и знака подчеркивания («_»), начинающиеся с заглавной буквы или знака подчеркивания. Особая переменная – анонимная. Она представляется знаком подчеркивания. Сложный терм это: 1) структура, состоящая из атома-предиката ( или функтора) и компонент, т.е. термов в скобках через запятую; при этом компоненты сами могут являться сложными термами; например информация о книгах библиотеки может состоять из следующих данных: автор, название, издательство, год выпуска – книга(“Л.Н. Толстой”, “Война и мир”, “Художественная литература”, “2002”). 2) список, т.е. упорядоченный набор связанных между собой термов; имеется возможность работать как целиком со списком, так и с отдельными входящими в него термами. Константы и структуры представляют объекты предметной области, а списки – упорядоченные наборы объектов. Роль структур заключается в группировке некоторых объектов, представляющих составной объект. База знаний, описывающая предметную область, задается фактами и правилами. Факты – это отдельные предикаты, состоящие из имени предиката и, возможно, термов, представляющих его аргументы. Правила имеют вид: p 1 (…): – p 2 (…), …, pn (…), n ≥ 2, где pi – предикаты. Приведем примеры простых баз знаний, пояснив кроме синтаксиса также их семантику. Фрагмент словаря синонимов и антонимов может быть представлен следующей базой знаний: synonym("храбрый","отважный"). synonym("храбрый","бесстрашный"). synonym("современный","новый"). synonym("редкий","неупотребительный"). antonym("храбрый","трусливый").
antonym("честный","бесчестный"). antonym("современный","старый"). antonym("редкий","частый"). Фрагмент описания предметной области «Дифференцирование», который представляет правило дифференцирования суммы, может быть представлен следующими фактом и правилом: diff(Х,Х,1). diff (U+V, X, A+B): – diff (U, X, A), diff (V, X, B). Отметим, что в первом из этих примеров мы использовали только факты. Все они представляют два предиката, для имен которых использованы функторы synonym и antonym. Вы можете без труда заметить, что их компоненты подобраны так, что они действительно являются, соответственно, синонимами и антонимами друг друга в общепринятом понимании этих терминов. Во втором примере имеется факт diff(Х,Х,1). Он отражает простейшее правило дифференцирования, согласно которому производная по X функции F(X) = X равна 1. Правило второго примера интерпретируется так: если производная по X функции U равна A, а производная по X функции V равна B, то производная по X суммы U+V равна A+B. Вопросы представляются в виде одного или нескольких предикатов, называемых целями: ?- p 1 (…), p 2 (…), …, pn (…), n ≥ 1. Список целей, заданный этим вопросом, таков: p 1 (…), p 2 (…), …, pn (…). Если вопрос состоит из одного предиката, то он называется простым, в противном случае – составным. Активная цель – это первая цель списка (в нашем примере p 1). После осуществления логического вывода активной цели, она исключается из списка, который в случае нашего примера примет вид: p 2 (…), …, pn (…). В этом случае говорят, что цель доказана или достигнута и активной становится цель p 2. Работа заканчивается либо после достижения последней цели списка pn (в случае наличия решений), либо при возникновении тупиковой ситуации, когда вывод какой-нибудь активной цели оказывается невозможным. Программы на Прологе состоят из двух частей – описания предметной области и вопроса: 1) Факты и правила, описывающие предметную область. 2) Вопрос. Например, приписав вопрос ?- synonym("храбрый",X), antonym("храбрый", Y) к базе знаний первого примера, получим программу. Ответы на вопросы пользователей формируются в процессе выполнения программ и в разных версиях языка представляются по-разному. Мы примем следующий вариант. Если ответ должен быть положительным или отрицательным, то он представляется в форме Yes и No соответственно. Если же требуется указать выполненные в процессе логического вывода подстановки, вместо переменных, входящих в цели, то они перечисляются в ответе, после чего указывается число найденных решений. Например, ответ на приведенный выше вопрос выглядит так: X = "отважный", Y = "трусливый" X = "бесстрашный", Y = "трусливый" 2 Solutions
Типы вопросов. В зависимости от вида вопросы языка Пролог делятся на несколько типов. Тип вопроса влияет как на его обработку алгоритмом логического вывода, так и на вид ответа. Различные варианты вопросов удобно рассмотреть на примере предметной области, представляющей родственные отношения (для удобства будем нумеровать предложения, описывающие предметную область).
Граф родственных отношений, представленный этой таблицей, выглядит следующим образом (верхние вершины дуг – родители, нижние – дети):
Рассмотрим типы вопросов. 1) Вопросы, в целях которых отсутствуют переменные. С помощью таких вопросов пользователь может спросить, верно или нет некоторое предположение (свойство, отношение). Например: «Верно ли, что отцом Юлии является Петр?» На Прологе: ? – отец(«Петр», «Юлия») Или: «Верно ли, что Павел является дедушкой Марии?» На Прологе: ? – дед(«Павел», «Мария») На первый вопрос должен быть дан положительный ответ, который система выдаст в виде: Yes. Ответ на второй вопрос отрицательный: No. Вопросы этого типа могут быть и составными, например: «Верно ли, что Анна является бабушкой, а Андрей дедушкой Юлии?» ? – бабка(«Анна», «Юлия»), дед(«Андрей», «Юлия»). Ответ: Yes. Или: «Верно ли, что отцом и матерью Петра являются Иван и Мария?» ? – отец(«Иван», «Петр»), мать(«Мария», «Петр»). Ответ: No. Заметим, что во втором вопросе первая цель представлена правильным предположением, а вторая – неправильным. Так как для положительного ответа требуется, чтобы все предположения были правильными, в данном случае дается отрицательный ответ. 2) Вопросы с использованием переменных (не анонимных). Семантика этих вопросов совсем другая. С их помощью пользователь может узнать, для каких объектов предметной области выполнены свойства или отношения, указанные в вопросе. Например: «Кто является отцом Юлии?». На Прологе: ? – отец (Х, «Юлия»). Или: «Укажите дедушек и бабушек Павла». На Прологе: ? – дед(Х, «Павел»), бабка(Y, «Павел»). В ответах на вопросы этого типа перечисляются значения переменных, при которых предикаты вопросов являются истинными. На первый вопрос будет дан ответ: Х = «Петр». 1 Solution. На второй вопрос будет получен ответ: Х = «Андрей», Y = «Анна» Х = «Иван», Y = «Мария». 2 Solutions. Вопрос может быть таким, что вариантов ответов на него нет, например: «Кто является дедушкой Петра?» ? – дед(Х, «Петр»). Тогда ответ системы будет выглядеть так: No Solution. 3) Вопросы, в которых используется анонимная переменная. Анонимная переменная играет в Прологе особую роль. С ее помощью пользователь может узнать, существуют ли в предметной области такие объекты, для которых его предположение оказывается истинным. При этом его интересует лишь существование таких объектов, но не они сами. Например: «Известен ли хоть один дедушка Юлии?» Или: «Указаны ли в предметной области внуки Петра?» На Прологе:
? – дед(_, «Юлия»). ? – дед(«Петр», _). Ответы на подобные вопросы представляются в такой же форме, как в случае вопросов первого типа: Yes и No соответственно. Как видно из приведенных типов вопросов, при отсутствии анонимных переменных их обработка предполагает полный перебор выводов (так как необходимо найти все варианты ответов). Если в вопросе используется анонимная переменная, перебор может быть сокращен. Так, обрабатывая вопрос? – дед(_, «Юлия»),системе достаточно обнаружить одного деда, хотя как видно из схемы родственных отношений примера, в БЗ их двое. Приведем пример работы алгоритма логического вывода, представив ее в виде таблицы со следующими полями: 1) №№ варианта и шага вывода. Так как потребуется перебор, будет осуществляться возврат на уже выполненные шаги с целью поиска других вариантов их выполнения. Возврат будет осуществляться с помощью процедуры бэктрекинга. 2) Список целей. 3) № предложения (факта или правила), выбранного для резолюции. 4) Унификатор 5) Стек возвратов, используемый процедурой бэктрекинга. Задается в виде: пар: № шага, на который нужно вернуться, и № первого предложения, с которого нужно продолжить просмотр. 6) Примечания. Пусть пользователь ввел вопрос:? – дед(«Иван»,Х). Работа алгоритма логического вывода может быть представлена следующей таблицей:
Так как после шага 1.7 стек возвратов оказался пустым, полный перебор осуществлен и алгоритм логического вывода заканчивает работу. В результате будет сформирован ответ: Х = «Юлия» Х = «Павел» 2 Solutions.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-03-10; просмотров: 73; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.189.189.63 (0.039 с.) |