Теоретические основы логического программирования.

Введение

Язык Пролог был разработан в начале 70-х годов ХХ века в Марсельском университете во Франции группой исследователей под руководством А. Колмероэ. Название языка получено от фразы на английском языке “PROgramming in LOGic”, что означает – программирование средствами логики.

Пролог используется во многих прикладных областях, таких как, например, разработка компиляторов, управление реляционными базами данных, создание прототипов прикладных систем. Но наибольшее применение этот язык нашел в области искусственного интеллекта (ИИ). Пролог с успехом используется для трансляции команд на естественном языке в инструкции искусственных языков систем ИИ, для машинного перевода с одного естественного языка на другой, для создания систем символьной обработки, способных решать уравнения большой сложности, производить интегрирование и дифференцирование, и для автоматического доказательства теорем.

На Прологе написано множество экспертных систем (ЭС) и оболочек ЭС. На этом языке написаны такие пакеты программ, как GURU, ESP/ADVISOR и APES, каждый из которых представляет собой так называемую оболочку ЭС – комплекс программ, включающий в себя готовую машину вывода и средства создания и обновления базы знаний (БЗ) ЭС. Первоначально эта БЗ пуста, и для получения ЭС, полностью готовой к эксплуатации, достаточно лишь занести в БЗ формализованные знания, т.е. наполнить ее, а создавать программы не требуется. Любая оболочка ЭС может применяться для разработки многих ЭС различного применения.

Пролог существенно отличается от традиционных языков программирования. Он не является прямым потомком ни какого, другого языка программирования, в языке Пролог логика предикатов непосредственно применена в программировании. Связь математической логики и языка Пролог показана на рис. 1.

По принятой классификации язык логического программирования Пролог относится к языкам более высокого уровня, чем алгоритмические языки программирования, такие, как Фортран, Паскаль, Си и другие языки. Программа на алгоритмическом языке представляет собой описание шагов алгоритма, то есть перечень инструкций, каждая из которых предписывает ЭВМ некоторое конкретное действие. Приказной характер инструкций алгоритмических языков позволяет назвать традиционный стиль программирования императивным.

Рассуждения в терминах алгоритмов решения задач не является для человека основным способом мышления. Выводы, которые делает человек, чаще основаны на знаниях, описывающих некоторые конкретные свойства объектов предметной области, не привязанных к конкретным действиям, направленным на решение задачи. Для пользователя¾непрограммиста неважно, какой алгоритм заложен в программе, если она решает интересующую его задачу. В первую очередь, пользователя интересует описание связи между входными данными и результатами, а не алгоритм.

В отличие от традиционного стиля программирования в процессе логического программирования сами инструкции не задаются, а вместо алгоритма явно в виде аксиом формулируются описания (декларации) свойств объектов и отношений между объектами некоторой предметной области. Это множество аксиом является альтернативой обычной программе и называется логической программой.

Логическая программа выполняется, если задано логическое утверждение, подлежащее доказательству. Такое утверждение называется целевым утверждением. Выполнение программы состоит в попытке доказать истинность целевого утверждения, используя аксиомы логической программы. Особенностью Пролога является то, что целевые утверждения неявно содержат кванторы существования, в них утверждается, что существуют объекты с заданными свойствами.

Например, целевое утверждение может быть сформулировано следующим образом:

«Существует список Х, такой, что упорядочение списка [3,1,2,7] приводит к списку Х».

В системах программирования языка Пролог используется конструктивный метод доказательства целевых утверждений. Если доказательство прошло успешно, то в процессе доказательства будут найдены и выданы в качестве ответа конкретные объекты, соответствующие неопределенным объектам, входящим в целевое утверждение.

В приведенном примере, если программа содержит подходящие аксиомы сортировки, результатом доказательства (вычисления) целевого утверждения должен быть ответ:

X=[1,2,3,7]

YES. 

Ключевая идея, положенная в основу логического программирования, ¾ это декларативность. Если программа на алгоритмическом языке содержит ответ на вопрос, как решается проблема, то программа на языке Пролог представляет собой ответ на вопрос, что истинно. Как будет установлена истинность утверждения, определяется Пролог—системой.

Программист, работая на языке Пролог, вместо того, чтобы описывать алгоритм, процедуру решения задачи, описывает предметную область, декларируя, что именно является истинным в этой предметной области. Чтобы такое описание, представляющее собой декларативный компонент, стало программой, с ним связывается процедурный компонент, не зависящий от предметной области, метод логического вывода (или метод интерпретации описания).

Для Пролога, где предметная область описывается с помощью хорновских предложений, в качестве способа логического вывода выбран поиск сверху вниз. Программирование на Прологе сводится к представлению описания задачи в виде множества хорновских предикатов, интерпретации этого описания с помощью Пролог - системы и затем выдачи вопросов Пролог - системе, которая отвечает на вопросы, используя для логического вывода

заключений поиск сверху вниз. Программист знает, что с декларативно сформулированной программой на языке Пролог всегда связан невидимый для пользователя интерпретатор, осуществляющий логический вывод. Интерпретатор принимает от программиста декларативную программу и вопросы, осуществляет вывод, анализируя программу, а затем выдает пользователю ответ и, возможно, запоминает полученный ответ, делая его частью программы. Таким образом, написание программы сводится только к составлению декларативных спецификаций предметной области.

С момента разработки первого транслятора языка Пролог группой А. Колмероэ до настоящего времени появилось множество других реализаций этого языка, отличающихся как своими возможностями, так и синтаксисом. Большинство различий между версиями Пролога относится к организации ввода/вывода в логических программах и набора встроенных (или системных) предикатов, но не затрагивают основных принципов логического программирования.

Первой эффективной реализацией языка Пролог был созданный в Эдинбургском университете компилятор/интерпретатор для ЭВМ DEC-10. Эдинбургская версия Пролога стала основой стандарта для языка Пролог.

В настоящее время разработаны системы программирования на языке Пролог для всех основных типов ЭВМ, от больших, средних и малых ЭВМ, а также для персональных компьютеров. Для персональных ЭВМ интерпретаторы и компиляторы Пролога разрабатываются и распространяются рядом фирм и организаций. Некоторые коммерческие реализации языка Пролог представлены в таблице 1.

Первые реализации Пролога на ПЭВМ представляли собой, в основном, интерпретаторы; к ним относятся системы Micro-Prolog и Arity Prolog первых версий. Затем появились более эффективные компилирующие системы, такие как Quintec-Prolog, Turbo Prolog 2.0, PDC Prolog, позволяющие обеспечить на 1-2 порядка более быстрое выполнение программ по сравнению с системами программирования интерпретирующего типа.

Теоретические основы логического программирования.