Ермаков И. Е. Структурирование "промышленного" цикла / 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), которое привело к пониманию следующей проблемы: у большинства программистов не сформировано структурное отношение к программе (здесь слово «структурное» употребляем без прямой связи со структурным программированием, а в общем смысле). Программа для них — это нечто сродни литературному тексту, который пишет программист-«писатель», пытаясь описать требующиеся от машины действия. Более того, в таком отношении присутствует даже некая «художественная трепетность».
Вывод: восприятие программы как инженерной системы, составленной из конструкций, которые соединяются по определённым правилам, не сформировано у массовых программистов, и это представляет реальную проблему для развития ИТ как инженерной деятельности. Обязательное требование к инженерной деятельности — наличие строгих (обычно математизированных) методов, позволяющих анализировать и гарантировать свойства создаваемых конструкций, выводя их из свойств использованных элементов и соединений. Как это может выглядеть для ПО, было показано, например, Дейкстрой в «Дисциплине программирования».