Самитов р.К. Машинно-ориентированное программирование.
Базовая модель вычислителя.
Внутренняя память вычислителя - двух видов:
регистровая – характеризуется очень высокой скоростью выборки данных и небольшим объемом;
будем считать, что имеется некий набор переменных (регистров) R1, R2,... неструктурного типа, представляющих регистровую память;
оперативная – характеризуется много меньшей скоростью выборки данных, но много большим объемом.
CONST LЭлемент=?; LMemo=?;
TYPE Bit{Бит, двоичный разряд}= 0..1;
ЭлементПамяти= ARRAY[0.. LСлово] OF Bit;
VAR Memo: ARRAY[0.. LMemo] OF ЭлементПамяти.
ЭлементПамяти – базовая минимально адресуемая единица памяти. Абсолютный адрес памяти – номер (индекс) элемента памяти. Сегодня общепринятым стандартом элемента памяти является байт (Byte) – 8-ми разрядный.
Поскольку память способна хранить только 0-1-наборы, и к тому же оперативная память представлена всего одной переменной Memo (типа массив) возникают вопросы о представлении и размещении значений интересующих нас типов в такой памяти. Эти вопросы мы рассмотрим позже.
Набор базовых операторов - команды вычислителя.(*)
Обозначения R – регистровая переменная, S – переменная (неструктурного типа), размещенная в оперативной памяти.
Команды пересылки.
R := R’
R := S
S := R
Команды преобразований. θ – операция преобразования, например арифметическая + - * / и т.п.
R := R θ R’
R := R θ S
Отметим, что значение 1-го операнда операции теряется, поскольку команда размещает результат на его месте.
Команды сравнения. θ – операция сравнения, например = < > ≤ ≥ и т.п.
Comp := R θ R’
Comp := R θ S
Comp – специальная переменная типа BOOLEAN (называется – код условия), причем единственная переменная такого типа. В правой части оператора присваивания она не может быть использована.
Команды перехода (безусловного и условного).
Goto метка
IF Comp THEN GOTO метка
Порядок выполнения действий.
Основным является последовательный порядок выполнения действий, т.е. сохраняется единственная структура управления – составной оператор (а точнее, только композиция – «точка с запятой»). В остальном управление порядком выполнения действий обеспечивается с помощью команд перехода.
Декомпозиция структур управления.
IF E THEN S ELSE S’ сводится к:
Comp := NOT E;
IF Comp THEN GOTO 1; S; GOTO 2; 1:S’; 2:;
WHILE E DO S сводится к:
2: Comp := NOT E;
IF Comp THEN GOTO 1; S; GOTO 2; 1:;
Декомпозиция выражений.
Текущие соглашения:
R1, R2,... – регистры.
Константы и остальные переменные – размещены в оперативной памяти.
Можно использовать (нерегистровые) переменные с индексами, но индексом может быть только регистр.
Пока предполагаем, что вопросы, связанные с базовыми типами данных, решаются согласно требованиям языка Паскаль.
Декомпозиция арифметических выражений.
x[20-j*k]:=(y-z)/(y+z) сводится к:
R1:=20; R2:=j; R2:=R2*k; R1:=R1-R2; R3:=y; R3:=R3-z; R4:=y; R4:=R4+z; R3:=R3/R4; x[R1]:=R3;
Декомпозиция логических выражений.
Мы рассмотрим реализацию логических операций, которая соответствует процедурной семантике – «быстрому вычислению логических выражений». Требованиям классической семантики она естественно тоже удовлетворяет, но классическая семантика допускает и другие реализации.
Comp := E OR E’ сводится к:
Comp := E; IF Comp THEN GOTO 1; Comp := E’; 1:;
Comp := E AND E’ сводится к:
Comp := E; IF Comp THEN GOTO 1; GOTO 2;
1: Comp := E’; 2:;
Comp := NOT E сводится к:
Comp := E; IF Comp THEN GOTO 1;
Comp := (R1=R1); GOTO 2; 1: Comp := (R1<R1); 2:;
Представленная здесь реализация операции NOT – семантически точная, но явно неестественная. Это связано с жесткими ограничениями на использование переменной Comp и отсутствием данных типа BOOLEAN в выбранной модели вычислителя.
Если, например, в реализации OR и AND переставить местами E и E’, то получим реализацию, приемлемую для классической семантики, но неправильную для процедурной.
Декомпозиция структур данных.
Представление данных типа SET.
VAR xSet: SET OF T;
В языке Паскаль T – ординальный тип, причем ограниченный. Поэтому можно воспользоваться представлением VAR xArray: ARRAY[1..k] OF 0..1, где
k – мощность множества возможных значений типа T,
xArray[i] соответствует i-му по порядку элементу из множества возможных значений типа T,
xArray[i]=1, если этот i-й по порядку элемент xSet, а иначе = 0.
Операции над множествами (объединение, пересечение, разность, включение и принадлежность) реализуются соответствующим программированием соответствующих операций над массивами, представляющими множества.
Устранение многомерных массивов основано на сведении
VAR xArray: ARRAY[T1,T2,...] OF T
к VAR xArrOfArr: ARRAY[T1] OF ARRAY[T2] OF ... T
и xArray[i,j,...] к xArrOfArr[i][j]...
Осталось самое главное – устранить древовидное представление вложений оставшихся базовых структур данных (линейные массивы и записи).
Оно основано:
на сведении базовых (неструктурных) типов данных к универсальному типу (0-1-наборы),
и сведении древовидного представления к линейному.
Однако сначала рассмотрим пример применения уже рассмотренных сведений. PROGRAM\MOP\PRG00\Project1.dpr
Исходная процедура имеет:
// Входной параметр типа
TYPE TIn0= ARRAY[1..10,1..20] OF
RECORD r: REAL; c: CHAR; s: SET OF 1..15 END;
// Выходной параметр типа
TOut0= ARRAY[1..20] OF REAL;
PROCEDURE Proc0(x:TIn0; VAR y:TOut0);
VAR i,j:INTEGER;
BEGIN FOR j:=1 TO 20 DO
BEGIN y[j]:=0;
FOR i:=1 TO 10 DO
IF (x[i,j].c='Z')AND(j IN x[i,j].s)
THEN y[j]:=y[j]+x[i,j].r
END END;
Декомпозиция структур управления: устраним FOR и IF операторы.
PROCEDURE Proc1(x:TIn0; VAR y:TOut0);
LABEL 101,102,201,202,301,302;
VAR i,j:INTEGER; comp:BOOLEAN;
B
EGIN
j:=1;
102:Comp:=(j>20);
IF Comp THEN GOTO 101;
y[j]:=0;
i:=1;
202:Comp:=(i>10);
IF Comp THEN GOTO 201;
Comp
:= NOT ((x[i,j].c='Z')AND
(j IN x[i,j].s));
IF Comp THEN GOTO 301;
y[j]:=y[j]+x[i,j].r; IF... FOR i:=... FOR j:=...
GOTO 302;
301:
302:
GOTO 202;
201:
GOTO 102;
101:
END;
Декомпозиция логических выражений.
PROCEDURE Proc2(x:TIn0; VAR y:TOut0);
LABEL 101,102,201,202,301,302,401,402,501,502;
VAR i,j:INTEGER; comp:BOOLEAN; R1:INTEGER;
BEGIN j:=1;
102:Comp:=(j>20);
IF Comp THEN GOTO 101;
y[j]:=0;
i:=1;
202:Comp:=(i>10);
IF
Comp THEN GOTO 201;
Comp := (x[i,j].c='Z');
IF Comp THEN GOTO 501;
GOTO 502; ...AND...
501:Comp := (j IN x[i,j].s);
502:
IF Comp THEN GOTO 401; NOT(...AND...)
Comp:=(R1=R1);
GOTO 402;
401:Comp:=(R1<R1);
402:
IF Comp THEN GOTO 301;
y[j]:=y[j]+x[i,j].r;
GOTO 302;
301:
302:
GOTO 202;
201:
GOTO 102;
101:
END;
Декомпозиция структур данных:
устраним SET OF 1..15 -> ARRAY[1..15] OF 0..1
и ARRAY[1..10,1..20] OF -> ARRAY[1..10] OF ARRAY[1..20] OF
// Тип входного параметра теперь:
TYPE TIn3= ARRAY[1..10] OF ARRAY[1..20] OF
RECORD r: REAL; c: CHAR;
s: ARRAY[1..15] OF 0..1 END;
PROCEDURE Proc3(x:TIn3; VAR y:TOut0);
LABEL 101,102,201,202,301,302,401,402,501,502;
VAR i,j: INTEGER; comp:BOOLEAN; R1:INTEGER;
BEGIN j:=1;
102:Comp:=(j>20);
IF Comp THEN GOTO 101;
y[j]:=0;
i:=1;
202:Comp:=(i>10);
IF Comp THEN GOTO 201;
Comp := (x[i][j].c='Z');
IF Comp THEN GOTO 501;
GOTO 502;
501:Comp := (x[i][j].s[j]=1);
502:
IF Comp THEN GOTO 401;
Comp:=(R1=R1);
GOTO 402;
401:Comp:=(R1<R1);
402:
IF Comp THEN GOTO 301;
y[j]:=y[j]+x[i][j].r;
GOTO 302;
301:
302:
GOTO 202;
201:
GOTO 102;
101:
END;
Теперь приведем операторы присваивания к «командной» форме с учетом ограничений на размещение операндов.
PROCEDURE Proc4(x:TIn3; VAR y:TOut0);
LABEL 101,102,201,202,301,302,401,402,501,502;
VAR {i}R1,{j}R2:INTEGER; comp:BOOLEAN;
R3:REAL; R4:CHAR; R5:INTEGER;
// R3,R4,R5 - для промежуточных вычислений
BEGIN R2:=1;
102:Comp:=(R2>20);
IF Comp THEN GOTO 101;
R3:=0;
y[R2]:=R3;
R1:=1;
202:Comp:=(R1>10);
IF Comp THEN GOTO 201;
R4:=x[R1][R2].c;
Comp:=(R4='Z');
IF Comp THEN GOTO 501;
GOTO 502;
501:R5:=x[R1][R2].s[R2];
Comp:=(R5=1);
502:
IF Comp THEN GOTO 401;
Comp:=(R1=R1);
GOTO 402;
401:Comp:=(R1<R1);
402:
IF Comp THEN GOTO 301;
R3:=y[R2];
R3:=R3+x[R1][R2].r;
y[R2]:=R3;
GOTO 302;
301:
302:
GOTO 202;
201:
GOTO 102;
101:
END;
Представление данных базового типа.
Представление целых чисел в форме с фиксированной точкой.
Представление вещественных чисел в нормализованной форме с плавающей точкой.
Представление символов.
Размещение данных в оперативной памяти и адресация данных.
Поле памяти – последовательность смежных байтов (элементов оперативной памяти). Уже значения базовых типов обычно занимают не один элемент памяти, а поле. Поле идентифицируется парой: базовый адрес – абсолютный адрес крайнего левого байта памяти, длина поля – количество байтов. Элементы поля (и субполя неединичной длины) идентифицируются своими абсолютными адресами (и длиной), но их можно идентифицировать парой: базовый адрес поля, смещение элемента в поле = (абсолютный адрес элемента - базовый адрес поля). Смещение еще называют относительным адресом.