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

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

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

L_{1 =} †A†, L_{2 =} †BC† Ñ /

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

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

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

Ch присваивается значение Θ L₂

Содержимое INPUT становится < L₁Ñ Θ L₂, Λ L₂>

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

Θ L_{2 =} Θ(†BC† Ñ /) = B

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

< L₁Ñ Θ L₂, Λ L₂>

= <†A†Ñ Θ (†BC† Ñ /), Λ (†BC† Ñ /)>

= <†A†Ñ B), †C† Ñ /)>

= <†A B†), †C† Ñ /)>

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

Описание файла как 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)	<x, y, t>	<††, ††, W>
WRITE(F1, Ch)	<x, ††, W>	<xÑv, ††, W>	v
WRITELN(F1, Ch)	<x, ††, W>	<xÑvÑ/, ††, W>	v
RESET(F1)	<x, y, t>	<††, x&y, R>
READ(F1, Ch)	<x, yÑ/, R>	<xÑ(Θ(yÑ/)), Λ(yÑ/), R>	Θ(yÑ/)
READLN(F1)	<x, (yÑ/)&z, R> (y не содержит /)	<x&(yÑ/), z, R>	Θ(yÑ/)

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

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

	F1	Ch
VAR Ch:CHAR; F1: TEXT; BEGIN Ch := ‘A’; REWRITE(F1); WRITE(F1, Ch); Ch := ‘B’; WRITELN(F1); RESET(F1); READ(F1, Ch); READ(F1, Ch); END.	?     <††, ††, W> <†A†, ††, W>   <†A†Ñ /, ††, W> <††, †A†Ñ /, R> <†A†, ††Ñ /, R> <†A†Ñ /, ††, R>	?     A     B     A □

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

Множества

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

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

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

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

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

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

L = <†th†, †is †, †is †, †a †, †list example†>

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

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

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

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

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

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

{A, †mixed†, <†can†, {†of†, †beans†}>}

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

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

†list example† Î S

но

†list † Ï S

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

†string† ¹ {†string†} ¹ <†string†>

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

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

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

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