История создания и развития языка

Разработка языка Prolog началась в 1970 году Аланом Кулмероэ и Филиппом Расселом. Их целью было создание языка, который мог бы делать логические заключения на основе заданного текста. Название Prolog является сокращением от "Programminginlogic". Итак, Prolog, как язык, был разработан в Марселе в 1972 году. Предварительно на основе некоторого "принцип резолюции" Ковальского, сотрудника Эдинбургского университета, была создана модель, на основе которой и был разработан механизм логических выводов.

Первая реализация языка Prolog с использованием компилятора Никлауса Вирта "Algol-W" была закончена в 1972 году, а основы современного языка были заложены позднее, в 1973 г. Использование языка Prolog постепенно распространялось среди тех, кто занимался логическим программированием, в основном благодаря личным контактам, а не через коммерциализацию продукта. В настоящее время существует несколько различных, но довольно похожих между собой версий языка. Хотя стандарта языка Prolog не существует, однако версия, разработанная в Эдинбургском университете, стала наиболее широко используемым вариантом. Здесь надо отметить тот факт, что недостаток разработок эффективных приложений Prolog сдерживал его распространение вплоть до 1980 г.

Теория логического программирования со временем совершенствовалась. Существенный вклад в ее развитие внесла работа Р. Ковальского "Логика предикатов как язык программирования". В 1976 г. Ковальский и М. ванЭмден предложили два подхода к прочтению текстов логических программ — процедурный и декларативный. Оба этих подхода стали активно использоваться при написании программ на языке Prolog.

Только в 1977 году Д. Уоррен и Ф. Перейра создают в университете Эдинбурга интерпретатор/компилятор языка Prolog для ЭВМ DEC-10, тем самым переведя методы логического программирования в практическую плоскость. Позднее в 1980 году К. Кларк и Ф. Маккейб в Великобритании разработали версию Prolog для персональных ЭВМ.

Интересный факт: в октябре 1981 года мир облетела новость о японском проекте создания ЭВМ пятого поколения. В основу методологии разработки программных средств было положено логическое программирование. Целью проекта декларировалось создание систем обработки информации, базирующихся на знаниях, а главным средством реализации должен был стать именно язык Prolog.

В это же время (начало 1980-х годов) появляется множество коммерческих реализаций Prolog практически для всех типов компьютеров. К наиболее известным можно отнести "CProlog", "QuintusProlog", "SilogicKnowledgeWorkbench", "Prolog-2", "ArityProlog", "Prolog-86", "ТurboProlog" и др. В данной статье мы опирались на версию языка "SWI-Prolog".

Существует мнение, что Prolog — уже почти умерший язык, что он за небольшой промежуток времени (1970-1980-е годы) смог пройти весь жизненный цикл — от начальных разработок, стремительного повышения интереса со стороны узких специалистов, затем стремительный взлет популярности, падение интереса и почти полное забвение. Мнение вызвано тем, что такая судьба — обычное явление в мире информационных технологий, где новые, более совершенные, дидактически верные и теоретически более красивые языки программирования возникают каждый год и тихо умирают. Сторонники мнения аргументируют его тем, что структура Prolog-программ очень трудна для восприятия из-за того, что иногда невозможно визуально предугадать ход логического вывода — единственный предикат-факт, запрятанный где-то в конце текста программы, может направить работу в совершенно непредсказуемое русло. В некотором они правы: трудность сопровождения Prolog-программ и трудность мышления на Prolog для рядовых программистов оказались непреодолимыми препятствиями для его широкого распространения. Да и, конечно, во времена разработки Prolog ждали от него большего, но потом оказалось, что сам по себе язык программирования помочь в решении серьезнейших задач, например, связанных с принятием компьютером решений (machinereasoning), не может.

Но всё же язык Prolog используется и сегодня при решении целого класса достаточно специфических задач. Об этом — в следующей части.

Область использования

Основные области применения Пролога:

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

Области, для которых Пролог не предназначен: большой объем арифметических вычислений (обработка аудио, видео и т.д.); написание драйверов.

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

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

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

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

Также Prolog используется при написании новых специфичных языков программирования. Например, функциональный язык Erlandпостороен на основе Prolog. По сути, Erland является усовершенствованием Prolog для некоторых специфических целей, связанных с задами реального времени.

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

2. Пролог - язык начального обучения программированию. Преимущества и недостатки языка Пролог.

Мы остановимся на наиболее известной у нас в стране и довольно эффективной версии Пролога — Турбо Прологе. Его начинала разрабатывать фирма BorlandInternational в содружестве с датской компанией PrologDevelopmentCenter (PDC). Первая версия вышла в 1986 году. Последняя совместная версия имела номер 2.0 и была выпущена в 1988 году.

 

В 1990 году PDC получила монопольное право на Турбо Пролог и дальше продвигала его под названием PDC Prolog.

 

В 1992 году вышла версия PDC Prolog 3.31.

 

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

 

Сейчас вышла шестая версия системы VisualProlog, которая, однако, довольно далеко шагнула в сторону не только от эдинбургской версии Пролога, но даже и от своей пятой версии, которая практически без проблем принимала программы на Турбо Прологе.

 

Исходя из соображений малого объема, доступности, малой ресурсоемкости, традиций, а также отсутствия всего лишнего, в том числе графической оболочки, остановимся на Турбо Прологе 2.0, хотя, наверное, это выбор довольно спорный. Но наша цель на данный момент — сосредоточиться на самом языке. Всюду, где это возможно, мы будем изучать Пролог, желательно как можно ближе к "чистому" Прологу. Попытаемся разобраться и с теоретическими основами этого языка.

 

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

 

В отличие от "классического" Пролога в Турбо Прологе нельзя определять операции. Турбо Пролог является компилируемым, а не интерпретируемым языком. К достоинствам Турбо Пролога относится возможность присоединять к программе на этом языке процедуры, написанные на Паскале, Си, Фортране или ассемблере.

3. Хорновские дизъюнкты. Особенности работы с негативными знаниями в Прологе

Хорновский дизъюнкт — дизъюнктивный одночлен с не более чем одним положительным литералом. Изучены Альфредом Хорном (англ. AlfredHorn) в 1951 году в связи с их важной ролью в теории моделей и универсальной алгебре. Впоследствии стали основой для языка логического программирования Пролог, в котором программа являются непосредственно набором хорновских дизъюнктов, а также нашли важные приложения в конструктивной логике и теории сложности вычислений.

Существует два вида хорновских дизъюнктов.

Хорновский дизъюнкт с заголовком - это дизъюнкт, содержащий одну литеру без отрицания. Он может содержать одну или несколько литер с отрицанием или не содержать их вообще, например:
A:-B,C,..D;
A:-B;
A:-.

Последний из приведенных дизъюнктов можно записывать без знака ":-", то есть в виде А.

Хорновский дизъюнкт без заголовка - это дизъюнкт, не содержащий литер без отрицания, например:
:-B,C,..D;
:- A.

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

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

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

Любая задача, которая может быть выражена с помощью хорновских дизъюнктов, должна иметь только один дизъюнкт без заголовка (целевой); все остальные дизъюнкты должны быть с заголовками (гипотезы).

Хорновские дизъюнкты были выбраны в качестве основы для создания программных систем автоматического доказательства теорем.

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

4. Предложения: факты и правила. Цели внутренние и внешние.

5. Отношения (предикаты). Переменные свободные и связанные.

6. Семантические модели Пролога: декларативная и процедурная

7. Рекурсия. Достоинства и недостатки рекурсии. Хвостовая рекурсия.

8. Структура программы на Турбо-Прологе.

9. Домены: стандартные, списковые, составные. Альтернативные домены.

10. Программы: "Родственники", факториал, возведение в степень, числа Фиббоначи.

11. Метод поиска в глубину. Откат после неудачи. Отсечение и откат. Метод поиска, определяемый пользователем.

12. Списки. Рекурсивное определение списка. Операции над списками.

13. Нахождение суммы элементов списка, среднего и минимального значений; алгоритмы сортировки списков: пузырьковый, выбором, вставкой, слиянием, быстрая сортировка.

14. Реализация множеств в Прологе. Операции над множествами: превращение списка во множество, принадлежность элемента множеству, объединение, пересечение, разность, включение, дополнение.

15. Бинарные деревья, двоичные справочники и операции над ними.

16. Обработка строк.

17. Описание файлового домена. Стандартные предикаты Турбо-Пролога для работы с файлами.

18. Запись информации в файл. Чтение информации из файла. Переписывание информации из файла в файл.

19. Работа с внутренними (динамическими) базами данных: добавление фактов в базу, удаление фактов из базы.

20. Применение Пролога в области искусственного интеллекта. Тест Тьюринга.