Теоретические основы логического программирования
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский государственный горный университет
Кафедра «Вычислительные машины»
КАРПОВИЧ Е.Е.
Утверждено УМС МГГУ
в качестве учебного пособия
Программирование на языке Пролог
Учебное пособие
Для студентов специальности АСП дневного отделения
Часть 1
Москва
2002
УДК 681.142.2(075.8)
Карпович Е.Е. Программирование на языке Пролог. Учебное пособие,
часть 1.-М.: МГГУ, 2002 г., с. 97.
В пособии представлено описание синтаксиса и семантики декларативного языка логического программирования Пролог, рассмотрены принципы рекурсивного программирования на Прологе. Приведены примеры рекурсивных программ обработки списков и множеств. Описаны возможности интерпретатора Arity Prolog, и приведено описание стандартных предикатов, предопределенных в системе программирования Arity Prolog. Рекомендуется в качестве учебного пособия по дисциплинам «Логическое программирование» и «Интеллектуальные подсистемы САПР» для студентов, обучающихся по специальности «Автоматизированные системы проектирования».
Рецензенты:
доктор техн. наук, проф. кафедры АСУ Московского государственного горного университета Куприянов В.В.;
канд. техн. наук проф. кафедры ТиМИБ Московского государственного социального университета Хорев П. Б.
© Московский государственный горный университет
|
|
|
1. Введение. 4
2. Теоретические основы логического программирования. 9
2.1 Основные определения логики предикатов первого порядка. 9
2.2 Стандартные формы представления формул исчисления предикатов. 11
3. Синтаксис языка программирования Пролог. 13
3.1. Основные элементы языка Пролог. 13
3.2. Представление клауз Хорна на языке Пролог. Факты. Правила. Вопросы. 15
4. Семантика языка программирования Пролог. 21
4.1 Декларативная и процедурная семантика программ на языке Пролог. 21
4.2. Вычислительная модель логической программы. 23
5. Рекурсивное программирование на языке Пролог. 34
5.1 Рекурсивные правила. 34
5.2 Схема поиска решений в рекурсивных программах. 36
5.3. Списки и их представление на Прологе. 37
5.4. Типовые процедуры обработки списков на языке Пролог. 40
5.5 Множества и их представление на языке Пролог. Простые программы обработки множеств. 55
5.6 Пролог¾программы сортировки списков. 63
6. Стандартные предикаты языка Пролог. 66
6.1. Арифметические предикаты. 66
6.2. Предикаты сравнения арифметических выражений и символьных термов. 67
6.3. Предикаты определения типов термов. 68
6.4. Примеры программ с использованием арифметических предикатов. 68
|
|
|
6.5. Предикаты ввода¾вывода термов и символов. 70
6.6. Стандартные предикаты управления логическим выводом. 73
6.7. Стандартные предикаты обработки списков. 75
6.8. Стандартные предикаты обработки строк. 76
7. Система программирования Arity Prolog 5.0. 78
7.1. Описание среды программирования Arity Prolog 5.0. 78
7.2. Методические указания по лабораторным работам. 80
Приложение 1. Варианты заданий по лабораторной работе 2. 84
Приложение 2. Варианты заданий по лабораторной работе 4. 88
Приложение 3. Варианты заданий по лабораторной работе 5. 91
Список литературы. 96
Введение
Язык Пролог был разработан в начале 70-х годов ХХ века в Марсельском университете во Франции группой исследователей под руководством А. Колмероэ. Название языка получено от фразы на английском языке “PROgramming in LOGic”, что означает – программирование средствами логики.
Пролог используется во многих прикладных областях, таких как, например, разработка компиляторов, управление реляционными базами данных, создание прототипов прикладных систем. Но наибольшее применение этот язык нашел в области искусственного интеллекта (ИИ). Пролог с успехом используется для трансляции команд на естественном языке в инструкции искусственных языков систем ИИ, для машинного перевода с одного естественного языка на другой, для создания систем символьной обработки, способных решать уравнения большой сложности, производить интегрирование и дифференцирование, и для автоматического доказательства теорем.
|
|
|
На Прологе написано множество экспертных систем (ЭС) и оболочек ЭС. На этом языке написаны такие пакеты программ, как GURU, ESP/ADVISOR и APES, каждый из которых представляет собой так называемую оболочку ЭС – комплекс программ, включающий в себя готовую машину вывода и средства создания и обновления базы знаний (БЗ) ЭС. Первоначально эта БЗ пуста, и для получения ЭС, полностью готовой к эксплуатации, достаточно лишь занести в БЗ формализованные знания, т.е. наполнить ее, а создавать программы не требуется. Любая оболочка ЭС может применяться для разработки многих ЭС различного применения.
Пролог существенно отличается от традиционных языков программирования. Он не является прямым потомком ни какого, другого языка программирования, в языке Пролог логика предикатов непосредственно применена в программировании. Связь математической логики и языка Пролог показана на рис. 1.
По принятой классификации язык логического программирования Пролог относится к языкам более высокого уровня, чем алгоритмические языки программирования, такие, как Фортран, Паскаль, Си и другие языки. Программа на алгоритмическом языке представляет собой описание шагов алгоритма, то есть перечень инструкций, каждая из которых предписывает ЭВМ некоторое конкретное действие. Приказной характер инструкций алгоритмических языков позволяет назвать традиционный стиль программирования императивным.
|
|
|
Рассуждения в терминах алгоритмов решения задач не является для человека основным способом мышления. Выводы, которые делает человек, чаще основаны на знаниях, описывающих некоторые конкретные свойства объектов предметной области, не привязанных к конкретным действиям, направленным на решение задачи. Для пользователя¾непрограммиста неважно, какой алгоритм заложен в программе, если она решает интересующую его задачу. В первую очередь, пользователя интересует описание связи между входными данными и результатами, а не алгоритм.
В отличие от традиционного стиля программирования в процессе логического программирования сами инструкции не задаются, а вместо алгоритма явно в виде аксиом формулируются описания (декларации) свойств объектов и отношений между объектами некоторой предметной области. Это множество аксиом является альтернативой обычной программе и называется логической программой.
Логическая программа выполняется, если задано логическое утверждение, подлежащее доказательству. Такое утверждение называется целевым утверждением. Выполнение программы состоит в попытке доказать истинность целевого утверждения, используя аксиомы логической программы. Особенностью Пролога является то, что целевые утверждения неявно содержат кванторы существования, в них утверждается, что существуют объекты с заданными свойствами.
Например, целевое утверждение может быть сформулировано следующим образом:
«Существует список Х, такой, что упорядочение списка [3,1,2,7] приводит к списку Х».
В системах программирования языка Пролог используется конструктивный метод доказательства целевых утверждений. Если доказательство прошло успешно, то в процессе доказательства будут найдены и выданы в качестве ответа конкретные объекты, соответствующие неопределенным объектам, входящим в целевое утверждение.
В приведенном примере, если программа содержит подходящие аксиомы сортировки, результатом доказательства (вычисления) целевого утверждения должен быть ответ:
X=[1,2,3,7]
YES.
Ключевая идея, положенная в основу логического программирования, ¾ это декларативность. Если программа на алгоритмическом языке содержит ответ на вопрос, как решается проблема, то программа на языке Пролог представляет собой ответ на вопрос, что истинно. Как будет установлена истинность утверждения, определяется Пролог—системой.
Программист, работая на языке Пролог, вместо того, чтобы описывать алгоритм, процедуру решения задачи, описывает предметную область, декларируя, что именно является истинным в этой предметной области. Чтобы такое описание, представляющее собой декларативный компонент, стало программой, с ним связывается процедурный компонент, не зависящий от предметной области, метод логического вывода (или метод интерпретации описания).
Для Пролога, где предметная область описывается с помощью хорновских предложений, в качестве способа логического вывода выбран поиск сверху вниз. Программирование на Прологе сводится к представлению описания задачи в виде множества хорновских предикатов, интерпретации этого описания с помощью Пролог - системы и затем выдачи вопросов Пролог - системе, которая отвечает на вопросы, используя для логического вывода
заключений поиск сверху вниз. Программист знает, что с декларативно сформулированной программой на языке Пролог всегда связан невидимый для пользователя интерпретатор, осуществляющий логический вывод. Интерпретатор принимает от программиста декларативную программу и вопросы, осуществляет вывод, анализируя программу, а затем выдает пользователю ответ и, возможно, запоминает полученный ответ, делая его частью программы. Таким образом, написание программы сводится только к составлению декларативных спецификаций предметной области.
С момента разработки первого транслятора языка Пролог группой А. Колмероэ до настоящего времени появилось множество других реализаций этого языка, отличающихся как своими возможностями, так и синтаксисом. Большинство различий между версиями Пролога относится к организации ввода/вывода в логических программах и набора встроенных (или системных) предикатов, но не затрагивают основных принципов логического программирования.
Первой эффективной реализацией языка Пролог был созданный в Эдинбургском университете компилятор/интерпретатор для ЭВМ DEC-10. Эдинбургская версия Пролога стала основой стандарта для языка Пролог.
В настоящее время разработаны системы программирования на языке Пролог для всех основных типов ЭВМ, от больших, средних и малых ЭВМ, а также для персональных компьютеров. Для персональных ЭВМ интерпретаторы и компиляторы Пролога разрабатываются и распространяются рядом фирм и организаций. Некоторые коммерческие реализации языка Пролог представлены в таблице 1.
| Система программирования на языке Пролог | Фирма - разработчик |
| Quintec-Prolog | Quintec System Ltd. |
| Micro-Prolog | Logic programming Associates Ltd. |
| Arity Prolog 6.0 | Arity Corp. |
| Turbo Prolog 2.0 | Borland Int. |
| PDC Prolog | Prolog Development Centre |
| Visual Prolog | Prolog Development Centre |
| Prolog + Logic Server 3.3 | Amzi |
Первые реализации Пролога на ПЭВМ представляли собой, в основном, интерпретаторы; к ним относятся системы Micro-Prolog и Arity Prolog первых версий. Затем появились более эффективные компилирующие системы, такие как Quintec-Prolog, Turbo Prolog 2.0, PDC Prolog, позволяющие обеспечить на 1-2 порядка более быстрое выполнение программ по сравнению с системами программирования интерпретирующего типа.
Теоретические основы логического программирования.
Дата добавления: 2018-04-04; просмотров: 715; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!