Список как математическая идея хорошо при описании файлов. Рассмотрим INPUT. При выполнении программы, нам необходимо знать только две вещи про INPUT: какая часть данных уже прочитана и какая осталась. В таблицах выполнения это разделение отмечалось курсором.
Если рассмотреть содержимое INPUT как 2-список символьных строк, это формализует разделение на прошлое/будущее и позволяет точно рассуждать о том, что произойдет при выполнении оператора READ. Представим, что INPUT это 2-список L, состоящий из символьных строк. Первая, L1 уже считана (строка прошлого), вторая, L2 – то, что осталось (строка будущего). Таким образом, INPUT представлен списком < L1, L2>. Например, если в таблице выполнения строка символов ABC, тогда
L1 = †A†, L2 = †BC† Ñ /
где./ - используемый нами символ маркера конца строки.
Списковые операции могут быть использованы для того, чтобы дать следующее описание выражениям READ и WRITE для одного символа.
Пусть содержимое INPUT список L = < L1, L2>, где L2 ¹ ††. Тогда оператор READ(Ch) имеет следующее значение.
Ch присваивается значение Θ L2
Содержимое INPUT становится < L1Ñ Θ L2, Λ L2>
В вышеприведенном примере для READ(Ch), Ch будет иметь следующее значение.
Θ L2 = Θ(†BC† Ñ /) = B
а INPUT будет иметь следующее значение:
< L1Ñ Θ L2, Λ L2>
= <†A†Ñ Θ (†BC† Ñ /), Λ (†BC† Ñ /)>
= <†A†Ñ B), †C† Ñ /)>
= <†A B†), †C† Ñ /)>
Или, пусть содержимое OUTPUT будет <L1, ††> и v – значение Ch. Тогда WRITE(Ch) имеет следующее значение: содержимое OUTPUT становится <L1 Ñ 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 не имеют общих элементов, то говорят, что они не пересекающиеся.
