Существенная сложность

Эссенциальная сложность — это численная мера, определенная Томасом Дж. Маккейбом-старшим в его широко цитируемой статье 1976 года, более известной благодаря введению цикломатической сложности . Маккейб определил существенную сложность как циклическую сложность сокращенного CFG ( графа потока управления ) после итеративной замены (сокращения) всех структурного программирования управляющих структур , то есть тех, которые имеют одну точку входа и одну точку выхода (например, if-then-else). и циклы while) с отдельными операторами-заполнителями. ^[1]^: 317^[2]^: 80

Процесс сокращения МакКейба предназначен для моделирования концептуальной замены структур управления (и фактических операторов, которые они содержат) вызовами подпрограмм, отсюда и требование, чтобы структуры управления имели одну точку входа и одну точку выхода. ^[1]^: 317 (В настоящее время подобный процесс подпадает под общий термин « рефакторинг» .) Очевидно, что все структурированные программы имеют существенную сложность 1, как это определено Маккейбом, поскольку все они могут быть итеративно сведены к одному вызову подпрограммы верхнего уровня. ^[1]^: 318 Как объясняет Маккейб в своей статье, его основная метрика сложности была разработана для того, чтобы измерить, насколько далека от этого идеала (полностью структурирована) данная программа. ^[1]^: 317 Таким образом, существенные числа сложности больше 1, которые можно получить только для неструктурированных программ, указывают на то, что они находятся дальше от идеала структурированного программирования. ^[1]^: 317

Чтобы избежать путаницы между различными понятиями сводимости к структурированным программам, важно отметить, что статья Маккейба кратко обсуждает, а затем оперирует в контексте статьи С. Рао Косараджу 1973 года , в которой дано уточнение (или альтернативный взгляд) на структурированную программу. теорема . В основополагающей статье Бема и Якопини 1966 года было показано, что все программы могут быть [пере]писаны с использованием только конструкций структурированного программирования (также известных как структуры D: последовательность, if-then-else и цикл while), однако при преобразовании случайного программу в структурированную программу, возможно, потребуется ввести дополнительные переменные (и использовать их в тестах), а некоторый код может быть дублирован. ^[3]

В своей статье Бём и Якопини предположили, но не доказали, что необходимо вводить такие дополнительные переменные для некоторых видов неструктурированных программ, чтобы преобразовать их в структурированные программы. ^[4]^: 236 Пример программы (как мы теперь знаем) действительно требует таких дополнительных переменных — это цикл с двумя условными выходами внутри него. Чтобы ответить на гипотезу Бема и Якопини, Косараджу определил более ограничительное понятие редукции программы, чем эквивалентность Тьюринга, используемую Бёмом и Якопини. По сути, понятие редукции Косараджу налагает, помимо очевидного требования, что две программы должны вычислять одно и то же значение (или не завершать работу) при одних и тех же входных данных, что две программы должны использовать одни и те же примитивные действия и предикаты, последние понимаются как используемые выражения. в условных предложениях. Из-за этих ограничений сокращение Косараджу не позволяет вводить дополнительные переменные; присвоение этим переменным привело бы к созданию новых примитивных действий, а проверка их значений изменила бы предикаты, используемые в условных выражениях. Используя это более ограничительное понятие редукции, Косараджу доказал гипотезу Бема и Якопини, а именно, что цикл с двумя выходами не может быть преобразован в структурированную программу. не вводя дополнительных переменных , но пошел дальше и доказал, что программы, содержащие многоуровневые разрывы (из циклов), образуют иерархию, такую, что всегда можно найти программу с многоуровневыми разрывами глубины n , которую невозможно свести к программе из нескольких -уровневые разрывы с глубиной меньше n , опять же без введения дополнительных переменных. ^[4]^[5]

Маккейб отмечает в своей статье, что, учитывая результаты Косараджу, он намеревался найти способ отразить основные свойства неструктурированных программ в терминах их графов потока управления. ^[1]^: 315 Он начинает с того, что сначала идентифицирует графы потока управления, соответствующие наименьшим неструктурированным программам (к ним относятся ветвление в цикл, ветвление из цикла и их аналоги «если-то-иначе»), которые он использует для формулировки теоремы, аналогичной Куратовского , и после этого он вводит свое понятие существенной сложности, чтобы дать масштабный ответ («мера структурированности программы», по его словам), а не ответ «да/нет» на вопрос о том, является ли поток управления программой график структурирован или нет. ^[1]^: 315 Наконец, понятие сокращения, используемое Маккейбом для сокращения CFG, не то же самое, что понятие Косараджу о сокращении блок-схем. Сокращение, определенное в CFG, не знает и не заботится о входных данных программы, это просто преобразование графа . ^[6]

Например, следующий фрагмент программы на языке C имеет существенную сложность, равную 1, поскольку внутренний оператор if и for можно сократить, т. е. это структурированная программа.

   for (i = 0; i < 3; i++) {
      if (a[i] == 0) b[i] += 2;
   }

Следующий фрагмент программы на языке C имеет сложность, равную четырем; его CFG неприводим. Программа находит первую строку z, которая полностью равна нулю, и помещает этот индекс в i; если его нет, в i помещается -1.

   for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++) {
         if (z[i][j] != 0)
            goto non_zero;
      }
      goto found;
non_zero:
   }
   i = -1;
found:

Идея сводимости CFG путем последовательного коллапса подграфов (в конечном итоге до одного узла для корректных CFG) также используется в современной оптимизации компилятора. Однако понятие структуры управления с одним входом и одним выходом из структурного программирования заменяется понятием естественного цикла , который определяется как «цикл с одним входом и несколькими выходами, имеющий только одну ветвь, ведущую обратно к входу изнутри». это". Области CFG, которые не могут быть сведены к естественным петлям, называются несобственными областями ; эти регионы в конечном итоге имеют довольно простое определение: множественные, сильно связанные компоненты CFG. Таким образом, простейшая несобственная область представляет собой цикл с двумя точками входа. Множественные выходы не вызывают проблем анализа в современных компиляторах. Неправильные регионы (множественные входы в циклы) вызывают дополнительные трудности при оптимизации кода. ^[7]

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Маккейб (декабрь 1976 г.). «Мера сложности». Транзакции IEEE по разработке программного обеспечения (4): 308–320. дои : 10.1109/tse.1976.233837 . S2CID 9116234 .
^ http://www.mccabe.com/pdf/mccabe-nist235r.pdf ^{[ только URL-адрес PDF ]}
^ Дэвид Энтони Ватт; Уильям Финдли (2004). Концепции проектирования языков программирования . Джон Уайли и сыновья. п. 228. ИСБН 978-0-470-85320-7 .
^ Jump up to: ^а ^б С. Рао Косараджу (декабрь 1974 г.). «Анализ структурированных программ». Журнал компьютерных и системных наук . 9 (3): 232–255. дои : 10.1016/S0022-0000(74)80043-7 .
^ Более современную трактовку тех же результатов см.: Козен, Теорема Бема – Якопини ложна, пропозиционально.
^ Маккейб делает сноски к двум определениям на страницах 315 и 317.
^ Стивен С. Мучник (1997). Расширенная реализация проекта компилятора . Морган Кауфманн. стр. 196–197 и 215 . ISBN 978-1-55860-320-2 .

[mccabe76-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Маккейб (декабрь 1976 г.). «Мера сложности». Транзакции IEEE по разработке программного обеспечения (4): 308–320. дои : 10.1109/tse.1976.233837 . S2CID 9116234 .

[2] ttp://www.mccabe.com/pdf/mccabe-nist235r.pdf ^{[ только URL-адрес PDF ]}

[WattFindlay2004-3] Дэвид Энтони Ватт; Уильям Финдли (2004). Концепции проектирования языков программирования . Джон Уайли и сыновья. п. 228. ИСБН 978-0-470-85320-7 .

[K-4] Jump up to: ^а ^б С. Рао Косараджу (декабрь 1974 г.). «Анализ структурированных программ». Журнал компьютерных и системных наук . 9 (3): 232–255. дои : 10.1016/S0022-0000(74)80043-7 .

[5] Более современную трактовку тех же результатов см.: Козен, Теорема Бема – Якопини ложна, пропозиционально.

[6] Маккейб делает сноски к двум определениям на страницах 315 и 317.

[Muchnick1997-7] Стивен С. Мучник (1997). Расширенная реализация проекта компилятора . Морган Кауфманн. стр. 196–197 и 215 . ISBN 978-1-55860-320-2 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]