Вычислительные сети, теория и практика.

ЦИКЛИЧЕСКОЕ ВЫПОЛНЕНИЕ КОМАНД
В ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ С ВНУТРЕННИМ ЯЗЫКОМ ВЫСОКОГО УРОВНЯ

С.А. Чернов

(Москва, Московский Энергетический Институт (ТУ), Россия)

Архитектура базовой вычислительной машины (БВМ) с внутренним языком высокого уровня разрабатываемая на кафедре ВМСиС МЭИ(ТУ) к настоящему времени доведена до уровня программной модели. Основой работы является предложенная Фальком В.Н. теоретическая модель языка программирования высокого уровня [1] Архитектура БВМ представляет собой один из вариантов реализации абстрактной Falgol-машины [1], имеющей стековую организацию и выполняющей анализ и направленное преобразование программы во время вычислений.

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

Несмотря на то, что разработанный базовый машинный язык (БМЯ) – внутренний язык БВМ, является языком высокого уровня, набор примитивов и программных конструкций, предоставляемых языком программисту, достаточно своеобразен и отличается от соответствующих средств общепринятых языков высокого уровня таких, как, например, Pascal или C. Переход к программированию на БМЯ может быть облегчён за счёт использования БМЯ-макроопределений основных конструкций этих ЯВУ. Ниже рассматриваются возможные варианты БМЯ-макроопределений циклических конструкций while и for языка Pascal.

Оператор while языка Pascal позволяет организовать циклическое выполнение простого или составного оператора при заданном условии. Формат оператора while:

while A do B,

где A – условие продолжения цикла, выражение логического типа; B – итерируемый оператор. Макроопределение на БМЯ, реализующее семантику этого оператора может выглядеть следующим образом.

WHILE(A,B) = [A,B: <f:(val_B, ex, val_f, ex) val_A, ex, tex > ex ]

Параметры A, B – константные процедуры, указаны в порядке размещения в абстрактном левом стеке – ALS [2]. Процедура A должна в результате распроцедуривания оставлять на верхнем уровне ALS команду true или false. Если распроцедуривание A дало true, то распроцедуривается P, что приводит к распроцедуриванию B с последующим распроцедуриванием f, т.е. к новой итерации, иначе выполнение макроса завершается. Заметим, что размещение команды ex последней командой процедуры P позволяет не сохранять адрес возврата при распроцедуривании f. В результате, количество итераций не ограничено, несмотря на то, что они реализуются через рекурсию. Реализация цикла через рекурсию в языке Pascal при значительном числе итераций привела бы к переполнению стека.

Пример 1. Запишем на базовом машинном языке Pascal-программу, вычисляющую сумму целых чисел от 1 до 9.

1.	var i,s:integer;
2.	i:=1;s:=0;
3.	while i<=9 do
4.	begin
5.	s:=s+i;
6.	i:=i+1;
7.	end;

Получим:

1.	{while:
2.	//макроопределение цикла while
3.	([A,B:<f:(val_B,ex,val_f,ex)val_A,ex,tex> ex])ass_while
4.
5.	//вычисление суммы чисел от 1 до 9
6.	{i=1,s=0:
7.	(val_s,val_i,add,ass_s, //s:=s+i;
8.	val_i,inc,ass_i) //i:=i+1;
9.	(val_i,9,le)val_while,ex, //i<=9
10.	}
11.	}

Результат работы программы – сумма, накопленная в переменной s.

Оператор for осуществляет циклическое выполнение участка программы с изменением параметра цикла и завершением итераций при достижении им определенного значения. Формат оператора for:

for v:=A to B do C,

где v – параметр цикла, переменная порядкового типа, A, B – начальное и конечное значения, выражения того же типа, что и v, С – произвольный оператор языка Pascal. БМЯ-макроопределение, реализующее семантику этого оператора может выглядеть следующим образом.

FOR(v,A,B,C)= [C,B,A,v: val_A, val_v, assign
<f:(val_C, ex, val_v, value, inc, val_v, assign, val_f, ex) val_v, value, val_B, le, tex > ex],

где v – указатель переменной блока var, переменная, как и в Pascal'е, является внешней по отношению к макросу FOR. Параметры: A, B – начальное и конечное значения целого или бинарного типа; C – тело цикла, константная процедура.

Пример 2. Запишем на базовом языке Pascal-программу, вычисляющую факториал 5:

1.	var i,p:integer;
2.	begin
3.	p:=1;
4.	for i:=2 to 5 do
5.	begin
6.	p:=p*i;
7.	end
8.	end

Код на БМЯ будет иметь следующий вид:

1.	{cycle_for:
2.	//макроопределение цикла for
3.	([C,B,A,v:val_A,val_v,assign,
4.	<f:(val_C,ex,val_v,value,inc,val_v,assign,val_f,ex)
5.	val_v,value,val_B,le,tex>ex
6.	])ass_cycle_for,
7.
8.	//вычисление факториала 5
9.	{i,p=1:
10.	var_i,2,5(val_p,val_i,mul,ass_p)val_cycle_for,ex
11.	}
12.	}

Результат работы программы – значение факториала, находящееся в переменной p.

Существенным недостатком реализации циклов описанным способом является неконстантность рекурсивной процедуры (РП) f и, как следствие, необходимость её просмотра и вынесения в память подпрограмм (SbrM) при каждом распроцедуривании значений переменных while и cycle_for. В результате, в памяти БВМ образуется значительный объём мусора. Константность РП можно обеспечить посредством:

1) записи параметров макросов A, B, C в переменные блока, внешние по отношению к РП и всей процедуре макроопределения (см. [2]), но при этом невозможна вложенность циклов;

2) временного размещения параметров РП в ALS.

Во втором случае, макроопределения для циклов for и while примут следующий вид:

FOR₁(v,B,C) = <f:[C,B,v: val_v, val_B, val_C
([C,B,v: val_C, ex, val_v, val_B, val_C,
val_v, value, inc, val_v, assign], val_f, ex) (del, del, del) val_v, value, val_B, le] ex, ex>

WHILE₁(A,B) = <f:[A,B: val_B, val_A
([A,B: val_B, ex, val_B, val_A] val_f, ex) (del, del)
val_A] ex, ex, ex>

Начальное значение A должно присваиваться переменной, заданной параметром v, перед вызовом FOR₁. Приведённые макроопределения WHILE₁ и FOR₁ являются константными процедурами. Объём генерируемого ими мусора не зависит от числа обращений к ним. В остальном, эти макроопределения аналогичны рассмотренным ранее.

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

1) подстановкой и последовательным выполнением команд составляющих макроопределение;

2) специализированными аппаратными средствами БВМ, при условии эквивалентности [2] алгоритмов интерпретации этих команд в БВМ алгоритмам интерпретации их макроопределений в АМ.

Второй вариант, с точки зрения эффективности БВМ – предпочтительнее.

ЛИТЕРАТУРА

1. Фальк В.Н. Теоретическая модель языка программирования высокого уровня // Программирование, №4, 1987. - С. 3-12

2. Чернов С.А. Исследование и реализация базовой вычислительной машины с внутренним языком высокого уровня. 05.13.15 – Вычислительные машины и системы. Дис. на соискание уч. степени канд. техн. наук / МЭИ. – М., 2003.

3 Модели и методы для обоснования выбора состава аппаратных средств ВС