Пролог как универсальный язык высокого уровня
Российский университет дружбы народов, аспирант
Аннотация: В статье представлена краткая история развития, список основных реализаций языка и краткое описание их особенностей, актуальность и применение языка Пролог в наши дни.
Ключевые слова: язык Пролог, язык Лисп, обработка списков, процедурные языки, системы программирования, логические высказывания.
1. Введение
На сегодняшний день существует множество реализаций языка Пролог, как компиляторов, так и интерпретаторов языка. Отметим, что Пролог не является языком программирования в чистом виде. Язык можно использовать в качестве оболочки экспертной системы, а также как инструмент для создания интеллектуальной базы данных не реляционного типа. Математическая модель, положенная в основу языка, базируется на теории исчисления предикатов, в частности, на процедурной интерпретации Хорновских дизъюнктов, предложенной Робертом Ковальским [1].
Пролог является не процедурным, а декларативным языком. Сама "программа" строится из последовательности фактов и правил, и затем формулируется утверждение, которое Пролог будет пытаться доказать с помощью введенных правил. Таким способом можно описывать достаточно сложные проблемы, которые Пролог будет решать автоматически с помощью метода сопоставления и рекурсивного поиска.
2. Немного истории
Алан Колмероэ, автор языка Пролог, начал работы над полноценной компьютерной реализацией трудов Ковальского с 1972 года во французском университете Марсель-Экс. Он составил алгоритм формального способа интерпретации процесса логического вывода и разработал систему автоматического доказательства теорем, которая была написана на Фортране. Она и послужила прообразом Пролога. [4]
Первое время, в начале 70-х, Пролог был не очень популярен, так же как и Лисп. Он пребывал в некоем забвении, вызванном отсутствием хороших реализаций, но вскоре появились первые компиляторы с этого языка, в частности, прекрасная реализация Дэвида Уоррена для компьютера DEC-10 в Эдинбурге, ставшая своего рода стандартом вплоть до сегодняшнего дня. Эффективность этой версии заставила специалистов по искусственному интеллекту по-новому взглянуть на Пролог, что и послужило в дальнейшем стимулом для ряда специалистов по логическому программированию к переходу на этот язык [2].
Сразу после появления Эдинбургской версии Пролога появилась возможность создания интеллектуальных не реляционных баз знаний с иерархической структурой на основе стандартного механизма с гибкой организацией очень сложных запросов. Были написаны эффективные программы для решения переборных задач, в частности, из области молекулярной биологии и проектирования СБИС, где требовалось учитывать либо сложные внутренние структуры, либо большое число правил, описывающих организацию объекта. Хорошо зарекомендовал себя Пролог в качестве экспертной оболочки, а также в задачах грамматического разбора. Был написан на Прологе первый высокопроизводительный компилятор (Эдинбургская версия).
Но в силу своей специфичности и сильной ориентированности на встроенные алгоритмы поиска доказательств Прологу не суждено было воплотиться в конкретном стандарте, который получил бы массовое признание. На сегодня имеется стандарт ISO/IEC 13211- 1:1995, но он поддерживается далеко не всеми коммерческими системами, имеющими различные принципы реализации и цели, для которых планируется использовать эти системы. Фактически первым и единственным стандартом осталась версия языка, созданная в Эдинбурге для PDP в 70-х годах. [5]
Программа на Прологе постепенно стала приближаться к обычным процедурным - последовательным - языкам. Немалую роль в этом сыграло и искусственно введенное понятие отсечения goto, чтобы программист мог по своему усмотрению динамически отсекать бесплодные ветви деревьев перебора, что приводило к многократному (на 2-3 порядка) повышению скорости работы программ, но при этом сильно нарушалась ясность ее структуры, и возникало множество проблем, связанных с отладкой. В целях получения высокоэффективных исполняемых модулей были предприняты попытки написания компиляторов Пролог - программ в Си - код. Однако, в отличие от процедурных языков сверхвысокого уровня, для Пролога хорошего результата добиться не удалось. Дело в том, что структура декларативной "программы" с большим количеством базовых фактов приводила к появлению крайне неуклюжих конструкций. Например, появлялись switch-операторы языка Си с более чем 15000 условиями выбора case.
Данные причины привели к большому многообразию версий языка (как коммерческих, так и свободно распространяемых). Российскому программисту, например, была знакома версия TurboProlog (фирмы Borland), который сейчас выходит под маркой PDC Prolog.
В настоящее время, хочется обратить внимание на Visual Prolog 5.2 и Amzi Prolog+Logic Server, Beta 6.1.21 (пакет объектных plug-in компонентов, предназначенных для интегрирования с различными системами программирования, такими, как Си, Си++, Java, Visual Basic, Delphi, различные СУБД, электронные таблицы, и т. д.). [1]
3. Возможности Пролога и его отличие от других языков высокого уровня
Традиционные, процедурные, языки программирования, такие как C, Pascal, Ada и др. требуют подробного описания последовательности действий, приводящих к получению результата из входных данных. В отличие от них, программа на Прологе состоит из ряда логических высказываний, описывающих задачу. Но одних фактов для решения задачи обычно недостаточно (если мы не пишем базу данных). [3]
Базу фактов составляют утверждения, описывающие факты предметной области в виде структур, функторами которых являются атомы - имена отношений (предикатные буквы), а компонентами - предметные константы. Система программирования Пролог позволяет ставить запросы к базе фактов, касающиеся непосредственного ее содержимого. Простейшим видом запроса является запрос на проверку наличия в базе какого-либо факта, а введенные элементы языка Пролог позволяют рассмотреть более сложные типы запросов к базе фактов. Возможности языка Пролог для работы с базой фактов во многом совпадают с возможностями, предоставляемыми системами управления реляционными базами данных. Языком представления знаний Пролог делают имеющиеся в нем средства для описания базы правил. Правило представляет собой дизъюнкт Хорна, содержащий один положительный литерал и несколько отрицательных.
Таким образом, язык Пролог позволяет создавать программы, обладающие свойством недетерминизма, т. е. программы, способные давать ответы на запросы, в которых априорно не фиксируются объекты, являющиеся исходными и результирующими. Утверждения программ на языке Пролог в значительной степени независимы друг от друга, что позволяет легко модифицировать программы, пополняя и изменяя факты и правила. Интерпретатор системы программирования Пролог, реализуя линейную по входу версию метода резолюции, осуществляет поиск ответа на запрос полным перебором, используя стратегию поиска в глубину. Для реализации режима с возвращением применяется механизм бэктрекинга. С целью сокращения количества вариантов перебора в больших программах на языке Пролог целесообразно включать в правила условия эвристического характера.
4. Выводы
Язык пролог критикуется в первую очередь за свою недостаточную гибкость. Это заключается в трудности изучения языка, более высоких требований к квалификации программиста на Прологе, трудности отладки программы, неразвитости технологии программирования, плохой контролируемости промежуточных результатов. Но Мощность языка Пролог и визуальной среды разработки программ делает простой и интуитивно понятной разработку экспертных систем, основанных на знаниях, систем поддержки принятия решений, планирующих программ, развитых систем управления базами данных и др., а также обеспечивает повышение скорости разработки приложений. Какие еще есть возможности у языка Пролог, никто до конца еще не знает, так как язык до сих пор находится в развитии. На сегодняшний день перспектива развития всемирной Сети только увеличивает возможности изучения языка еще быстрее, и область его применения постоянно расширяется, в него вносятся новые дополнительные функциональные возможности, призванные удовлетворить возрастающие потребности пользователей, и кто знает, чем нас удивит язык Пролог завтра.
Литература
1. Amzi Prolog+Logic Server, Logic Explorer, WebLS, Adventure in Prolog tutorial, Expert Systems in Prolog, Freeware, Articles, Source Code, Consulting http://www. prolog. md/index. php? option=com_content&view=article&id=11&Itemid=81&lang=ru .
2. . Использование языка ПРОЛОГ для организации управляющей программы в системах программирования. Материалы семинара "Программные средства как продукция производственно-технического назначения". - Калинин. 1985, - С.134-137.
3. И. Братко. Алгоритмы искусственного интеллекта на языке PROLOG=Prolog Programming For Artificial Intelligence. – М.: Вильямс, 2004. – 640 с.
4. Планета КИС Технологии Языки программирования Пролог (www. kis. pcweek. ru).
5. Планета КИС Технологии Языки программирования Пролог в России (www. kis. pcweek. ru).
Prologue as universal language of high level
Zhantemirova Aida Sharshenbekovna
People’s friendship university of Russian, post-graduate student
Summary: In article the short history of development, the list of the basic realizations of language and the short description of their features, an urgency and application of language the Prologue is presented today.
Keywords: language the Prologue, language of Lisp, processing of lists, procedural languages, programming systems, logic statements.
