52 ]. Фундаментальные структуры банных

- - --

Однако существует структура, которая является усло>к, ненной, поскольку ее кардинальное число не ограничено, щ которая так щироко и часто используется, что ее приходите^ включить в число фундаментальных структур. Это - после, довательность. Для описания абстрактного понятия последо. вательности мы вводим следующую терминологию и нотацию;

1. < > обозначает пустую последовательность.

2. <хо> обозначает последовательность, состоящую из един, ственной компоненты хо, она называется единичной последовательностью.

3. Если X = <,хи ХтУ ч у = iyi.....Fn> - последовательности, то

--.-Х&У^{Х].....JCn Vi.....Ц„) (1.41)

есть конкатенация х и у.

4. Если X = <xi, ..., ХпУ - непустая последовательность, го

first (x) = xi (1.42)

обозначает первый элемент х. Б. Если X = <xi, ..., ХпУ - непустая последовательность, го

rest{x) = (x2, Хп) .(1.43)

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

(first (х)) & rest {х)х (1.44)

Введение этих обозначений не предполагает, что они будут использоваться в конкретных программах и обрабатываться реальными вычислительными мащинами. В действительности весьма существенно, что операция конкатенации не используется в общем виде и обработка последовательностей ограничивается применением тщательно отобранного множества операций, предполагающих определенный порядок использования. Сами операторы определяются с помощью абстрактных понятий последовательности и конкатенации. Тщательный выбор множества операторов, работающих с последовательностями, позволяет при реализации находить удобное и эффективное представление последовательности на любом данном запоминающем устройстве. В результате соответствующий механизм динамического распределения памяти может быть достаточно простым, что позволяет программист) работать, не вникая в его тонкости.

. Для того чтобы было ясно, что последовательность, вво димая в качестве базового типа, допускает применение только ограниченного множества операторов, основанных строго последовательном доступе к компонентам, эта стрУ

type Г = file of Го

(1.45)

Это значит, что любой файл типа Т состоит из О или более компонент типа То. - .

Примеры:

type/ех == file of сЛаг

type deck - file of card

Смысл последовательного доступа заключается в том, что в каждый момент доступна лишь одна определенная компонента последовательности. Эта компонента определяется текущей позицией механизма доступа. Позиция с помощью файловых операций может меняться, определяя либо следующую компоненту (см. get), либо первую компоненту всей последовательности (см. reset). Формально мы определим позицию файла, считая, что файл состоит из двух частей: части Xl слева от текущей позиции и части хц справа от нее. Очевидно, что всегда справедливо равенство (инвариант)

xxi&xj, (1.46)

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

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

Некоторые запоминающие устройства на самом деле до- Ускают только последовательный доступ к находящейся на Их информации. Очевидно, что к таким устройствам отно-

называется последовательным файлом или просто фай-По аналогии с определениями типа для массивов и мно-есг^ файловый тип определяется так:

означает присваивание

которое фактически добавляет значение xf к последов тельности х. 3. Инициация просмотра. Операция

reset (х) (1.4Sl

означает одновременные присваивания

xi>:=x

х\ := first (х)

сятся все виды лент. Но даже на магнитных барабанах и д^, , ках каждая отдельная дорожка представляет собой sanobji нающее устройство с последовательным доступом. Строго следовательный доступ - основное свойство всех устройс), с механическим перемещением, а также некоторых других

1.11.1. Элементарные операции над файлами

Теперь мы попытаемся сформулировать абстрактное тщ тие последовательного доступа с помощью некоторого мно жества элементарных операций над файлами, KOTopii имеются в распоряжении программиста. Они определяютс! в терминах понятий последовательности и конкатенации. Су ществует операция, инициализирующая процесс формировав ния аила, отшрацин, инициализирующаянросмотр, опера, ция, добавляющая компоненту в конец последовательности, и операция, позволяющая при просмотре переходить к сле^, дующей компоненте. Две последние здесь определяютс8 в форме, предполагающей наличие явной вспомогательно! переменной, которая представляет собой буфер. Мы считаем что такой буфер автоматически связывается с каждой фаир ловой переменной х, и обозначаем его через х\. Ясно, чта^ если X - типа Т, то к\ принадлежит его базовому типу Zj

1. Построение пустой последовательности. Операция

rewrite {х) (1.47

означает присваивание

х - ( >

Эта операция используется для уничтожения текущего зна* чения X и инициации процесса построения новой последо^ вательности, она соответствует разметке ленты.

2. Увеличение последовательности. Операция

рШ(х) (lAh