Описание файлов с помощью списков.

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

Если рассмотреть содержимое INPUT как 2-список символьных строк, это формализует разделение на прошлое/будущее и позволяет точно рассуждать о том, что произойдет при выполнении оператора READ. Представим, что INPUT это 2-список L, состоящий из символьных строк. Первая, L1 уже считана (строка прошлого), вторая , L2 – то, что осталось (строка будущего). Таким образом, INPUT представлен спискомL1, L2. Например, если в таблице выполнения строка символов ABC, тогда

L1 = †A†, L2 = †BC† N /

где ./ — используемый нами символ маркера конца строки.

Списковые операции могут быть использованы для того, чтобы дать следующее описание выражениям READ и WRITE для одного символа.

Пусть содержимое INPUT список L =L1, L2, где L2 ¹ ††. Тогда оператор READ(Ch) имеет следующее значение.

Ch присваивается значение ? L2

Содержимое INPUT становитсяL1N ? L2, ? L2

В вышеприведенном примере для READ(Ch), Ch будет иметь следующее значение.

? L2 = ?(†BC† N /) = B

а INPUT будет иметь следующее значение:

L1N ? L2, ? L2

Или, пусть содержимое OUTPUT будети v – значение Ch. Тогда WRITE(Ch) имеет следующее значение: содержимое OUTPUT становится .

Описание файла как 2-списка достаточно точно, но оно не адекватно для описания требований CF Pascal к файловым операциям. Например, оператор READ не может быть выполнен для OUTPUT. Файловые переменные описанные как TEXT, могут считываться и записываться, но в соответствии с определенными правилами. Например, последовательность

REWRITE(F1);

WRITE(F1, Ch);

WRITELN(F1);

RESET(F1);

READ(F1, Ch);

Является допустимой, но

REWRITE(F2);

WRITE(F2, Ch);

READ(F2, Ch);

допустимой не является, потому что к F2 перед выполнением оператора READ должно быть применен оператор RESET.

Для того, чтобы зафиксировать использование фалов формально, в описание файла нужно ввести дополнительную информацию, поэтому мы расширим 2-список до 3-списка, содержащего строку прошлого, строку будущего и состояние файла, которое может быть символом R или W, которые обозначают доступен ли файл для чтения или для записи.

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

Исходное состояние	Применяемая операция и новое состояние файла
RESET	REWRITE	READ/READLN	WRITE/WRITELN
R	R	W	R
W	R	W		W

Например, если состояние файла R, выражение REWRITE переводит его в состояние W. Пустая ячейка под READ/READLN c строке W означает, что в состоянии W к файлу неприменимы операции чтения.

В следующей таблице приведены значения для выражений READ и WRITE и использованием значений файлов в форме 3-списка. Таблица не описывает недопустимые комбинации.

	F1	Ch(изначально v)
до	после
REWRITE(F1)
WRITE(F1, Ch)			v
WRITELN(F1, Ch)			v
RESET(F1)
READ(F1, Ch)			?(yN/)
READLN(F1)	(y не содержит /)		?(yN/)

Например, первая строка в таблице представляет значение выражения REWRITE. Оно преобразует состояниевдля любых строк x, y и состояния файла t.

Таблица выполнения ниже демонстрирует успешные операции над файлами в форме 3-списка.

	F1	Ch
VARCh:CHAR;F1: TEXT;BEGINCh := ‘A’;REWRITE(F1);WRITE(F1, Ch);Ch := ‘B’;WRITELN(F1);RESET(F1);READ(F1, Ch);READ(F1, Ch);END.	?	?ABA?

После первого оператора READ EOLN принимает значение TRUE, после последнего оператора READ EOF становится TRUE, и если бы программа выполнила еще один оператор READ, то произошло бы аварийное завершение ее работы.

Множества

Множества – наборы объектов, где не имеет значение порядок и повторяемость элементов. Множества это основное математическое понятие, на котором базируются отношения и функции.

Новые идеи: Множество, принадлежность множеству, подмножество, мощность множества, операции над множествами, объединение, пересечение, разность (различность).

Строки и списки – это наборы объектов, к которых порядок и повторение элементов имеют значение. Набор данных, в котором порядок и повторение элементов не имеет значения называется множеством. Во множестве элементы просто сгруппированы и никакой не является первым или следующим и не повторяется.

Элементы множества записываются в фигурных скобках. Конечно, элементы множества имеют определенный порядок при записи, но он не существенен. Например:

{A, B} и {B, A} описывают одно и то же множество.

Любой список задает множество, элементами которого являются элементы списка (множество элементов списка). Например, список

L =

Имеет множество его элементов

S = {†th†, †is †, †a †, †list example†}

В котором повторяющийся элемент †is † появляется только один раз. Поскольку порядок элементов не имеет значения, это же множество может быть записано в виде

S = {†list example†, †a †, †is †,†th† } = {†th†, †a †, †list example†, †is †}

Мы будем упоминать размер, говоря о множествах, например S можно назвать 4-множеством.

Элементы множества не обязательно должны быть одного типа, например следующее 3-множество

{A, †mixed†, }

содержит элемент символ, строку, и 2-список, который в свою очередь содержит строку и 2-множество, элементы которого являются строками.

Фундаментальная связь между элементом и множеством является его принадлежность данному множеству, для обозначения используется символ I. В примере приведенном выше

†list example† I S

но

†list † I S

Множество, не имеющее элементов называется пустым множеством и записывается {}. Пустое множество отличается от пустого списка . Например дляможет быть выполнена конкатенация с другим списком, но это невозможно для {}. 1-множество называется одиночка (singleton). 1-множество отличается от его единственного элемента, и от списка с таким элементом. Например:

†string† ¹ {†string†} ¹

Множество S является подмножеством T, S I T , если каждый элемент S является элементом T. Таким образом, S I T если и только если для каждого x, x I T если x I S.

Множества S и T равны, S = T, если им принадлежать одни и те же элементы. Таким образом, S = T, если и только если S I T и T I S.

Пустое множество является подмножеством любого множества, включая себя самого, поскольку оно не имеет элементов, то значит в нем нет элемента, которого может не оказаться в любом другом множестве. Таким образом {} I S, для любого S.

Если множества S и T не имеют общих элементов, то говорят, что они не пересекающиеся.

Статьи к прочтению:

КС | 3.4. Вывод списка файлов и каталогов [Dir]

Похожие статьи: