Глава 2. Реализация и расширения

2.1. Шитый код и его разновидности

Логически можно выделить два подхода к реализации языков программирования — трансляцию и интерпретацию [10]. Транслятор преобразует входной текст программы в машинный код данной ЭВМ; впоследствии этот код, объединяясь с другими машиниыми модулями, образует рабочую программу, которую можно загрузить в оперативную память и исполнить. Интерпретатор непосредственно исполняет программу на языке высокого уровня, рассматривая входной текст как последовательность кодов операций, управляющих его работой. Между этими полюсами располагается целый спектр промежуточных подходов, состоящих в предварительном преобразовании входного текста программы в некоторый промежуточный язык с последующей интерпретацией получившегося кода. Чем ближе промежуточный язык к машинному языку, тем ближе данный подход к классической трансляции, а чем ближе он к исходному языку программирования, тем ближе этот подход к интерпретации.

Оптимальный вариант промежуточного языка должен существенно отличаться от исходного языка программирования и быть удобным для создания простых и надежных интерпретаторов. Примером одного из таких промежуточных языков является известный П-код, используемый во многих реализациях языка Паскаль. Рассматриваемые нами варианты шитого кода образуют специальный класс представлений промежуточных языков, особенно удобных для интерпретации [22, 25, 29].

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

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

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

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

NEXT (следующий) — переход к интерпретации следующей ссылки в данной последовательности ссылок;

CALL (вызов) — переход в подпрограмму верхнего уровня, представленную в шитом коде;

RETURN (возврат) — возврат из подпрограммы верхнего уровня на продолжение интерпретации.

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

Из всех разновидностей шитого кода подпрограммный максимально эффективен по времени исполнения. Он удобен в том случае, когда архитектура данной ЭВМ включает аппаратные стеки, команду перехода на подпрограмму (перехода с возвратом), в которой адрес возврата запоминается на вершине стека, и команду возврата по адресу, находящемуся на вершине стека. Для ЭВМ СМ-4 и «Электроника-60» это команды JSR и RST, для микропроцессора К580 — команды CALL и RET.

Рис. 2.1. Подпрограммный шитый код

Структура подпрограммного шитого кода приведена на рис. 2.1. Каждая ссылка на операцию промежуточного языка представляется в виде машинной команды перехода на соответствующую подпрограмму. Стек возвратов используется для сохранения адреса возврата этими командами, а в качестве указателя текущего места в интерпретируемой последовательности ссылок выступает внутренний регистр счетчика адреса. Высокоуровневая подпрограмма на промежуточном языке представляет собой последовательность таких же команд перехода с возвратом, которая заканчивается командой возврата по адресу, снимаемому с вершины стека возвратов. Подпрограмма нижнего уровня должна заканчиваться такой же командой возврата для продолжения обработки. Таким образом, в подпрограммном шитом коде интерпретатор реализуется непосредственным образом в структуре самого кода. Действие NEXT состоит в исполнении пары команд JSR/RST, действие CALL как таковое отсутствует, действие RETURN состоит в команде RST. Подпрограммный шитый код в отличие от всех остальных разновидностей допускает большую оптимизацию по времени счета за счет непосредственной вставки подпрограмм нижнего уровня в место их вызова.

Рис. 2.2. Прямой шитый код

Прямой шитый код (рис. 2.2.) уступает подпрограммному по скорости исполнения, но дает выигрыш по объему памяти, необходимой для его размещения. В качестве последовательности операций промежуточного языка выступает последовательность адресов соответствующих подпрограмм. Ее можно рассматривать как последовательность вызовов подпрограммного шитого кода с удаленным кодом команды JSR (именно это и дает экономию объема памяти примерно на 1/3 по сравнению с подпрограммным кодом). Поскольку код команды отсутствует, требуется специальный интерпретатор последовательности ссылок. Подпрограммы верхнего уровня должны начинаться машинными командами, выполняющими действие CALL (положить текущее значение указателя на стек возвратов, перевести указатель на начало последовательности адресов данной подпрограммы, исполнить NEXT) и заканчиваться адресом подпрограммы RETURN (снять значение со стека возвратов и заслать его в указатель, исполнить NEXT). Подпрограммы в машинном коде должны заканчиваться исполнением действия NEXT (скопировать адрес подпрограммы по текущему значению указателя в рабочую ячейку, перевести указатель на следующий элемент кода, передать управление по адресу в рабочей ячейке). В тех случаях, когда архитектура ЭВМ позволяет выразить действия CALL и NEXT одной-двумя машинными командами (например, для ЭВМ СМ-4), эти команды вставляются непосредственно в подпрограммы; если же требуется более длинная последовательность команд, то в подпрограммы вставляются команды перехода на соответствующие точки, которые выносятся в отдельное подпрограммное ядро.

Рис. 2.3. Косвенный шитый код

Косвенный шитый код уступает прямому по скорости исполнения, но имеет то преимущество, что его высокоуровневые подпрограммы не зависят от машины, поскольку не содержат машинных кодов. Как и в случае прямого кода, последовательность операций промежуточного языка состоит из последовательности адресов подпрограмм, разница заключается в организации этих подпрограмм и действиях интерпретатора (рис. 2.3.). Теперь чтобы передать управление на машинный код, в действии NEXT требуется выполнить еще одно разыменование. Подпрограмма верхнего уровня начинается не машинными командами для действия CALL, а ячейкой, где записан адрес этой точки, и заканчивается ячейкой, где записан адрес ячейки с адресом точки RETURN. Подпрограмму на машинном языке представляет ячейка, где записан адрес начала соответствующего кода. Завершающим действием такой подпрограммы, как и раньше, является исполнение действия NEXT. Для этого обычно используется безусловный переход на соответствующую точку интерпретатора.

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

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