Часть V. Проектирование программ в O Pascal.
Расширенные возможности O (Optimization) Pascal позволяют произвольный доступ к данным и управление выполнением. Два новых типа данных в O Pascal, массивы и указатели, позволяют произвольный доступ к данным. Переменная типа:
ARRAY [j] OF T
Является ограниченным списком элементов типа T, чьи элементы индексированы значениями порядкового типа J. Для любого типа T, также существует предопределенный, неограниченный список элементов типа T, индексированный значениями неупорядоченного типа “указатель”.
Части программ с массивами и указателями имеют частные функции значения, но формальный вывод функций из текста программ рассматриваться не будет. Использование указателей и массивов может обеспечить значительный выигрыш в скорости программ, но они должны использоваться с большой осторожностью, например, только тогда, когда функция части программы может быть определена и верифицирована как минимум неформально. Мы уже видели подобную ситуацию с итерационными операторами. После завершения оператора WHILE он может быть заменен группой вложенных операторов IF. Но оператор WHILE настолько эффективен (в терминах количества строк), что стоят дополнительных усилий, требуемых для вычисления функции их частного значения. На самом деле, не существует механического способа доказательства завершимости цикла и следовательно, механического способа верификации функции частного значения для оператора WHILE. Тем не менее, мы можем ограничить себя написанием операторов WHILE, чье завершение может быть доказано специальным образом (ad hoc proof).
Аналогично, хотя механический вывод функций частного значения может быть невозможен для случаев, когда используются массивы и указатели, мы можем ограничить себя до случаев, когда возможны специальные (ad hoc) способы вывода и верификации.
Оператор GOTO позволяет перенос выполнения в практически любую точку программы. Их функция частного значения также не будет рассматриваться. Однако, операторы GOTO вводятся только в целях повышения эффективности. Они могут быть систематическим образом исключены для получения эквивалентной программы без GOTO (GOTO-free program), которая может быть проанализирована более легко.
O Pascal содержит новый тип данных, REAL, который обладает свойствами действительных чисел. Его преимущество в том, что в довольно широких пределах, числа любого размера могут обрабатываться одинаково. Его недостаток в том, что числа округляются в процессе вычисления и ошибки округления могут накапливаться и вести к неверным результатам.
Составные типы данных в O Pascal.
Тип данных массив предоставляет возможность создавать коллекцию объектов, в которой обращение к каждому элементу может быть сделано так же быстро как и к любому другому. Размер коллекции ограничен и задается жестко, но когда эти ограничения не важны, массивы могут обеспечить поразительное увеличение в скорости. Массивы полезны для реализации абстрактных типов данных и операций поиска и сортировки.
Массивы – наборы с фиксированным количеством объектов, которые могут быть использованы для замещения функций (если их область определения невелика) или файлов (когда они содержат немного компонентов). Как и функции, массивы задают соответствие области определения из элементов одного типа в область значений из элементов, возможно, другого типа. С массивами, моделирующими функцию, значение функции может быть выбрано из массива вместо вычисления каждый раз, когда это необходимо, часто с громадным выигрышем в скорости. Когда массив моделирует файл, доступ к каждому элементу требует фиксированного времени, обеспечивая большой выигрыш в скорости.
Массивы.
Массив образуется из двух типов: его компонентов и индексов. Значения индексов используются для выбора значений компонентов. Мощь массивов в возможности вычисления значения индекса и использования его для получения значения компонента за время, которое не зависит от значения индекса или истории предыдущего использования массива.
В Паскале тип данных массив описывается следующим оператором.
TYPE
ArrType = ARRAY [IndexType] OF ComponentType;
Область определения для данного массива это IndexType, а область значений – это подмножество ComponentType. В Паскале IndexType ограничен порядковыми типами иными, исключая INTEGER, так что количество значений в области определения ограничено объявлением. Переменная массива, скажем ArrVar1 или ArrVar2 может быть объявлена с данным типом, и также будет полезна переменная с типом индекса.
VAR
Index: IndexType;
ArrVar1, ArrVar2: ArrType;
Переменные массивов ставят в соответствие значениям типа IndexType значения типа ComponentType. Это соответствие достигается указанием индекса для переменной массива. Операция указания индекса в Паскале обозначается квадратными скобками, например:
ArrVar1[Index]
Соответствие, представленное массивом ограниченное и явное; каждому элементу области определения с помощью присваивания ставится в соответствие элемент области значений. Присваивание обычно выполняется для одного индекса, но также и целый массив может быть присвоен другому массиву. Оператор:
ArrVar1[Index]:= CTypeValue
изменяет значение соответствия, представленного ArrVar1 в точке области определения, заданной Index на значение CTypeValue, но оставляет соответствие в остальном неизменным.
Оператор:
ArrVar1:= ArrVar2
изменяет все соответствие присваиванием всех компонентов ArrVar2 соответствующим компонентам ArrVar1.
В следующем примере, и тип и индексы массива Arr являются поддиапазоном INTEGER и оператор FOR присваивает каждому элементу в массиве значение равное его позиции. То есть этому массиву присваивается функция эквивалентности (identity function) на области определения {1, 2, 3, 4, 5}.
TYPE
Both = 1.. 5;
VAR
I: Both;
Arr: ARRAY [Both] OF Both;
BEGIN
FOR I:= 1 TO 5
DO
Arr[I]:= I
END
Шифрование – идеально подходящий способ применения для массивов. Простейший способ зашифровать сообщение – использовать замещающий шифр, который заменяет символы в сообщении символами из кода. Сообщение может быть представлено как массив символов с целыми индексами, которые указывают позицию каждого символа в сообщении. Предположим, что сообщения длиной до Len будут состоять только из заглавных букв.
CONST
Len = 20;
TYPE
Str = ARRAY [1.. Len] OF ‘A’.. ‘Z’;
VAR
Msg: Str;
Другой массив символов может хранить символы шифра (не только буквы) значениями индексов которого являются буквы, которые встречаются в исходном сообщении.
TYPE
Chiper = ARRAY [‘A’.. ‘Z’] OF CHAR;
VAR
Code: Chiper;
Символы в сообщении, которые не являются большими буквами, воспроизводятся без замен.
Следующий раздел проекта читает и шифрует определенное количество входных строк в соответствии с выше описанной схемой. Поскольку каждая входная строка сохраняется в Msg перед шифровкой, MSG дополняется пробелами после чтения каждой строки таким образом, что символы более длинной ранее считанной строки не появлялись в зашифрованном выводе следующей, более короткой.
Design Part 1
PROGRAM Encryption(INPUT, OUTPUT);
{Переводит символы из INPUT в код согласно Chiper
и печатает новые символы в OUTPUT}
CONST
Len = 20;
TYPE
Str = ARRAY [1.. Len] OF ‘A’.. ‘Z’;
Chiper = ARRAY [‘A’.. ‘Z’] OF CHAR;
VAR
Msg: Str;
Code: Chiper;
BEGIN {Encryption}
{Инициализировать Code}
WHILE NOT EOF
DO
BEGIN
{читать строку в Msg и распечатать ее}
{дополнить Msg пробелами}
{распечатать кодированное сообщение}
END
END. {Encryption}
Инициализация массива шифра это длинная последовательность присваиваний, поэтому она объединяется в процедуру.
Design Part 1.1.
{Инициализировать Code}
Initialize(Code);
Design Part 1.1.1.
PROCEDURE Initialize(VAR Code: Chiper);
{Присвоить Code шифр замены}
BEGIN {Initialize}
Code['A']:= 'Z';
Code['B']:= 'Y';
Code['C']:= 'X';
Code['D']:= '#';
Code['E']:= 'V';
Code['F']:= 'U';
Code['G']:= 'T';
Code['H']:= 'S';
Code['I']:= 'I';
Code['J']:= 'Q';
Code['K']:= 'P';
Code['L']:= '!';
Code['M']:= 'N';
Code['N']:= 'M';
Code['O']:= '2';
Code['P']:= 'K';
Code['Q']:= '$';
Code['R']:= 'D';
Code['S']:= 'H';
Code['T']:= '*';
Code['U']:= 'F';
Code['V']:= 'E';
Code['W']:= 'T';
Code['X']:= 'C';
Code['Y']:= 'B';
Code['Z']:= 'A';
END; {Initialize}
Символы считываются в последовательные элементы Msg до тех пор, пока не встретится маркер конца строки.
Design Part 1.2.
{читать строку в Msg и распечатать ее}
I:= 0;
WHILE NOT EOLN AND (I < Len)
DO
BEGIN
I:= I + 1;
READ(Msg[I]);
WRITE(Msg[I])
END;
READLN;
WRITELN;
Индекс I теперь находится в позиции последнего символа в сообщении и для очистки оставшейся части строки необходимо заполнить ее пробелами.
Design Part 1.2.
{дополнить Msg пробелами}
FOR I:= I+1 TO Len
DO
BEGIN
Msg[I]:= ‘ ‘;
END
Поскольку шифрование Msg занимает несколько строк кода, они оформляются процедурой.
Design Part 1.4.
{распечатать кодированное сообщение}
Encode(Msg)
Элементы Msg с ‘A’ по ‘Z’ используются как индексы в массиве Code для получения их кодированных значений. Другие символы распечатываются без перевода.
Design Part 1.4.
PROCEDURE Encode(VAR S: Str);
{Выводит символы из Code, соответствующие символам из S}
VAR
Index: 1.. Len;
BEGIN {Encode}
FOR Index:= 1 TO Len
DO
IF S[Index] IN [‘A’.. ‘Z’]
THEN
WRITE(Code[S[Index]])
ELSE
WRITE(S[Index]);
WRITELN
END; {Encode}
Ниже приведен финальный текст программы и примеры ввода/вывода.
PROGRAM Encryption(INPUT, OUTPUT);
{Переводит символы из INPUT в код согласно Chiper
и печатает новые символы в OUTPUT}
CONST
Len = 20;
TYPE
Str = ARRAY [1.. Len] OF ‘A’.. ‘Z’;
Chiper = ARRAY [‘A’.. ‘Z’] OF CHAR;
VAR
Msg: Str;
Code: Chiper;
{Включить PROCEDURE Encode(VAR S: Str);}
{Включить PROCEDURE Initialize(VAR Code: Chiper);}
BEGIN {Encryption}
{Инициализировать Code}
Initialize(Code);
WHILE NOT EOF
DO
BEGIN
{читать строку в Msg и распечатать ее}
I:= 0;
WHILE NOT EOLN AND (I < Len)
DO
BEGIN
I:= I + 1;
READ(Msg[I]);
WRITE(Msg[I])
END;
READLN;
WRITELN;
{дополнить Msg пробелами}
FOR I:= I+1 TO Len
DO
BEGIN
Msg[I]:= ' ';
END
{распечатать кодированное сообщение}
Encode(Msg)
END
END. {Encryption}
Выполнение:
INPUT: NOW IS THE TIME
END
OUTPUT: NOW IS THE TIME
M2T IH *SV *INV
END
VM#
Синтаксис и семантика для массивов.
Следующие синтаксические правила описывают тип данных массив.
<составной тип>::= <неупакованный структурированный тип>
<неупакованный структурированный тип>::= SET OF <базовый тип>
| FILE OF <тип компонентов>
| RECORD <список полей> END
| ARRAY [<список индексного типа>] OF <тип компонентов>
<список индексного типа>::= <список индексного типа>, порядковый тип
| <порядковый тип>
Поскольку значения массивов могут использоваться как другие переменные, определение <переменной> должно быть расширено, чтобы включить их.
<переменная>::= <идентификатор переменной> | <переменная буфера>
| <переменная-компонент>
<переменная-компонент>::= <описатель поля> | <индексированная переменная>
<индексированная переменная>::= <переменная массива> [<список выражений>]
<переменная массива>::= <переменная>
<список выражений>::= <список выражений>, <выражение> | <выражение>
Формально, значения соответствующие переменным массивов в состоянии выполнения являются отношениями. В парах отношения массив-значения первые элементы принадлежат конечному множеству значений индексного типа, а вторые элементы множеству значений типа компонентов. Таким образом, количество возможных значений переменой массива велико. Каждый индекс может находится в паре с любым из возможных значений компонента, так что для N индексов и M возможных значений компонентов, массив может иметь MN значений, каждое из которых представляет из себя соответствие значений индексам. Например, переменная:
VAR
Carray: ARRAY [1..3] OF CHAR;
имеет 1283 ~ 2 100 000 возможных значений для Паскаль-машины со 128 символьными значениями, одним из которых будет {<1, X>, <2, B>, <3, 3>}. Это значение может быть результатом присваивания:
CArray[1]:= ‘X’;
CArray[2]:= ‘B’;
CArray[3]:= ‘3’;
Раз каждый индекс в массиве имеет присвоенный ему компонент, значение массива должно быть функцией. Однако, до тех пор пока индекс остается несвязанным, эта часть массива подобна неинициализированной переменной. Например, если к CArray были применены только первое и третье присваивания, его значение будет:
{<1, X>, <3, 3>}È{ <2, c>: c - символ},
которое мы обычно сокращаем до
{<1, X>, <3, 3> <2,?> }.
Эти значения могут появляться в состоянии выполнения с идентификатором массива.
S = {CArray·{<1, X>, <3, 3> <2,?> },...}
Значение <индексированной переменной> может быть получено может быть получено из значения соответствующего массива. Например для приведенного выше состояния S:
CArray[1](S) = X
В общем, для идентификатора массива A и индекса I, где I принадлежит типу J:
A[I] = {<s, v>: s(I) является значением типа J, v = (s(A))(s(I))}
Определение присваивания (раздел 6.2.1) применимо к массивам без изменений, но не покрывает случай, где элемент массива находится в левой части присваивания. В этом случае присваивание завершается с ошибкой, если значение индекс не является допустимым значением соответствующего типа. Формально, для индекса I типа J:
A[I]:= E = {<s, t>: I(s) является значением типа J, t =s,
за исключением того, что A[I](t)=E(s)}
Во всех других случаях значение выражения становится присоединенным к идентификатору в левой части в состоянии выполнения после выполнения оператора.
Когда оператор присваивания присваивает один идентификатор массива другому идентификатору, его значением становится отношение, представляющее значение массива в целом.
Параметры-массивы.
Целые массивы компонентов могут появляться как фактические параметры в программах. Как и другие составные типы Паскаля, массивы обычно передаются по ссылке как параметры-переменные по соображениям эффективности. Если массив передается как параметр-значение, неявно присутствующая операция копирования должна будет скопировать каждый компонент. Однако, компоненты массивов могут эффективно связываться как с параметрами-значениями так и с параметрами-переменными. Определения раздела 9.1.4 не адекватны для случая алиасинга между индексным идентификатором и компонентом массива с таким индексом, переданным в параметре-значении.
Следующая программа обозначает некоторые сложности, которые могут возникнуть. Index передается параметру First, а Arr[Index] передается параметру Second. Таким образом, возникает алиасинг Second (через индекс Index) к First. First (или Index) инкрементируется до использования Second (или Arr[Index]). Однако, именно значение Arr[2], а не Arr[3] будет изменено, потому что связывание имени фактического параметра с именем формального параметра происходит при вызове процедуры, а не когда параметр-переменная используется.
PROGRAM Bind(INPUT, OUTPUT);
VAR
Arr: ARRAY [1..5] OF INTEGER;
Index: INTEGER;
PROCEDURE IncreaseParams(VAR First, Second: INTEGER);
BEGIN {IncreaseParams}
First:= First + 1;
Second:= Second + 1;
END; {IncreaseParams}
BEGIN {Bind}
FOR Index:= 1 TO 5
DO
BEGIN
Arr[Index]:= 1
END
Index:= 2;
IncreaseParams(Index, Arr[Index]);
WRITELN(‘Index is’, Index:2);
FOR Index:= 1 TO 5
DO
BEGIN
WRITELN(‘Arr[‘, Index:1, ‘] is ‘, Arr[Index]:2)
END
END. {Bind}
Выполнение:
OUTPUT: Index is 3
Arr[1] is 1
Arr[2] is 2
Arr[3] is 1
Arr[4] is 1
Arr[5] is 1
В этом особом случае, когда индекс в массиве и компонент с таким же индексом переданы как параметры-переменные, фактический параметр скопированный в тело процедуры должен иметь его индекс вычисленный в состоянии вызова, а не последующее состояние вычисленное в теле процедуры.