02.04. РОЖДЕННЫЙ ПОЛЗАТЬ ПОЛУЧИЛ ПРИКАЗ ЛЕТАТЬ

ЧЕТВЕРТАЯ ГЛАВА. РОЖДЕННЫЙ ПОЛЗАТЬ ПОЛУЧИЛ ПРИКАЗ ЛЕТАТЬ

ЗАДАЧА 1 ("ПРАВИЛА"). ЭТАП 3 ("FORTH")

Забавно, как FORTH сам собой появляется там, где хотят решить задачу постепенно.

С.Б.РУДНЕВ, В.А.ЧЕТВЕРНИН
ПЕРЕНОСИМАЯ РАБОЧАЯ СМЕСЬ - ЯДРО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПЕРСОНАЛЬНОЙ ЭВМ
Персональные ЭВМ в задачах информатики. Новосибирск: ВЦ СОАН. 1984. С.58-72.

ВВЕДЕНИЕ

В работе [1] было определено предварительное понятие "рабочая смесь". Настоящая статья посвящена уточнению этого понятия и описание основных механизмов, лежащих в основе функционирования рабочей смеси.

Напомним, что в рабочей смеси существует несколько процессоров как аппаратных, так и программных (интерпретаторов), "выполняющих" программные отрезки, каждый из которых реализован объектным кодом соответствующего процессора системы. Программные отрезки, которые в дальнейшем, следуя терминологии статьи [1], будем называть также рабочими отрезками фактически представляют собой некоторый функциональный эквивалент подпрограмм и процедур в обычных языках программирования. Отход от обычной терминология вызван тем, что термины "подпрограмма" и "процедура" в значительной степени нагружены смыслом, который, по мнении авторов, может затенить основные принципы функционирования рабочей смеси.

Совокупность рабочих отрезков представляет собой ту программную обстановку, в которой исполняются программы. Каждая программа в рабочей смеси состоит из некоторого набора рабочих отрезков, вызывающих друг друга независимо от того, каким процессором исполняется конкретный рабочий отрезок. Для того, чтобы более наглядно представить себе строение рабочей смеси, можно разбить все существующие в системе отрезки на классы, или множества. Каждый конкретный класс включает в себя те рабочие отрезки, которые выполняются определенным процессором. Естественно, что подобные классы могут пересекаться и/или вкладываться друг в друга. Будем говорить, что рабочие отрезки, принадлежащие некоторому классу, написаны одним "цветом"; точно так же можно охарактеризовать и любой из процессоров в системе, т.е. присвоить "цвет" и ему. Понятие "цвет" вводится здесь для большей наглядности и краткости изложения, так как манипулирование с выражениями типа "... объектный код, на котором написан этот рабочий отрезок..." затруднительно и для читателя.

Для ясности сразу же определим цвет машинного уровня программ как "черный", т.е. аппаратура обеспечивает движение управления по отрезкам "черного" цвета.

На практике наиболее часто реализуется "вложенная" интерпретация, т.е. существует несколько "разноцветных" слоев программ, один над другим. Примером подобной реализации может служить программное обеспечения персональной мини-ЭВМ Оливетти P6066.

На самом нижнем уровне в ОС P6066 в кодах команд аппаратного процессора CPU-19M реализован интерпретатор ассемблера типа IBM/360. На этом языке написан интерпретатор языка Бейсик, на котором, в свою очередь, реализованы несколько пакетов прикладных программ, в частности графический пакет для работы с дисплеем. Пользователю доступны только два верхних слоя Программного обеспечения (в последних версиях ОС можно из программ, написанных на языке Бейсик, вызвать ассемблерные модули). Все это значительно замедляет скорость выполнения программ, по сравнению) с возможностями аппаратуры.

В подобных ситуациях естественно говорить не о "цвете" программ, а об уровнях вложенности, так как программы одного уровня (цвета) имеют доступ (могут вызывать) только к единственному уровню, который они непосредственно объемлют; их же, в свою очередь, вызывают программы, находящиеся уровнем выше.

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

Именно такой работой занимаются различные трансляторы с языков программирования. Они "опускают" программы, написанные различным цветом разных языков, к "черному" слою. Иногда встречаются и исключения. Например, некоторые реализации Паскаля и Модулы-2 "опускают" программы в промежуточный цветной слои P- или M-кода, который затем интерпретируется с минимальными затратами.

Более интересным с нашей точки зрения, является случай "распределенной" интерпретации, когда программа представляет собой совокупность программных отрезков разных цветов, которые могут вызвать друг друга, независимо от того, какого цвета они сами и/или вызываемые ими отрезки. Именно такую распределенную интерпретацию должна обеспечивать система программирования "рабочая смесь".

УПРАВЛЕНИЕ В РАБОЧЕЙ СМЕСИ

Перечислим сначала основные цели, которые преследовались при проектировании системы программирования, в основу которой положены принципы работы рабочей смеси. Часть из них была определена в работе [l] и отражает общие требования к удобной и эффективной системе программирования. Необходимо обеспечить:
- возможность написания и отладки сложных программных систем по частям, каждая из которых может создаваться, транслироваться и отлаживаться, вообще говоря, отдельно от других;
- возможность управлять эффективностью получаемой рабочей программы, т.е такими ее параметрами, как объем, скорость выполнения и т.д.;
- реализацию общего механизма свертки [макросы, подпрограммы, структуры данных...- G.] и предоставить программисту возможность самому описывать те понятия и действия, в которых он нуждается, вместе со средствами управление эффективностью их использования;
- эффективное применение средств высокого уровня, включая применение соответствующих языков программирования и обеспечение легкого включения накопленных пакетов прикладных программ, и, как следствие этого,- резкое сокращение сроков создании сложных программных систем.

Добавим к этому несколько пунктов, которые возникают в связи с ориентацией системы программирования на микропроцессоры:
- необходимо учитывать и обеспечить гибкое взаимодействие вновь создаваемых частей программ с программами, находящимися в постоянной памяти аппаратных процессоров, ток как в большинстве случаев использования микропроцессорной техники объем таких программ значителен, а возможность замены их на другие зачастую отсутствует;
- необходимо получить возможность, не изменяя программы в целом, транслировать или преобразовывать некоторую часть ее программных отрезков с высоких уровней (цветов) на более низкие, получая тем самым возможность в наиболее "узких" местах оптимизировать либо время выполнения, либо объем занимаемой памяти. Кроме того, возможность свободного обращения из программных отрезков нижнего уровня к произвольным программным отрезкам более высоких уровней позволит сократить время отладки за счет интерпретации, а затем получить достаточно эффективный объектный код;
- необходимо обеспечить переносимость программ с одного типа оборудования на другой с минимальными затратами, так как в связи с резким ростом разнообразия типов выпускаемых микропроцессорных устройств стало очевидным, что разрабатывать заново программное обеспечение отдельно для каждого из них невозможно. Естественно потребовать при этом обеспечения максимально возможной оптимизации программ в расчете на конкретный тип оборудования.

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

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

Что же представляют собой многие из используемых ныне программных систем на основе интерпретации? Подавляющее большинство из них имеет "луковичное" строение, подобно упомянутой выше операционной системе для мини-ЭВМ P6066. При создании подобных систем, по-видимому, ставилась единственная задача: максимально быстро перенести уже имеющееся программное обеспечение на новый вид оборудования, не считаясь с потерей эффективности, поскольку производительность и дешевизна нового оборудования позволяла все-таки в целом получить приемлемые показатели.

В таких системах "слои" программ, находящиеся на разных уровнях интерпретации, замкнуты по передачам управления внутри себя или имеют выход на один-два "слоя" вниз к аппаратуре. Обращение же с нижнего уровня вверх очень затруднительно и требует от программиста больших усилий при написании программ. Во всяком случае, авторам не известны системы, в которых достаточно просто можно было бы обратиться из программы на ассемблере к программе, скажем, на Бейсике или Паскале.

Между тем очевидно, что именно за счет использования сверток уже на самых нижних уровнях, где аппаратура может быть использована максимально эффективно, но нет возможностей подключать средства высокого уровня, можно резко увеличить мощность средств, представляемых пользователю. Таким образом, необходимо обеспечить:
- "прозрачность" программных слоев не только сверху вниз но и в обратном направлении;
- доступность произвольного слоя из любого другого, не обязательно близлежащего;
- простоту обращения из программы к программе, написанной другим цветом.

Если реализовать перечисленные выше условия, то исчезает вложенность уровней интерпретации; трудно становится выделить слои в программном обеспечении - они как бы перемешиваются друг с другом. Возникает система с распределенной или смешанной интерпретацией. Собственно, название "рабочая смесь" и возникло в результате подобных раcсуждений.

В работе [1] было показано, что для того чтобы обеспечить возможность поддерживать распределенную интерпретации, необходимо иметь набор узкоспециализированных интерпретаторов (процессоров), каждый из которых будет работать при обращении (или вызове) к рабочему отрезку определенного цвета. Для каждого управления в такой системе должен быть свой интерпретатор, что, впрочем, не исключает случая, когда обработку программ нескольких цветов будет вести один и тот же интерпретатор, как, например, в случае программ, составленных для микропроцессоров INTEL-8080, Z80.

Естественно считать, что большинство интерпретаторов (для эффективности) будут представлять собой отрезки "черного" цвета; но предлагаемая организация допускает и интерпретаторы, написанные любыми другими цветами.

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

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

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

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

Дескрипторы отрезков логично собирать в специальные словари, и, следовательно, ссылки на них из тел отрезков могут быть косвенными, относительными (в зависимости от реализаций конкретных интерпретаторов вызовов).

Алгоритм простейшего из интерпретаторов вызовов можно описать так:
- определяется цвет отрезка;
- если он "черный", то управление передается по адресу, выбранному из дескриптора;
- если же цвет не "черный", то он рассматривается как адрес дескриптора интерпретатора этого цвета; адрес текущего дескриптора помещается на стек вычислений (по нему интерпретатор найдет адрес отрезка); выбирается следующий дескриптор, и цикл повторяется заново до тех пор, пока управление не попадет на "черный" отрезок.

Таким образом, все передачи управления в рабочей смеси поддерживаются частью виртуальной машины, состоящей из двух стеков управления и вычислений [1], и набора интерпретаторов вызовов. На рис.1 приводится пример архитектуры подобной машины.


Рис.1.

Надо отметить, что затраты как по памяти, так и по времени на передачи управления с помощью описанного механизма минимальны. К примеру, на таком маломощном процессоре как INTEL-8080, ядро системы занимает менее 50 байт, а на передачи управления от отрезка одного цвета другому затрачивается от полутора до трех десятков команд (если присутствуют процессоры, реализованные в несколько слоев интерпретации, то естественно, больше). Причем не налагается никаких ограничений на возможности передачи управления от "черного" отрезка к "черному' с помощью обычных команд CALL.

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

Еще одним примером является так называемый Ультра-интерпретатор, который предлагается в качестве основного интерпретатора рабочей снеси. Рабочие отрезки для него составляются из элементов, представляющих собой ссылки на дескрипторы других отрезков (как в словарях, так и вне их). Реализован начальный набор "черных" отрезков (примитивов), выполняющих элементарные действия, пользуясь которыми можно конструировать любые программные отрезки. Естественно, что из любого отрезка Ультра-кода обеспечивается возможность вызвать как "черный" так и любой другой отрезок. Надо отметить, что Ультра-отрезок очень просто (при помощи смешанных вычислений) можно преобразовать в "черный" отрезок, выполняющий те же функции, и тем самым повысить скорость его выполнения.

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

Нетрудно видеть, что в ОС, построенной по такому принципу, накладные расходы сведены до минимума так как (не считая действий, обеспечивающих функционирование рабочей смеси) системные действия исполняются только тогда, когда это необходимо,- либо для обработки прерывания, либо для выполнения заказа прикладной программы, и эффективность операционной системы зависит от эффективности составляющих ее отрезков.

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

ДАННЫЕ В РАБОЧЕЙ СМЕСИ

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

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

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

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

Множеством рабочих областей, существующих в каждый конкретный момент исполнения программы, назовем средой. Среда изменяется в случае добавления или удаления рабочей области.

Из каких областей состоит среда, определяется всем предыдущим ходом исполнения программы. При исполнении одного и того же участка программы среда может быть всякий раз другой. Если провести аналогию с формальными и фактическими параметрами в языках программирования, то можно сказать, что в программе используются указания на формальные области, т.е. ссылка на память должна состоять из "имени" формальной области и адреса внутри области, а связь формальных областей с конкретными областями среды должна устанавливаться, в общем случае, во время исполнения.

Таким образом, возникает необходимость поддерживать постоянно меняющееся отображение, не обязательно взаимнооднозначное, множества "имен" формальных областей в множество областей среды. Образом этого отображения будет множество доступных в данный момент областей.

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

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

Если в любой момент выполнения процедуры возможны обращения к переменным из нескольких областей данных, то, чтобы иметь возможность ссылаться на них, в некоторых реализациях адреса этих областей собираются в таблицу, обычно называемую дисплеем. Дисплеи есть не что иное, как способ реализации отображения формальных областей в среду.

Б большинстве языков программирования высокого уровня вызов и возврат из процедуры (функции, подпрограммы) являются свертками независимых, по нашему мнению, действий, а именно
- действий по изменению среды и организации ее связи с программой,
- собственно действий по передаче управления.

Причем набор действий по изменению среды и организации связи с ней жестко ограничивается частично самим языком, частично его конкретной реализацией.

Естественно желание каждого системного программиста - получить в свое распоряжение эти средства и возможность применять их в произвольном сочетании с любыми другими действиями, в том числе, и по передаче управления.

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

Так как программа взаимодействует со средой через отображение то набор средств по управлению средой (с точки зрения программы) должен фактически представлять собой набор средств по изменению этого отображения.

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

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

Поскольку основным механизмом передачи управления в рабочей смеси является вызов рабочего отрезка, т.е. переход с возвратом, то и "коренные" изменения отображений необходимо производить, сохраняя возможность возврата к предыдущему отображению (естественно, с учетом текущего отображения).

Основу предлагаемой реализации составляет два стека: областей и отображений. Стек областей содержит описатели существующих областей среды (допускаются также пустые описатели). Элементами стека отображений является указатели на элементы стека областей. Значение верхнего элемента стека отображений будем называть указателем текущего отображения (УТО). Часть стека областей, ограниченная указателем стека областей и УТО, представляет собой текущее отображение (нулевой формальной области соответствует область, на описатель которой показывает УТО, и т.д. по направлению к вершине стека областей).

Описатели областей среды представляют собой ссылки на уникальные полные описатели областей, которые могут содержать в себе точный адрес, размер области, счетчик количества ссылок на нее, а также другую полезную информацию. Такие описатели областей собираются в таблицу описателей.

Адрес данных в теле рабочего отрезка представляет собой указание на область данных внутри текущего отображения и смещение внутри этой области.

Структура доступа к памяти приведена на рис.2.


Рис.2.

Возможны различные реализации обращения к областям среды в текущем отображении, а именно:
- адресация относительно УТО, как описывалось выше;
- адресация относительно вершины стека областей по направлению к УТО.

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

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

При рекурсивном вызове отрезка осуществляется построение нового текущего отображения для него. В таком же стиле можно например реализовать рекурсивный вызов сопрограммы с собственными значениями и т.д.

Все операции над стеками отображений и областей осуществляются на основе базового набора примитивов, реализованных в рабочей смеси.

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

В предлагаемом случае стратегия размещения областей данных внутри пространства оперативной памяти программиста может не интересовать.

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

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

Кроме того остается возможность подвергнуть отрезок трансформациям в стиле смешанных вычислений [2], для того чтобы "жестко" настроить его на данные. В этом случае на время работы преобразованного отрезка области данных связываются с конкретными адресами к памяти, и поэтому не могут быть перемещаемыми, но сокращается время доступа к ним.

Остается добавить, что в предложенном варианте довольно легко реализуется раздельная трансляция рабочих отрезков (оформленных, скажем, в виде модулей).

ЗАКЛЮЧЕНИЕ

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

В настоящее время один из вариантов рабочей смеси используется для разработки системы программирования высокого уровня на мини-ЭВМ МРАМОР [3].

ЛИТЕРАТУРА
1. Берс А.А., Поляков В.Г.. Руднев С.Б. Основные принципы разработки системы программирования для микропроцессоров.- В сб.: Программное обеспечение задач информатики. Новосибирск. 1982. с.5-28.
2. Ершов А.П. Смешанные вычисления: потенциальные применения и проблемы исследования.- В сб.: Теория и практика программного обеспечения ЭВМ. Новосибирск. 1981, ч.1, с.5-40.
3. Берс А.Д., Поляков В.Г. Архитектура многофункционального автоматизированного рабочего места обслуживания редакции.- Наст. сб.