Ермаков И. Е. Структурирование "промышленного" цикла / Ermakov I. E. “Industrial” loop structuring

В одном из обсуждений на форуме (http://forum.oberoncore.ru/viewtopic.php?p=42396#p42396) был представлен пример «промышленного цикла» (из компиляторного проекта), вместе с утверждением, что досрочный выход из цикла «на практике необходим, без него трудно строить сложные циклы».

Автор выполнил эквивалентное преобразование цикла в обычный WHILE.

Исходный цикл:

LOOP
  next := calc_next(curr);

  IF (next = NIL) OR NOT p(next) OR NOT p2(first, next) THEN
    EXIT;  
  END;    

  next_transformed := transform (next);
            
  IF NOT p3(curr_transformed, next_transformed, init_transformed) THEN
    EXIT;
  END;

  IF p4() THEN
    IF f(next) # fff THEN
      EXIT;
    END;
    INC(fff);
  END;
  
  INC(zzz);
  curr := next;
  curr_transformed := next_transformed;

  mmm := bar (curr_transformed, init_transformed, zzz);
  IF p5(zzz, mmm) THEN
    selected := curr;
  END;
END;

Пояснения: в последовательности выделяется подпоследовательность, обладающая свойствами p() & p2() & p3() & p4() & f(next) = fff. Должен быть возвращён последний элемент этой подпоследовательности, обладающий свойством p5().

(Из такой спецификации цикла возникает подозрение в плохой организации программы уровнем выше. Однако даже в такой постановке удаётся построить строгий и прозрачный цикл.)

Дополнительные пояснения от автора: p4() инвариантен к параметрам цикла (т.е. просто некая внешняя конфигурация).

Было замечено, что в условиях инвариантного p4() нет смысла в отдельном счётчике fff. Было получено пояснение, что он уже имеет какое-то начальное значение до цикла, т.е. = zzz + const. Мы будем использовать fff как константу в цикле, прибавляя его к zzz.

Восстановление семантики и преобразование к нормальному виду

http://forum.oberoncore.ru/viewtopic.php?p=42454#p42454

Видим, что цикл работает над парой элементов из последовательности (без знания задачи неясно, какие там взаимосвязи, следуем букве). Чтобы не сбивать мысль, не будем называть их curr и next, а назовём a и b. INVAR(a, b): b = CalcNext(a). Разумеется, переменные для хранения трансформаций сразу не заводим, чтобы не загромождать работу (это - финальная оптимизация).

Таким образом, выписываем из LOOP-а все ситуации завершения:

(b = NIL) OR ~P(b) OR ~P2(first, b) OR ~P3(Transform(a), Transform(b)) OR P4() & (f(b) # count)

Инвертируем эту дизъюнкцию и получаем условие продолжения цикла. Цикл проходит по последовательности до тех пор, пока одно из условий не окажется нарушенным (полный проход по начальной подпоследовательности, элементы которой обладают конъюнкцией 4-х свойств).

Полезное действие цикла - запоминание последнего встреченного элемента, обладающего свойством p5().

Таким образом, неоптимизированный вариант цикла выглядит следующим образом:

b := CalcNext(a);
count := 0;
WHILE (b # NIL)
   & P(b) & P2(first, b)
   & P3(Transform(a), Transform(b), init_transformed)
   & (~P4() OR (f(b) = count + fff))
DO
   IF p5(count+1, Bar(Transform(a), init_transformed, count+1) THEN
      selected := a
   END;
   INC(count);
   a := b;
   b := CalcNext(b)
END;

Tranform() требует аргумента, не равного NIL. Обратим внимание, что все вызовы Tranform(b) в условии цикла находятся под охраной первого конъюнкта b # NIL (предусловие a # NIL гарантируется задачей). Грамотный программист должен уметь пользоваться сокращённой семантикой логических операций cand и cor (которая обязательна во всех современных языках).

Чтобы избежать повторного вычисления Transform, выполним оптимизацию, введя дополнительные переменные ta и tb (и не забывая про необходимость охраны IF b # NIL на вычисление Transform(b)).

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

ta := Transform(a);
b := CalcNext(a);
IF b # NIL THEN tb := Transform(b) END;
count := 0;
WHILE (b # NIL)
   & P(b) & P2(first, b)
   & P3(ta, tb, init_transformed)
   & (~P4() OR (f(b) = count))
DO
   IF p5(count+1, Bar(ta, init_transformed, count+1) THEN
      selected := a
   END;
   INC(count);
   a := b; ta := tb;
   b := CalcNext(b);
   IF b # NIL THEN tb := Transform(b) END
END;

Мнения о цикле

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

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

Как аргумент за первый цикл приводится то, что он «соответствует линейному мышлению: читаем — и постепенно понимаем, как он работает».

По этому поводу можно заметить, во-первых, что основное требование — прозрачность свойств составленной конструкции. И изучать цикл должен не в порядке выполнения его машиной, а с помощью инструмента логических рассуждений (начать с того, что построен он должен быть посредством таких рассуждений, а не путём постепенного подбора команд). Основной смысл цикла — это его цель, в какое конечное состояние он должен привести (какое постусловие обеспечить). В состояние из каких возможных классов (например, у поиска два или более исхода: не нашли, нашли А, нашли Б… И т.п.) Действия же, которые в цикле происходят — это отнюдь не его смысл, а «грязная работа» по продвижению от начального состояния к целевому. Чем проще эти внутренние действия, тем лучше. И уж конечно, они не должны содержать вперемешку ещё и принятие решений о том, достигнута цель или нет.

Во-вторых, эта тема спровоцировала дальнешее обсуждение (http://forum.oberoncore.ru/viewtopic.php?t=2348), которое привело к пониманию следующей проблемы: у большинства программистов не сформировано структурное отношение к программе (здесь слово «структурное» употребляем без прямой связи со структурным программированием, а в общем смысле). Программа для них — это нечто сродни литературному тексту, который пишет программист-«писатель», пытаясь описать требующиеся от машины действия. Более того, в таком отношении присутствует даже некая «художественная трепетность».

Вывод: восприятие программы как инженерной системы, составленной из конструкций, которые соединяются по определённым правилам, не сформировано у массовых программистов, и это представляет реальную проблему для развития ИТ как инженерной деятельности. Обязательное требование к инженерной деятельности — наличие строгих (обычно математизированных) методов, позволяющих анализировать и гарантировать свойства создаваемых конструкций, выводя их из свойств использованных элементов и соединений. Как это может выглядеть для ПО, было показано, например, Дейкстрой в «Дисциплине программирования».

© 2005-2016 OberonCore и коллектив авторов.