Реализация структурных типов.
Наличие в нашем языке операции определения подстроки позволяет сделать неожиданный вывод. Достаточно иметь в нашем языке единственную переменную - с некоторым стандартным именем 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 N1:T1;…; Nm:Tm end - последовательность m битовых полей разных длин Len(T1),…,Len(Tm) - т.е. снова некоторое битовое поле Memory[AdrRec,L] длины L= Len(T1)+…+Len(Tm). Нетрудно вычислить AdrRec+ Len(T1)+…+Len(Tk-1) - адрес начала поля, содержащего значение r. Nk и таким образом реализовать операцию доступа по имени, для каждого имени Nk.
Закончим тему примером трансляции "вручную".
Пример. Написать программу на определенном выше языке, определяющую, есть ли данное значение 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]. См. определение операторов обработки очереди далее)
Интуитивная "идея" стека - "тот, кто пришел последним, уходит первым" (Last In First Out, англ.) или идея магазинной памяти (здесь имеется в виду магазин, т.е. обойма автоматического оружия) - можно точно (=формально) описать следующим образом.
Операторы и функции определения стека.
Операторы.
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;
Интуитивная идея очереди - "тот, кто пришел первым, первым и уйдет" (First In First Out, англ.)
Операторы и функции определения очереди.
Операторы.
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) (очередь пуста) - тождественен соответствующему предикату над стеком.
Стек и очередь - абстрактные для Паскаля типы, потому их необходимо реализовать имеющимися в нем средствами.