La complejidad esencial es una medida numérica definida por Thomas J. McCabe, Sr., en su artículo de 1976 muy citado, más conocido por introducir la complejidad ciclomática . McCabe definió la complejidad esencial como la complejidad ciclomática del CFG reducido ( gráfico de flujo de control ) después de reemplazar iterativamente (reducir) todas las estructuras de control de programación estructuradas , es decir, aquellas que tienen un único punto de entrada y un único punto de salida (por ejemplo, if-then-else y bucles while) con declaraciones únicas de marcador de posición. [1] : 317 [2] : 80
El proceso de reducción de McCabe está destinado a simular el reemplazo conceptual de las estructuras de control (y las declaraciones reales que contienen) con llamadas a subrutinas, de ahí el requisito de que las estructuras de control tengan una sola entrada y un solo punto de salida. [1] : 317 (Hoy en día, un proceso como este caería bajo el término general de refactorización .) Todos los programas estructurados tienen evidentemente una complejidad esencial de 1 según lo definido por McCabe porque todos pueden reducirse iterativamente a una sola llamada a un top- subrutina de nivel. [1] : 318 Como explica McCabe en su artículo, su métrica de complejidad esencial fue diseñada para proporcionar una medida de cuán lejos de este ideal (de estar completamente estructurado) estaba un programa dado. [1] : 317 Por lo tanto, mayores que 1 números de complejidad esencial, que solo se pueden obtener para programas no estructurados, indican que están más lejos del ideal de programación estructurada. [1] : 317
Para evitar la confusión entre varias nociones de reducibilidad a programas estructurados, es importante señalar que el artículo de McCabe analiza brevemente y luego opera en el contexto de un artículo de 1973 de S. Rao Kosaraju , que dio un refinamiento (o visión alternativa) del programa estructurado. teorema . El artículo seminal de 1966 de Böhm y Jacopini mostró que todos los programas pueden [re] escribirse utilizando solo construcciones de programación estructuradas (también conocidas como estructuras D: secuencia, si-entonces-si no y mientras-bucle), sin embargo, al transformar un ciclo aleatorio programa en un programa estructurado es posible que sea necesario introducir variables adicionales (y utilizarlas en las pruebas) y es posible que se duplique algo de código. [3]
En su artículo, Böhm y Jacopini conjeturaron, pero no probaron, que era necesario introducir tales variables adicionales para ciertos tipos de programas no estructurados con el fin de transformarlos en programas estructurados. [4] : 236 Un ejemplo de programa (que ahora conocemos) requiere tales variables adicionales es un ciclo con dos salidas condicionales dentro. Para abordar la conjetura de Böhm y Jacopini, Kosaraju definió una noción de reducción de programa más restrictiva que la equivalencia de Turing utilizada por Böhm y Jacopini. Esencialmente, la noción de reducción de Kosaraju impone, además del requisito obvio de que los dos programas deben calcular el mismo valor (o no terminar) dadas las mismas entradas, que los dos programas deben usar las mismas acciones primitivas y predicados, entendiendo estos últimos como expresiones utilizadas. en los condicionales. Debido a estas restricciones, la reducción de Kosaraju no permite la introducción de variables adicionales; asignar a estas variables crearía nuevas acciones primitivas y probar sus valores cambiaría los predicados usados en los condicionales. Utilizando esta noción más restrictiva de reducción, Kosaraju demostró la conjetura de Böhm y Jacopini, a saber, que un bucle con dos salidas no se puede transformar en un programa estructurado sin introducir variables adicionales , pero fue más allá y demostró que los programas que contienen rupturas multinivel (de bucles) Formar una jerarquía, de modo que siempre se pueda encontrar un programa con rupturas multinivel de profundidad n que no se pueda reducir a un programa de rupturas multinivel con profundidad menor que n , nuevamente sin introducir variables adicionales. [4] [5]
McCabe señala en su artículo que, en vista de los resultados de Kosaraju, tenía la intención de encontrar una manera de capturar las propiedades esenciales de los programas no estructurados en términos de sus gráficos de flujo de control. [1] : 315 Procede identificando primero los gráficos de flujo de control correspondientes a los programas no estructurados más pequeños (estos incluyen la ramificación en un bucle, la ramificación de un bucle y sus contrapartes if-then-else) que utiliza para formula un teorema análogo al teorema de Kuratowski , y luego introduce su noción de complejidad esencial para dar una respuesta de escala ("medida de la estructuración de un programa" en sus palabras) en lugar de una respuesta de sí / no a la pregunta de si El gráfico de flujo de control de un programa está estructurado o no. [1] : 315 Finalmente, la noción de reducción utilizada por McCabe para encoger el CFG no es la misma que la noción de Kosaraju de reducir los diagramas de flujo. La reducción definida en el CFG no conoce ni se preocupa por las entradas del programa, es simplemente una transformación gráfica . [6]
Por ejemplo, el siguiente fragmento de programa en C tiene una complejidad esencial de 1, porque la instrucción if interna y for pueden reducirse, es decir, es un programa estructurado.
para ( i = 0 ; i < 3 ; i ++ ) { si ( a [ i ] == 0 ) b [ i ] + = 2 ; }
El siguiente fragmento de programa en C tiene una complejidad esencial de cuatro; su CFG es irreductible. El programa encuentra la primera fila de z que es todo cero y pone ese índice en i; si no hay ninguno, pone -1 en i.
for ( i = 0 ; i < m ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { if ( z [ i ] [ j ] ! = 0 ) goto non_zero ; } goto encontrado ; distinto de cero : } i = -1 ; encontrado :
La idea de reducibilidad de CFG mediante colapsos sucesivos de subgráficos (en última instancia, a un solo nodo para CFG de buen comportamiento) también se utiliza en la optimización de compiladores modernos. Sin embargo, la noción de la programación estructurada de estructura de control de entrada única y salida única se reemplaza por la de bucle natural , que se define como un " bucle de entrada única y salida múltiple, con una sola rama de regreso a la entrada desde dentro eso". Las áreas del CFG que no se pueden reducir a bucles naturales se denominan regiones inadecuadas ; estas regiones terminan teniendo una definición bastante simple: componentes de entrada múltiple y fuertemente conectados del CFG. La región impropia más simple es, por tanto, un bucle con dos puntos de entrada. Las salidas múltiples no causan problemas de análisis en los compiladores modernos. Las regiones incorrectas (entradas múltiples en bucles) causan dificultades adicionales en la optimización del código. [7]
Ver también
Referencias
- ↑ a b c d e f g McCabe (diciembre de 1976). "Una medida de complejidad". Transacciones IEEE sobre ingeniería de software (4): 308–320. doi : 10.1109 / tse.1976.233837 . S2CID 9116234 .
- ^ http://www.mccabe.com/pdf/mccabe-nist235r.pdf
- ^ David Anthony Watt; William Findlay (2004). Conceptos de diseño de lenguajes de programación . John Wiley e hijos. pag. 228. ISBN 978-0-470-85320-7.
- ^ a b S. Rao Kosaraju (diciembre de 1974). "Análisis de programas estructurados" . Revista de Ciencias de la Computación y Sistemas . 9 (3): 232-255. doi : 10.1016 / S0022-0000 (74) 80043-7 .
- ↑ Para un tratamiento más moderno de los mismos resultados, ver: Kozen, The Böhm-Jacopini Theorem is False, Propositionally
- ^ McCabe anota las dos definiciones de en las páginas 315 y 317.
- ^ Steven S. Muchnick (1997). Implementación avanzada del diseño del compilador . Morgan Kaufmann. págs. 196-197 y 215 . ISBN 978-1-55860-320-2.