Трассировка программы

Очевидно, в ходе выполнения вычислений согласно некоторой блок-схеме для каждого входного состояния S выбирается некоторая ветка блок-схемы, т.е. последовательность операторных блоков S₁, …, S_n. Последовательность значений S₁(S), S₂S₁(S), …, S_nS_n-1…S₁(S) называется трассой выполнения.

Понятие трассы используется для трассировки - проверки работы алгоритмов путем выписывания трассы для данного входного состояния.

x,y:=y,x

x:=X y:=Y

x:=x•y y:=x/y x:=x/y

z:=x x:=y y:=z

x:=x+y y:=x-y x:=x-y

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

Структурное программирование

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

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

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

Структурный подход к программированию выделяет три операторных конструкции (структуры):

1. Композиция

Если S₁ и S₂ – допустимые блок-схемы, то S₁→ S₂ также допустима.

С труктура полного условного оператора. Блок-схема – определение (процедуры вычисления) оператора, состоящая из

- операторных блоков в квадратах,

- предикатных блоков в ромбах,

- значков Н (начало вычисления), К (конец вычисления) и

- соединяющих их стрелок.

При этом в операторный блок могут входить несколько стрелок, а выходит единственная. В условный блок входит несколько стрелок, а выходит – две, помеченных знаками + и -, соответствующих значениям true и false. Из значка Н выходит единственная стрелка, не входит ни одна. В значок К входит единственная стрелка, не выходит ни одна.

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

Программы, как файловые процедуры

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

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

Файлы обеспечивают хранение больших объемов данных, предназначенных (как правило) для долговременного хранения, но обеспечивают относительно низкую скорость обмена с оперативной памятью.

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

Определим эти понятия формально, как тип данных.

Множеством значений потока является множество всех последовательностей неопределенной длины < a_1,…, a_i,…,a_n> , где a_i элементы некоторого базового типа d. На каждый момент времени один из них считается текущим значением. Обозначим его через a_i , а номер i назовем маркером (потока).

На входных потоках определена функция распознавания конца потока eof(f). Эта функция принимает значений true в случае, если i>n .

Оператор чтения из потока read(f,x) определяется следующим образом:

{f→<a₁, …, a_n>, iI, eof(f)→false}

read(f,x)

{f→<a₁, …, a_n>, x→a_i, iI+1}

При eof(f)=true выполнение оператор read не определено.

Для файлов определен также оператор reset(f):

{} Reset(f) {i1}

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

Частный случай – структура укороченного условного оператора:

3. Структура цикла с предусловием

М ножество трасс такой структуры описывается просто: S1(x), S1(S1(x)),… S1(S1(S1(x))),…

Результатом S(x) выполнения оператора является S1^k(x), где i₀ – наименьший номер такой, что условие B называют условием продолжения цикла, а оператор S – телом цикла.