Данный пост является репостом постов #829362, #844329 и #858270 моего микроблога на Жуйке. Текст не является точным репостом, т.к. немного подправлен.
Введение
Есть такой функциональный язык программирования — Рефал (рекурсивные фукции, алгоритмический язык, Refal — recursive functions, algorithmic language). Придуман в СССР кибернетиком Турчиным где-то в 60-70 годы прошлого века. Как любят писать во введении в мануалах ко всяким диалектам (см. ниже) Рефала, «сначала Рефал создавался как метаалгоритмический язык для описания семантики других языков программирования, но с появлением эффективных реализаций на ЭВМ он стал применяться как обычный язык программирования». Применяли его преимущественно для преобразований сложных алгебраических выкладок, написания трансляторов (на Рефале 2 был написан компилятор Фортрана) и других задач символьных вычислений.
За время долгой истории Рефала было разработано несколько различных малосовместимых между собой диалектов: первая реализация, позже названная базисным Рефалом (с очень странным синтаксисом), Рефал 2 с не странным, но тем не менее, очень неудобным синтаксисом, ориентированном на перфокарты, Рефал 5 с условиями и блоками, Рефал Плюс с «многоаргументными» функциями, блоками и хитрой системой неуспехов и откатов, Рефал 6 — тот же Рефал 5, но тоже с хитрой системой неуспехов и откатов, но с более согласованным синтаксисом, по сравнению с Рефалом Плюс.
У нас в универе (МГТУ имени Н. Э. Баумана) на кафедре ИУ9 разрабатывают Рефал 7. В УдГУ ведётся разработка Динамического Рефала (Dynamic Refal, D-Refal). Я сам разработал два диалекта: Модульный Рефал (основной проект) и Простой Рефал (своего рода черновик).
Если сравнивать с другими языками программирования, то Рефал идеологически больше всего похож на Эрланг — тоже динамически типизирован, та же основная идея: функция есть набор предложений с левой частью — образцом и правой частью — результатом выполнения. Особенность Рефала в том, что основной структурой данных является не однонаправленный список (голова+хвост), а двунаправленное рефал-выражение. Определение последнего элемента выполняется столь же быстро, как и первого, два рефал-выражения конкатенируются в одно за постоянное время (в отличие от конкатенации списков за линейное время). Резко повышается выразительность образцов (левых частей), поскольку можно смотреть не только в начало, но и в середину рефал-выражения (про конец я и не говорю).
Для начального ознакомления рекомендую зайти на сайт http://www.refal.org/ и найти там руководство по Рефалу 5. Оно наиболее понятное и простое.
Реализации Рефала: особенности и критика
На настоящий момент в открытом доступе (на сайте http://www.refal.org/) находятся следующие диалекты Рефала: Рефал 2, Рефал 5, Рефал 6 и Рефал Плюс.
Первым мне на глаза попался диалект Рефала 5, разработанный Турчиным. У него сравнительно простой, а главное, понятный синтаксис и грамотно написанное руководство. Я его прочёл и остался очень доволен.
Ранее, я читал книжку Андрея Александреску «Современное проектирование на C++», которая мне очень понравилась, так что функциональная парадигма мне была знакома. В Рефале я увидел то же самое: то же сопоставление с образцом (как выбор конкретизации шаблона в Си++) и выбор действия в зависимости от результата сопоставления!
Но позже выяснился недостаток Рефала 5: он был замкнут. Компилятор генерил файлы интерпретируемого кода (который я недавно расшифровал методами обратной инженерии, это было занятно), которые затем выполняются интерпретатором. Рефал 5 предоставляет ограниченный набор встроенных функций: преимущественно это арифметика и консольный и файловый ввод-вывод. Расширить его другими возможностями без модификации компилятора и интерпретатора (что, кстати, запрещает лицензия), почти невозможно. Единственный способ — писать утилитки на Си и вызывать их функцией System, что явный костыль.
Пробовал я написать программу («монитор»), которая запускает Рефал 5, перехватывая себе потоки stdin и stdout. Можно, выводя из программы на Рефале специально помеченные строки, перехватывать их «монитором», обрабатывать как вызовы неких функций и писать в stdin. Программа на Рефале могла бы интерпретировать ввод с stdin как результат вызова внешней функции. Но, как оказалось, интерпретатор не сбрасывает поток и поэтому команды тупо не доходят. Когда я экспериментировал, я не знал, как писать в stderr (а пишется туда весьма неочевидным и недокументированным образом), а ведь он должен, по идее, не кэшироваться.
Аналогичным недостатком обладал и более продвинутый диалект Рефал 6. Его лицензия позволяет модифицировать исходники, но автор, похоже, забросил свой проект.
Рефал 2 лишён этого недостатка — у него весьма понятный и хорошо документированный интерфейс с Си, но реликтовый синтаксис самого Рефала не внушал желания на нём программировать.
Рефал Плюс имеет довольно продвинутый, но в то же время мудрёный синтаксис, имеющий кучи синтаксического сахара. Тогда я его не осилил, не осилил и теперь.
Поэтому я решил писать свой диалект.
Блекджек и шлюхи
Дело было в далёком 2007 году. Именно в тот год (на Старый Новый год) я заинтересовался Рефалом и первым диалектом, как уже было сказано, был Рефал 5. Понимая замкнутость языка, я сначала придумывал разные костыли (см. выше про stdin/stdout), но потом решил написать свой диалект. Примерно в это же время я купил и прочитал книжку Сергея Залмановича Свердлова «Языки программирования и методы трансляции», которая на меня оказала сильное влияние. Книга была написана убеждённым паскалистом, превознасящим Оберон, поэтому я решил взять этот самый Оберон за основу модульности языка. (Диалекты Рефал 2, Рефал 5 и Рефал 6 исповедуют модульность в стиле Си — чтобы использовать функцию, надо в одном модуле сделать её экспортируемой (типа, не static), в другом объявить директивой $EXTERN; диалект Рефал Плюс, исповедующий концепцию Модулы, я тогда не осилил.) Т.к. Рефал позиционируется как язык для символических вычислений: алгебраические выкладки, доказательства теорем, трансляторы искусственных и естественных языков и т.д., я решил писать самоприменимый компилятор.
Летом 2007 года я написал первую версию (0.1), которая компилировала код на Модульном Рефале в код на Рефале 5. Поскольку синтаксис и семантика управляющих конструкций Модульного Рефала уже, чем у Рефала 5, трансляция представляла собой просто переписывание кода с переименовыванием идентификаторов. Но на этой стадии уже производилась полная проверка исхнодного кода на синтаксические и семантические ошибки, обработка межмодульных связей, поиск всех зависимых модулей (в командной строке достаточно указать только головной) и их перекомпиляция по необходимости (как в make). Компиляция в Рефал 5 меня сильно не смущала, ведь у Страуструпа его компилятор (не препроцессор) cfront тоже компилировал Си++ в Си.
Дальше я постепенно улучшал имеющийся компилятор, добавляя в него новые фичи (указатели на функции, инициализация и финализация модулей и т.д.), рефакторизуя код (сначала в нём не было поддержки архитектуры с несколькими front-end'ами и back-end'ами) и тщательнее продумывая концепцию модулей (например, придумал объединять модули в пакеты). Параллельно я думал уже о компиляции в императивный язык. В результате летом 2008 года я за время отпуска написал ещё один компилятор — компилятор Простого Рефала.
Особенностью языка Простой Рефал была ориентация на компиляцию в Си++, в частности в нём нет продвинутой модульности, все функции перед их использованием должны быть объявлены или определены, ведь основной задачей было изучить компиляцию в императивный код (что для Рефала достаточно нетривиально).
Затем я прикрутил к Модульному Рефалу два новых back-end'а — один из них генерил код на Простом Рефале, второй был фактически куском самого Простого Рефала для компиляции в Си++.
Летом 2009 года я существенно переработал Простой Рефал, добавив к нему безымянные вложенные функции (или, как сказал бы лиспер, лямбда-функции) в стиле Рефала 7, что существенно повысило его юзабельность. Таким образом, Простой Рефал стал первым практически применимым компилятором Рефала со вложенными фукнциями (у Рефала 7 на тот момент был back-end в байт-код Java, который по-нормальному надо дорабатывать, на практике применять затруднительно). В Модульном Рефале они тоже рано или поздно появятся.
Этой зимой (2010 год) я за время зимних праздников очень качественно внутренне переработал библиотеку, а к лету вплотную приблизился к версии 0.2.
Версия 0.2 была завершена в середине октября. О том, что включает в себя компилятор, читайте в ближайших постах.
Комментариев нет:
Отправить комментарий