Введение в язык логического программирования Пролог
На протяжении многих тысячелетий человечество занимается накоплением, обработкой и передачей знаний. Для этих целей непрерывно изобретаются новые средства и совершенствуются старые: речь, письменность, почта, телеграф, телефон и т. д. Большую роль в технологии обработки знаний сыграло появление компьютеров.
В октябре 1981 года Японское министерство международной торговли и промышленности объявило о создании исследовательской организации — Института по разработке методов создания компьютеров нового поколения (Institute for New Generation Computer Technology Research Center). Целью данного проекта было создание систем обработки информации, базирующихся на знаниях. Предполагалось, что эти системы будут обеспечивать простоту управления за счет возможности общения с пользователями при помощи естественного языка. Эти системы должны были самообучаться, использовать накапливаемые в памяти знания для решения различного рода задач, предоставлять пользователям экспертные консультации, причем от пользователя не требовалось быть специалистом в информатике. Предполагалось, что человек сможет использовать ЭВМ пятого поколения так же легко, как любые бытовые электроприборы типа телевизора, магнитофона и пылесоса. Вскоре вслед за японским стартовали американский и европейский проекты.
Появление таких систем могло бы изменить технологии за счет использования баз знаний и экспертных систем. Основная суть качественного перехода к пятому поколению ЭВМ заключалась в переходе от обработки данных к обработке знаний. Японцы надеялись, что им удастся не подстраивать мышление человека под принципы функционирования компьютеров, а приблизить работу компьютера к тому, как мыслит человек, отойдя при этом от фон неймановской архитектуры компьютеров. В 1991 году предполагалось создать первый прототип компьютеров пятого поколения.
Теперь уже понятно, что поставленные цели в полной мере так и не были достигнуты, однако этот проект послужил импульсом к развитию нового витка исследований в области искусственного интеллекта и вызвал взрыв интереса к логическому программированию. Так как для эффективной реализации традиционная фон неймановская архитектура не подходила, были созданы специализированные компьютеры логического программирования PSI и PIM.
В качестве основной методологии разработки программных средств для проекта ЭВМ пятого поколения было избрано логическое программирование, ярким представителем которого является язык Пролог. Думается, что и в настоящее время Пролог остается наиболее популярным языком искусственного интеллекта в Японии и Европе (в США, традиционно, более распространен другой язык искусственного интеллекта —язык функционального программирования Лисп).
Название языка "Пролог" происходит от слов ЛОГическое ПРОграммирование (PROgrammation en LOGique во французском варианте и PROgramming in LOGic — в английском).
Пролог основывается на таком разделе математической логики, как исчисление предикатов. Точнее, его базис составляет процедура доказательства теорем методом резолюции для хорновских дизъюнктов. Этой теме будет посвящена следующая лекция.
В истории возникновения и развития языка Пролог можно выделить следующие этапы.
В 1965 году в работе "A machine oriented logic based on the resolution principle", опубликованной в 12 номере журнала "Journal of the ACM", Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название "принцип резолюции". Эту работу можно прочитать в переводе: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции // Кибернетический сборник. — Вып. 7 (1970). На самом деле, идея данного метода была предложена Эрбраном в 1931 году, когда еще не было компьютеров (Herbrand, "Une methode de demonstration", These, Paris, 1931). Робинсон модифицировал этот метод так, что он стал пригоден для автоматического, компьютерного использования, и, кроме того, разработал эффективный алгоритм унификации, составляющий базис его метода.
В 1973 году "группа искусственного интеллекта" во главе с Аланом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (от Programmation en Logique). Она и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алана Колмероэ. Программа была написана на Фортране и работала довольно медленно.
Большое значение для развития логического программирования имела работа Роберта Ковальского "Логика предикатов как язык программирования" (Kowalski R. Predicate Logic as Programming Language. IFIP Congress, 1974), в которой он показал, что для того чтобы добиться эффективности, нужно ограничиться использованием множества хорновских дизъюнктов. Кстати, известно, что Ковальский и Колмероэ работали вместе в течение одного лета.
В 1976 г. Ковальский вместе с его коллегой Маартеном ван Эмденом предложил два подхода к прочтению текстов логических программ: процедурный и декларативный. Об этих подходах речь пойдет в третьей лекции.
В 1977 году в Эдинбурге Уоррен и Перейра создали очень эффективный компилятор языка Пролог для ЭВМ DEC–10, который послужил прототипом для многих последующих реализаций Пролога. Что интересно, компилятор был написан на самом Прологе. Эта реализация Пролога, известная как "эдинбургская версия", фактически стала первым и единственным стандартом языка. Алгоритм, использованный при его реализации, послужил прототипом для многих последующих реализаций языка. Как правило, если современная Пролог-система и не поддерживает эдинбургский Пролог, то в ее состав входит подсистема, переводящая прологовскую программу в "эдинбургский" вид. Имеется, конечно, стандарт ISO/IEC 13211– 1:1995, но его поддерживают далеко не все Прологсистемы.
В 1980 году Кларк и Маккейб в Великобритании разработали версию Пролога для персональных ЭВМ.
В 1981 году стартовал вышеупомянутый проект Института по разработке методов создания компьютеров нового поколения.
На сегодня существует довольно много реализаций Пролога. Наиболее известные из них следующие: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic Knowledge Workbench, Strawberry Prolog, SWI Prolog, UNSW Prolog и т. д.
В нашей стране были разработаны такие версии Пролога как Пролог-Д (Сергей Григорьев), Акторный Пролог (Алексей Морозов), а также Флэнг (А Манцивода, Вячеслав Петухин).
Стерлинг и Шапиро в книге "Искусство программирования на языке Пролог" пишут: "Зрелость языка означает, что он больше не является доопределяемой и уточняемой научной концепцией, а становится реальным объектом со всеми присущими ему пороками и добродетелями. Настало время признать, что хотя Пролог и не достиг высоких целей логического программирования, но, тем не менее, является мощным, продуктивным и практически пригодным формализмом программирования".
Традиционно под программой понимают последовательность операторов (команд, выполняемых компьютером). Этот стиль программирования принято называть императивным. Программируя в императивном стиле, программист должен объяснить компьютеру, как нужно решать задачу.
Противоположный ему стиль программирования — так называемый декларативный стиль, в котором программа представляет собой совокупность утверждений, описывающих фрагмент предметной области или сложившуюся ситуацию. Программируя в декларативном стиле, программист должен описать, что нужно решать.
Соответственно и языки программирования делят на императивные и декларативные.
Императивные языки основаны на фон неймановской модели вычислений компьютера. Решая задачу, императивный программист вначале создает модель в некоторой формальной системе, а затем переписывает решение на императивный язык программирования в терминах компьютера. Но, во-первых, для человека рассуждать в терминах компьютера довольно неестественно. Во-вторых, последний этап этой деятельности (переписывание решения на язык программирования) по сути дела не имеет отношения к решению исходной задачи. Очень часто императивные программисты даже разделяют работу в соответствии с двумя описанными выше этапами. Одни люди, постановщики задач, придумывают решение задачи, а другие, кодировщики, переводят это решение на язык программирования.
В основе декларативных языков лежит формализованная человеческая логика. Человек лишь описывает решаемую задачу, а поиском решения занимается императивная система программирования. В итоге получаем значительно большую скорость разработки приложений, значительно меньший размер исходного кода, легкость записи знаний на декларативных языках, более понятные, по сравнению с императивными языками, программы.
Известна классификация языков программирования по их близости либо к машинному языку, либо к естественному человеческому языку. Те, что ближе к компьютеру, относят к языкам низкого уровня, а те, что ближе к человеку, называют языками высокого уровня. В этом смысле декларативные языки можно назвать языками сверхвысокого или наивысшего уровня, поскольку они очень близки к человеческому языку и человеческому мышлению.
К императивным языкам относятся такие языки программирования,как Паскаль, Бейсик, Си и т. д. В отличие от них, Пролог является декларативным языком.
При программировании на Прологе усилия программиста должны быть направлены на описание логической модели фрагмента предметной области решаемой задачи в терминах объектов предметной области, их свойств и отношений между собой, а не деталей программной реализации. Фактически Пролог представляет собой не столько язык для программирования, сколько язык для описания данных и логики их обработки. Программа на Прологе не является таковой в классическом понимании, поскольку не содержит явных управляющих конструкций типа условных операторов, операторов цикла и т. д. Она представляет собой модель фрагмента предметной области, о котором идет речь в задаче. И решение задачи записывается не в терминах компьютера, а в терминах предметной области решаемой задачи, в духе модного сейчас объектноориентированного программирования.
Пролог очень хорошо подходит для описания взаимоотношений между объектами. Поэтому Пролог называют реляционным языком. Причем "реляционность" Пролога значительно более мощная и развитая, чем "реляционность" языков, используемых для обработки баз данных. Часто Пролог используется для создания систем управления базами данных, где применяются очень сложные запросы, которые довольно легко записать на Прологе.
В Прологе очень компактно, по сравнению с императивными языками, описываются многие алгоритмы. По статистике, строка исходного текста программы на языке Пролог соответствует четырнадцати строкам исходного текста программы на императивном языке, решающем ту же задачу. Пролог-программу, как правило, очень легко писать, понимать и отлаживать. Это приводит к тому, что время разработки приложения на языке Пролог во многих случаях на порядок быстрее, чем на императивных языках. В Прологе легко описывать и обрабатывать сложные структуры данных. Проверим эти утверждения на собственном опыте при изучении данного курса.
Прологу присущ ряд механизмов, которыми не обладают традиционные языки программирования: сопоставление с образцом, вывод с поиском и возвратом. Еще одно существенное отличие заключается в том, что для хранения данных в Прологе используются списки, а не массивы. В языке отсутствуют операторы присваивания и безусловного перехода, указатели. Естественным и зачастую единственным методом программирования является рекурсия. Поэтому часто оказывается, что люди, имеющие опыт работы на процедурных языках, медленней осваивают декларативные языки, чем те, кто никогда ранее программированием не занимался, так как Пролог требует иного стиля мышления, отказа от стереотипов императивного программирования.
Мне приходилось обучать Прологу школьников и студентов. Однажды занятие спецкурса по Прологу посетила одна преподавательница информатики. К тому времени у нее был довольно большой опыт программирования (и преподавания) на императивных языках. После окончания занятия она долго не могла прийти в себя. Реакция у нее была примерно следующая: "Я не понимаю, как такое может быть! Как программа в несколько строк на Прологе может делать то, на что в программе на Паскале понадобится несколько страниц текста?" Несмотря на то, что человеком она была далеко не глупым, она так и не смогла преодолеть "императивную зашоренность" и начать программировать в декларативном стиле. В отличие от нее, студенты и школьники, даже уже имеющие опыт программирования на императивных языках, но еще не "закостеневшие" в этом направлении, довольно легко воспринимали декларативный подход и без труда начинали программировать на Прологе. Так, один из школьников (семиклассник) после пары месяцев изучения Пролога написал на нем приставку к авиационной системе бронирования билетов "Габриель", которая использовалась в новосибирском "Аэрофлоте".
Как язык программирования Пролог очень хорошо, на мой взгляд, подходит для начального обучения программированию, так как он ориентирован на человеческое мышление в отличие от императивных языков, ориентированных на компьютер. Теми, кто только начинает изучать программирование, Пролог легко осваивается. Практически полное отсутствие синтаксических конструкций, таких как ветвления, циклы и т.д. также влияет на скорость освоения языка. Кроме того, программирование на Прологе, как мне кажется, упорядочивает мышление и позволяет человеку, изучающему этот язык программирования, лучше разобраться в своей мыслительной деятельности. Очень часто для того, чтобы запрограммировать решение задачи, программисту (или эксперту в некоторой предметной области) вначале требуется понять, как он сам решает эту задачу, провести некую формализацию, перевести свои знания из неявных в явные.
Однако, в отличие от некоторых приверженцев Пролога, я не склонен думать, что Пролог — лучший язык всех времен и народов, универсальный "решатель" любой задачи. На наш взгляд, для каждого языка существует свой класс задач, для решения которых он подходит лучше других языков программирования. Соответственно, для решения любой задачи есть оптимальный язык (языки) программирования. Многие задачи,хорошо решаемые императивными языками типа Паскаля и Си, плохо решаются на Прологе, и наоборот. Поэтому совсем даже неплохо, если человек владеет не одним инструментом решения задач, а может воспользоваться наиболее подходящим из имеющихся в его распоряжении. Давайте посмотрим, в каких областях наилучшим образом себя показал Пролог.
Основные области применения Пролога:
- быстрая разработка прототипов прикладных программ;
- автоматический перевод с одного языка на другой;
- создание естественно-языковых интерфейсов для существующих систем;
- символьные вычисления для решения уравнений, дифференцирования и интегрирования;
- проектирование динамических реляционных баз данных;
- экспертные системы и оболочки экспертных систем;
- автоматизированное управление производственными процессами;
- автоматическое доказательство теорем;
- полуавтоматическое составление расписаний;
- системы автоматизированного проектирования;
- базирующееся на знаниях программное обеспечение;
- организация сервера данных или, точнее, сервера знаний, к которому может обращаться клиентское приложение, написанное на каком-либо языке программирования.
Области, для которых Пролог не предназначен: большой объем арифметических вычислений (обработка аудио, видео и т.д.); написание драйверов.
Изучать Пролог без привязки к конкретной его версии, мне кажется, не совсем целесообразно. Как уже было сказано выше, версий Пролога очень много, и нужно выбрать какую-нибудь одну из них, чтобы привязать к этой версии разбираемые примеры. Мы остановимся на наиболее известной у нас в стране и довольно эффективной версии Пролога — Турбо Прологе. Его начинала разрабатывать фирма Borland International в содружестве с датской компанией Prolog Development Center (PDC). Первая версия вышла в 1986 году. Последняя совместная версия имела номер 2.0 и была выпущена в 1988 году.
В 1990 году PDC получила монопольное право на Турбо Пролог и дальше продвигала его под названием PDC Prolog.
В 1992 году вышла версия PDC Prolog 3.31.
В 1996 году, при участии группы питерских программистов, Prolog Development Center выпустила систему Visual Prolog 4.0. В состав среды Visual Prolog были включены инструментальные средства генерации кода, конструирующие управляющую логику, интерфейс визуального программирования и многие другие средства, позволяющие ускорить разработку приложений. Помимо прочих достоинств среды Visual Prolog стоит обратить внимание на возможность использования в идентификаторах символов национального алфавита, в частности, можно употреблять в программах русские имена доменов, предикатов и переменных, что делает программу более понятной и самодокументированной.
Сейчас вышла шестая версия системы Visual Prolog, которая, однако, довольно далеко шагнула в сторону не только от эдинбургской версии Пролога, но даже и от своей пятой версии, которая практически без проблем принимала программы на Турбо Прологе.
Исходя из соображений малого объема, доступности, малой ресурсоемкости, традиций, а также отсутствия всего лишнего, в том числе графической оболочки, остановимся на Турбо Прологе 2.0, хотя, наверное, это выбор довольно спорный. Но наша цель на данный момент — сосредоточиться на самом языке. Всюду, где это возможно, мы будем изучать Пролог, желательно как можно ближе к "чистому" Прологу. Попытаемся разобраться и с теоретическими основами этого языка. Но, тем не менее, я считаю, что программирование стоит осваивать, имея доступ к компьютеру с установленной на нем конкретной версией изучаемого языка. Все разбираемые в лекциях примеры будут работоспособны во второй версии Турбо Пролога и выше. В частности, они должны компилироваться в Visual Prolog версий 4–5.2. Как правило, их можно без особых проблем перенести и в другие версии Пролога. При этом, возможно, потребуется легкая модификация. Например, замена конструкции ": — " на "is" и т.д.
Самое существенное отличие Турбо Пролога от эдинбургской версии (так называемого "классического" Пролога) — наличие в нем строгой типизации данных для повышения скорости трансляции и выполнения программ. В начале программы на Турбо Прологе обычно располагаются разделы описаний доменов (типов данных) и предикатов. В Турбо Прологе отсутствует возможность рассматривать правила как данные, т. е. добавлять и удалять их во время работы, сопоставлять имя предиката с переменной. Изменяемой частью программы является внутренняя база данных (их может быть несколько). Во время выполнения программы в нее можно добавлять и из нее можно удалять факты.
В отличие от "классического" Пролога в Турбо Прологе нельзя определять операции. Турбо Пролог является компилируемым, а не интерпретируемым языком. К достоинствам Турбо Пролога относится возможность присоединять к программе на этом языке процедуры, написанные на Паскале, Си, Фортране или ассемблере.
