|
«LISP был для нас не просто языком, который используют для определенных целей, им можно было полюбоваться, как прелестной вещью. Поэтому существовала постоянная напряженность в отношениях между теми, кто восхищался LISPoм за его чистоту, и теми, кто стремился использовать его для различных вычислений. Безусловно, с помощью LISPa проделано множество вычислений. Но в самом начале было не так. Часто говорили, что главная цель LISPa — делать больше LISPa».
Эти слова принадлежат бывшему дипломнику Джона Маккарти в период разработки нового языка программирования. Для специалистов по информатике эти слова неудивительны, т. к. имя Джона Маккарти известно во всем мире. Его называют отцом искусственного интеллекта, он первый ввел термин "искусственный интеллект" и создал первый язык искусственного интеллекта. Джон Маккарти сыграл решающую роль в основании двух самых известных научных центров США по исследованию проблем искусственного интеллекта — в Массачусетском университете в 1957 году и в Стэнфордском университете в 1963 году. Среди его многочисленных работ, внесших значительный вклад в науку, наиболее важные относятся к концу 50-х годов, когда он работал в Массачусетском Технологическом институте. Именно там в 1959 году Маккарти предложил концепцию разделения времени — режима работы компьютера, который позволяет нескольким программистам, работая за разными терминалами, одновременно использовать его память и процессор. Помимо всего прочего, это означало, что исследователи в области искусственного интеллекта получили возможность составлять и проверять экспериментальные программы непосредственно, не ожидая по нескольку часов и дней, пока их задания, заложенные среди других в пакеты перфокарт, будут обработаны единственным оператором вычислительной машины.
В средние века знание латинского и греческого языков являлось существенной частью образования любого ученого. Ученый, владеющий только одним языком, неизбежно чувствовал себя неполноценным, поскольку он был лишен той полноты восприятия, которая возникает благодаря возможности посмотреть на мир сразу с двух точек зрения. Таким же неполноценным ощущает себя сегодняшний исследователь в области искусственного интеллекта, если он не обладает основательным знакомством как с Лиспом, так и с Прологом - с этими двумя основополагающими языками искусственного интеллекта, без знания которых невозможен более широкий взгляд на предмет исследования.
Язык программирования Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов, древовидное представление структур данных и автоматический возврат. Этот небольшой набор образует удивительно мощный и гибкий программный аппарат. Пролог особенно хорошо приспособлен для решения задач, в которых фигурируют объекты (в частности, структуры) и отношения между ними. Например, нетрудно сформулировать общее поло¬жение в виде следующего правила: если X ближе к наблюдателю, чем Y, а Y - ближе, чем Z, то объект X находится ближе, чем Z. Пользуясь правилами и фактами, пролог-система может проводить рассуждения относительно имеющихся пространственных отношений и, в частности, проверить, насколько они согласуются с вышеуказанным общим правилом. Все эти возможности придают Прологу черты мощного языка для решения задач искусственного интеллекта, а также любых задач, требующих нечислового программирования.
Само название Пролог есть сокращение, означающее программирование в терминах, логики. Идея использовать логику в качестве языка программирования возникла впервые в начале 70-х годов. Первыми исследователями, разрабатывавшими эту идею, были Роберт Ковальский из Эдинбурга (теоретические аспекты), Маартен ван Эмден из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ из Марселя (реализация). Сегодняшней своей популярности Пролог во многом обязан эффек¬тивной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном в середине 70-х годов.
Поскольку Пролог уходит своими корнями в мате¬матическую логику, его преподавание часто начинают с изложения логики. Однако такое введение в Пролог, насыщенное математическими понятиями, приносит мало пользы в том случае, когда Пролог изучается в качестве практического инструмента программирования. Поэтому в данном курсе мы сосредоточим свое внимание на навыках использования базовых механизмов Пролога для решения целого ряда содержательных задач. В то время как традиционные языки программирования являются процедурно-ориентированными, Пролог основан на описательной или декларативной точке зрения на программирование. Это свойство Пролога коренным образом меняет программистское мышление и делает обучение программированию на Прологе увлекательным занятием, требующим определенных интеллектуальных усилий.
Пролог используется во многих прикладных областях, таких как, например, разработка компиляторов, управление реляционными базами данных, создание прототипов прикладных систем. Но наибольшее применение этот язык нашел в области искусственного интеллекта (ИИ). Пролог с успехом используется для трансляции команд на естественном языке в инструкции искусственных языков систем ИИ, для машинного перевода с одного естественного языка на другой, для создания систем символьной обработки, способных решать уравнения большой сложности, производить интегрирование и дифференцирование, и для автоматического доказательства теорем.
На Прологе написано множество экспертных систем (ЭС) и оболочек ЭС. На этом языке написаны такие пакеты программ, как GURU, ESP/ADVISOR и APES, каждый из которых представляет собой так называемую оболочку ЭС – комплекс программ, включающий в себя готовую машину вывода и средства создания и обновления базы знаний (БЗ) ЭС. Первоначально эта БЗ пуста, и для получения ЭС, полностью готовой к эксплуатации, достаточно лишь занести в БЗ формализованные знания, т.е. наполнить ее, а создавать программы не требуется. Любая оболочка ЭС может применяться для разработки многих ЭС различного применения.
Пролог существенно отличается от традиционных языков программирования. Он не является прямым потомком ни какого, другого языка программирования, в языке Пролог логика предикатов непосредственно применена в программировании.
По принятой классификации язык логического программирования Пролог относится к языкам более высокого уровня, чем алгоритмические языки программирования, такие, как Фортран, Паскаль, Си и другие языки. Программа на алгоритмическом языке представляет собой описание шагов алгоритма, то есть перечень инструкций, каждая из которых предписывает ЭВМ некоторое конкретное действие. Приказной характер инструкций алгоритмических языков позволяет назвать традиционный стиль программирования императивным.
Рассуждения в терминах алгоритмов решения задач не является для человека основным способом мышления. Выводы, которые делает человек, чаще основаны на знаниях, описывающих некоторые конкретные свойства объектов предметной области, не привязанных к конкретным действиям, направленным на решение задачи. Для пользователя непрограммиста неважно, какой алгоритм заложен в программе, если она решает интересующую его задачу. В первую очередь, пользователя интересует описание связи между входными данными и результатами, а не алгоритм.
В отличие от традиционного стиля программирования в процессе логического программирования сами инструкции не задаются, а вместо алгоритма явно в виде аксиом формулируются описания (декларации) свойств объектов и отношений между объектами некоторой предметной области. Это множество аксиом является альтернативой обычной программе и называется логической программой.
Логическая программа выполняется, если задано логическое утверждение, подлежащее доказательству. Такое утверждение называется целевым утверждением. Выполнение программы состоит в попытке доказать истинность целевого утверждения, используя аксиомы логической программы. Особенностью Пролога является то, что целевые утверждения неявно содержат кванторы существования, в них утверждается, что существуют объекты с заданными свойствами.
Например, целевое утверждение может быть сформулировано следующим образом:
«Существует список Х, такой, что упорядочение списка [3,1,2,7] приводит к списку Х».
В системах программирования языка Пролог используется конструктивный метод доказательства целевых утверждений. Если доказательство прошло успешно, то в процессе доказательства будут найдены и выданы в качестве ответа конкретные объекты, соответствующие неопределенным объектам, входящим в целевое утверждение.
В приведенном примере, если программа содержит подходящие аксиомы сортировки, результатом доказательства (вычисления) целевого утверждения должен быть ответ:
X=[1,2,3,7]
YES.
Ключевая идея, положенная в основу логического программирования, это декларативность. Если программа на алгоритмическом языке содержит ответ на вопрос, как решается проблема, то программа на языке Пролог представляет собой ответ на вопрос, что истинно. Как будет установлена истинность утверждения, определяется Пролог—системой.
Программист, работая на языке Пролог, вместо того, чтобы описывать алгоритм, процедуру решения задачи, описывает предметную область, декларируя, что именно является истинным в этой предметной области. Чтобы такое описание, представляющее собой декларативный компонент, стало программой, с ним связывается процедурный компонент, не зависящий от предметной области, метод логического вывода (или метод интерпретации описания).
Для Пролога, где предметная область описывается с помощью хорновских предложений, в качестве способа логического вывода выбран поиск сверху вниз. Программирование на Прологе сводится к представлению описания задачи в виде множества хорновских предикатов, интерпретации этого описания с помощью Пролог системы и затем выдачи вопросов Пролог системе, которая отвечает на вопросы, используя для логического вывода заключений поиск сверху вниз. Программист знает, что с декларативно сформулированной программой на языке Пролог всегда связан невидимый для пользователя интерпретатор, осуществляющий логический вывод. Интерпретатор принимает от программиста декларативную программу и вопросы, осуществляет вывод, анализируя программу, а затем выдает пользователю ответ и, возможно, запоминает полученный ответ, делая его частью программы. Таким образом, написание программы сводится только к составлению декларативных спецификаций предметной области.
С момента разработки первого транслятора языка Пролог группой А. Колмероэ до настоящего времени появилось множество других реализаций этого языка, отличающихся как своими возможностями, так и синтаксисом. Большинство различий между версиями Пролога относится к организации ввода/вывода в логических программах и набора встроенных (или системных) предикатов, но не затрагивают основных принципов логического программирования.
Первой эффективной реализацией языка Пролог был созданный в Эдинбургском университете компилятор/интерпретатор для ЭВМ DEC-10. Эдинбургская версия Пролога стала основой стандарта для языка Пролог.
В настоящее время разработаны системы программирования на языке Пролог для всех основных типов ЭВМ, от больших, средних и малых ЭВМ, а также для персональных компьютеров. Для персональных ЭВМ интерпретаторы и компиляторы Пролога разрабатываются и распространяются рядом фирм и организаций.
Предлагаемое пособие можно использовать в курсе лекций по искусственному интеллекту, ориентированном на прологовскую реализацию. Предполагается, что студент имеет общее представление о вычислительных машинах, но предварительные знания в области искусственного интеллекта необязательны. От студента не требуется также какого-либо программистского опыта. Дело в том, что богатый программистский опыт вместе с приверженностью к традиционному процедурному программированию (например, на Паскале) может стать помехой при изучении Пролога, требующего свежего программистского мышления.
Среди различных диалектов Пролога мы будем опираться на версию Arity Prolog 5.0.(рисунок 1).
Рисунок 1 - Структура окна среды программирования Arity Prolog
|
