flowchart TD P[/"Программа P на языке L"/] I["Интерпретатор языка L"] D[/"Исходные данные X для P"/] R[/"P(X) - результат применения P к X"/] %% N:::hidden --> D %% linkStyle 0 display:none; P ---> I D --> I I --> R
История рефал-компилятора
С.А.Романенко
Институт прикладной математики им. М.В.Келдыша АН СССР
ноябрь 1976 г.
1. Почему началась разработка рефал-компилятора?
Работа над рефал-компилятором началась осенью 1969 года. Первоначально в ней принимали участие два человека: В.Ф.Турчин и С.А.Романенко (в то время студент 2-го курса). Разработка компилятора началась из-за неудовлетворенности рефал-интерпретатором (который был создан В.Ф.Турчиным, С.Н.Флоренцевым и В.Ю.Олюниным в 1967-1969гг) [1, 2].
Рефал-интерпретатор имел ряд недостатков. Некоторые из них были очевидны уже в 1969 году, в то время как другие были осознаны только в процессе работы над рефал-компилятором. Эти недостатки с нынешней точки зрения можно классифицировать следующим образом:
- невысокая скорость работы рефал-программ;
- расточительное расходование памяти под поле зрения;
- системные недостатки, вызванные низкой коммуникабельностью интерпретатора с внешним миром;
- недостатки входного языка.
В момент начала работы над компилятором были ясно осознаны только первые два недостатка: низкая скорость интерпретации и расточительное расходование памяти под обрабатываемую информацию. В конце концов, скорость работы удалось поднять в 2.5-5 раз. Что же касается экономии памяти, то фактически положение никак не изменилось с 1969 года. Представление информации в поле зрения то же самое, что было у рефал-интерпретатора.
В докладе [3] обсуждался некий метод автоматического выталкивания информации из поля зрения на внешние устройства, однако не было сделано никаких шагов для его практического воплощения.
Впоследствии нечто в таком роде реализовал Л.Ф.Лебедев в рефал-интерпретаторе для М-220 [6].
2. Чем отличается рефал-компилятор от рефал-интерпретатора.
Известно, что языки программирования можно реализовывать как с помощью компиляторов, так и с помощью интерпретаторов. Пусть у нас есть язык L. Тогда интерпретатор - это программа, которая берет программу P на языке L, берет исходные данные X для программы P и вырабатывает P(X) = I(P,X) - результат применения интерпретатора I к программе P и исходным данным X.
Теперь, пусть у нас имеется компилятор C с языка L на язык L₀, то есть программа, которая текст на языке L преобразует в текст на языке L₀: P₀ = C(P).
flowchart TD P[/"Программа P на языке L"/] C["Компилятор"] P0[/"Программа P₀ на языке L₀"/] P --> C C --> P0
Ясно, что нас интересует не сам перевод P с языка L на L₀, а результат применения программы P к исходным данным X . Чтобы получить его, все равно нужен интерпретатор, на сей раз - интерпретатор I₀ для языка L₀. Тогда результат счета получается как
P(X) = I₀ (P₀, X) = I₀(C(P), X)Таким образом, имеем следующую схему:
flowchart TD P[/"Программа P на L"/] C["Компилятор C"] CP[/"Программа C(P) на L₀"/] I["Интерпретатор I₀"] D[/"Исходные данные X"/] R[/"Результат применения P к X"/] P --> C C --> CP CP --> I D --> I I --> R
Видно, что без интерпретатора обойтись невозможно. Сколько ни компилируй с языка на язык - все равно, рано или поздно наступит время выполнить программу, ибо иначе вся предыдущая деятельность теряет смысл. А выполнить программу может, по определению, только интерпретатор.
Компиляторы обычно реализуются программным путем. Интерпретаторы иногда реализуются аппаратно, а иногда - программно. Лучший способ реализации интерпретатора с точки зрения скорости вычисления I₀(P₀, X) - аппаратный, однако он же и самый дорогой, ибо для каждого языка L₀, реализуемого интерпретатором, придется паять особую машину.
Каждый компьютер представляет собой интерпретатор некоего языка, который обычно называют системой команд этого компьютера. Обычно компиляторы переводят программы в команды компьютера. Тем самым, используется интерпретатор, реализованный аппаратно.
Если нам нужен интерпретатор языка L₀, а под рукой нет подходящего компьютера, можно реализовать интерпретатор программным путем. Работать он будет сравнительно медленно.
При реализации фортрана, в качестве интерпретатора можно выбрать почти любой компьютер. Это понятно, ибо фортран предназначен для обработки числовой информации. Большинство же компьютеров имеют подходящую для таких задач систему команд.
Другое дело - реализация рефала. Тут требуются совершенно другие операции: синтаксическое отождествление, подстановка. Большинство компьютеров не предназначены для выполнения таких действий. Поэтому нужно либо изготавливать особый компьютер, либо реализовать нужный интерпретатор программным путем.
Отсюда видно, в чем состояла специфика работы над рефал-компилятором, по сравнению с компилятором с фортрана. Когда нужно сделать компилятор с фортрана, то язык L₀ и его интерпретатор уже заданы заранее: это некий компьютер с некоторой системой команд. Когда же началась работа над рефал-компилятором, еще не было ни языка L₀, ни его интерпретатора. Поэтому нужно было создать сразу и L₀, и C, и I₀ . Мы говорим, что работа велась над рефал-компилятором, чтобы противопоставить ее ранее сделанному рефал-интерпретатору. В действительности же, сущность работы заключалась в разработке языка L₀. Если нет L₀, то нельзя разработать ни C, ни I₀. Если L₀ выбрать неудачно, то плохими окажутся и C, и I₀.
В дальнейшем C будет называться рефал-компилятором, L₀ - языком сборки рефала (refal assembly language), I₀ - интерпретатором языка сборки.
Получаем следующую схему:
flowchart TD P[/"Программа на рефале"/] C["Компилятор с рефала на язык сборки"] CP[/"Программа на языке сборки"/] I["Интерпретатор языка сборки"] D[/"Исходное поле зрения"/] R[/"Результат работы программы"/] P --> C C --> CP CP --> I D --> I I --> R
Полезно сравнить это с рефал-интерпретатором. Интерпретатор, описанный в [1, 2], состоит из двух основных блоков: процессора и препроцессора. Препроцессор производит предварительный анализ рефал-предложений: определяет порядок отождествления, классифицирует переменные выражений на открытые и закрытые, заменяет индексы переменных на адреса, указывающие на отведенные для них места в таблицах и т.д. Таким образом, препроцессор переводит исходные предложения рефала на некоторый особый, внутренний язык, который затем непосредственно интерпретируется процессором. Таким образом, общая структура интерпретатора такова:
flowchart TD P[/"Программа на рефале"/] C["Препроцессор"] CP[/"Программа во внутреннем представлении"/] I["Процессор"] D[/"Исходное поле зрения"/] R[/"Результат работы программы"/] P --> C C --> CP CP --> I D --> I I --> R
Сразу же бросается в глаза поразительное сходство между внутренней структурой интерпретатора и схемой реализации рефала на основе компиляции. Препроцессор - это фактически компилятор, который переводит предложения с рефала во “внутреннее представление”. Процессор - это “чистый” интерпретатор, который интерпретирует программы “во внутреннем представлении”.
Этот пример лишний раз показывает условность всяческих классификаций. На практике редкий интерпретатор обходится без того, чтобы подвергнуть исходную программу некоторой перекодировке. Даже когда мы вызываем программы, написанные в командах машины, дело не обходится без элементов компиляции. В самом деле, во всех развитых операционных системах готовые к исполнению программы хранятся в виде загрузочных модулей. Загрузочный модуль непосредственно выполнить нельзя. Предварительно его надо “загрузить” посредством загрузчика, который “настраивает” программу на те адреса, на которых она будет выполняться. Загрузчик - это типичный компилятор, который переводит программу с “языка загрузочного модуля” в “абсолютную программу”.
Когда же языки реализуются с помощью компиляторов, то и здесь дело редко обходится без элементов интерпретации. Так, например, компиляторы с фортрана оставляют операторы FORMAT в исходном виде. Затем форматы интерпретируются особыми подпрограммами во время исполнения программы. А о компиляторах с кобола и говорить нечего.
Из сказанного видно, что разница между реализациями языков на основе интерпретации и компиляции носит скорее количественный характер. Пропорция между интерпретацией и компиляцией может меняться в широких пределах.
Почему же реализация рефала, описанная в [1, 2], называется рефал-интерпретатором? Согласно [2], процессор и препроцессор рефал-интерпретатора были написаны в кодах машины БЭСМ-6 и занимали:
процессор - 100008 слов
препроцессор - 40008 слов.
В глаза сразу же бросается явное преобладание процессора над препроцессором. Это указывает на то, что исходная программа на рефале подвергается не очень значительной переработке препроцессором, зато во время выполнения программы процессор выполняет довольно сложный анализ применяемых предложений.
При реализации рефала на основе компиляции, рефал-компилятор должен проделывать достаточно сложный анализ программы, пытаться ее оптимизировать. За счет этого можно максимально упростить язык сборки, а значит - и интерпретатор языка сборки.
Язык сборки должен адекватно отражать особенности рефала и компилятора с рефала. В то же время он не обязан отражать особенности конкретных компьютеров. Нужно было постараться сделать язык сборки достаточно простым, чтобы интерпретатор языка сборки относительно легко поддавался программной и аппаратной реализации.
3. Этапы изготовления рефал-компилятоpа.
Исходя из всех перечисленных соображений, В.Ф.Турчин разработал следующую технологию изготовления рефал-компилятора.
Разрабатывается машинно-независимый язык сборки. Программным путем реализуется интерпретатор языка сборки для машины БЭСМ-6.
На рефале пишется простейший компилятор с рефала на язык сборки. Этот компилятор отлаживается с помощью рефал-интерпретатора.
Рефал-компилятор компилирует сам себя на язык сборки. В этот момент он работает с помощью рефал-интерпретатора. Получается рефал-компилятор на языке сборки, который может работать на БЭСМ-6 без рефал-интерпретатора с помощью интерпретатора языка сборки. Теперь рефал-интерпретатор больше не нужен.
Пишется на рефале сложный, оптимизирующий компилятор с рефала на язык сборки. Его будем называть “большим компилятором”, в отличие от простейшего компилятора, который мы будем называть “малым компилятором”. Большой компилятор отлаживается с помощью малого компилятора и интерпретатора языка сборки.
Большой компилятор переводится на язык сборки с помощью малого. Получается оптимизирующий, но сам не оптимизированный компилятор на языке сборки.
Большой компилятор компилирует сам себя на язык сборки. Получается оптимизирующий и сам оптимизированный компилятор с рефала на язык сборки, который сам - на языке сборки.
С этого момента работа по созданию рефал-компилятора для БЭСМ-6 закончена. Мы получили компилятор на языке сборки, а язык сборки - машинно-независимый. Следовательно, мы получили компилятор в машинно-независимом виде.
Однако, для его работы необходим интерпретатор языка сборки. Поэтому, чтобы перенести компилятор на другие машины - необходимо для каждой из них написать свой интерпретатор языка сборки. Это относительно легкая задача, ибо интерпретатор языка сборки значительно проще, чем компилятор с рефала. Кроме того, интерпретатор языка сборки можно написать на каком-либо машинно-независимом языке программирования: АЛМО [16], PL/I [15] и т.д. В этом случае получается полностью машинно-независимая реализация рефала.
Затем могут появиться аппаратные реализации интерпретатора языка сборки, для которых будет использоваться разработанный компилятор с рефала на язык сборки.
Этот проект опирался на использование рефал-интерпретатора, однако без интерпретатора можно было и обойтись. Для этого малый компилятор, написанный на рефале, можно было бы вручную перевести на язык сборки и отладить на интерпретаторе языка сборки. Однако для этого нужно заранее зафиксировать язык сборки и не менять его во время отладки компилятора, поэтому наличие рефал-интерпретатора облегчало работу.
4. Первые успехи на БЭСМ-6.
В.Ф.Турчин разработал первоначальный вариант языка сборки и написал на рефале основную часть компилятора. С.А.Романенко разработал и написал на автокоде БЕМШ интерпретатор языка сборки для БЭСМ-6.
Затем С.А.Романенко начал отладку интерпретатора языка сборки, а также рефал-компилятора, пользуясь рефал-интерпретатором. Тесты для интерпретатора языка сборки составлялись вручную.
Уже 15 ноября 1969 года заработал первый простенький тест на языке сборки, который являлся переводом следующих предложений:
§k'ПОВТС'() e₁ ~ k'П' e₁. k'ДУБ' e₁.
§k'ПОВТС'(eᵣ*) e₁ ~ k'ПОВТС'(eᵣ) e₁ e₁.
§k'ДУБ' e₁ e₁ ~ k'ДУБ' e₁.
§k'ДУБ' s₁ ~ k'П' s₁ ДУБА ДАЛ.В начальное поле зрения заносилось выражение:
\(\texttt{§k'ПОВТС'(}\underbrace{** \ldots *}_{\mbox{n-раз}}\texttt{) 𝓔₀ .}\)
Чтобы отладить компилятор, потребовалось гораздо больше времени. Так получилось из-за того, что во время отладки происходила переработка языка сборки, компилятора и интерпретатора языка сборки.
Возникали новые идеи, вскрывались ошибки и противоречия, допущенные при первоначальной разработке. Компилятор сначала работал чудовищно медленно, умудряясь тратить на одно предложение рефала до 45 секунд. Внезапно обнаружилось, что пустые значения переменных обрабатываются неверно в процессе замены левой части предложения на правую.
Все это привело к тому, что в процессе отладки “на ходу” менялся язык сборки и его интерпретатор, переписывались заново различные части компилятора.
Наконец, 27 октября 1970 года была скомпилирована и запущена на счет первая программа объемом в 100 предложений. Компиляция была произведена посредством рефал-компилятора, который работал с помощью рефал-интерпретатора.
После этого нужно было прокомпилировать компилятор на самом себе и избавиться от рефал-интерпретатора! На это потребовался еще целый месяц. Наконец, к концу ноября 1970 года, заработал компилятор на языке сборки, уже независимый от рефал-интерпретатора.
Процесс получения готовой к исполнению программы посредством этого компилятора выглядел так.
Сначала вызывается рефал-компилятор. На вход ему подается программа на рефале. Он переводит ее на язык сборки. Однако, язык сборки нужно представить в таком виде, чтобы его “понял” интерпретатор языка сборки. Поэтому программа на языке сборки превращается в набор констант на автокоде БЕМШ. Таким образом, конечным продуктом рефал-компилятора является модуль на автокоде БЕМШ.
После этого вызывается транслятор с автокода и автокодный модуль превращается в объектный модуль.
Затем вызывается редактор связей, который объединяет этот объектный модуль с другими объектными модулями: интерпретатором языка сборки и стандартными функциями (“машинными процедурами”). Только после этого получается готовая к исполнению программа.
flowchart TD classDef data fill:beige; MR[/"Модуль на рефале"/] %% class MR data; RC["Рефал-компилятор"] MA[/"Модуль на автокоде"/] %% class MA data; AT["Транслятор с автокода"] MO[/"Объектный модуль"/] %% class MO data; I[/"Интерпретатор языка сборки"/] %% class I data; LK["Редактор связей"] F[/"Стандартные функции"/] %% class F data; R[/"Готовая программа"/] %% class R data; MR --> RC --> MA --> AT --> MO I & MO & F --> LK --> R
Практически это выглядело так: сначала с перфокарт вводилась рефал-программа, и запускался рефал-компилятор. Результат его работы (модуль на автокоде) записывался на магнитную ленту. Нужно было подождать, пока проработает рефал-компилятор и убедиться, что он успешно закончил работу. Затем с помощью другой колоды перфокарт вызывался транслятор с автокода. Он записывал объектный модуль на магнитную ленту. Дождавшись конца его работы, нужно было взять третью колоду перфокарт и запустить редактор связей. Он записывал готовую программу на магнитную ленту. После этого нужно было взять четвертую колоду перфокарт и смело запускать на счет готовую рефал-программу.
А как работали тогда с рефал-интерпретатором? Чтобы пропустить через него задачу, достаточно было взять рефал-программу на перфокартах, подложить к ней исходные данные, карты для вызова интерпретатора и все это один раз ввести в машину. А для рефал-компилятора необходимо было последовательно запустить с перфокарт четыре задачи.
Ясно, что в таком виде рефал-компилятор никуда не годился. Хоть он и работал “в принципе”, через него очень трудно было пропустить даже отлаженную программу, а об отладке и говорить нечего!
Причина такого прискорбного состояния дел крылась в том, что рефал-компилятор гораздо теснее связан с операционной системой, чем рефал-интерпретатор. Он использовал и транслятор с автокода, и редактор связей. Видимо, такова судьба большинства компиляторов. Интерпретатор получает на входе все необходимые данные и сразу вырабатывает окончательный продукт. Результат же работы компилятора самостоятельной ценности не имеет. Его еще требуется соединить с исходными данными и вызвать. А это требует, чтобы компилятор работал в соответствующей “среде”.
Итак, в ноябре 1970 года, когда рефал-компилятор заработал, неожиданно оказалось, что впереди еще много работы системного характера. На БЭСМ-6 в то время не было ни языка управления заданиями, ни управления данными. Поэтому в ноябре-декабре 1970 года Ан.В.Климов и С.А.Романенко занялись разработкой монитора “БОСС” для БЭСМ-6. Это был проект специализированного монитора, предназначенного для работы с рефал-программами. Основная его задача была - создать нужную среду для рефал-компилятора.
Этот проект остался только на бумаге, однако работа была проделана не зря: самые серьезные ошибки и нелепые решения, сделанные во время работы над “БОССом”, уже не повторились впоследствии при разработке мониторов “Рефал” для БЭСМ-6 [7] и “Секач” для МИНСК-32 [10].
В это время вмешательство А.И.Илюшина резко изменило направление работы, в результате чего все работы на БЭСМ-6 временно приостановились.
5. Переход на ЕС ЭВМ.
А.И.Илюшин предложил перенести рефал-компилятор с БЭСМ-6 на машины серии ЕС ЭВМ.
В январе-феврале 1971 года Ан.В.Климов (тогда студент 2-го курса МГУ) написал интерпретатор языка сборки для ЕС ЭВМ. В марте 1971 года он передал его для отладки Е.В.Травкиной через А.И. Илюшина (С.А.Романенко и Ан.В.Климов в то время доступа к ЕС ЭВМ не имели). В мае 1971 года состоялся семинар в МИФИ, на котором встретились все те, кто в дальнейшем принимал участие в работах на ЕС ЭВМ. Тогда же Ан.В.Климов внес в рефал-компилятор необходимые изменения, скомпилировал его на БЭСМ-6 и выдал на перфокарты в виде констант ассемблера ЕС ЭВМ. В таком виде компилятор был передан И.Б.Щенкову.
Летом 1971 года Е.В.Травкина занималась отладкой интерпретатора языка сборки, а И.Б.Щенков осваивал ЕС ЭВМ и вел подготовку к запуску компилятора.
В октябре 1971 года рефал-компилятор на ЕС ЭВМ заработал.
6. Новый язык сборки и компилятор.
В это время С.А.Романенко занимался разработкой нового, усовершенствованного (по его мнению) варианта языка сборки и соответствующего ему компилятора. Изменения затронули, в основном, операторы, производящие синтаксическое отождествление. Новые операторы позволяли реализовать более совершенный алгоритм отождествления.
Этот вариант языка сборки и методы компиляции на него были изложены в [4]. После этого язык сборки стабилизировался и уже не претерпел заметных изменений. Этот его вариант и поныне (ноябрь 1976 года) используется во всех компиляторах с рефала для машин БЭСМ-6, ЕС ЭВМ, М-220 и МИНСК-32.
В октябре 1971 года С.А.Романенко передал Е.В.Травкиной описание нового языка сборки. В течение двух недель она написала и отладила новый интерпретатор языка сборки, включая средства отладки (пошаговую прокрутку).
В ноябре 1971 года С.А.Романенко передал Е.В.Травкиной новый компилятор, написанный на рефале. Это был малый, неоптимизирующий компилятор, объемом приблизительно в 70 предложений. Е.В.Травкина перевела его вручную на язык сборки и отладила. Эта работа, включая перфорацию, заняла шесть дней.
В декабре 1971-январе 1972 г. Е.В.Травкина написала на ассемблере недостающие части компилятора: входную и выходную перекодировку, блок синтаксического контроля.
Таким образом, первый, годный к практическому употреблению, рефал-компилятор появился на ЕС ЭВМ в январе 1972 года. Работа по его непосредственному изготовлению заняла 4 месяца. В ней участвовали два человека.
Такая высокая скорость работы объясняется следующими причинами:
имелось большое количество машинного времени;
уже был опыт изготовления предыдущей версии компилятора на БЭСМ-6 и переноса его на ЕС ЭВМ;
на ЕС ЭВМ имелась мощная операционная система ОС ЕС, поэтому не пришлось тратить силы на системную работу, не имеющую прямого отношения к компилятору;
в работе участвовало только два человека, между которыми отсутствовали идейные разногласия. Применялись “лобовые” методы работы (ручная компиляция на язык сборки), гарантировавшие быстрое получение результата.
7. Переход на метакод-Б. Символы-числа.
В процессе работы над второй версией компилятора на ЕС ЭВМ по предложению А.И.Илюшина был произведен переход на новое представление рефал-программ на перфокартах. Это представление получило название “метакод-Б” [7], в отличие от старого “метакода-А”, которым пользовался рефал-интерпретатор.
Метакод-Б использует только самые распространенные литеры, которые имеются практически на всех перфораторах, принтерах, терминалах. В метакод-Б были введены изобразительные средства, служащие для разбиения рефал-программ на модули и обеспечивающие связь между модулями.
Тогда же в язык были введены символы-числа и разделение составных символов на два класса: символы-метки и символы-числа.
С точки зрения рефал-интерпретатора, составным символом являлась произвольная цепочка объектных знаков, не содержащая апострофов и заключенная в апострофы. Например:
'В ЛЕСУ РОДИЛАСЬ ЕЛОЧКА. В ЛЕСУ…’
'123'
'А+Б-В'В рефал-компиляторе допускаются составные символы двух типов. Символ-метка - это идентификатор в апострофах. Например:
'пси'
'ФУНКЦ2'Этот идентификатор рассматривается как имя некоторой функции. При трансляции с рефала на автокод он непосредственно переходит в метку автокода. Если рефал-компилятор не использует автокод, а непосредственно вырабатывает объектный модуль, он сам создает таблицу меток, в которой хранит информацию о символах-метках.
Символ-число - это целое неотрицательное число, заключенное в апострофы. Например:
'1024'
'0'Это число не может быть сколь угодно большим. Для каждой реализации указывается максимальный допустимый символ-число. Для БЭСМ-6 это '32767' (215-1). По этой причине символы-числа были также названы макроцифрами.
В рефал-интерпретаторе макроцифр не было. Поэтому каждое целое число приходилось изображать как последовательность объектных знаков-цифр. Например:
32767Здесь пришлось потратить пять объектных знаков: 3,2,7,6,7. Изображение этого числа в виде макроцифры снижает расход памяти на его хранение в пять раз и повышает скорость обработки.
Макроцифры были использованы во второй версии рефал-компилятора. Было улучшено внутреннее представление обрабатываемых предложений рефала и операторов языка сборки. Так, например, то, что в первой версии изображалось как
(TPL,25,36)стало изображаться как
('TPL' '25' '36')То, что в прежнем представлении занимало 11 слов, в новом представлении заняло 5 слов.
8. Оптимизирующий компилятор.
В январе-феврале 1972 года С.А.Романенко написал на рефале большой, оптимизирующий компилятор с рефала. Он отлаживался на ЕС ЭВМ с помощью малого компилятора в феврале-марте 1972 года.
Затем, отлаженный большой компилятор был скомпилирован сам на себе.
Большой компилятор делал следующие оптимизации программы на языке сборки:
- оптимизация удлинений открытых переменных (см. [5]);
- оптимизация замены левой части на правую;
- создание дерева из левых частей предложений (в пределах одной функции), чтобы операторы, общие для нескольких предложений, выполнялись только один раз.
Эти оптимизации описаны в [4].
Чтобы проделать оптимизации 1 и 2, достаточно провести анализ отдельного предложения, вне связи с остальными предложениями. Оптимизация 3 требует уже совместного анализа нескольких предложений, входящих в одну и ту же функцию. Но связи различных функций между собой не учитываются. Чтобы увеличить глубину компиляции, нужно делать глобальный анализ всей программы. Этого существующий рефал-компилятор не делает.
В дальнейшем производилось сравнение большого и малого компиляторов.
На БЭСМ-6 оказалось, что скорость компиляции у малого компилятора в 1.36 раз больше, чем у большого. Зато объем скомпилированной программы больше для малого компилятора в 1.17 раз, а время ее работы в 1.5 раз больше.
Для М-220 скорость компиляции отличается в 6-7 раз, время работы в 1.6-2.5 раз, а размер программа в 1.15-1.20 раз.
9. Вновь на БЭСМ-6. Мониторная система “Рефал”.
Весной 1972 года возобновилась работа на. БЭСМ-6. В апреле 1972 года Ан.В.Климов написал интерпретатор нового языка сборки для БЭСМ-6. Он был отлажен за две с половиной недели.
В мае 1972 года Ан.В.Климов разработал монитор “Рефал” для БЭСМ-6 [7], который был отлажен в июне 1972 года.
Хотя монитор “Рефал” разрабатывался для того, чтобы пропускать рефал-программы, он по существу не содержал в себе ничего специфического, особо предназначенного для рефала. Он имел много общего с DOS/360, хотя устроен был гораздо проще.
Кроме монитора в состав мониторной системы “Рефал” вошли: компилятор с рефала, транслятор с автокода БЕМШ, редактор связей, редактор файлов (update) и несколько утилит для обслуживания библиотек. Автокод БЕМШ и редактор связей были взяты в готовом виде, для чего пришлось написать для них новые головные программы.
Развитие мониторной системы “Рефал” происходило постепенно.
К ноябрю 1972 года в нее были включены автокод БЕМШ, редактор связей и рефал-компилятор. Это был необходимый минимум, чтобы обеспечить работу рефал-компилятора.
Таким образом, можно считать, что на БЭСМ-6 первый пригодный к практическому употреблению рефал-компилятор появился в ноябре 1972 года.
В первой половине 1973 года продолжалась работа по развитию мониторной системы “Рефал”. Были написаны различные утилиты, а также ряд машинных процедур для рефала.
Над мониторной системой “Рефал” работали Ан.В.Климов и Е.В.Травкина.
10. Недостатки мониторной системы “Рефал”. Символы-ссылки.
Эксплуатация компилятора и мониторной системы “Рефал” показала, что они не свободны от ряда недостатков.
При создании мониторной системы “Рефал” предполагалось, что все библиотеки будут располагаться на дисках. Между тем, оказалось, что на многих БЭСМ-6 дисков нет. Мониторная система “Рефал” могла работать и с лентой, но при этом много времени уходило на перемотку ленты. Время прохождения задачи через машину резко возрастало, на что жаловались пользователи.
Другие недостатки носили более принципиальный характер и касались связи рефал-программ с внешним миром.
Многие приложения рефала связаны с его использованием в качестве универсального макропроцессора и языка для написания компиляторов. В таких приложениях результат работы рефал-программы самостоятельной ценности не имеет и должен проходить дальнейшую обработку. Пусть, например, рефал-программа порождает программы на фортране. А как их использовать? Ведь в мониторной системе “Рефал” не было компилятора с фортрана. Приходилось выдавать фортран-программу на перфокарты и дальше работать с ней в рамках мониторной системы “Дубна”. Это мало кого устраивало. Таким образом, недостатком было уже наличие собственного монитора, замкнутого в себе.
Другой недостаток заключался в том, что из рефал-программы нельзя было вызывать программы на других языках. Большинство задач, в которых может применяться обработка символьной информации, не могут сводиться только к ней. Например, в интерактивной системе рефал может успешно применяться для первичной обработки сообщений, поступающих с терминала, а также для преобразования сообщений, выдаваемых системой в “человеческий” вид. Ясно, что рефал-программа может проанализировать и “понять” запрос, поступивший с терминала, а чтобы выполнить его, она, как правило, должна вызывать программы, написанные на других языках.
Еще один недостаток был связан с самим языком рефал.
Любая информация, обрабатываемая рефал-программой, должна быть представлена в виде рефал-выражения, которое представляет из себя дерево (хотя и не обязательно бинарное, как в языке ЛИСП). Во многих задачах обработки символьной информации приходится иметь дело со структурами более общего вида, то есть более или менее сложными графами. Граф можно изобразить с помощью рефал-выражения, но при этом при его обработке неизбежно придется использовать ассоциативные поиски. Это снижает эффективность алгоритма, и усложняет его. Пример такой задачи см. в [11]. Следует заметить, что при представлении любых данных на перфокартах их неизбежно приходится изображать в виде линейной последовательности знаков. Однако, после того как данные введены в машину, их можно преобразовать во внутреннее представление, которое может быть самым различным и зависит в основном от того, какие операции мы намерены производить над данными [12]. Ясно, что максимальную свободу в выборе представления для данных мы имеем при программировании в командах машины. Если мы используем какой-то язык программирования, то уже должны смириться с некоторыми ограничениями, ибо каждый язык навязывает нам свою систему понятий и предлагает свои способы описания данных и операций над ними. Рефал не представляет в этом смысле исключения. Он предлагает программисту мыслить в терминах выражений. Чтобы ослабить это ограничение, есть два выхода:
- разрешить вызывать из программ на рефале программы на других языках;
- расширить класс данных, которые может обрабатывать рефал-программа.
Эти два способа не противоречат друг другу и могут мирно сосуществовать.
Чтобы облегчить обработку графов на рефале, С.А.Романенко предложил ввести в рефал в дополнение к символам-меткам и символам-числам, символы нового типа: символы-ссылки.
Каждый символ-ссылка [8] ссылается на некоторый объект, именуемый “ящиком”. Несколько символов-ссылок могут ссылаться на один и тот же ящик. Каждый ящик может содержать произвольное выражение. Если у нас есть ссылка на ящик, мы можем извлечь его содержимое или положить в него любое выражение. Таким образом, появляется возможность естественным способом изображать графы и обрабатывать их без применения ассоциативных поисков.
11. Переход в мониторную систему “Дубна”.
Зимой 1974 года С.А.Романенко и Ан.В.Климов пришли к выводу, что следует перенести рефал-компилятор в широко распространенную на БЭСМ-6 мониторную систему “Дубна”. Одновременно было решено улучшить внутреннюю структуру интерпретатора языка сборки и системы отладки. Раньше они составляли единое, монолитное целое. Было решено разбить их на отдельные подпрограммы, которые бы вызывались по соглашению о связях, принятому в мониторной системе “Дубна”. Был разработан способ связи между рефал-программой и фортран-программой, который позволяет осуществить их глубокое взаимодействие и полный контроль над рефал-программой со стороны фортран-программы [9]. При этом рефал-программа выступает по отношению к фортран-программе как полусопрограмма, которая при каждом обращении к ней продвигается на заданное число шагов [9].
Было решено ввести в рефал символы-ссылки [8]. Это потребовало предусмотреть в реализации рефала аппарат для сборки мусора. Возможность сборки мусора пришлось учесть при реализации многих операторов языка сборки и в стандартных функциях (машинных процедурах).
Работы по переходу в мониторную систему “Дубна” начались в марте 1974 года. В них принимали участие С.А.Романенко, Ан.В.Климов, Л.В.Проворов и Е.В.Травкина. Работа была, в основном, проделана за два месяца. Такую высокую скорость работы, несмотря на большое число участников, следует отнести за счет того, что были приняты меры, чтобы расчленить рефал-систему на слабо взаимодействующие части со стандартными интерфейсами. Благодаря этому удалось избежать впадения в логические ошибки и противоречия, столь часто возникающие в системном программировании из-за взаимного недопонимания между участниками работы.
Переход в мониторную систему “Дубна” имел следствием гибель мониторной системы “Рефал”, в которую было вложено много умственных и физических сил. Однако, сохранение и развитие мониторной системы “Рефал” привело бы в будущем к бессмысленному, постоянному поглощению человеческого труда.
Лучше ужасный конец, чем ужас без конца!
12. Рефал-компилятор на языке АСТРА.
Многие пользователи рефала в мониторной системе “Дубна” жаловались на низкую скорость компиляции с рефала. В связи с этим С.А.Романенко решил изготовить новый компилятор с рефала, значительно повысив скорость компиляции и не слишком ухудшив получающиеся при этом программы.
Было решено написать компилятор на языке АСТРА [13, 14]. При этом оказалось, что некоторые оптимизации, которые делал большой компилятор, легко запрограммировать на языке АСТРА, в то время как программирование других, хотя и вполне возможно, но потребует сравнительно большой работы. Исходя из этого было решено не делать оптимизацию замены левой части предложения на правую и построение дерева из левых частей предложений функции. Эти оптимизации требуют накопления в памяти как рефал-предложений, так и сгенерированной программы на языке сборки. Это потребовало бы использования динамического распределения памяти. В то же время оптимизация удлинений открытых переменных не составляла труда, ибо для нее достаточно удерживать в памяти лишь левую часть очередного предложения.
Работа по написанию и отладке компилятора была начата С.А.Романенко в мае 1976 года и заняла 4 месяца.
Объем получившегося компилятора - 2300 предложений на языке АСТРА. Скорость компиляции по сравнению с прежним компилятором возросла в 40-45 раз и составляет примерно 100 рефал-предложений в секунду (без печати листинга). Скомпилированная программа занимает на 5% меньше памяти, чем при использовании прежнего компилятора, однако скорость ее работы на 15% меньше.
Язык АСТРА позволяет использовать все особенности машины БЭСМ-6 и получать эффективные программы. В то же время он сокращает размер программ по сравнению с программированием на автокоде в 5-6 раз и примерно во столько же раз труд по их написанию. Описательная часть программы отделяется от исполнительной, что позволяет резко облегчить переделку программ и повышает их читабельность.
13. Компилятор для МИНСК-32.
Осенью 1972 года началась работа по переносу рефал-компилятора на МИНСК-32. Первые же выходы на МИНСК-32 показали, что в стандартной операционной системе для МИНСК-32 не предусмотрены язык управления заданиями и управление данными. Это не сулило ничего хорошего, так как стало ясно, что придется делать много системной работы, не имеющей прямого отношения к рефал-компилятору.
В октябре 1972 года С.А.Романенко написал и отладил монитор “Секач” для МИНСК-32 [10]. В дальнейшем монитор “Секач” совершенствовался, разрастался и получил довольно широкое распространение вне связи с рефалом. Его развитием занимались М.Р.Ковтун, Арк.В.Климов и В.Л.Кистлеров. Эта работа включала в себя написание различных утилит и переделку головных программ ряда стандартных трансляторов, поставляемых вместе с операционной системой МИНСК-32.
Непосредственной работой над рефал-компилятором занимался, главным образом, Арк.В.Климов. Работа была закончена весной 1975г.
Литература.
С.Н.Флоренцев, В.Ю.Олюнин, В.Ф.Турчин. Рефал-интерпретатор. Доклады 1-й Всесоюзной конференции по программированию. Киев, 1968.
С.Н.Флоренцев, В.Ю.Олюнин, В.Ф.Турчин. Эффективный интерпретатор для языка РЕФАЛ. Препринт ИПМ АН СССР, М., 1969.
С.А.Романенко, В.Ф.Турчин. Рефал-компилятор. Доклады 2-й Всесоюзной конференции по программированию. Новосибирск, 1970.
Ан.В.Климов, С.А.Романенко, В.Ф.Турчин. Компилятор с языка РЕФАЛ. ИПМ АН СССР, М., 1972.
С.А.Романенко, Ан.В.Климов, В.Ф.Турчин. Теоретические основы синтаксического отождествления в языке РЕФАЛ. Препринт ИПМ АН СССР, М., 1973.
О.Ф.Бобкова, И.Н.Кузнецова, Л.Ф.Лебедев, Л.И.Лунева, Э.И.Макарова, Г.П.Хвостунова. Реализация рефал-интерпретатора на ЭВМ М-220. В сб. “Языки программирования и методы их реализации”. Киев, 1973.
Ан.В.Климов, С.А.Романенко, Е.В.Травкина. Инструкция по работе с мониторной системой “Рефал” для БЭСМ-6. ИПМ АН СССР, М., 1974.
Ан.В.Климов, Л.В.Проворов , С.А.Романенко, Е.В.Травкина. Рефал в мониторной системе “Дубна” БЭСМ-6. Входной язык компилятора и запуск программ. Препринт ИПМ АН СССР, М., 1975.
Ан.В.Климов, С.А.Романенко. Рефал в мониторной системе “Дубна”. Интерфейс рефала и фортрана. ИПМ АН СССР, М., 1975.
С.А.Романенко, М.Р.Ковтун, Арк.В.Климов, В.Л.Кистлеров. Мониторная система “СЕКАЧ” (описание и инструкция по использованию). М., ЦНИПИАСС,1976.
Н.Г.Арсентьева, Э.К.Янова. Опыт программирования одной лингвистической задачи на языке рефал. Препринт ИПМ АН СССР. М., 1976.
Д.Кнут. Искусство программирования для ЭВМ. T.1. Основные алгоритмы. М., “Мир”, 1976.
В.М.Михелев, В.Ю.Вершубский. АСТРА - язык для записи Алгоритмов Системного программирования и ТРАНСЛЯЦИИ. Препринт ИПМ АН СССР, М., 1974.
В.М.Михелев, В.Ю.Вершубский. АСТРА. Новые возможности языка. Препринт ИПМ АН СССР, М., 1976.
В.В.Богданов, Е.А.Ермаков, А.В. Маклаков. Программирование на языке АЛМО. М., “Статистика”, 1976.