пятница, 5 октября 2012 г.

Break или не break?


В общении с коллегами — учителями информатики — я много раз сталкивался с твёрдым убеждением, что использование оператора break для досрочного выхода из цикла — это «неграмотно», «грязный хак», «не соответствует принципам структурного программирования» и вообще «я своим ученикам такое не зачту». В то же время общение с профессиональными программистами показывает, что такой прием на практике применяется очень часто, потому что это удобно и в большинстве случаев делает программу более понятной.

Такой «разброд» имеет совершенно объяснимые причины. Большинство преподавателей, с одной стороны, когда-то заучили, что структурное программирование — это хорошо, а любое отступление от него — это плохо. С другой стороны, сами они уже фактически отошли от промышленного программирования: я могу на пальцах одной руки пересчитать знакомых (в том числе и по Интернету) учителей информатики, которые сами написали что-то стóящее. Таким образом, наблюдаем закон Дж.Б. Шоу в действии.

Попробуем разобраться в сути вещей. Оператор break — это фактически оператор перехода, знаменитый GOTO, который в 1970-е годы был морально уничтожен, прежде всего, стараниями «отца структурного программирования» Эдсгера Дейкстры [1]. Однако сами «отцы» хорошо понимали, что программа без GOTO ещё не становится автоматически структурной программой. Поэтому появилось на свет эссе Дональда Кнута «Структурное программирование с операторами GOTO» [2]. Кнут писал (перевод мой):

«Другими словами, мы не должны просто удалять операторы GOTO из-за того, что сейчас модно это делать; присутствие или отсутствие операторов GOTO — это не главный вопрос. Истинная цель состоит в том, чтобы формулировать наши программы таким образом, чтобы их было легко понимать.»

Посмотрим, как обстоит дело с пониманием программ, содержащих циклы с операторами break и сравним их с программами, где операторов break умышленно избегают.

Пример 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);
Какая программа понятнее, каждый решает сам. :-)

Итак, подытожим.
  1. Оператор break есть практически во всех современных языках программирования. «Значит, это кому-нибудь нужно!»
  2. Это инструмент, который нужно использовать в соответствии с его назначением.
  3. Само по себе наличие или отсутствие оператора break ничего не говорит о том, грамотно ли написана программа; задача состоит в том, чтобы сделать ее наиболее понятной и «прозрачной».
  4. Использование оператора 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 нельзя считать отступлением от структурного программирования, если это не ухудшает читаемость программы и не приводит к запутыванию логики алгоритма.

В то же время попытки избавиться от этих операторов (для того, чтобы формально соблюсти «классические правила») могут привести к ухудшению читаемости программы.

Литература
  1. Dijkstra E.W., Go To Statement Considered Harmful // Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148. (PDF)
  2. Knuth D.E. Structured Programming with GO TO Statements // ASM Computing Surveys. 1974. 6(4). P.261-301. (HTML, PDF)
  3. Непейвода H.H., Скопин И.Н. Основания программирования. — Москва-Ижевск: Институт компьютерных исследований, 2003. (PDF)
  4. Гарднер М., Математические головоломки и развлечения. — М.: Мир, 1999.

Ярлыки: , , , , , , ,

Комментарии: 23:

В 5 октября 2012 г., 20:22 , Blogger Astislav Bogevolnov сказал(а)...

По моему опыту, брейк совершенно незаменим в случае, если нужно обработать исключительную ситуацию в схемах большой вложенности. Он существенно повышает читаемость в тех местах, где использование try except finally не критично.

 
В 5 октября 2012 г., 21:26 , Blogger miks сказал(а)...

На мой взгляд, страх 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:

Предложите лучший вариант :)

 
В 5 октября 2012 г., 21:48 , Blogger КП сказал(а)...

>> Предложите лучший вариант :)
Попробую. :-)

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;

 
В 5 октября 2012 г., 23:27 , Blogger miks сказал(а)...

Ой, мерзость какая!
Exit - это еще хуже чем break!
break хоть из цикла выходит, а эта сразу из процедуры!

 
В 5 октября 2012 г., 23:32 , Blogger КП сказал(а)...

> Ой, мерзость какая!

Да нет, это ведь то же самое! Фактически, в данном случае Exit = break из вложенного цикла. Или GOTO, который вы предложили применить.

 
В 5 октября 2012 г., 23:45 , Blogger miks сказал(а)...

Это я неудачно шучу так. Просто без exit и goto этот пример вообще безобразно программируется.

Кстати, еще про continue надо поговорить до кучи. Можно, конечно. и без него, но есть ли случаи, когда с ним - лучше?

 
В 6 октября 2012 г., 6:50 , Blogger КП сказал(а)...

По поводу continue — это ведь тот же goto. Думаю, что вот этот случай оправдывает его использование, если T — достаточно большой блок операторов:
for i:=1 to N do begin
  x := S(...);
  if not Good(x) then continue;
  T;
end;

 
В 6 октября 2012 г., 22:54 , Blogger miks сказал(а)...

Еще, как верно заметил автор первого комментария, использование try/except для обработки исключений - стандартная конструкция современных языков. Обрабатывать ошибки по-другому - нарушает многие каноны хороших программ. А разве переход от места возникновения исключения на обработчик исключения вверх на несколько подпрограмм - это не аналог break, только гораздо более махровый? Может, указанные Вами в статье учителя хотят и обработку исключений запретить?

Вопрос серьёзный: без break можно обойтись, но как обойтись без обработки исключений?

 
В 6 октября 2012 г., 23:29 , Anonymous GIP сказал(а)...

Решение первой задачи без Break:
s := 0;
Readln(x);
while x<>999 do begin
s := s + x;
Readln(x);
end;

 
В 7 октября 2012 г., 17:55 , Blogger КП сказал(а)...

> Решение первой задачи без Break:

Я знаю про это решение, но мне очень не нравится, что дважды используется оператор Readln. Это "размазывает" логику и делает программу менее понятной.

 
В 7 октября 2012 г., 17:57 , Blogger КП сказал(а)...

> как обойтись без обработки исключений?

Теоретически можно. Раньше ведь обходились, до начала 90-х. Коды возврата из функций...

 
В 7 октября 2012 г., 19:51 , Anonymous GIP сказал(а)...

Возвращаясь к решению первой задачи без Break: мне, напротив, это решение кажется наиболее логичным, естественным, поскольку в заголовке цикла сформулировано простое и понятное условие завершения, а Readln(x)перед циклом можно сравнить с инициализацией счетчика, которую мы делаем при замене цикл for на while

 
В 7 октября 2012 г., 19:58 , Blogger КП сказал(а)...

> Возвращаясь к решению первой задачи без Break: мне, напротив, это решение кажется наиболее логичным

Это дело вкуса, конечно. Да и речь, собственно, не о том. Мысль состоит в том, что решение с break, по крайней мере, ничем не хуже решения без break, и часто выглядит значительно понятнее. Вместо того же Readln могут быть совершенно другие операторы.

 
В 20 ноября 2012 г., 20:51 , Anonymous Linne сказал(а)...

О первой задаче. А если так:
s:=0;
x:=0;
while x<>999 do
begin
s := s+x;
Readln(x)
end;

 
В 20 ноября 2012 г., 20:56 , Blogger КП сказал(а)...

> О первой задаче. А если так:

Это ведь тоже искусственно. При чтении кода сразу возникает вопрос: "А почему в x записываем 0"? И потом: "А почему еще ничего не ввели, а уже суммируем?"

Понятность повышается? Нет.

 
В 31 марта 2013 г., 21:10 , Blogger Victor Sokolov сказал(а)...

To break or not to break. :)

Если уж приравнивать break к goto - то нужно все операторы управления процессом выполнения объявить вне закона - исключения, например. Что, конечно же, недопустимо по практическим соображениям.

Я бы немного переформулировал Кнута. Думаю, есть определенная неточность перевода с английского. Простота (simplicity) это в смысле программирования скорее "очевидность".

По возможности, нужно избавить программы от неочевидных и нестандартных ходов, пусть даже это и рождает некоторый оверхед в плане объема кода или его оптимальности.

Давно хотел спросить, хотя это и не очень в теме этого поста. Что вы думаете об использовании в обучении программированию сред типа Squeak (Smalltalk)? Если отвлечься от методических требований, конечно.

 
В 11 апреля 2013 г., 9:17 , Anonymous Валерий Лаптев сказал(а)...

Вставлю свои 5 копеек.
Структурная конструкция цикла предполагает, что вход сверху, а выход - исключительно снизу.
В этом плане конструкция цикла представляет собой неделимый "кирпич", который можно "таскать" по коду "куда угодно". И я об этом не задумываюсь.
Если же в ней есть выход из середины - она уже не является таким "монолитом", я должен разобрать логику этого выхода.

 
В 11 апреля 2013 г., 13:59 , Blogger Илья Ермаков сказал(а)...

На эту тему:
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

 
В 11 апреля 2013 г., 14:14 , Blogger Илья Ермаков сказал(а)...

Вот на сходную тему - о том, почему могут быть плохи return-ы из середины процедуры:
http://forum.oberoncore.ru/viewtopic.php?p=42554#p42554

 
В 11 апреля 2013 г., 14:24 , Blogger Илья Ермаков сказал(а)...

Также в вышеприведённой статье "Базовые паттерны циклов" прошу обратить внимание на то, почему повторение "лишней" инструкции до цикла - не громоздко, а как раз логично.

Потому что стоит заметить, что такая инструкция выполняется n+1 раз, в отличие от остальных, которые выполняются n раз. И совершенно логично такой дополнительный раз вынести за цикл.

Для иллюстрации цикл покраски забора из N секций и, разумеется, N+1 столбов:
Покрасить столб;
ЦИКЛ N раз:
Покрасить секцию;
Покрасить столб
КОНЕЦ
- вот яркая иллюстрация. Пытаться засунуть покраску "лишнего" столба внутрь цикла - это противоестественное занятие, простие.

Это же касается циклов в духе:
for....
...
if НАШЛИ then
что-то делаем; break
end if
end for
Никого не коробит, что внутри цикла оказалось однократное действие, которое, вообще-то, должно находится логичным образом после цикла? :)

Всё это, мне кажется, от недостаточного внимания к логическим свойствам программ. От отношения к ним, как "литературному произведению". "Лишь бы машина понимала". Более продвинутое: "ну и лишь бы читателям потом тоже было нормально". Но никто не доходит до "лишь бы обладало понятными, гарантированными, доказуемыми свойствами".

 
В 11 апреля 2013 г., 14:34 , Blogger Илья Ермаков сказал(а)...

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

Но, Константин Юрьевич, Вы же сами привели чистый классический вариант линейного поиска (который обязан знать и использовать любой образованный программист, имхо):

[ЦИТАТА]
Вот альтернатива без 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) - так сделано, например, в Аде.

С уважением.
Простите за некоторый "напор", но на Вас большая ответственность, потому что Вас читают многие-многие :)

 
В 23 января 2017 г., 17:54 , Anonymous Анонимный сказал(а)...

а как с постусловием решить это? Дан массив действительных чисел. Среди них есть равные. Найти первый max элемент и заменить ТОЛЬКО его нулем. Подробно, если не сложно. Заранее преблагодарен.

 
В 23 января 2017 г., 21:14 , Blogger КП сказал(а)...

> Дан массив действительных чисел. Среди них есть равные.
> Найти первый max элемент и заменить ТОЛЬКО его нулем.

Зачем тут цикл с условием? Почему не так:

  nMax := 1;
  for i:=1 to N do
    if A[i] > A[nMax] then
      nMax := i;
  A[nMax] := 0;

 

Отправить комментарий

Подпишитесь на каналы Комментарии к сообщению [Atom]

<< Главная страница