От двоичного кодирования к системам автоматической генерации кода

Вид материала

Документы

Содержание Пропел ли Пролог свою «лебединую песню»? Iso/iec 13211-1:1995 Arity Prolog 6.1. Turbo Prolog Русский Пролог

Подобный материал:

• План урока. Организационный момент. Изучение новой темы. Закрепление нового материала., 59.75kb.
• Майзаков Максим Александрович Разработка модулей автоматической генерации заданий, 799.4kb.
• Кафедра Вычислительной Техники Расчётно-пояснительная записка, 484.99kb.
• Генерация эффективного кода для процессорных архитектур с явным параллелизмом, 466.42kb.
• Вопросы к экзамену по дисциплине «Системное программное обеспечение» 4 курс (1 семестр), 17.38kb.
• 1. История языков высокого уровня, 299.15kb.
• Контрольные вопросы: Определение кода и способа помехоустойчивого кодирования (СПхК)., 40.69kb.
• Оптимизации генерации кода в jit-компиляторе виртуальной машины Java, 259.66kb.
• Перечень применяемых кодов, 180.07kb.
• Название проекта, 26.73kb.

Форт еще жив

Я долго думал, к какому поколению отнести этот язык. Его вполне можно причислить не то, что к третьему, а даже ко второму поколе­нию, так как Форт допускает низкоуровневое кодирование. Но, при­помнив историю С, сразу понял, что это, конечно, язык четвертого поколения. Форт создавался для тех же целей, что и С, но по потенциаль­ной мощности вполне сопоставим с языками типа Smalltalk.

Этот удивительный язык появился на свет в начале 70-х годов благо­даря стараниям Чарльза Мура. Он стал своего рода ответом на потреб­ности программистов в языке, с одной стороны, обладающим мощными и гибкими выразительными средствами, а с другой — пригодным для эффективной реализации на компьютерах с небольшими объемами памяти. А самое главное, язык обязан был выдавать очень быстрый и компактный код. То есть была нужна подходящая замена ассемблеру, так как из-за медленных компьютеров с ограниченными ресурсами использовать существовавшие в то время языки программирования для ряда задач не представлялось возможным.

Однако ветвь Форта для большинства проектов оказалась тупиковой. Появившийся примерно в то же время язык С, который создавался с аналогичными целями, быстро завоевал всемирное признание. Про Форт многие программисты, решающие «глобальные» задачи, быстро забыли. Почему же это произошло?

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

Но самое интересное, что Форт ограничивался очень небольшим набо­ром синтаксических конструкций. Реализовать его в базовом виде можно очень быстро, и поэтому Форт-система без проблем была реали­зована на множестве платформ. Это связано не с числом конструкций языка, а с самой идеологией Форта, на которой надо остановиться не­много поподробнее.

Форт работает с памятью только в виде виртуального стека. Все опера­ции в нем осуществляются над данными, хранящимися на вершине стека, и записываются последовательно — в обратной польской форме. Например, при выполнении двух команд + / сначала произойдет сло­жение двух чисел с вершины стека. Сами числа будут удалены оттуда, а на их место будет положена сумма. Затем произойдет деление этой суммы на следующее число в стеке. То есть если в стеке были записаны числа 3 5 8, то эти две команды выполнят действие (3+5)/8. Управляю­щие структуры, которых довольно мало: условный оператор и опера­тор цикла, — также основаны на анализе данных, хранящихся на вер­шине стека. Например, проверяется, лежат ли там логические значения ИСТИНА или ЛОЖЬ.

Все! На этом описание языка почти заканчивается. Конечно, есть еще переменные и возможность работы с адресами. Однако без наличия структур, позволяющих вычленять управляющие последовательности команд в отдельные модули, например в подпрограммы, язык програм­мирования существовать не может. Форт содержит оригинальные сред­ства, позволяющие гибко и наглядно описывать структуру решаемой задачи.

Любой последовательности команд можно поставить в соответствие «слово» — обычный идентификатор. Например, вышеприведенные команды можно «обозвать» СЛОЖ_ДЕЛ с помощью такой строки:

: СЛОЖ_ДЕЛ + / ;

Слово СЛОЖ_ДЕЛ записывается в специальный словарь Форт-системы и становится доступным для дальнейшего использования наряду с обыч­ными командами. Для достижения большей эффективности это «сло­во» может быть откомпилировано. Так можно легко описывать доволь­но сложные процессы вычислений, группировать их в слова и затем работать уже только с ними, зная, какие действия со стеком они выпол­няют. Например, управляющие команды для процессора микроволно­вой печи можно задать в таком виде:

температура 200 объект курица жарить

Форт-системы обычно очень компактны. Ядро занимает 10-15 Кбайт (!), а получающийся код по объему и эффективности не уступает ассем­блеру.

Но есть, конечно, у Форта и недостатки, причем они оказались настоль­ко существенными, что чаша весов при выборе языка, способного заме­нить ассемблер, быстро склонилась в сторону С. Основная проблема заключается в сложности восприятия текста, записанного в обратной польской форме, и, соответственно, в трудоемкой отладке. Чем дальше язык отходит от привычной для человека формы описания алгоритма, тем тяжелее с ним работать и тем больше ошибок возникает на этапе разработки. Язык Форт позволяет создавать очень эффективные про­граммы, но с появлением быстродействующих компьютеров скорость работы и тем более небольшие объемы памяти, занимаемые програм­мой, практически перестали играть важную роль. На первый план вы­шли языки, обладающие максимально выразительными средствами.

Сегодня Форт используется преимущественно для программирования микропроцессоров, где его качества проявляются наиболее выгодно. Такая ниша довольно объемна, и Форт уверенно чувствует себя в ней. Этот факт, в частности, подтверждают несколько стандартов языка, обновляемых с завидной регулярностью. Скорость обновления диктуется самой идеологией Форт-системы, как переносимого и не завися­щего от платформы продукта. Американский национальный стандарт описывает версию ANS Forth, такие компании, как IBM, HP, Sun, Apple и другие, поддерживают стандарт IEEE 1275 от 1994 года.

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

Как это бывает практически со всеми необъектными языками, родив­шимися достаточно давно, рано или поздно в них пытаются добавить понятие объекта. Но если в одни языки это понятие вписывается орга­нично, как, например, в Аду, то в Форте эти попытки привели к потере гибкости и не получили большого распространения.

Бесплатных версий Форта в мире довольно много. Информацию о них можно найти на сайте www.forth.org. Из коммерческих версий Форта можно выделить кросс-платформный вариант SwiftForth (www.forth.com). Вообще, множество версий языка Форт практически для всех мыслимых платформ объясняется максимальной простотой языка. Вы можете найти Форт для Windows и OS/2, для компьютеров Amiga и Macintosh, для систем Sun и так далее. И стоят они недорого — от 100 до 300 дол­ларов.

Для ряда задач, где требуется действительно быстрая переработка и анализ числовой информации, Форт пока незаменим, так как относи­тельная простота языка в сочетании с его гибкостью и широкой рас­пространенностью позволяют решать эти задачи очень эффективно, не прибегая к ассемблеру.


Пропел ли Пролог свою «лебединую песню»?

Пролог по праву считается одним из наиболее ярких языков програм­мирования. Заложенная в него концепция логического программиро­вания с годами только набирает популярность.

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

У многих людей, знакомых с логическим программированием, обычно возникают ассоциации с японским проектом компьютеров пятого поко­ления, все программное обеспечение которых создавалось на базе Про­лога. Некоторые эксперты считают, что этот проект фактически прова­лился, и причиной этому послужили некоторые присущие Прологу функциональные ограничения (хотя это не так — см. главу «Как японцы компьютерный мир осчастливили»).

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

Фактически Пролог является не процедурным, а декларативным язы­ком. Человек лишь описывает структуру задачи, а «внутренний мотор» Пролога сам ищет решение. Более того, в языке вообще не существует понятия последовательности команд — она скрыта в математической модели языка. Хотя, конечно, небольшой список «линейных» опера­торов типа repeat присутствует, но он ограничен возможностями исполь­зования лишь для конкретных случаев.

Математическая модель Пролога основана на теории исчисления пре­дикатов, в частности, на процедурной интерпретации Хорновых дизъ­юнктов (содержащих не более одного заключения) Роберта Ковальского из Эдинбурга. Ее в алгоритмическом, машинно-ориентированном виде, выразил коллега Ковальского Маартен ван Эмден. Надо сказать, что работы этих ученых из-за большой сложности их практической реали­зации на компьютерах (по тем временам) подвергались большой кри­тике со стороны американских специалистов по искусственному интел­лекту.

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

В качестве типовых данных Пролог использует элементарные единицы данных, так называемые атомы: строки символов и числа. Из атомов составляются списки и бинарные деревья. Сама «программа» строится как последовательность фактов и правил, а затем формулируется утвер­ждение, которое Пролог будет пытаться доказать с помощью введен­ных правил.

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

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

Но в силу своей специфичности и сильной ориентированности на встро­енные алгоритмы поиска доказательств Прологу не суждено было воплотиться в конкретном стандарте, который получил бы массовое признание. На сегодня имеется стандарт ISO/IEC 13211-1:1995, но он поддерживается далеко не всеми коммерческими системами, имеющими различные принципы реализации и цели, для которых планируется использовать эти системы. Фактически первым и единственным стандартом осталась версия языка, созданная в Эдинбурге для PDP в 70-е годы! И хотя ее поддерживают не все сегодняшние системы, их разработчики обычно прилагают к своим продуктам препроцессор, пе­реводящий программу данного диалекта к эдинбургскому виду.

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

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

В целях получения высокоэффективных исполняемых модулей были предприняты попытки написания компиляторов, транслирующих текст Пролог-программ в код на языке С. Однако, в отличие от проце­дурных языков сверхвысокого уровня, для Пролога хорошего резуль­тата добиться не удалось. Структура декларативной «программы» с большим количеством базовых фактов приводила к появлению крайне неуклюжих конструкций. Например, появлялись операторы switch языка С с более чем 15000 (!) условиями выбора case. Такие синтаксически корректные выражения многие компиляторы считали ошибкой или выдавали неэффективный код.

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

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

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

Для примера приведем систему SWI-Prolog (ftp://swi.psy.uva.nl), содержа­щую быстрый компилятор, профилировщик, набор библиотек и удоб­ный интерфейс для подключения модулей на языке С. Она реализо­вана для ряда С/шя-платформ, таких как HP и Linux, а также для Windows, NeXT, OS/2, Sun и SPARC.

Несколько лет назад в Пролог было введено понятие объекта. Появился ряд объектных диалектов, таких как freeware-версия OL(P) — Objec: Layer for Prolog. Это простой компилятор объектного кода в обычный Пролог, поддерживающий все принципы объектно-ориентированного программирования, вплоть до множественного наследования. Не обо­шлось, конечно, и без коммерческих объектных версий, не получив­ших, впрочем, большого успеха из-за появления нового полудеклара­тивного языка с мощными средствами объектно-ориентированног программирования — Smalltalk.

Из коммерческих реализаций Пролога надо упомянуть бывшую одно время весьма популярной систему Arity Prolog 6.1. Вариант Delphin: Prolog, работающий на ряде Unix-платформ, включает в себя высокс производительные компилятор и интерпретатор, интерфейсные библи I теки и поддерживает эдинбургский стандарт. Для системы Windoi имеется прекрасная 32-разрядная версия LPA-Prolog как со «стандарт­ным», так и с расширенным объектным синтаксисом, с набором бис лиотек для работы с оконным интерфейсом, с поддержкой DDE и пр токола ODBC и с возможностью создания библиотек DLL.

Знакомый многим отечественным программистам Turbo Prolog, рабатывавшийся ранее фирмой Borland, теперь выступает под мар PDC Prolog и реализован для операционных систем MS-DOS, Wind( OS/2 и Unix/Linux. Правда, сохранились как достоинства, так и н статки первоначального варианта. Имеется удобная среда разработ*; и быстрый компилятор, но наблюдается несовместимость с подав! щим большинством других диалектов этого языка. Существует cm альная версия для визуальной разработки VisualProlog.

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

Однако нельзя сказать, что Пролог свою «лебединую песню» про Как наиболее известный и наиболее простой в освоении из всех де ративных языков, он остается и сегодня прекрасным средством быстрого создания экспертных систем и интеллектуальных баз зна требующих сложной структуры запроса. Хорошая реализация Пр га — это, по сути, CASE-система, только простая в изучении и гиб! использовании, что косвенно подтверждается ценами на разли* версии этого языка.


Русский Пролог

В Старом свете родились практически все наиболее красивые я; программирования. Заложенные в них оригинальные идеи основывались на фундаментальных математических теориях. Разрабатывались такие языки и в СССР, продолжают они разрабатываться и в России (например, язык Dynamo фирмы «Параграф» для описания трехмерных виртуальных миров). Наиболее почтенный по возрасту, но с годами только становящийся мощнее — это язык РЕФАЛ (РЕкурсивных Функций АЛгоритмический язык).

О судьбе этого языка я узнал из первых рук — от Владимира Хорошевского, профессора, члена-корреспондента РАЕН, руководителя ceктора экспертных систем отдела проблем искусственного интеллекта РАН.

Первую версию РЕФАЛа разработал В.Ф. Турчин еще в 1964 году, Этот язык, реализовавший концепцию сопоставления с образцом, родился раньше Пролога и СНОБОЛа, которых часто считают родоначальниками этого направления. В основе РЕФАЛа лежит теория нормальных алгоритмов Маркова (реализованная во внутренней машине вывода), которая потенциально мощнее теории исчисления Хорновых дизъюн­ктов, воплощенной в Прологе. Благодаря этому язык, созданный в СССР, позволяет решать некоторые задачи значительно эффективнее, чем его зарубежные собратья. Немаловажно, что РЕФАЛ превосходит известные языки сопоставления с образцом по своей выразительной мощности и легкости понимания текста программ.

Первоначально так называемый базисный РЕФАЛ позиционировался как язык для преобразования произвольных языковых конструкций, своего рода метаалгоритмический язык.

Первый интерпретатор РЕФАЛа на БЭСМ-6 написали С. Флоренцев и С. Романенко. Он выполнял до 300 конкретизации (сопоставлений с образцом и преобразований образца к требуемому результату) в секунду, что даже по нынешним временам довольно высокий результат. В основе интерпретатора лежала абстрактная РЕФАЛ-машина, работающая с бесконечным полем памяти. Модель данных поддерживала двунаправленные списки, а в РЕФАЛ-2 добавилось понятие закольцованных ссылок, в результате чего появи­лась возможность работать не только с древовидными структурами, но и с графами и сетями. Естественно уложился в эту концепцию процесс отождествления «слева направо» и «справа налево», что сделало РЕФАЛ симметричным языком.

Язык РЕФАЛ-2 появился в 70-е годы. Были написаны компиляторы практически для всех платформ (М220, БЭСМ, СМ, ЕС ЭВМ). Для записи исходных текстов программ разработчики создали метакод-Б, позво­ливший описывать структуру решаемой задачи намного нагляднее, чем в ранних вариантах представления программ. Скорость работы тоже впечатляла: на IBM PC XT программа выполнялась со скоростью 1500 кон­кретизации в секунду! Семантика РЕФАЛа как декларативного языка позволила также получить очень хорошие тестовые результаты при реализации на параллельных компьютерах.

Однако по ряду причин судьба этого языка сложилась несчастливо. В. Турчин уехал из России, и на некоторое время РЕФАЛ был предан забвению. Однако энтузиасты компьютерного дела продолжали совер­шенствовать язык, и на сегодняшний день имеются две версии: РЕФАЛ-5 и РЕФАЛ+. Синтаксис языка сблизился с C++ и поддерживает объект­ную идеологию. Объектно-ориентированное программирование выра­жено в представлении функций языка как объектов, которые можно использовать в качестве образцов наравне со стандартными объектами C++, что превращает РЕФАЛ в очень мощную открытую систему про­граммирования. Сегодня последние версии языка реализованы на самых разли платформах. В Институте прикладной математики (ИПМ) РАН i ботан транслятор с РЕФАЛа для .R/SC-архитектур. При реализации ряда алгоритмов он позволяет получать выигрыш примерно в 5 ] сравнению с результатами известных западных фирм, использу) другие языки. При реализации РЕФАЛа на спецпроцессоре выи еще больше.

Сегодня РЕФАЛ прочно занимает свою нишу, не опасаясь никаки: курентов. Например, он успешно используется физиками Обн] при реализации аналитических преобразований, а также мне математическими центрами России. Одно из основных приме! РЕФАЛа — разработка трансляторов с языков программиров; когда сам РЕФАЛ используется как метаязык. В ИПМ на нем был быстро написан высокоэффективный транслятор CERN Fortran.

Благодаря тому что РЕФАЛ был разработан в нашей стране, не об его вниманием и военные. Для современной боевой техники не] требуется быстро модифицировать средства разработки, делая и: кватными растущим возможностям электроники. РЕФАЛ подде вает создание быстро совершенствующихся узкоспециализирова языков программирования.

Наконец, еще одна интересная область, где используется РЕФА это искусственный интеллект. Здесь РЕФАЛ применяется и как к ное средство разработчика, и как инструмент для создания яз представления знаний, ориентированных на конкретные области менения в искусственном интеллекте. Одним из фундаментал направлений, позволяющих эффективно использовать мощь РЕФ является анализ естественных языков. С помощью РЕФАЛа соз лингвистические процессоры, экспертные системы и многое друго одном из проектов оптимизации исходных текстов программ на РЕ<5 в качестве языка, осуществляющего необходимые преобразование стов, был взят сам РЕФАЛ.

В 80-е годы американцы были серьезно озабочены японским прое компьютеров пятого поколения, опасаясь появления конкуре] сфере компьютерных технологий. Однако язык Пролог, выбранЕ качестве базового для машины вывода систем пятого поколени оправдал ожиданий, возможно потому, что его система логичес вывода обладает рядом ограничений. А РЕФАЛ, имеющий в своей 0( мощную математическую модель, существенно превосходящую лог, вполне мог удовлетворить требованиям японской системы. Поз можно надеяться, что если мы доживем до реализации подобного екта компьютеров нового поколения в России, то в качестве базе языка будет выбран именно РЕФАЛ.