Перейти к содержимому

Язык программирования Пролог

Язык программирования ПРОЛОГ (PROLOG) создан во Франции в Марсельском университете в 1971 году. Его разработал Ален Кольмеро (Colmerauer - его фамилию по-разному переводят на русский язык).

Название языку, как говорят, дал коллега создателя - Ф. Руссель или жена последнего, хотя в дальнейшем его стали расшифровывать как "Программирование в терминах ЛОГики" (PROLOG - PROgramming in LOGic). Язык ПРОЛОГ имел непосредственного предшественника. Вот что говорит А.Кольмеро: "Риск, присущий данному проекту (проекту создания ПРОЛОГа), заключается в том, что мы могли создать язык высокого уровня, который оказался бы неэффективным. Но я однажды уже рискнул и одержал победу - так несколько лет назад был создан язык SYSTEM-Q".

Разрабатывая новый язык программирования для задач анализа и понимания естественных языков, А.Кольмеро решил использовать язык формальной логики, а точнее логики предикатов первого порядка (здесь ПРОЛОГ имеет общие корни с реляционными базами данных) и метод автоматического доказательства теорем.

Язык ПРОЛОГ основан на концепциях логического программирования, предложенных профессором Лондонского университета Робертом Ковальским, и представляет собой среду, ориентированную на рассуждения или дедукцию. "ПРОЛОГ часто путают с логическим программированием - пишет Р.Ковальский. ПРОЛОГ базируется на логическом программировании почти в таком же смысле, в каком ЛИСП базируется на лямбда исчислении". То есть можно сказать, что первым применением логического программирования является язык ПРОЛОГ. При логическом программировании, которое реализуется на языке ПРОЛОГ, осуществляется обработка символьной информации (решение проблем), в ходе которой процесс доказательства теорем интерпретируется как процесс вычисления или процесс выполнения программы. Соответствие процесса доказательства теорем и процесса выполнения программы и было установлено Р.Ковальским. А метод автоматического доказательства теорем, называемый методом резолюций, разработал Дж.Робинсон в середине 60-х годов.

Надо сказать, что попытка реализовать некоторые идеи логического программирования были сделаны разработке малоизвестных языков QA3 и QA4, а также Хьюиттом и Зусманом из Массачуссетского технологического института при создании языков ПЛЭНЕР (PLANNER) и МИКРО-ПЛЭНЕР (MICRO-PLANNER).

До начала 80-х годов ПРОЛОГ был уделом ученых, работавших в основном в области логического программирования и мало знаком широкому кругу программистов и пользователей компьютеров (для многих непосвященных название языка ассоциировалось с аналогичным названием фирмы, производящей микропроцессорную технику).

Ситуация стала меняться с октября 1981 года, когда Япония известила мир программе создания вычислительных машин пятого поколения, в которых язык ПРОЛОГ выбран а качестве базового языка программирования. На протяжении 80-х годов ПРОЛОГ не сходит со страниц многочисленных научных журналов по вычислительной технике и публикаций в области искусственного интеллекта.

Однако растущую популярность ПРОЛОГа, как отмечают венгерские специалисты Б. Домелки и П. Середи, нельзя объяснить только выбором авторов японского проекта, здесь кроются более глубокие причины.

При решении проблем "кризиса программного обеспечения", ПРОЛОГ можно рассматривать как универсальный язык сверхвысокого уровня с хорошо определенной и логически обоснованной семантикой. ПРОЛОГ, будучи языком логического программирования, не только изменяет стиль программирования задач (в смысле фон Неймана), но и укоренившуюся (в течение четырех поколений) архитектуру вычислительных машин. "Компьютеры по существу, никогда не менялись, они только становились меньше и мощнее, а языки приспосабливались к первоначальной архитектуре, - замечает А.Кольмеро. - Когда мы писали ПРОЛОГ, то буквально поддразнивали машину, заставляя ее делать все, что нам хотелось".

Программа на языке ПРОЛОГ содержит две составные части: факты и правила. Факты представляют собой данные, с которыми оперирует программа, а совокупность фактов составляет базу данных ПРОЛОГа, которая является не чем иным, как реляционной базой. Основная операция, выполняемая над данными, - это операция сопоставления, называемая также операцией унификации или согласования. Правила состоят из заголовка и подцелей. Выполнение программы, написанной на ПРОЛОГе начинается с запроса и состоит в доказательстве истинности некоторого логического утверждения в рамках заданной совокупности фактов и правил. Алгоритм этого доказательства (алгоритм логического вывода) и определяет принципы исполнения программы, написанной на ПРОЛОГе.

В отличие от программ, составленных на языках процедурного типа (БЕЙСИК, ПАСКАЛЬ и др.), предписывающих последовательность шагов, которые должен выполнить компьютер для решения задачи, в ПРОЛОГе программист описывает факты, правила, отношения между ними, а также запросы по проблеме.

Первый интерпретатор ПРОЛОГа, написанный на ФОРТРАНе, разработан А.Кольмеро и Ф.Русселем в 1973 году. Затем появился компилятор ПРОЛОГа, созданный Д.Уорреном и Ф.Перейра из Эдинбургского университета для машины DEC-10.

Большие успехи в развитии и распространении ПРОЛОГа были достигнуты в Венгрии, там ученые начали заниматься реализацией языка с 1974 года. В 1975 году они создали интерпретатор ПРОЛОГа, написанный на языке CDL. Основные работы по совершенствованию языка начиная с 1978 года велись в Будапештстком институте по координации вычислительной техники, где в 1981 - 1982 годах создана модульная система ПРОЛОГ - М-ПРОЛОГ на языке CDL-2. Там же в 1982 году разработан Т-ПРОЛОГ для моделирования дискретных систем, а в 1985 году появились мини-ПРОЛОГ для персональных компьютеров и Т/ТС-ПРОЛОГ для моделирования дискретно-непрерывных систем. Версии, разработанные Будапештским институтом, реализованы на многих компьютерах различных фирм (IBM, Siemens, Tektronix, Motorola).

В начале 80-х годов фирма Silogic Inc. (Лос-Анжелес) создала набор интерпретаторов для различных типов компьютеров - от машин на базе микропроцессоров Z80 с ОС CP/M до машин DEC-20 с ОС TOPS-20, а также несколько компиляторов.

В последние годы наибольшую популярность получили версии ПРОЛОГа, реализованные на персональных компьютерах - сейчас в мире их насчитывается около пятнадцати. Среди них такие как Эрити/ПРОЛОГ (Arity/PROLOG), Микро-ПРОЛОГ, ПРОЛОГ-86, ПРОЛОГ-В (PROLOG-V), ПРОЛОГ-2, АЛС ПРОЛОГ (ALS PROLOG), Квинтус ПРОЛОГ (Quintus Prolog), ТУРБО-ПРОЛОГ и др. Только три из перечисленных - ПРОЛОГ-2, Эрити/ПРОЛОГ и Турбо-ПРОЛОГ имеют возможность компиляции. ПРОЛОГ-2 фирмы Expert Systems International (ESI) превосходит в скорости интерпретируемый ПРОЛОГ-1 в 20 раз. Эрити/ПРОЛОГ фирмы Arity (отеление фирмы Lotus Advanced Devrlopment Group) представляет собой программную среду, включающую все необходимые средства разработки программ на ПРОЛОГе. Фирма Borland International в 1985 году выпустила первую версию компилятора Турбо-ПРОЛОГ, которая обеспечивает многооконный интерфейс и графические возможности.

На сегодняшний день не существует стандарта на язык программирования ПРОЛОГ. В то же время считается, что версия двух профессоров Эдинбургского университета У. Клоксина и К. Меллиша может быть принята за стандартную.

Первая аппаратная реализация языка относится к 1984 году, когда Д.Уорреном был разработан конвейерный процессор языка ПРОЛОГ - SRI. Затем в рамках реализации японского проекта машин пятого поколения в 1985 году появился действующий макет машины PSI (Personal Sequential Interface Machine - персональная ЭВМ последовательного вывода), а в 1986 году опытный образец машины CHI (Cooperative High - Speed Interface Machine - параллельная быстродействующая машина вывода). Машина PSI с производительностью 30 тыс. логических выводов в секунду создавалась в качестве средства разработки программного обеспечения всего японского проекта. Усовершенствованный вариант PSI-II имеет производительность 150 тыс. логических выводов в секунду. Основной целью разработки CHI и модификации CHI-II было дальнейшее повышение производительности, которая была доведена до 400 тыс. логических выводов в секунду.

В СССР работы по логическому программированию ведутся с 60-х годов. В частности в ЛОМИ им. Стеклова велись работы по автоматическому доказательству теорем. С. Ю. Масловым в рамках этих работ был предложен обратный метод вывода - на год раньше метода резолюций. В.Б.Борщевым и М.В.Хомяковым независимо от зарубежных работ начиная с 1972 года разрабатывалась версия логического программирования. К идеям логического программирования примыкают в этот период работы А.П.Ершова и А.С.Клещева, а также работы А.М.Степанова по описанию абстрактной параллельной машины для языков логического программирования.

Впервые в нашей стране язык ПРОЛОГ (базовый входной язык системы ПРОЛОГ-ЕС) был реализован в конце 70-х годов сотрудниками Института кибернетики им. В. М. Глушкова АН УССР и Рижского политехнического института для ЕС ЭВМ с операционными системами ДОС и ОС. Для написания основных модулей системы ПРОЛОГ-ЕС использован язык ФОРТРАН-IV, а ввод-вывод написан на АССЕМБЛЕРе.

В дальнейшем появились версии: ПРОЛОГ-СМ для мини-ЭВМ СМ-4, функционирующая под управлением операционной системы ОС РВ; система программирования ПРОЛОГ-32, реализованная на ЭВМ СМ-1700 и работающая под управлением операционной системы ДЕМОС-32; система программирования Микро-ПРОЛОГ для персональных компьютеров ЕС-1840, ЕС-1841, IBM PC/XT/AT, функционирующая под управлением операционных систем АЛЬФА ДОС и MS DOS. В Институте программных систем АН СССР разработана версия ПРОЛОГа для персонального компьютера "Ямаха MSX". Интерпретаторы языка ПРОЛОГ созданы для школьных компьютеров отечественного производства - "Корвет", УКНЦ, БК-0010.

Возможности применения языка ПРОЛОГ весьма обширны. Вот что пишет по этому поводу Р.Ковальский: "Сила и эффективность языка ПРОЛОГ и его реализаций оказалась такими, что он нашел многочисленные и разнообразные применения. Среди наиболее известных - применение в символической математике, планировании, автоматизированном проектировании, построении компиляторов, базах данных, обработке текстов на естественных языках, машинной индукции, отладке и экспертных системах".

Наверное, самое характерное применение ПРОЛОГа - это экспертные системы (ЭС). Пролог вносит своеобразный вклад в создание ЭС, особенно для механизма логического вывода. Модели представления знаний в ЭС включают систему продукций, фреймы, семантические сети, логику предикатов. Разработанные языки представления знаний часто зависят от тех моделей представления, которые они используют. Язык ПРОЛОГ можно использовать для применения любой модели, его можно рассматривать и как воплощение модели представления знаний, и как язык представления знаний. Определение, данное Р.Ковальским:

                Алгоритм = Логика + Управление

подтверждает это утверждение и помогает прояснить термин "управление" в экспертных системах. В этом определении ЛОГИКА показывает, что является проблемой (областью), а УПРАВЛЕНИЕ - как эффективно использовать логику для решения проблем.

Как утверждают создатель языка и его коллеги, "ПРОЛОГу суждено сыграть одну из первых ролей в развитии информатики", и в частности, "при правильном преподавании информатики необходимо использовать такой язык, который помогал бы структурировать мышление. Сначала пользователей взращивали на АЛГОЛе-60, затем на ПАСКАЛе. Лучше их воспитывать на ЛИСПе, но еще лучше - на ПРОЛОГе".

//Вычислительная техника и ее применение N2'91

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *