История и перспективы развития языка Пролог

К 2011 году большинство программ будут писать компьютеры…».

Методическое пособие

для изучения языка

логического программирования

Пролог (Prolog)

Составил:
ст.преп. каф. ВСиТ
Богданов А.А.

Архангельск,

2003г.

СОДЕРЖАНИЕ

История и перспективы развития языка Пролог

Краткая инструкция по работе в среде PIE32

Механизм вывода в системе Пролог в примерах.

Ян Пирсон

футуролог, исследователь из British Telecom.

В отличие от подавляющего большинства других языков Пролог (Prolog) обычно рассматривается в одном контексте с понятием "логическое программирование". По прогнозам футурологов, в скором будущем решая задачу, человек не будет задавать последовательность команд на компьютер-ориентированном языке, а будет описывать ее в совершенно абстрактных логических терминах, не оперирующих определениями "байт" или "указатель". То есть он будет создавать модель анализируемой проблемы и пытаться получить положительные или отрицательные результаты этого анализа. Результатом такого анализа может быть, например, структура сложного устройства, план мероприятий для достижения некоторой цели, набор правил для решения задачи или даже оптимизированная программа на процедурном языке (например, C++).

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

Фактически Пролог является не процедурным, а декларативным языком. И относится к группе пост объектно-ориентированных языков – функциональным языкам. Человек лишь описывает структуру задачи, а Пролог-машина вывода сама ищет решение. Более того, здесь вообще не существует понятия последовательности команд, все это скрыто в математической модели языка. Однако справедливо заметим, что хотя в идеальной модели Пролог-машины последовательность целей не играет роли, в ее реализациях от порядка следования целей зависит скорость работы экспертной системы (ЭС), а порой и ее работоспособность.

Если в императивных языках (Pascal, C++ и т.п.) программа представляет собой набор выполняемых в определенном программистом порядке команд, то функциональная программа представляет из себя совокупность функций. Функции определяются через другие функции или рекурсивно – через самих себя.

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

Математическая модель Пролога основана на теории исчисления предикатов, в частности, на процедурной интерпретации Хорновых дизъюнктов, содержащих не более одного заключения, Роберта Ковальского из Эдинбурга. Алан Колмероэ, автор языка Пролог, начал работы над полноценной компьютерной реализацией трудов Ковальского с 1972 года во французском университете Марсель-Экс. Он составил алгоритм формального способа интерпретации процесса логического вывода и разработал систему автоматического доказательства теорем, которая была написана на Фортране. Она и послужила прообразом Пролога. Название его произошло от Programmation en Loqicue - ЛОГическое ПРОграммирование. Вскоре появились первые компиляторы с этого языка, в частности, прекрасная реализация Дэвида Уоррена для компьютера DEC-10 в Эдинбурге, ставшая своего рода стандартом вплоть до сегодняшнего дня. Эффективность этой версии заставила специалистов по искусственному интеллекту по-новому взглянуть на Пролог. В некоторых приложениях, типичных для Лиспа, таких как обработка списков, Пролог уже не уступал своему конкуренту, что и послужило в дальнейшем стимулом для ряда специалистов по логическому программированию к переходу на этот язык.

В качестве типовых данных Пролог использует элементарные единицы данных, так называемые атомы - строки символов и числа. Из атомов составляются списки и бинарные деревья. Сама "программа" строится из последовательности фактов и правил, и затем формулируется утверждение, которое Пролог будет пытаться доказать с помощью введенных правил. Таким способом можно описывать очень сложные проблемы, которые будут решаться самим Прологом автоматически. Это происходит с помощью метода сопоставления и рекурсивного поиска. Рекурсия играет в Прологе большую роль.

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

Долгое время среди разработчиков этого языка шла напряженная борьба между сторонниками оригинальной семантики Пролога и специалистами, стремившимися пожертвовать ясной структурой языка ради повышения эффективности реализации. В частности, стала играть роль последовательность правил в базе данных. Дело в том, что нередко для получения быстрого ответа оптимально использовать сначала, например, наиболее простые правила, или наиболее эффективные с точки зрения человека. Программа на Прологе постепенно стала приближаться к обычным процедурным - последовательным языкам. Немалую роль в этом сыграло и искусственно введенное понятие отсечения (обозначается символом “!”), своего рода аналог столь нелюбимого Дейкстрой GoTo. Теперь программист мог по своему усмотрению динамически отсекать бесплодные, по его мнению, ветви деревьев перебора, что приводило к многократному (на два-три порядка) повышению скорости работы программ, но при этом сильно нарушалась ясность ее структуры и возникало множество проблем, связанных с отладкой.

К счастью, развитие вычислительной техники в сочетании с уникальной структурой языка дало свои результаты. При появлении первых параллельных компьютеров люди, программирующие на Прологе, быстро осознали пагубность различных "нововведений" типа оператора отсечения, лишавших язык оригинальной чистоты, и вернулись к первоначальной версии языка. Пресловутая последовательность правил перестала играть роль, так как появилась возможность вычислять их параллельно, а в силу того, что математическая теория Пролога не накладывает никаких требований на упорядоченность фактов и правил в базе, то скорость работы программы стала линейно пропорциональной числу процессоров. Имеются бесплатные и коммерческие версии Пролога для реализаций на параллельных компьютерах, например, Densitron CS Prolog для транспьютеров, или Paralogic. В японском проекте компьютера пятого поколения все программное обеспечение создавалось на Пролог подобном языке.

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

Перечислим некоторые из них: SWI-Prolog, Amzi!-Prolog. Знакомый многим программистам TurboProlog, разрабатывавшийся ранее фирмой Borland, теперь выступает под маркой PDC Prolog и реализован для DOS, Windows, OS/2 и UNIX. Правда, как недостатки, так и достоинства его сохранились. Удобная среда разработчика и быстрый компилятор - но несовместимость с подавляющим большинством других диалектов этого языка. Есть специальная версия для визуальной разработки VisualProlog. На нем написана маленькая, простая и удобная Пролог-машина Prolog-Interface-Engine - PIE32. Именно на ней рекомендуется выполнять лабораторные работы.

Современные профессиональные Пролог-системы обеспечивают скорость работы, не уступающую скорости выполнения аналогичных программ, написанных на Си (конечно, если не решать на Прологе задачи подобные Фурье-преобразованию). Заметим, что в России уже очень давно ведутся работы над языком РЕФАЛ, имеющим сходную с Прологом декларативную идеологию. Но если раньше про Пролог говорили, что это "самый функциональный из декларативных языков и наоборот", то самым функциональным из декларативных сегодня является именно РЕФАЛ-5 (http://www.refal.ru). Но на сегодняшний день, к большому сожалению, для этого языка нет интегрированной среды разработки. Эффективное применение существующих строчных компиляторов недоступно значительной части потенциальных пользователей.

HASKELL (http://www.haskell.org). "чистый" функциональный язык. Программы на HASKELL состоят исключительно из функций. Язык основан на лямбда-исчислении и назван в честь логика Хаскела Кэрри, чьи работы были положены в основу языка.

К функциональным языкам также относятся ML, Caml и F# от Microsoft Research (http://research.microsoft.com/projects/ilx/fsharp.htm). F# предполагается использовать для обработки XML документов.

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

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

Оболочка PIE32 (Prolog-Interface-Engine под Win32) написана в среде Visual Prolog 5 датской фирмы PDC (Prolog Development Center). PIE32 оформлена в виде стандартного многооконного MDI приложения. На панели инструментов нестандартными пиктограммами продублированы основные команды меню:

· работа с файлами: New, Open, Consult (Открыть и собрать);

· правка: Undo, Redo, Cut, Copy, Paste;

· работа с базой знаний: Reconsult (Собрать БЗ), Reset (Сбросить БЗ), Trace On/Off (Вкл/Выкл трассировку БЗ), Pause On/Off (Пауза), Stop (Остановить вывод).

Оболочка содержит окна двух типов: окно встроенного редактора баз знаний и окно диалога. Оба окна являются простыми текстовыми редакторами, но со специфическими функциями. Редактор базы знаний раскрашивает все слова в разные цвета. Основной цвет – черный, идентификаторы переменных – зеленые, строки текста и ремарки – синие, незавершенные строки – красные. Одновременно может быть открыто несколько окон редактора базы знаний.

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

Перед работой с базой знаний ее необходимо «собрать», т.е. перевести ее текстовое описание во внутреннюю структуру данных, удобную для обработки и хранения в оперативной памяти. База знаний собирается командами Consult (при открытии) и Reconsult (после редактирования). Собирается только текущая база знаний, расположенная в активном окне редактора баз знаний.

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

Дата добавления: 2014-12-27