Break или не break?
В общении с коллегами — учителями информатики — я много раз сталкивался с твёрдым убеждением, что использование оператора break для досрочного выхода из цикла — это «неграмотно», «грязный хак», «не соответствует принципам структурного программирования» и вообще «я своим ученикам такое не зачту». В то же время общение с профессиональными программистами показывает, что такой прием на практике применяется очень часто, потому что это удобно и в большинстве случаев делает программу более понятной.
Такой «разброд» имеет совершенно объяснимые причины. Большинство преподавателей, с одной стороны, когда-то заучили, что структурное программирование — это хорошо, а любое отступление от него — это плохо. С другой стороны, сами они уже фактически отошли от промышленного программирования: я могу на пальцах одной руки пересчитать знакомых (в том числе и по Интернету) учителей информатики, которые сами написали что-то стóящее. Таким образом, наблюдаем закон Дж.Б. Шоу в действии.
Попробуем разобраться в сути вещей. Оператор break — это фактически оператор перехода, знаменитый GOTO, который в 1970-е годы был морально уничтожен, прежде всего, стараниями «отца структурного программирования» Эдсгера Дейкстры [1]. Однако сами «отцы» хорошо понимали, что программа без GOTO ещё не становится автоматически структурной программой. Поэтому появилось на свет эссе Дональда Кнута «Структурное программирование с операторами GOTO» [2]. Кнут писал (перевод мой):
«Другими словами, мы не должны просто удалять операторы GOTO из-за того, что сейчас модно это делать; присутствие или отсутствие операторов GOTO — это не главный вопрос. Истинная цель состоит в том, чтобы формулировать наши программы таким образом, чтобы их было легко понимать.»
Пример 1. С клавиатуры вводятся числа, ввод заканчивается числом 999. Вычислить сумму введенных чисел.
Вот решение с использованием break:
s := 0; while True do begin Readln(x); if x = 999 then break; s := s + x; end;На взгляд автора, этот алгоритм очень хорошо соответствует словесному описанию: «строим цикл, выход из которого происходит при получении числа 999».
Теперь посмотрим на «кошерные» альтернативы. Нужно как-то выполнить те же действия (то есть, выйти из цикла при получении числа 999), не используя оператор выхода из цикла.
Во-первых, можно поставить условие цикла x <> 999, но при этом нужно будет инициализировать переменную x до цикла каким-то «магическим числом», отличным от 999, например, 1 (или 998 :-). Программист, который будет разбираться в таком коде через некоторое время, спасибо вам не скажет. Кроме того, вторую часть тела цикла придется взять в условный оператор, а эта вторая часть может быть достаточно большой. Читабельность явно не повышается. Зато программа «структурная», можно «взять с полки пирожок». :-)
s:=0; x := 1; while x <> 999 do begin Readln(x); if x <> 999 then s := s + x; end;Заметим, что число 999 появляется в программе дважды: в заголовке цикла и в условии в теле цикла, что само по себе уже нехорошо.
Можно вынести оператор Readln за цикл, продублировав его в теле цикла:
s := 0; Readln(x); while x <> 999 do begin s := s + x; Readln(x); end;На взгляд автора, при этом два оператора ввода, выполняющие одну и ту же функцию, «размывают» логику программы и не добавляют ей «прозрачности». Кроме того, вместо Readln в других ситуациях может стоять целая группа операторов, и тут уже дублирование будет выглядеть совсем некрасиво.
Кроме того, можно ввести логическую переменную (флаг), которой присваивается истинное значение при получении числа 999:
stop := False; while not stop do begin Readln(x); if x = 999 then stop := True else s := s + x; end;Но тут нужно вспомнить о «бритве Оккама» — не плоди лишних сущностей. И ещё — любое усложнение системы, как правило, снижает её надежность.
Еще один вариант — перейти на цикл с постусловием:
s := 0; repeat Readln(x); if x <> 999 then s := s + x; until x = 999;Во-первых, как и в одном из предыдущих вариантов, здесь два раза всплывает число 999. Во-вторых, вторую часть тела цикла снова нужно помещать в условный оператор. В-третьих, читать программы с циклами repeat — это сущее наказание: встретив слово repeat, судорожно пытаемся найти соответствующий until с условием, без этого всё вообще непонятно. Потом опять нужно смотреть наверх: что же там в теле цикла...
Можно, конечно, и так :-):
s := 0; try while True do begin Readln(x); if x = 999 then raise Exception.Create(''); s := s + x; end; except end;Но по сути это то же самое, что и break. Использовать здесь исключения — всё равно, что гвозди микроскопом забивать.
Рассмотрим еще один пример.
Пример 2. Найти в массиве A[1..N] элемент, равный X, или сообщить, что такого элемента нет.
Решение с помощью break:
nX := 0; for i:=1 to N do if A[i] = X then begin nX := i; break; end; if nX = 0 then writeln('Не нашли!') else writeln('nX = ', nX);Как и для первого примера, программа с break почти дословно повторяет словесное описание идеи решения: «просматриваем все элементы массива с первого до последнего; как только нашли нужный элемент, запоминаем его номер и выходим из цикла».
Вот альтернатива без break:
nX := 1; while (nX <= N) and (A[nX] <> X) do Inc(nX); if nX > N then writeln('Не нашли!') else writeln('nX = ', nX);Теперь представим себе, что будет, если в трансляторе включена проверка выхода за границы массива, логические выражения вычисляются полностью и элемента, равного X, в массиве нет: программа вылетит в результате обращения за пределы массива.
Вот еще вариант, с логической переменной:
nX := 1; found := False; repeat if A[nX] = X then found:= True else Inc(nX); until found or (nX > N); if not found then writeln('Не нашли!') else writeln('nX = ', nX);Какая программа понятнее, каждый решает сам. :-)
Итак, подытожим.
- Оператор break есть практически во всех современных языках программирования. «Значит, это кому-нибудь нужно!»
- Это инструмент, который нужно использовать в соответствии с его назначением.
- Само по себе наличие или отсутствие оператора break ничего не говорит о том, грамотно ли написана программа; задача состоит в том, чтобы сделать ее наиболее понятной и «прозрачной».
- Использование оператора break относится к так называемым «структурным» переходам [3], то есть к переходам вперёд в пределах того же модуля, что не нарушает принципы структурного программирования.
Разобравшись с break, можно перейти к его непосредственному «родственнику» — оператору continue, который передает управление сразу в конец цикла, переходя к следующему шагу, если требуется.
Пример 3. В цикле обрабатываются все элементы массива A[1:N]. Для каждого из них сначала выполняются операторы S1, S2, ..., SN, в результате вычисляется некоторое значение x. Если получено значение x = 1, нужно выполнить еще операторы T1, T2, ..., TM, а в противном случае перейти к следующему элементу.
«Классическое» решение выглядит так:
for i:=1 to N do begin S1; S2; ... x := SN; if x = 1 then begin T1; T2; ... TM; end end;Вроде бы всё хорошо. Но мы потеряли «локальность»: при достаточно длинном теле условного оператора нужно еще «сканировать» цикл до конца, проверяя, не выполняются ли какие-то действия в том случае, когда x <> 1. А эту проблему может элегантно решить continue:
for i:=1 to N do begin S1; S2; ... x := SN; if x <> 1 then continue; T1; T2; ... TM end;Здесь уже точно ясно, что при x <> 1 никаких дополнительных операций не происходит. По мнению автора, такой вариант более «прозрачен» и, по крайней мере, не хуже предыдущего.
Остается еще один «смежный» вопрос: можно ли писать подпрограммы с несколькими выходами? Давайте посмотрим пример рекурсивной процедуры.
Пример 4. Разработать процедуру, которая выводит на экран решение задачи «Ханойская башня» [4].
Рекурсивное решение этой задачи хорошо известно, одна из реализаций выглядит так:
procedure Hanoi(n, k, m: integer); var p: integer; begin if n = 0 then exit; p := 6 - k - m; Hanoi(n-1, k, p); writeln(k, ' -> ', m); Hanoi(n-1, p, m) end;Здесь n — количество дисков, которые нужно перенести; k — номер начального стержня и m — номер конечного стержня.
И все было бы хорошо, но тут нарушен ещё один принцип, который стал «священной коровой» ортодоксального структурного программирования: процедура имеет (увы :-) два выхода, один естественный, и второй — по признаку окончания рекурсии.
Можно ли было обойтись без этого? Да, можно, «упаковав» все тело процедуры внутрь условного оператора:
procedure Hanoi(n, k, m: integer); var p: integer; begin if n > 0 then begin p := 6 - k - m; Hanoi(n-1, k, p); writeln(k, ' -> ', m); Hanoi(n-1, p, m) end end;Но тут мы опять теряем локальность — при достаточно длинном тексте процедуры нужно еще посмотреть, не выполняются ли какие-то действия после условного оператора. Да и не совсем понятно, зачем добавлять лишний уровень вложенности. «Не плоди лишних сущностей». По мнению автора, первое приведенное решение более понятное и более красивое.
Пример 5. Разработать функцию, которая определяет, если ли в квадратной матрице элемент, равный заданному значению.
Будем предполагать, что введен тип данных
type Matrix = array[1..N,1..N] of integer;Тогда функцию можно написать так:
function Find(const A: Matrix; X: integer): boolean; var i, j: integer; begin Result := True; for i:=1 to N do for j:=1 to N do if A[i,j] = X then exit; Result := False end;Здесь оператор exit фактически выполняет роль break для вложенного цикла. С формальной точки зрения у функции два выхода. В общем, «я своим ученикам никогда такое не зачту» — уже слышу я от учителей информатики.
А давайте подумаем, какие альтернативы? Можно вот так:
function Find(const A: Matrix; X: integer): Boolean; var i, j: integer; label finish; begin Result := True; for i:=1 to N do for j:=1 to N do if A[i,j] = X then goto finish; Result := False; finish: end;Но тут вообще «криминал» — метка и goto! Хотя по сути ничего не изменилось, тот же выход из вложенного цикла.
Конечно, здесь можно использовать исключение:
function Find(const A: Matrix; X: integer): Boolean; var i, j: integer; begin Result := False; try for i:=1 to N do for j:=1 to N do if A[i,j] = X then raise Exception.Create(''); except Result := True end end;Но ведь это далеко не «исключительная ситуация», поэтому по смыслу исключения здесь всё-таки не особо уместны. Кроме того, нужно учитывать, что при обработке исключений выполняется большое число машинных команд, что снижает эффективность программы.
Любителей «чистого» структурного программирования наверняка устроит такой вариант решения:
function Find(A: Matrix; X: integer): Boolean; var i, j: integer; begin Result := False; for i:=1 to N do for j:=1 to N do if A[i,j] = X then Result := True end;Но, к сожалению, по эффективности он не может составить конкуренцию предыдущим, так как в любом случае рассматриваются все N2 элементов массива, даже если элемент A[1,1] равен X.
Выводы
Эта статья, прежде всего, о том, что любые идеи и принципы нужно воспринимать в контексте конечной цели. Одна из основных целей концепции структурного программирования — повысить читаемость программ и за счёт этого облегчить их отладку, тестирование и сопровождение. Поэтому применение операторов break, continue и exit нельзя считать отступлением от структурного программирования, если это не ухудшает читаемость программы и не приводит к запутыванию логики алгоритма.
В то же время попытки избавиться от этих операторов (для того, чтобы формально соблюсти «классические правила») могут привести к ухудшению читаемости программы.
Литература
- Dijkstra E.W., Go To Statement Considered Harmful // Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148. (PDF)
- Knuth D.E. Structured Programming with GO TO Statements // ASM Computing Surveys. 1974. 6(4). P.261-301. (HTML, PDF)
- Непейвода H.H., Скопин И.Н. Основания программирования. — Москва-Ижевск: Институт компьютерных исследований, 2003. (PDF)
- Гарднер М., Математические головоломки и развлечения. — М.: Мир, 1999.
Ярлыки: Дейкстра, Кнут, Паскаль, программирование, break, continue, exit, goto
Комментарии: 23:
По моему опыту, брейк совершенно незаменим в случае, если нужно обработать исключительную ситуацию в схемах большой вложенности. Он существенно повышает читаемость в тех местах, где использование try except finally не критично.
На мой взгляд, страх break - это проблемы тех учителей, которые его запрещают. В ВУЗе потом приходится переучивать. Замечу, что ни один из студентов не смог достойно объяснить, почему break, который запрещал учитель, это плохо.
Я вот усугублю: найти элемент в матрице:
IsFound := False;
for i:=1 to n do
for j:=1 to n do
if a[i,j]=x then
begin
IsFound := True;
goto en;
end;
en:
Предложите лучший вариант :)
>> Предложите лучший вариант :)
Попробую. :-)
type matr = array[1..N,1..N] of integer;
function FindMatr(A: matr; X: integer): boolean;
var i, j: integer;
begin
Result := True;
for i:=1 to N do
for j:=1 to N do
if A[i,j] = X then Exit;
Result := False;
end;
Ой, мерзость какая!
Exit - это еще хуже чем break!
break хоть из цикла выходит, а эта сразу из процедуры!
> Ой, мерзость какая!
Да нет, это ведь то же самое! Фактически, в данном случае Exit = break из вложенного цикла. Или GOTO, который вы предложили применить.
Это я неудачно шучу так. Просто без exit и goto этот пример вообще безобразно программируется.
Кстати, еще про continue надо поговорить до кучи. Можно, конечно. и без него, но есть ли случаи, когда с ним - лучше?
По поводу continue — это ведь тот же goto. Думаю, что вот этот случай оправдывает его использование, если T — достаточно большой блок операторов:
for i:=1 to N do begin
x := S(...);
if not Good(x) then continue;
T;
end;
Еще, как верно заметил автор первого комментария, использование try/except для обработки исключений - стандартная конструкция современных языков. Обрабатывать ошибки по-другому - нарушает многие каноны хороших программ. А разве переход от места возникновения исключения на обработчик исключения вверх на несколько подпрограмм - это не аналог break, только гораздо более махровый? Может, указанные Вами в статье учителя хотят и обработку исключений запретить?
Вопрос серьёзный: без break можно обойтись, но как обойтись без обработки исключений?
Решение первой задачи без Break:
s := 0;
Readln(x);
while x<>999 do begin
s := s + x;
Readln(x);
end;
> Решение первой задачи без Break:
Я знаю про это решение, но мне очень не нравится, что дважды используется оператор Readln. Это "размазывает" логику и делает программу менее понятной.
> как обойтись без обработки исключений?
Теоретически можно. Раньше ведь обходились, до начала 90-х. Коды возврата из функций...
Возвращаясь к решению первой задачи без Break: мне, напротив, это решение кажется наиболее логичным, естественным, поскольку в заголовке цикла сформулировано простое и понятное условие завершения, а Readln(x)перед циклом можно сравнить с инициализацией счетчика, которую мы делаем при замене цикл for на while
> Возвращаясь к решению первой задачи без Break: мне, напротив, это решение кажется наиболее логичным
Это дело вкуса, конечно. Да и речь, собственно, не о том. Мысль состоит в том, что решение с break, по крайней мере, ничем не хуже решения без break, и часто выглядит значительно понятнее. Вместо того же Readln могут быть совершенно другие операторы.
О первой задаче. А если так:
s:=0;
x:=0;
while x<>999 do
begin
s := s+x;
Readln(x)
end;
> О первой задаче. А если так:
Это ведь тоже искусственно. При чтении кода сразу возникает вопрос: "А почему в x записываем 0"? И потом: "А почему еще ничего не ввели, а уже суммируем?"
Понятность повышается? Нет.
To break or not to break. :)
Если уж приравнивать break к goto - то нужно все операторы управления процессом выполнения объявить вне закона - исключения, например. Что, конечно же, недопустимо по практическим соображениям.
Я бы немного переформулировал Кнута. Думаю, есть определенная неточность перевода с английского. Простота (simplicity) это в смысле программирования скорее "очевидность".
По возможности, нужно избавить программы от неочевидных и нестандартных ходов, пусть даже это и рождает некоторый оверхед в плане объема кода или его оптимальности.
Давно хотел спросить, хотя это и не очень в теме этого поста. Что вы думаете об использовании в обучении программированию сред типа Squeak (Smalltalk)? Если отвлечься от методических требований, конечно.
Вставлю свои 5 копеек.
Структурная конструкция цикла предполагает, что вход сверху, а выход - исключительно снизу.
В этом плане конструкция цикла представляет собой неделимый "кирпич", который можно "таскать" по коду "куда угодно". И я об этом не задумываюсь.
Если же в ней есть выход из середины - она уже не является таким "монолитом", я должен разобрать логику этого выхода.
На эту тему:
http://www.oberoncore.ru/wiki/%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D0%BC%D1%8B%D1%88%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0
- здесь цикл с break-ами трансформирован в структурную форму (кстати, автор цикла с брейками - из очень солидной компиляторной компании из Сибири и очень спорил "за брейк").
В конце статьи разобраны убедительные аргументы против брейка (о том, КАК думает программист, привыкший анализировать свойства программы в терминах утверждений и почему такому программисту очень не хочется читать цикл построчно в поисках брейка и "гонять его в уме").
Также в эту тему статья "Базовые паттерны циклов":
http://www.oberoncore.ru/wiki/%D0%BF%D0%B0%D1%82%D1%82%D0%B5%D1%80%D0%BD%D1%8B_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2
Вот на сходную тему - о том, почему могут быть плохи return-ы из середины процедуры:
http://forum.oberoncore.ru/viewtopic.php?p=42554#p42554
Также в вышеприведённой статье "Базовые паттерны циклов" прошу обратить внимание на то, почему повторение "лишней" инструкции до цикла - не громоздко, а как раз логично.
Потому что стоит заметить, что такая инструкция выполняется n+1 раз, в отличие от остальных, которые выполняются n раз. И совершенно логично такой дополнительный раз вынести за цикл.
Для иллюстрации цикл покраски забора из N секций и, разумеется, N+1 столбов:
Покрасить столб;
ЦИКЛ N раз:
Покрасить секцию;
Покрасить столб
КОНЕЦ
- вот яркая иллюстрация. Пытаться засунуть покраску "лишнего" столба внутрь цикла - это противоестественное занятие, простие.
Это же касается циклов в духе:
for....
...
if НАШЛИ then
что-то делаем; break
end if
end for
Никого не коробит, что внутри цикла оказалось однократное действие, которое, вообще-то, должно находится логичным образом после цикла? :)
Всё это, мне кажется, от недостаточного внимания к логическим свойствам программ. От отношения к ним, как "литературному произведению". "Лишь бы машина понимала". Более продвинутое: "ну и лишь бы читателям потом тоже было нормально". Но никто не доходит до "лишь бы обладало понятными, гарантированными, доказуемыми свойствами".
Посмотрел статью поподробнее...
Варианты с логическими флагами просто ужасны - и полностью, конечно, дискредитируют идею "программировать без брейк".
Но, Константин Юрьевич, Вы же сами привели чистый классический вариант линейного поиска (который обязан знать и использовать любой образованный программист, имхо):
[ЦИТАТА]
Вот альтернатива без break:
nX := 1;
while (nX <= N) and (A[nX] <> X) do
Inc(nX);
if nX > N then
writeln('Не нашли!')
else writeln('nX = ', nX);
[/ЦИТАТА]
И что же Вас беспокоит:
[ЦИТАТА]
Теперь представим себе, что будет, если в трансляторе включена проверка выхода за границы массива, логические выражения вычисляются полностью и элемента, равного X, в массиве нет: программа вылетит в результате обращения за пределы массива.
[/ЦИТАТА]
Беспокоит опция из тех дремучих времён, когда создаатели некоторых компиляторов ещё не знали, что сокращённое вычисление - это ОБЯЗАТЕЛЬНЫЙ И БЕЗАЛЬТЕРНАТИВНЫЙ режим, потому что в другом режиме "культурно по-Дейкстре" программировать невозможно?
Это выключающий такую опцию должен думать о том, что он рушит любую нормально написанную программу, имеющую хоть один линейный поиск.
Где сегодня Вы найдёте такую опцию?
Единственное, бывает, что в языках введено по две логических операций - полная и сокращённая (and и cand, or и cor) - так сделано, например, в Аде.
С уважением.
Простите за некоторый "напор", но на Вас большая ответственность, потому что Вас читают многие-многие :)
а как с постусловием решить это? Дан массив действительных чисел. Среди них есть равные. Найти первый max элемент и заменить ТОЛЬКО его нулем. Подробно, если не сложно. Заранее преблагодарен.
> Дан массив действительных чисел. Среди них есть равные.
> Найти первый max элемент и заменить ТОЛЬКО его нулем.
Зачем тут цикл с условием? Почему не так:
nMax := 1;
for i:=1 to N do
if A[i] > A[nMax] then
nMax := i;
A[nMax] := 0;
Отправить комментарий
Подпишитесь на каналы Комментарии к сообщению [Atom]
<< Главная страница