Реализация структурных типов.

 

Наличие в нашем языке операции определения подстроки позволяет сделать неожиданный вывод. Достаточно иметь в нашем языке единственную переменную - с некоторым стандартным именем Memory (память) - указывая все нужные значения как некоторые подстроки Memory[i,l] этой переменной. Далее (когда можно) мы используем обычные имена переменных (идентификаторы) вместо непривычных имен вида Memory[i,l]. И все же упомянутый факт принципиален для реализации структурных типов.

 

Индекс i (номер позиции начала поля) называется адресом значения Memory[i,l]. Понятно, что когда длина поля l заранее известна (как, например, в условленном нами случае представления скалярных типов), то по значению i можно однозначно восстановить содержимое поля Memory[i,l]. В этом смысле адрес i является указателем (индексом, ссылкой на, "именем") значения Memory[i,l]. Таким образом, каждое имя переменной имеет числовое значение - адрес начала поля соответствующей этой переменной.

 

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

 

Нетрудно представить значения структурных типов в виде совокупности полей. Так, массив array[1..n] of T - это последовательность n битовых полей, каждое длины Len(T) - т.е. некоторое битовое поле Memory[AdrA,L] длины L=Len(T)*n

 

Таким образом, Memory[AdrA+(i-1),Len(T)] - подполе, соответствующее значению a[i]. Строго говоря, синтаксис операции указания подполя не позволяет использовать аргументы-выражения, но соответствующее значение нетрудно вычислить и таким образом реализовать основную для массивов операцию выборки (доступа) a[i].

 

Аналогично, запись record N₁:T₁;…; N_m:T_m end - последовательность m битовых полей разных длин Len(T₁),…,Len(T_m) - т.е. снова некоторое битовое поле Memory[AdrRec,L] длины L= Len(T₁)+…+Len(T_m). Нетрудно вычислить AdrRec+ Len(T₁)+…+Len(T_k-1) - адрес начала поля, содержащего значение r. N_k и таким образом реализовать операцию доступа по имени, для каждого имени N_k.

 

Закончим тему примером трансляции "вручную".

Пример. Написать программу на определенном выше языке, определяющую, есть ли данное значение x в последовательности a из 10 чисел, если известны адрес AdrX числа x и AdrA начала поля, содержащего числа из а. Все числа представлены в некотором формате длины L=16.

 

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

 

 

b:=false;

i:=1;

while (i<=n) and not b do

if a[i]=x then

b:=true

else

i:=i+1

 

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

 

a) Избавимся от операций выборки.

b:=false;

i:=1;

CurrentAdr:=AdrA; {адрес начала текущей компоненты}

while (i<=n) and not b do

if Memory[CurrentAdr,16]=x

then b:=true

else begin i:=i+1; CurrentAdr:=CurrentAdr+16 end;

 

b) Избавимся от сложных выражений

b:=false;

i:=1;

CurrentAdr:=AdrA;

{go:= (i<=n) and not b}

{предполагаем быстрое означивание -см. "Вычисление свойств"}

go:=false;

if i<=n then if b=false then

go:=true

while go do

begin

if a[i]=x then b:=true else begin i:=i+1;CurrentAdr:=CurrentAdr+16 end;

go:=false; if i<=n then if b=false then go:=true

end;

 

c) Избавимся от структурных операторов.

b:=false;

i:=1;

CurrentAdr:=AdrA;

go:=false;

{if i<=n then if b=false then go:=true }

if i<=n then goto M1

if b=false then goto M1

go:=true;

M1: if go=false then goto M2 {while go }

{if a[i]=x then b:=true else inc(i);}

if a[i]=x then goto M3

i:=i+1;

CurrentAdr:=CurrentAdr+16

Goto M4

M3: b:=true

M4: {go:=false; if i<=n then if b=false then go:=true}

if i<=n then goto M5

if b=false then goto M5

go:=true;

M5: goto M1

 

Окончание - надо заменить идентификаторы на указание адреса xàMemory[AdrR,16] и соответствующие выражения для остальных переменных.

 

§ 9. Абстрактные линейные типы.

 

Напомним, понятие абстрактного типа относительно - это те типы, существующие как математическое понятие, т.е. пара <A,F>, F ÍAàA (см. "Основные понятия"), которые отсутствуют в данном языке программирования. Тип, абстрактный для одного языка, может быть вполне конкретным для другого.

 

Рассмотрим некоторые общие принципы реализации абстрактных типов на примере двух простых и естественных типов - стек и очередь. (Применение - см. далее "Перечисление последовательностей" и "Нелинейные абстрактные типы данных").

 

В обоих случаях, основным множеством типа является множество всех (конечных) последовательностей f произвольной длины LenF над некоторым базовым типом T - f Î NàT, Dom(f)=[1..LenF], LenF Î N. Т.е. оба типа, вообще говоря, - динамические; в случае фиксированной длины можно говорить о статических, (или, чуть точнее - псевдодинамических стеках и очередях, см. "Классификация типов").

(Строго говоря, в случае очереди удобнее считать последовательностью функцию f c областью определения - интервалом [n,m]=[n,n+LenF], отождествляя все такие интервалы одинаковой длины c интервалом [1..LenF]. См. определение операторов обработки очереди далее)

 

Интуитивная "идея" стека - "тот, кто пришел последним, уходит первым" (L ast I n F irst O ut, англ.) или идея магазинной памяти (здесь имеется в виду магазин, т.е. обойма автоматического оружия) - можно точно (=формально) описать следующим образом.

 

Операторы и функции определения стека.

 

Операторы.

Create(r) - создать пустой стек с именем r. Начиная работать в любом состоянии s, оператор доопределяет s, добавляя в него пару rà<> (<> - пустая последовательность) (см. определение состояния в "Основные понятия")

Destroy(r) - обратная к Create операция - убирает из текущего состояния пару ràR. Имя r перестает существовать, доступ к стеку теряется.

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

 

Push(r,x) - добавить компоненту x (базового типа T) в верхушку (конец) стека - начиная работать в состоянии ràR, cо стеком длины Len(R) Dom(R)=[1..Len(R)], этот оператор неявно доопределяет Dom(R) до [1..Len(R)+1] и осуществляет присваивание R[Len(R)+1]:=x.

Pop(r,x) - осуществляет присваивание x:=R[Len(R)] (кладет верхнюю компоненту стека в x) и сокращает Dom(R) до [1..Len(R)-1] (уничтожает верхушку стека).

 

Функция (предикат).

Empty(r)= true» Len(R)=0 (т.е. стек пуст)

 

 

Пример. Обратить (перевернуть) содержимое символьного файла «небольшой длины».

 

procedure Revolution(var InputFile, OutputDile: text);

var

c: char; {текущий символ}

r:tStack; {символьный стек}

begin

create(r); reset(InputFile);

while not eof(InputFile) do begin read(InputFile,c);push(r,c) end

close(InputFile);

rewrite(OutputFile);

while not Empty(r) do begin pop(r,c); write(OutputFile,c) end;

close(OutputFile);

destroy(r)

end;

 

Интуитивная идея очереди - "тот, кто пришел первым, первым и уйдет" (F irst I n F irst O ut, англ.)

 

Операторы и функции определения очереди.

 

Операторы.

Create(r),Destroy(r) - тождественны соответствующим стековым операциям.

Put(r,x) - Поставить В Очередь - добавить компоненту x (базового типа T) в конец очереди - начиная работать в состоянии ràR, cо очередью длины Len(R) Dom(R)=[n..m], этот оператор неявно доопределяет Dom(R) до [n..m+1] и осуществляет присваивание R[m]:=x.

Get(r,x) - Вывести Из Очереди - осуществляет присваивание x:=R[n] (кладет первую компоненту очереди в x) и сокращает Dom(R) до [n+1..m] (уничтожает начало очереди).

Предикат Empty(r) (очередь пуста) - тождественен соответствующему предикату над стеком.

 

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