Составные типы данных в D Pascal
Эта глава описывает три механизма создания составных значений в Паскале: множества, файлы и записи. Предлагается ограниченная версия множеств. Файлы расширяют текстовые фалы CF Pascal до фалов иных, чем CHAR типов. Записи предлагают механизм группировки для любого конечного набора типов.
Каждый порядковый тип содержит значения, которые являются атомарными – их значения не являются составными, поэтому неделимы. Составные типы данных, в свою очередь комбинируют ранее определенные типы, которые могут быть порядковыми или составными типами, в новые типы, которые содержат компоненты ранее определенных типов.
<новый тип>::= <новый порядковый тип> | <составной тип>
<составной тип>::= <структурированный тип>
<структурированный тип>::= SET OF <базовый тип>
| FILE OF <тип компонентов>
| RECORD <список полей> END
<базовый тип>::= <порядковый тип>
<порядковый тип>::= <новый порядковый тип> | <идентификатор порядкового типа>
<идентификатор порядкового типа>::= <идентификатор типа>
<тип компонентов>::= <описатель типа>
Множества, файлы и записи хранят компонентные типы разными способами. Множества и файловые типы хранят компоненты одинаковых типов, а записи – разных. Типы множеств и записей хранят компоненты без учета порядка, тогда как файловые типы образуют последовательности компонентов. Любой компонент записи может быть произвольно выбран, доступ к компонентам файла осуществляется последовательно. Для множеств операция выбора не определена.
Множества.
Тип данных множество позволяет программисту объявлять и использовать переменные, которые являются множествами, элементы которых хранятся в небольших, ограниченных наборах данных. Полный набор операций над множествами не поддерживается.
|
|
Тип данных множество определяется следующим образом:
TYPE
SetType = SET OF ComponentType;
где ComponentType является порядковым типом. Множества Паскаля ограничены по количеству хранимых элементов, максимальный размер такого набора данных не является частью спецификации Паскаля и зависит от реализации Паскаль-машины. Обычно это несколько сотен. Таким образом недопустимо следующее объявление.
TYPE
IntSet = SET OF INTEGER;
но допустимо
CONST
Max = 20;
TYPE
IntSet = SET OF 0.. Max;
Если Max выбрано достаточно небольшим, чтобы быть в установленных пределах. Объявление не обеспечивают начальных значений переменной множества, таким образом значение Sieve после
VAR
Sieve = SET OF 0.. Max;
неопределено.
Константы множеств описываются через перечисление значений множества, заключенные в квадратные скобки. Множество содержащее пустой список значений используется для представления пустого множества.
Возможные значения множества являются членами множества мощности (powerset), множества всех подмножеств набора значений использованного для определения типа. Например множество мощности для типа
TYPE
SmallIntSet = SET OF 1.. 3;
будет
{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
т.е. любые из этих множеств могут являться значениями типа SmallIntSet.
Константа множества с тремя элементами может быть записана как [1, 2, 3] или [ 1.. 3]
Любое из следующих присваиваний инициализирует Sieve значением {2, 3,..., 19, 20}:
Sieve:= [2.. 20];
Sieve:= [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
|
|
Sieve:= [2.. 9, 10, 11.. 15, 16, 17, 18.. 20];
Операциями над значениями типа множеств являются
+ (объединение множеств),
– (разность множеств),
* (пересечение множеств)
= (эквивалентность),
<> (неэквивалентность),
<= (нестрогое подмножество),
>= (нестрогое надмножество),
IN (членство в множестве).
| Операция | Операнды -> Результат |
| + – * | SET X SET -> SET |
| = <> <= >= | SET X SET -> BOOLEAN |
| IN | ComponentType X SET -> BOOLEAN |
| [ ] | ComponentType X ComponentType -> SET |
Операции объединения, разности и пересечения множеств определены только для пар множеств, но не для компонентов множеств. Таким образом, если Sieve имеет целые значения, недопустимо писать:
Sieve + 2
Вместо этого элемент может быть оформлен как значение типа 1-множество:
Sieve + [2]
Примеры выражений и их значения
| Выражение | Значение |
| [3, 5] <= [3.. 5] | TRUE |
| [3.. 5] <= [3.. 6] | TRUE |
| [3.. 5] >= [3.. 5] | TRUE |
| [3.. 5] >= [3.. 6] | FALSE |
Бинарный инфиксный оператор IN проверяет членство в множестве:
| Выражение | Значение |
| 4 IN [3.. 5] | TRUE |
| 4 IN [] | FALSE |
| 4 IN [3, 5] | FALSE |
Квадратные скобки используются не только для обозначения констант множеств, но и для формирования множеств из выражений, чьи значения являются элементами множеств. Например, если X имеет тип INTEGER и значение 3:
| Выражение | Значение |
| [2, X] | {2, 3} |
| [3.. X[] | {3} |
| [X.. X+2, SUCC(X+7)] | {3, 4, 5, 11} |
| [X.. 1] | {} |
Свойства операторов для множеств
| Оператор | Ассоциативность | Приоритет |
| [ ] | Нет | Высший |
| * | Левая | |
| + – | Левая | |
| сравнения | Нет | Низший |
Ниже приведено вычисление примеров множеств в нотации констант множеств Паскаля:
|
|
[1] + [7.. 9] * [7, 9] = [1] + [7, 9] = [1, 7, 9]
[4.. 6] – [4, 6] + [1] = [5] + [1] = [5, 1]
Правила синтаксиса и Значение.
Синтаксические правила для выражений с операциями над множествами приведены ниже.
<выражение>::= <простое выражение>
| <простое выражение> <оператор сравнения> <простое выражение>
<простое выражение>::= <простое выражение> <аддитивный оператор > <терм>
| <терм> | <знак> <терм>
<терм>::= <терм> <мультипликативный оператор> <множитель> | <множитель>
<множитель>::= <идентификатор> | <вызов функции>
|<беззнаковая константа> | (<выражение>)
| NOT <множитель> | <выражение множества>
<оператор сравнения>::= = | <> | < | <= | > | >= | IN
<знак>::= + | –
<аддитивный оператор>::= + | – | OR
<мультипликативный оператор>::= * | DIV | MOD | AND
<выражение множества>::= [<описатели элементов>]
<описатели элементов>::= <описатели элементов>, <описатель элементов> |
<описатель элементов>::= <выражение> | выражение.. выражение
Значение каждой операции между операндами-множествами и операндом-элементом может быть представлено в терминах обычных математических операторов
E1 = E2 (s) = (E1 (s) = E2 (s))
E1 <> E2 (s) = (E1 (s) ¹ E2 (s))
E1 <= E2 (s) = (E1 (s) Í E2 (s))
E1 >= E2 (s) = (E1 (s) Ê E2 (s))
Me IN E2 (s) = (E1 (s) Î E2 (s))
E1 + E2 (s) = (E1 (s) È E2 (s))
E1 – E2 (s) = (E1 (s) – E2 (s))
E1 * E2 (s) = (E1 (s) Ç E2 (s))
[Me] (s) = {Me (s)}
(E) (s) = E (s)
для любого состояния s. Для более сложных выражений порядок выполнения операций задается правилами синтаксиса, ассоциативности и предшествования.
Файлы.
Файлы являются упорядоченными последовательностями значений. Операторы WRITE добавляют значения к существующей последовательности (всегда в конец), операторы READ могут получать значения в той же последовательности, в которой они были ранее считаны. Значения не ограничены типом CHAR как в текстовых файлах, но могут быть представлены почти любым типом Паскаля. Буферные переменные и операторы PUT/GET предлагают дополнительные способы управления файлами.
Дополнительно к текстовым файлам, Паскаль позволяет нам определять новые файловые типы с компонентами любого ранее объявленного типа за исключением тех агрегатных типов, в которые входят файлы. Типичное объявление файлового типа:
VAR
IntFile: FILE OF INTEGER;
Значение IntFile является последовательностью значений типа INTEGER – только значения типа INTEGER могут быть считаны из или записаны в такой файл. Файловые переменные – единственный тип переменных Паскаля, которые не могут участвовать в операторах присваивания. Все файловые значения должны быть созданы с использованием преопределенных операций.
Объявление файловой переменной неявно объявляет буферную переменную, записываемую как файловый идентификатор, за которым следует стрелка вверх (например, IntFile^) того же типа, что и компоненты файла. Когда мы читаем файл, IntFIle^ содержит значение доступное для считывания. Новые элементы файла добавляются в файл заполнением буферной переменной и записью ее содержимого. Буферные переменные могут появляться везде, где появляются другие переменные. Например:
3 + IntFile^ * 7
Однако, буферные переменные не являются идентификаторами, поскольку завершаются на символ, который не является символом или цифрой. Таким образом, мы должны исправить наши синтаксические правила, заменив <идентификатор> в правой части правила для <множителя> на <ссылка на переменную>, которая покрывает идентификаторы и буферные переменные.
<множитель>::= <ссылка на переменную> | <вызов функции>
|<беззнаковая константа> | (<выражение>)
| NOT <множитель> | <выражение множества>
<ссылка на переменную>::= <идентификатор переменной> | <буферная переменная>
<буферная переменная>::= <файловая переменная>^
<файловая переменная>::= <ссылка на переменную>
Хотя синтаксические правила показывают, что идентификатор, за которым следует некоторое количество символов ^ является файловой переменной, фактически только один символ ^ может появляться.
Значения текстовых файлов – 3-списки. Первые два элемента которых строки будущего и прошлого файла. Для произвольных файлов значения прошлого и будущего – это списки элементов типа которым объявлен тип. Третий элемент – индикатор режима, который показывает, открыт ли файл для чтения или записи.
Поскольку объявление файловой переменной вводит буферную переменную семантика операторов объявления для файлов должна быть изменена для того, чтобы учесть буферную переменную.
VAR F: FILE OF TypeT (s) = s È {F <?,?,?>}
Нетекстовые файлы.
Файлы – это последовательности элементов одного типа. Операции над файлами перечислены ниже.
| Операция | Тип операнда -> Тип результата |
| REWRITE | FILE -> void |
| PUT | FILE -> void |
| RESET | FILE -> void |
| GET | FILE -> void |
| EOF | FILE -> BOOLEAN |
Термин void (пустой) обозначает, что эти операции не возвращают значение, эти операции похожи на операторы процедур Паскаля и могут появляться везде, где может появляться оператор. Действие этих операций на состояние файла представлено конечным автоматом ниже, который имеет два состояния R и W.
 |
Начальные RESET или REWRITE устанавливают файл в режим R или W.
REWRITE и PUT используются для построения файловых значений. REWRITE очищает файл и готовит его для записи.
REWRITE(F) = {(u,v): F не INPUT или OUTPUT и v = u за исключением того,
что v(F) = <<>, <>, W>}
Если файл открыт для записи, PUT добавляет значение переменной в буфере к файлу и оставляет значение переменной буфера неопределенной.
PUT(F) = {(u,v): u(F).3 = W и v = u, за исключением того, что v(F).1 = u(F).1Ñ(u(F^)) и v(F^) неопределено}
PUT неопределен, когда файл не открыт для чтения.
Например, для записи файла целых чисел, он должен быть объявлен и инициализирован.
VAR
IntList: FILE OF INTEGER;
BEGIN
REWRITE(IntList);
...
END
Значения присваиваются IntList^ таким образом, чтобы следующий оператор PUT добавит значение в IntList.
{Эквивалентно WRITE(IntList, 1)}
IntList^:= 1;
PUT(IntList); {Добавляет 1 в IntList, IntList^ неопрелен}
{Эквивалентно WRITE(IntList, 2)}
IntList^:= 2;
PUT(IntList); {Добавляет 2 в IntList, IntList^ неопрелен}
В этой точке IntList содержит значения 1 и 2 в списке прошлого, файл открыт для записи и содержимое IntList^ неопределено.
IntList = <<1, 2>, <>, W> и IntList^ неопределено
RESET и GET – операции, которые читают значения из файлов. RESET возвращет указатель файла в стартовую позицию для того, чтобы можно было начать чтение. Значению переменной файлового буфера присваивается значение первого компонента в списке будущего файл, если таковой имеется.
RESET(F) = = {(u,v): F не INPUT или OUTPUT и v = u за исключением того,
что v(F) = <<>, u(F).1 & u(F).2, R> и v(F^) = Θ(u(F).1 & u(F).2)}
Поскольку Θ не определена на пустых списках, значение переменной буфера также не определено, когда RESET применяется к пустому файлу.
Если файл открыт для чтения и его список будущего не пустой, GET переносит первый элемент списка будущего в список прошлого и присваивает значение нового первого элемента списка будущего переменной буфера.
GET(F) = {(u,v): u(F).3 = R и u(F).2 ¹ <> и v=u, за исключением того,
что v(F).1 = u(F).1 Ñ(Θ (u(F.2))), v(F).2 = Λ (u(F.2)), и v(F^) = Θ (Λ (u(F.2)))}
Если файл не открыт для чтения, программа при вызове GET выдает ошибку времени выполнения, также ошибка произойдет, если не осталось данных для считывания (список будущего пуст).
Записи.
Когда в программе должен быть использован сложный объект данных, удобно иметь общее имя для данных, которые его описывают и объявлять его без явного перечисления имен его частей. Записи Паскаля позволяют дать однажды описание объекта и использовать его далее по общему имени или по именам частей.
Записи позволяют группировать некоторое количество связанных данных, возможно разных типов, в один объект. Каждый элемент данных, называемых полем, состоит из имени, двоеточия и типа.
В следующем примере описано два типа записей, Date и WorkerInfo, каждый из которых содержит три поля. Некоторые из полей WorkerInfo таже являются записями. Таким образом, для описания сложных объектов, записи могут быть вложенными.
TYPE
Month = (NoMonth, Jan, Feb, Mar, Apr, May, Jun,
Jul, Aug, Sep, Oct, Nov, Dec);
DayNum = 1.. 31;
ValidYear = 1850.. 2050;
Date = RECORD
Mo: Month;
Day: DayNum;
Year: ValidYear;
END;
WorkerInfo = RECORD
SSNumber: INTEGER;
BirthDay: Date;
FirstHired: Date;
END;
Когда переменная объявляется с типом записи, ее имя ссылается на всю запись. Как общее имя переменная полезна, например при передаче параметров в процедуру. Однако для манипулирования частями записи нужны другие имена. Поля могут именоваться добавлением их имен из определения типа с именем переменной через точку. Например, переменная
VAR
Worker: WorkerInfo;
описывает Worker как запись с тремя полями SSNumber, BirthDay и FirstHired. Имена частей этой переменной будут
Worker.SSNumber
Worker.BirthDay
Worker.FirstHired
Первый элемент является атомарным и ему может быть присвоено значение
Worker.SSNumber = 123456789;
Две другие части являются записями и мы должны обращаться к их частям.
Worker.BirthDay.Mo = Feb;
Worker.FirstHired.Day = 22;