Не забывай - или проиграешь!
Сергей Бобровский
Лебединая песня Пролога
В отличие от подавляющего большинства других языков Пролог (Prolog) обычно рассматривается в одном контексте с понятием "логическое программирование". Сторонники этого направления считают, что человек должен не задавать компьютеру последовательность команд на некоем ориентированном на компьютер языке, а описывать саму задачу в совершенно абстрактных логических терминах, не оперирующих определениями "байт" или "указатель", то есть создавать своего рода модель анализируемой проблемы и пытаться получить положительные или отрицательные результаты этого анализа.
У многих людей, знакомых с логическим программированием, обычно возникают ассоциации с японским проектом компьютеров пятого поколения, все программное обеспечение которых создавалось на базе Пролога. Этот проект сегодня фактически провалился, и большое число экспертов считает, что причиной этому послужили некоторые присущие Прологу функциональные ограничения.
Строго говоря, Пролог не является языком программирования в чистом виде. С одной стороны, это оболочка экспертной системы, с другой - интеллектуальная база данных, что самое важное, не реляционная. Математическая модель, лежащая в основе Пролога, довольно сложна, и по мощности системы формирования запросов к базе с этим языком не сравнится ни одна из коммерческих СУБД.
Фактически Пролог является не процедурным, а декларативным языком. Человек лишь описывает структуру задачи, а внутренний "мотор" Пролога сам ищет решение. Более того, здесь вообще не существует понятия последовательности команд - все это скрыто в математической модели языка, - хотя, конечно, присутствует небольшой список "линейных" операторов типа repeat, но он ограничен возможностями использования лишь для конкретных случаев.
Математическая модель Пролога основана на теории исчисления предикатов, в частности на процедурной интерпретации Хорновых дизъюнктов (содержащих не более одного заключения) Роберта Ковальского из Эдинбурга. Ее в алгоритмическом, машинно-ориентированном виде выразил коллега Ковальского Маартен ван Эмден. Надо сказать, что работы этих ученых из-за большой сложности их практической реализации на компьютерах (по тем временам) подвергались серьезной критике со стороны американских специалистов по искусственному интеллекту.
Алан Колмероэ, автор языка Пролог, начал работы над полноценной компьютерной реализацией трудов Ковальского с 1972 года во французском университете Марсель-Экс. Он составил алгоритм формального способа интерпретации процесса логического вывода и разработал систему автоматического доказательства теорем, которая была написана на Фортране. Она-то и послужила прообразом Пролога. Название его произошло от Programmation en Loqicue - ЛОГическое ПРОграммирование. Говорят, что придумала это название жена Алана.
Первое время, в начале 70-х, Пролог был не очень популярен; как и Лисп, он пребывал в некоем забвении, вызванном отсутствием хороших реализаций, но вскоре появились первые компиляторы с этого языка, в частности прекрасная реализация Дэвида Уоррена для компьютера DEC-10 в Эдинбурге, ставшая своего рода стандартом вплоть до сегодняшнего дня. Эффективность этой версии заставила специалистов по искусственному интеллекту по-новому взглянуть на Пролог. В некоторых приложениях, типичных для Лиспа (таких, как обработка списков), Пролог уже не уступал своему конкуренту, что и послужило в дальнейшем стимулом для ряда специалистов по логическому программированию к переходу на этот язык.
В качестве типовых данных Пролог использует элементарные единицы данных, так называемые атомы - строки символов и числа. Из атомов составляются списки и бинарные деревья. Сама "программа" строится из последовательности фактов и правил, затем формулируется утверждение, которое Пролог будет пытаться доказать с помощью введенных правил.
Таким способом можно описывать очень сложные проблемы, которые будут решаться самим Прологом автоматически. Это происходит с помощью метода сопоставления и рекурсивного поиска. Вообще рекурсия играет в Прологе не меньшую роль, чем в Лиспе, хотя и носит декларативный характер.
Сразу после появления эдинбургской версии Пролога быстро были успешно осуществлены различные проекты, ранее казавшиеся очень сложными в реализации. Появилась возможность создания интеллектуальных нереляционных баз знаний с иерархической структурой на основе стандартного механизма с гибкой организацией очень сложных запросов. Были написаны эффективные программы для решения переборных задач, в частности из области молекулярной биологии и проектирования СБИС, где требовалось учитывать либо сложные внутренние структуры, либо большое число правил, описывающих организацию объекта. Хорошо зарекомендовал себя Пролог в качестве экспертной оболочки. А задачи грамматического разбора прямо-таки просились быть решенными на Прологе. Что весьма характерно, первый высокопроизводительный компилятор этого языка (эдинбургская версия) был написан на самом Прологе! И немудрено, ведь все формальные синтаксические описания грамматик в Бэкус-форме прекрасно записываются в терминах Пролога.
Но в силу своей специфичности и сильной ориентированности на встроенные алгоритмы поиска доказательств Прологу не суждено было воплотиться в конкретном стандарте, который получил бы массовое признание. На сегодня имеется стандарт ISO/IEC 13211-1:1995, но он поддерживается далеко не всеми коммерческими системами, имеющими различные принципы реализации и цели, для которых планируется использовать эти системы. Фактически первым и единственным стандартом осталась версия языка, созданная в Эдинбурге для PDP в 70-х годах! И хотя его поддерживают не все сегодняшние системы, их разработчики обычно прилагают к своим продуктам препроцессор, переводящий программу данного диалекта в эдинбургский вид.
Долгое время среди разработчиков этого языка шла напряженная борьба между сторонниками оригинальной семантики Пролога и специалистами, стремившимися пожертвовать ясной структурой языка ради повышения эффективности реализации. В частности, стала играть роль последовательность правил в базе данных. Дело в том, что нередко для получения быстрого ответа оптимально использовать сначала, например, наиболее простые правила или наиболее эффективные с точки зрения человека. Программа на Прологе постепенно стала приближаться к обычным процедурным - последовательным - языкам. Немалую роль в этом сыграло и искусственно введенное понятие отсечения, своего рода аналог столь нелюбимого Дейкстрой goto. Теперь программист мог по своему усмотрению динамически отсекать бесплодные, по его мнению, ветви деревьев перебора, что приводило к многократному (на два-три порядка) повышению скорости работы программ, но при этом сильно нарушалась ясность ее структуры и возникало множество проблем, связанных с отладкой.
В целях получения высокоэффективных исполняемых модулей были предприняты попытки написания компиляторов Пролог-программ в Си-код. Однако в отличие от процедурных языков сверхвысокого уровня для Пролога хорошего результата добиться не удалось. Дело в том, что структура декларативной "программы" с большим количеством базовых фактов приводила к появлению крайне неуклюжих конструкций. Например, появлялись switch-операторы языка Си с более чем 15 000 (!) условий выбора case. Такие синтаксически корректные выражения многие компиляторы расценивали как ошибку или выдавали неэффективный код.
К счастью, развитие вычислительной техники в сочетании с уникальной структурой языка дало свои результаты. При появлении первых параллельных компьютеров люди, программирующие на Прологе, быстро осознали пагубность различных "нововведений" типа оператора отсечения, лишавших язык оригинальной чистоты, и вернулись к первоначальной версии языка. Пресловутая последовательность правил перестала играть роль, так как появилась возможность вычислять их параллельно, а в силу того, что математическая теория Пролога не накладывает никаких требований на упорядоченность фактов и правил в базе, скорость работы программы стала линейно пропорциональной числу процессоров.
Имеются бесплатные версии Пролога для реализаций на параллельных компьютерах, но они либо усечены до возможности исполнения не более чем на двух процессорах, либо являются неэффективными. Да и коммерческих версий не так много, это, например, Densitron CS Prolog для транспьютеров или Paralogic. Информации по этим версиям очень мало, и цена их автору неизвестна. Она обычно определяется в индивидуальном порядке в зависимости от конфигурации многопроцессорной системы.
Большинство свободно распространяемых версий Пролога для обычных однопроцессорных компьютеров сегодня являются или усеченными подмножествами коммерческих продуктов, или поставляются бесплатно только для учебных и научных организаций. Кроме того, существует немало диалектов этого языка, весьма сильно отличающихся от оригинала и созданных для конкретных целей. Их тоже обычно можно получить даром.
Для примера приведем SWI-Prolog, содержащий быстрый компилятор, профилировщик, набор библиотек и удобный интерфейс для подключения Си-модулей. Он реализован для ряда UNIX-платформ, таких, как HP, IBM Linux, для NeXT, OS/2, Sun и Sparc.
Несколько лет назад в Пролог было введено понятие объекта. Появился ряд объектных диалектов, таких, как freeware-версия OL(P) - Object Layer for Prolog, простой компилятор объектного кода в обычный Пролог, - причем поддерживаются все принципы ООП, вплоть до множественного наследования. Не обошлось, конечно, и без коммерческих объектных версий, не получивших, впрочем, большого успеха из-за появления нового полудекларативного языка с мощными средствами ООП - Smalltalk.
Из коммерческих реализаций Пролога надо упомянуть бывший одно время весьма популярным Arity Prolog 6.1 ($650). Delphina Prolog, работающий на ряде UNIX-платформ, включает в себя высокопроизводительные компилятор и интерпретатор, интерфейсные библиотеки и поддерживает эдинбургский стандарт. Стоимость его - $10 000.
Для Windows (3.x, 95, NT) имеется прекрасная 32-разрядная версия LPA-Prolog как со "стандартным" синтаксисом, так и с расширенным объектным набором библиотек для работы с оконным интерфейсом, поддержкой DDE и ODBC-протокола и возможностью создания DLL. Цена около $1500.
Ничем не хуже ORISAbase для OS/2. Практически те же возможности, поддержка API Presentation Manager, SOM, SQL-запросов, графического интерфейса, объектных расширений и т. д. Стоит этот пакет, правда, подороже - 100 000 немецких марок.
Знакомый многим отечественным программистам TurboProlog, разрабатывавшийся ранее фирмой Borland, теперь выступает под маркой PDC Prolog и реализован для DOS, Windows, OS/2 и UNIX. Правда, как недостатки, так и достоинства его сохранились. Удобная среда разработчика и быстрый компилятор, но несовместимость с подавляющим большинством других диалектов этого языка. Есть специальная версия для визуальной разработки VisualProlog.
Едва появившись на свет, Пролог породил множество диалектов или даже совсем других языков типа Planner, основанных на декларативных принципах, но имеющих более узкие области применения. Самому же ему не суждено было воплотиться в строгом стандарте, скорее всего, как раз потому, что слишком глобальными оказались заложенные в него идеи.
Итак, Пролог свою "лебединую песню" пропел, но как наиболее известный и наиболее простой в освоении из всех декларативных языков он остается и сегодня прекрасным средством для быстрого создания различных экспертных систем и интеллектуальных баз знаний, требующих сложной структуры запроса. По сути, хорошая реализация Пролога - это та же CASE-система, только более простая в изучении и более гибкая в использовании, что косвенно подтверждается ценами на различные версии этого языка.
Но не ждет ли такая "лебединая" судьба и ряд других, переживающих сегодня фантастический успех новых языков программирования (ориентированных, в частности, на Интернет)? Возможно, скоро мы об этом услышим.
ItWeek №(053-054)29-30`1996 от 30.07.1996
Помещена в музей с разрешения редакции
22 августа 2018