stringtranslate.com

Teorema del programa estructurado

El teorema del programa estructurado , también llamado teorema de Böhm-Jacopini , [1] [2] es un resultado de la teoría del lenguaje de programación . Afirma que una clase de gráficos de flujo de control (históricamente llamados diagramas de flujo en este contexto) puede calcular cualquier función computable si combina subprogramas en sólo tres formas específicas ( estructuras de control ). Estos son

  1. Ejecutar un subprograma y luego otro subprograma (secuencia)
  2. Ejecutar uno de dos subprogramas según el valor de una expresión booleana (selección)
  3. Ejecutar repetidamente un subprograma siempre que una expresión booleana sea verdadera (iteración)

Sin embargo, el gráfico estructurado sujeto a estas restricciones, particularmente la restricción de bucle que implica una única salida (como se describe más adelante en este artículo), puede usar variables adicionales en forma de bits (almacenados en una variable entera adicional en la prueba original) para realice un seguimiento de la información que el programa original representa mediante la ubicación del programa. La construcción se basó en el lenguaje de programación P′′ de Böhm .

El teorema forma la base de la programación estructurada , un paradigma de programación que evita los comandos goto y utiliza exclusivamente subrutinas, secuencias, selección e iteración.

Representación gráfica de los tres patrones básicos del teorema del programa estructurado (secuencia, selección y repetición) utilizando diagramas NS (azul) y diagramas de flujo (verde).

Origen y variantes

El teorema suele acreditarse [3] : 381  a un artículo de 1966 de Corrado Böhm y Giuseppe Jacopini. [4] David Harel escribió en 1980 que el artículo de Böhm-Jacopini gozaba de "popularidad universal", [3] : 381  particularmente entre los defensores de la programación estructurada. Harel también señaló que "debido a su estilo bastante técnico [el artículo de Böhm-Jacopini de 1966] aparentemente se cita con más frecuencia que se lee en detalle" [3] : 381  y, después de revisar una gran cantidad de artículos publicados hasta 1980, Harel argumentó que los contenidos de la prueba de Böhm-Jacopini generalmente fueron tergiversados ​​como un teorema popular que esencialmente contiene un resultado más simple, un resultado que a su vez puede rastrearse hasta el inicio de la teoría de la computación moderna en los artículos de von Neumann [5] y Kleene . [3] : 383 

Harel también escribe que el nombre más genérico fue propuesto por HD Mills como "El teorema de la estructura" a principios de los años 1970. [3] : 381 

Versión popular del teorema de bucle único while

Esta versión del teorema reemplaza todo el flujo de control del programa original con un único whilebucle global que simula un contador de programa que recorre todas las etiquetas posibles (cuadros de diagrama de flujo) en el programa no estructurado original. Harel rastreó el origen de este teorema popular en dos artículos que marcaron el comienzo de la informática. Una es la descripción de 1946 de la arquitectura de von Neumann , que explica cómo funciona un contador de programa en términos de un bucle while. Harel señala que el bucle único utilizado por la versión popular del teorema de programación estructurada básicamente proporciona semántica operativa para la ejecución de un diagrama de flujo en una computadora von Neumann. [3] : 383  Otra fuente, incluso más antigua, en la que Harel rastreó la versión popular del teorema es el teorema de la forma normal de Stephen Kleene de 1936. [3] : 383 

Donald Knuth criticó esta forma de demostración, que da como resultado un pseudocódigo como el siguiente, señalando que la estructura del programa original se pierde por completo en esta transformación. [6] : 274  De manera similar, Bruce Ian Mills escribió sobre este enfoque que "El espíritu de la estructura de bloques es un estilo, no un lenguaje. Al simular una máquina Von Neumann, podemos producir el comportamiento de cualquier código espagueti dentro de los límites de un lenguaje estructurado en bloques. Esto no impide que sea espagueti." [7]

p : = 1 mientras p > 0 haga si p = 1 , luego realice el paso 1 del diagrama de flujo p : = número de paso sucesor resultante del paso 1 del diagrama de flujo ( 0 si no hay sucesor ) finalice si p = 2 , luego realice el paso 2 desde el diagrama de flujo p : = número de paso sucesor resultante del paso 2 del diagrama de flujo ( 0 si no hay sucesor ) finaliza si ... si p = n entonces realiza el paso n del diagrama de flujo p : = número de paso sucesor resultante del paso n del diagrama de flujo ( 0 si no hay sucesor ) terminar si terminar mientras

La prueba de Böhm y Jacopini

La prueba en el artículo de Böhm y Jacopini procede por inducción sobre la estructura del diagrama de flujo. [3] : 381  Debido a que empleaba coincidencia de patrones en gráficos , la prueba de Böhm y Jacopini no era realmente práctica como algoritmo de transformación de programas y, por lo tanto, abrió la puerta a investigaciones adicionales en esta dirección. [8]

Versión reversible

El Teorema del Programa Estructurado Reversible [9] es un concepto importante en el campo de la computación reversible . Postula que cualquier cálculo que se pueda lograr mediante un programa reversible también se puede lograr mediante un programa reversible utilizando sólo una combinación estructurada de construcciones de flujo de control, como secuencias, selecciones e iteraciones. Cualquier cálculo que se pueda realizar mediante un programa tradicional irreversible también se puede realizar mediante un programa reversible, pero con la restricción adicional de que cada paso debe ser reversible y generar algún resultado adicional. [10] Además, cualquier programa no estructurado reversible también se puede lograr a través de un programa reversible estructurado con una sola iteración sin ningún resultado adicional. Este teorema sienta los principios fundamentales para construir algoritmos reversibles dentro de un marco de programación estructurado.

Para el teorema del programa estructurado, se conocen métodos de prueba tanto locales [11] como globales [12] . Sin embargo, para su versión reversible, si bien se reconoce un método de prueba global, aún no se conoce un enfoque local similar al emprendido por Böhm y Jacopini [11] . Esta distinción es un ejemplo que subraya los desafíos y matices a la hora de establecer las bases de la computación reversible en comparación con los paradigmas informáticos tradicionales.

Implicaciones y refinamientos

La prueba de Böhm-Jacopini no resolvió la cuestión de si adoptar programación estructurada para el desarrollo de software, en parte porque era más probable que la construcción oscureciera un programa que lo mejorara. Al contrario, marcó el inicio del debate. La famosa carta de Edsger Dijkstra , " Ir a la declaración considerada dañina ", apareció en 1968. [13]

Algunos académicos adoptaron un enfoque purista del resultado de Böhm-Jacopini y argumentaron que incluso instrucciones como breaky returndesde el medio de los bucles son una mala práctica ya que no son necesarias en la prueba de Böhm-Jacopini y, por lo tanto, abogaron por que todos los bucles deberían tener un único punto de salida. Este enfoque purista está plasmado en el lenguaje de programación Pascal (diseñado en 1968-1969), que hasta mediados de la década de 1990 era la herramienta preferida para impartir clases de introducción a la programación en el mundo académico. [14]

Edward Yourdon señala que en la década de 1970 hubo incluso oposición filosófica a transformar programas no estructurados en estructurados por medios automatizados, basándose en el argumento de que era necesario pensar en forma de programación estructurada desde el principio. El contrapunto pragmático fue que tales transformaciones beneficiaron a una gran cantidad de programas existentes. [15] Entre las primeras propuestas para una transformación automatizada se encontraba un artículo de 1971 de Edward Ashcroft y Zohar Manna . [dieciséis]

La aplicación directa del teorema de Böhm-Jacopini puede dar lugar a la introducción de variables locales adicionales en el gráfico estructurado y también puede dar lugar a cierta duplicación de código . [17] Esta última cuestión se denomina problema del bucle y medio en este contexto. [18] Pascal se ve afectado por ambos problemas y, según estudios empíricos citados por Eric S. Roberts , los estudiantes de programación tuvieron dificultades para formular soluciones correctas en Pascal para varios problemas simples, incluida la escritura de una función para buscar un elemento en una matriz. Un estudio de 1980 de Henry Shapiro citado por Roberts encontró que usando solo las estructuras de control proporcionadas por Pascal, solo el 20% de los sujetos dieron la solución correcta, mientras que ningún sujeto escribió código incorrecto para este problema si se le permitía escribir una respuesta del medio de un bucle. [14]

En 1973, S. Rao Kosaraju demostró que es posible evitar agregar variables adicionales en la programación estructurada, siempre que se permitan rupturas de bucles de varios niveles y profundidad arbitraria. [1] [19] Además, Kosaraju demostró que existe una jerarquía estricta de programas, hoy en día llamada jerarquía de Kosaraju , en el sentido de que para cada número entero n , existe un programa que contiene una ruptura de varios niveles de profundidad n que no se puede reescribir como programa. con rupturas de varios niveles de profundidad menor que n (sin introducir variables adicionales). [1] Kosaraju cita la construcción de ruptura de múltiples niveles en el lenguaje de programación BLISS . Las pausas de varios niveles, en forma de palabra clave, en realidad se introdujeron en la versión BLISS-11 de ese idioma; el BLISS original solo tenía descansos de un solo nivel. La familia de lenguajes BLISS no proporcionaba un acceso ilimitado. El lenguaje de programación Java también seguiría más tarde este enfoque. [20] : 960–965 leave label

Un resultado más simple del artículo de Kosaraju es que un programa es reducible a un programa estructurado (sin agregar variables) si y sólo si no contiene un bucle con dos salidas distintas. Kosaraju definió la reducibilidad, en términos generales, como calcular la misma función y utilizar las mismas "acciones primitivas" y predicados que el programa original, pero posiblemente utilizando diferentes estructuras de flujo de control. (Ésta es una noción de reducibilidad más limitada que la que utilizó Böhm-Jacopini.) Inspirado por este resultado, en la sección VI de su muy citado artículo que introdujo la noción de complejidad ciclomática , Thomas J. McCabe describió un análogo del teorema de Kuratowski para la Gráficos de flujo de control (CFG) de programas no estructurados, es decir, los subgrafos mínimos que hacen que el CFG de un programa no sea estructurado. Estos subgrafos tienen una muy buena descripción en lenguaje natural. Ellos son:

  1. ramificación de un bucle (que no sea de la prueba del ciclo del bucle)
  2. ramificándose en un bucle
  3. ramificarse en una decisión (es decir, en una "rama" if)
  4. diversificarse de una decisión

McCabe realmente encontró que estos cuatro gráficos no son independientes cuando aparecen como subgrafos, lo que significa que una condición necesaria y suficiente para que un programa sea no estructurado es que su CFG tenga como subgrafo uno de cualquier subconjunto de tres de estos cuatro gráficos. También encontró que si un programa no estructurado contiene uno de estos cuatro subgrafos, debe contener otro distinto del conjunto de cuatro. Este último resultado ayuda a explicar cómo el flujo de control de un programa no estructurado se enreda en lo que popularmente se llama " código espagueti ". McCabe también ideó una medida numérica que, dado un programa arbitrario, cuantifica qué tan lejos está del ideal de ser un programa estructurado; McCabe llamó a su medida complejidad esencial . [21]

La caracterización de McCabe de los grafos prohibidos para la programación estructurada puede considerarse incompleta, al menos si las estructuras D de Dijkstra se consideran los bloques de construcción. [22] : 274–275  [ se necesita aclaración ]

Hasta 1990 hubo bastantes métodos propuestos para eliminar gotos de programas existentes, preservando al mismo tiempo la mayor parte de su estructura. Los diversos enfoques de este problema también propusieron varias nociones de equivalencia, que son más estrictas que la simple equivalencia de Turing, para evitar resultados como el teorema popular discutido anteriormente. El rigor de la noción de equivalencia elegida dicta el conjunto mínimo de estructuras de flujo de control necesarias. El artículo JACM de 1988 de Lyle Ramshaw examina el campo hasta ese momento y propone su propio método. [23] El algoritmo de Ramshaw se usó, por ejemplo, en algunos descompiladores de Java porque el código de la máquina virtual Java tiene instrucciones de rama con objetivos expresados ​​como compensaciones, pero el lenguaje Java de alto nivel solo tiene declaraciones multinivel breaky . [24] [25] [26] Ammarguellat (1992) propuso un método de transformación que se remonta a imponer la salida única. [8]continue


Aplicación a Cobol

En la década de 1980, el investigador de IBM, Harlan Mills, supervisó el desarrollo de COBOL Structuring Facility, que aplicaba un algoritmo de estructuración al código COBOL . La transformación de Mills implicó los siguientes pasos para cada procedimiento.

  1. Identificar los bloques básicos del procedimiento.
  2. Asigne una etiqueta única a la ruta de entrada de cada bloque y etiquete las rutas de salida de cada bloque con las etiquetas de las rutas de entrada a las que se conectan. Utilice 0 para regresar del procedimiento y 1 para la ruta de entrada del procedimiento.
  3. Divida el procedimiento en sus bloques básicos.
  4. Para cada bloque que sea el destino de una sola ruta de salida, vuelva a conectar ese bloque a esa ruta de salida.
  5. Declare una nueva variable en el procedimiento (llamada L como referencia).
  6. En cada ruta de salida restante no conectada, agregue una declaración que establezca L en el valor de la etiqueta en esa ruta.
  7. Combine los programas resultantes en una declaración de selección que ejecute el programa con la etiqueta de ruta de entrada indicada por L
  8. Construya un bucle que ejecute esta declaración de selección siempre que L no sea 0.
  9. Construya una secuencia que inicialice L a 1 y ejecute el bucle.

Esta construcción se puede mejorar convirtiendo algunos casos del enunciado de selección en subprocedimientos.

Ver también

Referencias

  1. ^ a b C Dexter Kozen y Wei-Lung Dustin Tseng (2008). "El teorema de Böhm-Jacopini es falso, proposicionalmente". Matemáticas de la construcción de programas (PDF) . Apuntes de conferencias sobre informática. vol. 5133, págs. 177-192. CiteSeerX  10.1.1.218.9241 . doi :10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. {{cite book}}: |journal=ignorado ( ayuda )
  2. ^ "CSE 111, otoño de 2004, TEOREMA DE BOEHM-JACOPINI". Cse.buffalo.edu. 2004-11-22 . Consultado el 24 de agosto de 2013 .
  3. ^ abcdefgh Harel, David (1980). "Sobre los teoremas populares" (PDF) . Comunicaciones de la ACM . 23 (7): 379–389. doi :10.1145/358886.358892. S2CID  16300625.
  4. ^ Bohm, Corrado; Giuseppe Jacopini (mayo de 1966). "Diagramas de flujo, máquinas de Turing y lenguajes con sólo dos reglas de formación". Comunicaciones de la ACM . 9 (5): 366–371. CiteSeerX 10.1.1.119.9119 . doi :10.1145/355592.365646. S2CID  10236439. 
  5. ^ Burks, Arthur W .; Goldstine, Herman ; von Neumann, John (1947), Discusión preliminar sobre el diseño lógico de un instrumento informático electrónico , Princeton, Nueva Jersey: Instituto de estudios avanzados
  6. ^ Donald Knuth (1974). "Programación estructurada con declaraciones go to". Encuestas Informáticas . 6 (4): 261–301. CiteSeerX 10.1.1.103.6084 . doi :10.1145/356635.356640. S2CID  207630080. 
  7. ^ Bruce Ian Mills (2005). Introducción Teórica a la Programación . Saltador. pag. 279.ISBN​ 978-1-84628-263-8.
  8. ^ ab Ammarguellat, Z. (1992). "Un algoritmo de normalización del flujo de control y su complejidad". Transacciones IEEE sobre ingeniería de software . 18 (3): 237–251. doi :10.1109/32.126773.
  9. ^ Yokoyama, Tetsuo; Axelsen, Holger Bock; Glück, Robert (enero de 2016). "Fundamentos de los lenguajes de diagramas de flujo reversibles". Informática Teórica . 611 : 87-115. doi : 10.1016/j.tcs.2015.07.046 .
  10. ^ Bennett, CH (noviembre de 1973). "Reversibilidad lógica de la computación". Revista IBM de investigación y desarrollo . 17 (6): 525–532. doi :10.1147/rd.176.0525.
  11. ^ ab Böhm, Corrado; Jacopini, Giuseppe (mayo de 1966). "Diagramas de flujo, máquinas de Turing y lenguajes con sólo dos reglas de formación". Comunicaciones de la ACM . 9 (5): 366–371. doi :10.1145/355592.365646.
  12. ^ Cooper, David C. (agosto de 1967). "Reducción de diagramas de flujo de Böhm y Jacopini". Comunicaciones de la ACM . 10 (8): 463. doi : 10.1145/363534.363539.
  13. ^ Dijkstra, Edsger (1968). "Ir a Declaración considerada nociva". Comunicaciones de la ACM . 11 (3): 147–148. doi : 10.1145/362929.362947 . S2CID  17469809.
  14. ^ ab Roberts, E. [1995] "Salidas de bucle y programación estructurada: reapertura del debate", Boletín ACM SIGCSE, (27)1: 268–272.
  15. ^ ES Yourdon (1979). Clásicos en Ingeniería de Software . Prensa Yourdon. págs. 49–50. ISBN 978-0-917072-14-7.
  16. ^ Ashcroft, Eduardo; Zohar Maná (1971). "La traducción de ir a programas a programas 'mientras'". Actas del Congreso IFIP .El artículo, que es difícil de obtener en las actas originales de la conferencia debido a su distribución limitada, se volvió a publicar en el libro de Yourdon de 1979, páginas 51-65.
  17. ^ 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.
  18. ^ Kenneth C. Louden; Kenneth A. Lambert (2011). Lenguajes de programación: principios y prácticas (3 ed.). Aprendizaje Cengage. págs. 422–423. ISBN 978-1-111-52941-3.
  19. ^ KOSARAJU, S. RAO. "Análisis de programas estructurados", Proc. Quinto Jarabe Anual de ACM. Teoría de la Computación, (mayo de 1973), 240-252; también Kosaraju, S. Rao (1974). "Análisis de programas estructurados". Revista de Ciencias de la Computación y de Sistemas . 9 (3): 232–255. doi :10.1016/S0022-0000(74)80043-7.citado por Donald Knuth (1974). "Programación estructurada con declaraciones go to". Encuestas Informáticas . 6 (4): 261–301. CiteSeerX 10.1.1.103.6084 . doi :10.1145/356635.356640. S2CID  207630080. 
  20. ^ Brender, Ronald F. (2002). "El lenguaje de programación BLISS: una historia" (PDF) . Software: práctica y experiencia . 32 (10): 955–981. doi :10.1002/spe.470. S2CID  45466625.
  21. ^ El artículo original es Thomas J. McCabe (diciembre de 1976). "Una medida de complejidad". Transacciones IEEE sobre ingeniería de software . SE-2 (4): 315–318. doi :10.1109/tse.1976.233837. S2CID  9116234.Para una exposición secundaria, ver Paul C. Jorgensen (2002). Pruebas de software: un enfoque artesanal, segunda edición (2ª ed.). Prensa CRC. págs. 150-153. ISBN 978-0-8493-0809-3.
  22. ^ Williams, MH (1983). "Esquemas de diagrama de flujo y el problema de la nomenclatura". La revista informática . 26 (3): 270–276. doi : 10.1093/comjnl/26.3.270 .
  23. ^ Ramshaw, L. (1988). "Eliminar las visitas y preservar la estructura del programa". Revista de la ACM . 35 (4): 893–920. doi : 10.1145/48014.48021 . S2CID  31001665.
  24. ^ Godfrey Nolan (2004). Descompilando Java . Presione. pag. 142.ISBN​ 978-1-4302-0739-9.
  25. ^ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf [ URL básica PDF ]
  26. ^ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf [ URL básica PDF ]

Otras lecturas

Material aún no cubierto anteriormente: