М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

L1: jump_gt R1,R2,L2 Завершить цикл, если больше

statement

incr R1 Увеличить индексный регистр

jump L1

L2:

Рассмотрим теперь простой цикл в языке С:

for (i = expression_1 ; expression_2; i++)

statement;

Это компилируется в

compute R1,expr_1

store R1,i Нижняя граница индексации

L1: compute R2,expr_2 Верхняя граница внутри цикла!

jump_gt R1,R2,L2 Завершить цикл, если больше

statement Тело цикла

load R1,i Увеличить индекс

incr R1

store R1,i

jump L1

L2:

Обратите внимание, что выражение expression_2, которое может быть очень сложным, теперь вычисляется внутри цикла. Кроме того, выражение expres-sion_2 обязательно использует значение индексной переменной i, которая из­меняется при каждой итерации. Таким образом, оптимизатор должен уметь выделить неизменяющуюся часть вычисления выражения expression_2, что­бы вынести ее из цикла.

Можно ли хранить индексную переменную только в регистре для увеличения эффективности? Ответ зависит от двух свойств цикла. В Ada индексная пере­менная считается константой и не может изменяться программистом. В языке С индексная переменная — это обычная переменная; она может храниться в реги­стре только в том случае, когда абсолютно исключено изменение ее текущего значения где-либо вне цикла. Никогда не используйте глобальную переменную в качестве индексной переменной, потому что другая процедура может прочи­тать или изменить ее значение:

int i;

void p2(void) {

i = i + 5;

}

void p1(void) {

for (i=0; i<100; i++) /* Глобальная индексная переменная */

p2(); /* Побочный эффект изменит индекс*/

}

Второе свойство, от которого зависит оптимизация цикла, — потенциальная возможность использования индексной переменной за пределами цикла. В Ada индексная переменная неявно объявляется for-оператором и недоступна за пределами цикла. Таким образом, независимо от того, как осуществляется выход из цикла, мы не должны сохранять значение регистра. Рассмотрим сле­дующий цикл поиска значения key в массиве а:

inta[100];

int i, key;

key = get_key();

for(i = 0;i< 100; i++)

if (a[i] == key) break;

process(i);

Переменная i должна содержать правильное значение независимо от спо­соба, которым был сделан выход из цикла. Это может вызывать затруднения при попытке оптимизировать код. Обратите внимание, что в Ada требуется явное кодирование для достижения того же самого результата, потому что ин­дексная переменная не существует вне области цикла:

Found: Integer := False;

for I in 1 ..100 loop

if A(l) = Key then

Found = I;

exit;

end if;

end loop;

Определение области действия индексов цикла в языке C++ с годами меня­лось, но конечное определение такое же, как в Ada: индекс не существует вне области цикла:

for(int i=0;i<100;i++){

// Индексная переменная является локальной для цикла

}

На самом деле в любом управляемом условием операторе (включая, if- и switch-операторы) можно задать в условии несколько объявлений; область их действия будет ограничена управляющим оператором. Это свойство может способствовать читаемости и надежности программы, предотвращая непред­намеренное использование временного имени.

6.5. «Часовые»

Следующий раздел не касается языков программирования как таковых; ско­рее, он предназначен для того, чтобы показать, что программу можно улуч­шить за счет более совершенных алгоритмов и методов программирования, не прибегая к «игре» на языковых частностях. Этот раздел включен в книгу, по­тому что тема выхода из цикла при последовательном переборе является пред­метом интенсивных дебатов, однако существует и другой алгоритм, который является одновременно ясным, надежным и эффективным.

В последнем примере предыдущего раздела (поиск в массиве) есть три ко­манды перехода в каждой итерации цикла: условный переход цикла for, услов­ный переход if-оператора и переход от конца цикла обратно к началу. Пробле­ма поиска в данном случае состоит в том, что мы проверяем сразу два условия: найдено ли значение key и достигнут ли конец массива? Используя «часового» (sentinel) *, мы можем два условия заменить одним. Идея состоит в том, чтобы ввести в начале массива дополнительно еще один элемент («часового») и хра­нить в нем эталонное значение key, которое нужно найти в массиве (рис. 6.4).

Поскольку мы обязательно найдем key либо как элемент массива, либо как искусственно введенный элемент, постольку достаточно проверять только од­но условие внутри цикла:

type А_Туре is array(0 .. 100) of Integer;

-- Дополнительное место в нулевой позиции для «часового»

function Find_Key(A: A_Type; Key: Integer)

return Integer is

I: Integer := 100; -- Поиск с конца

begin

A(0) := Key; -- Установить «часового»

while A(l) /= Key loop

I:=I-1;

end loop;

return I;

end Find_Key;

Если при возврате управления из функции значение I равно нулю, то Key в

массиве нет; в противном случае I содержит индекс найденного значения.

Этот код более эффективен, цикл чрезвычайно прост и может быть легко про-

верен.

6.6. Инварианты

Формальное определение семантики операторов цикла базируется на кон­цепции инварианта: формулы, которая остается истинной после каждого вы­полнения тела цикла. Рассмотрим предельно упрощенную программу для вы- числения целочисленного деления а на b с тем, чтобы получить результат у:

у = 0;

х = а;

while (х >- b) { /* Пока b «входит» в х, */

х -= b; /* вычитание b означает, что */

у++; /* результат должен быть увеличен */

}

и рассмотрим формулу:

a = yb +х

где курсивом обозначено значение соответствующей программной перемен­ной. После операторов инициализации она, конечно, будет правильной, по­скольку у = 0 и х = а. Кроме того, в конце программы формула определяет, что у есть результат целочисленного деления а/b при условии, что остаток х мень­ше делителя b.

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

(у + \)b + (х-b)=уb+b+х-b=уb+х=а

Таким образом, выполнение тела цикла переводит программу из состояния, которое удовлетворяет инварианту, в другое состояние, которое по-прежнему удовлетворяет инварианту.

Теперь заметим: для того чтобы завершить цикл, булево условие в цикле while должно иметь значение False, то есть вычисление должно быть в таком состоянии, при котором --(х > b), что эквивалентно х < b. Объединив эту фор­мулу с инвариантом, мы показали, что программа действительно выполняет целочисленное деление.

Точнее, если программа завершается, то результат является правильным. Это называется частичной правильностью. Чтобы доказать полную правиль­ность, мы должны также показать, что цикл завершается.

Это делается следующим образом. Так как во время выполнения програм­мы b является константой (и предполагается положительной!), нам нужно по­казать, что неоднократное уменьшение х на b должно, в конечном счете, при­вести к состоянию, в котором 0 < х < b. Но 1) поскольку х уменьшается неод­нократно, его значение не может бесконечно оставаться больше значения b; 2) из условия завершения цикла и из вычисления в теле цикла следует, что х никогда не станет отрицательным. Эти два факта доказывают, что цикл дол­жен завершиться.

Инварианты цикла в языке Eiffel

Язык Eiffel имеет в себе средства для задания контрольных утверждений вооб­ще (см. раздел 11.5) и инвариантов циклов в частности:

from

у = 0; х = а;

invariant

а = yb + х

variant

х

until

x< b

loop

x :=x-b;

у:=у+1;

end

Конструкция from устанавливает начальные условия, конструкция until зада­ет условие для завершения цикла, а операторы между loop и end образуют те­ло цикла. Конструкция invariant определяет инвариант цикла, а конструкция variant определяет выражение, которое будет уменьшаться (но останется неот­рицательным) с каждой итерацией цикла. Правильность инварианта проверя­ется после каждого выполнения тела цикла.

6.7. Операторы goto

В первоначальном описании языка Fortran был только один структурирован­ный управляющий оператор: оператор do, аналогичный циклу for. Все осталь­ные передачи управления делались с помощью условных или безусловных пе­реходов на метки, т. е. с помощью операторов, которые называются goto:

if(a.eq.b)goto12

…

goto 5

4 …

…

12 …

…

5 …

if (x .gt. y) goto 4

В 1968 г. Э. Дейкстра написал знаменитое письмо, озаглавленное «оператор goto следует считать вредным», с которого началась дискуссия о структур­ном программировании. Основной аргумент против goto состоит в том, чтс произвольные переходы не структуированы и создают «программу-спагет­ти», в которой возможные пути выполнения так переплетаются, что ее не­возможно понять и протестировать. Аргументом в пользу goto является то что в реальных программах часто требуются более общие управляющие структуры, чем те, которые предлагают структурированные операторы, и чтс принуждение программистов использовать их приводит к искусственному и сложному коду.

Оглядываясь назад, можно сказать, что эти дебаты были чересчур эмоцио­нальны и затянуты, потому что основные принципы совсем просты и не тре­буют долгого обсуждения. Более того, в современные диалекты языка Fortrar добавлены более совершенные операторы управления с тем, чтобы оператор goto больше не доминировал.

Можно доказать математически, что достаточно if- и while-операторов чтобы записать любую необходимую управляющую структуру. Кроме того эти операторы легко понять и использовать. Различные синтаксические рас­ширения типа циклов for вполне ясны и при правильном использовании не представляют никаких трудностей для понимания или сопровождения про­граммы. Так почему же языки программирования (включая Ada, при разра­ботке которого исходили из соображений надежности) сохраняют goto?

Причина в том, что есть несколько вполне определенных ситуаций, где лучше использовать goto. Во-первых, многие циклы не могут завершаться в точке входа, как того требует цикл while. Попытка превратить все циклы в циклы while может затемнить суть дела. В современных языках гибкости привносимой операторами exit и break, достаточно и оператор goto для этой цели обычно не нужен. Однако goto все еще существует и иногда может быть полезным. Обратите внимание, что как язык С, так и Ada, ограничивают при­менение goto требованием, чтобы метка находилась в той же самой процедуре.

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

В языке С нет никаких средств для обработки этой ситуации (не подходит даже goto по причине ограниченности рамками отдельной процедуры), поэто­му для обработки серьезных ошибок нужно использовать средства операцион­ной системы. В языках Ada, C++ и Eiffel есть специальные языковые конст­рукции, так называемые исключения (exseptions), см. гл. 11, которые непосред­ственно решают эту проблему. Таким образом, операторы goto в большин­стве случаев были вытеснены по мере совершенствования языков.

Назначаемые goto-операторы

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

assign 5 to Label

...

if (x .gt. y) assign 6 to Label

5 ...

Характеристики

Список файлов книги