М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 17
Текст из файла (страница 17)
Такая ситуация часто встречается при использовании указателей (гл. 8):
| Ada |
6.3. Операторы цикла
Операторы цикла наиболее трудны для программирования: в них легко сделать ошибку, особенно на границах цикла, то есть при первом и последнем выполнении тела цикла. Кроме того, неэффективная программа чаще всего расходует большую часть времени в циклах, поэтому так важно понимать их реализацию. Структура цикла показана на рис. 6.3. Оператор цикла имеет точку входа, последовательность операторов, которые составляют цикл, и одну
или несколько точек выхода. Так как мы (обычно) хотим, чтобы наши циклы завершались, с точкой выхода бывает связано соответствующее условие, которое определяет, следует сделать выход или продолжить выполнение цикла. Циклы различаются числом, типом и расположением условий выхода. Мы начнем с обсуждения циклов с произвольными условиями выхода, называемыми циклами while, а в следующем разделе обсудим частный случай — циклы for.
Наиболее общий тип цикла имеет единственный выход в начале цикла, т.е. в точке входа. Он называется циклом while:
| C |
while (s[i]. data != key)
Цикл while прост и надежен. Поскольку условие проверяется в начале цикла, мы знаем, что тело цикла будет полностью выполнено столько раз, сколько потребуется по условию. Если условие выхода сначала имеет значение False,то тело цикла не будет выполнено, и это упрощает программирование граничных условий:
| C |
while (count > 0) process(s[count].data);
Если в массиве нет данных, выход из цикла произойдет немедленно.
Во многих случаях, однако, выход естественно писать в конце цикла. Так обычно делают, когда нужно инициализировать переменную перед каждым выполнением. В языке Pascal есть оператор повторения repeat:
| Pascal |
read(v);
put_in_table(v);
until v = end_value;
В языке Pascal repeat заканчивается, когда условие выхода принимает значение True. He путайте его с циклом do в языке С, который заканчивается, когда условие выхода принимает значение False:
| C |
v = get();
put_in_table(v);
} while (v != end_value);
Принципы безупречного структурного программирования требуют, чтобы все выходы из цикла находились только в начале или конце цикла. Это делает программу более легкой для анализа и проверки. Но на практике бывают нужны выходы и из середины цикла, особенно при обнаружении ошибки:
while not found do
| Pascal |
(* Длинное вычисление *)
(* Обнаружена ошибка, выход *)
(* Длинное вычисление *)
end
Pascal, в котором не предусмотрен выход из середины цикла, использует следующее неудовлетворительное решение: установить условие выхода и использовать if-оператор, чтобы пропустить оставшуюся часть цикла:
while not found do
| Pascal |
(* Длинное вычисление *)
if error_detected then found := True
else
begin
(* Длинное вычисление *)
end
end
В языке С можно использовать оператор break:
while (!found) {
| C |
if (error_detected()) break;
/* Длинное вычисление */
}
В Ada есть обычный цикл while, а также оператор exit, с помощью которого можно выйти из цикла в любом месте; как правило, пара связанных операторов if и exit заменяется удобной конструкцией when:
while not Found loop
| Ada |
exit when error_detected;
- Длинное вычисление
end loop;
Операционная система или система, работающая в реальном масштабе времени, по замыслу, не должна завершать свою работу, поэтому необходим способ задания бесконечных циклов. В Ada это непосредственно выражается оператором loop без условия выхода:
| Ada |
…
end loop;
В других языках нужно написать обычный цикл с искусственным условием выхода, которое гарантирует, что цикл не завершится:
while(1==1){
| C |
}
Реализация
Цикл while:
| C |
while (expression)
statement;
реализуется так:
L1: compute R1.expr
jump_zero R1,L2 Выйти из цикла, если false
statement Тело цикла
jump L1 Перейти на проверку завершения цикла L2:
Обратите внимание, что в реализации цикла while есть две команды перехода! Интересно, что если выход находится в конце цикла, то нужна только одна команда перехода:
do{
| C |
} while (expression);
компилируется в
L1: statement
compute expr
jump_nz L1 He ноль — это True
Хотя цикл while очень удобен с точки зрения читаемости программы, эффективность кода может быть увеличена путем замены его на цикл do. Для выхода из середины цикла требуются два перехода точно так же, как и для цикла while.
6.4. Цикл for
Очень часто мы знаем количество итераций цикла: это либо константа, известная при написании программы, либо значение, вычисляемое перед началом цикла. Цикл со счетчиком можно запрограммировать следующим образом:
int i; /* Индекс цикла */
| C |
i = low; /* Инициализация индекса */
while (i <= high) { /* Вычислить условие выхода */
statement;
i++: /* Увеличить индекс */
};
Поскольку это общая парадигма, постольку для упрощения программирования во всех (императивных) языках есть цикл for. Его синтаксис в языке С следующий:
int i; /* Индекс цикла */
int low, high; /* Границы цикла */
| C |
for (i = low; i <= high; i++) {
statement;
}
В Ada синтаксис аналогичный, за исключением того, что объявление и увеличение переменной цикла неявные:
Low, High: Integer;
| Ada |
for I in Low .. High loop
statement;
end loop;
Ниже в этом разделе мы обсудим причины этих различий.
Известно, что в циклах for легко сделать ошибки в значениях границ. Цикл выполняется для каждого из значений от low до high; таким образом, общее число итераций равно high - low +1. Однако, если значение low строго больше значения high, цикл будет выполнен ноль раз. Если вы хотите выполнить цикл точно Л/ раз, цикл for будет иметь вид:
| Ada |
forlinl ..N loop...
и число итераций равно N -1 + 1 = N. В языке С из-за того, что для массивов индексы должны начинаться с нуля, цикл со счетчиком обычно записывается так:
| C |
Так как запись i < п означает то же самое, что и i <= (п - 1), цикл выполняется (п -1)-0+1 =п раз, как и требуется.
Обобщения в циклах for
Несмотря на то, что все процедурные языки содержат циклы for, они значительно отличаются по предоставляемым дополнительным возможностям. Две крайности — это Ada и С.
В Ada исходным является положение, что цикл for должен использоваться только с фиксированным числом итераций и что это число можно вычислить перед началом цикла. Объясняется это следующим: 1) большинство реальных циклов простые, 2) другие конструкции легко запрограммировать в явном виде, и 3) циклы for и сами по себе достаточно трудны для тестирования и проверки. В языке Ada нет даже классического обобщения: увеличения переменной цикла на значения, отличные от 1 (или -1). Язык Algol позволяет написать итерации для последовательности нечетных чисел:
| Algol |
for I := 1 to N step 2 do ...
в то время как в Ada мы должны явно запрограммировать их вычисление:
for l in 1 .. (N + 1)/2 loop
| Ada |
|1 =2*|-1;
…
end loop;
В языке С все три элемента цикла for могут быть произвольными выражениями:
| C |
В описании С определено, что оператор
| C |
эквивалентен конструкции
| C |
while (expression_2) {
statement;
expression_3;
}
В языке Ada также допускается использование выражений для задания границ цикла, но они вычисляются только один раз при входе в цикл. То есть
| Ada |
statement;
end loop;
эквивалентно
I = expression_1;
| Ada |
while (I < Temp) loop
statement;
I: = I + 1;
end loop;
Если тело цикла изменяет значение переменных, используемых при вычислении выражения expression_2, то верхняя граница цикла в Ada изменяться не будет. Сравните это с данным выше описанием цикла for в языке С, который заново вычисляет значение выражения expression_2 на каждой итерации.
Обобщения в языке С — нечто большее, чем просто «синтаксический сахар», поскольку операторы внутри цикла, изменяющие выражения expres-sion_2 и expression_3, могут вызывать побочные эффекты. Побочных эффектов следует избегать по следующим причинам.
• Побочные эффекты затрудняют полную проверку и тестирование цикла.
• Побочные эффекты неблагоприятно воздействуют на читаемость и поддержку программы.
•Побочные эффекты делают цикл гораздо менее эффективным, потому что выражения expression_2 и expression_3 нужно заново вычислять на каждой итерации. Если побочных эффектов нет, оптимизирующий компилятор может вынести эти вычисления за границу цикла.
Реализация
Циклы for — наиболее часто встречающиеся источники неэффективности в программах, потому что небольшие различия в языках или небольшие изменения в использовании оператора могут иметь серьезные последствия. Во многих случаях оптимизатор в состоянии решить эти проблемы, но лучше их понимать и избегать, чем доверяться оптимизатору. В этом разделе мы более подробно опишем реализацию на уровне регистров.
В языке Ada цикл
| Ada |
statement;
end loop;
компилируется в
compute R1,expr_1
store R1,l Нижняя граница индексации
compute R2,expr_2
store R2,High Верхняя граница индексации
L1: load R1,l Загрузить индекс
load R2,High Загрузить верхнюю границу
jump_gt R1,R2,L2 Завершить цикл, если больше
statement Тело цикла
load R1,l Увеличить индекс
incr R1
store R1,l
jump L1
L2:
Очевидная оптимизация — это закрепление регистра за индексной переменной I и, если возможно, еще одного регистра за High:
compute R1 ,ехрг_1 Нижняя граница в регистре
compute R2,expr_2 Верхняя граница в регистре
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
