Teorema del programa estructurado - Structured program theorem

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

El teorema del programa estructurado , también llamado teorema de Böhm-Jacopini , es un resultado en la teoría del lenguaje de programación . Establece 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 solo tres formas específicas ( estructuras de control ). Estos son

  1. Ejecutar un subprograma y luego otro subprograma (secuencia)
  2. Ejecutar uno de los 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 puede usar variables adicionales en forma de bits (almacenadas en una variable entera adicional en la prueba original) para realizar un seguimiento de la información que el programa original representa por 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.

Origen y variantes

El teorema se atribuye típicamente a un artículo de 1966 de Corrado Böhm y Giuseppe Jacopini . David Harel escribió en 1980 que el artículo de Böhm-Jacopini gozaba de "popularidad universal", 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" y, después de revisar un gran número de artículos publicados hasta 1980, Harel argumentó que el contenido del Las pruebas de Böhm-Jacopini generalmente se tergiversaron como un teorema popular que esencialmente contiene un resultado más simple, un resultado que se remonta al inicio de la teoría de la computación moderna en los artículos de von Neumann y Kleene .

Harel también escribe que HD Mills propuso el nombre más genérico como "El teorema de la estructura" a principios de la década de 1970.

Versión folklórica del teorema de ciclo simple 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 pasa por 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 solo proporciona semántica operativa para la ejecución de un diagrama de flujo en una computadora von Neumann. Otra fuente aún más antigua que Harel trazó la versión popular del teorema es Stephen Kleene 's forma normal teorema a partir de 1936.

Donald Knuth criticó esta forma de prueba, que da como resultado un pseudocódigo como el siguiente, al señalar que la estructura del programa original se pierde por completo en esta transformación. 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. Simulando una máquina de Von Neumann, podemos producir el comportamiento de cualquier código espagueti dentro de los confines de un lenguaje estructurado en bloques. Esto no impide que se convierta en espagueti ".

p := 1
while p > 0 do
    if p = 1 then
        perform step 1 from the flowchart
        p := resulting successor step number of step 1 from the flowchart (0 if no successor)
    end if
    if p = 2 then
        perform step 2 from the flowchart
        p := resulting successor step number of step 2 from the flowchart (0 if no successor)
    end if
    ...
    if p = n then
        perform step n from the flowchart
        p := resulting successor step number of step n from the flowchart (0 if no successor)
    end if
end while

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. Debido a que empleó la coincidencia de patrones en los gráficos , la prueba de Böhm y Jacopini no fue realmente práctica como un algoritmo de transformación de programas y, por lo tanto, abrió la puerta a investigaciones adicionales en esta dirección.

Implicaciones y refinamientos

La prueba de Böhm-Jacopini no resolvió la cuestión de si se debía adoptar la 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 perjudicial ", siguió en 1968.

Algunos académicos adoptaron un enfoque purista del resultado de Böhm-Jacopini y argumentaron que incluso las 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 solo punto de salida. Este enfoque purista está incorporado 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.

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

La aplicación directa del teorema de Böhm-Jacopini puede resultar en la introducción de variables locales adicionales en el gráfico estructurado, y también puede resultar en alguna duplicación de código . Este último problema se denomina problema de bucle y medio en este contexto. Pascal se ve afectado por ambos problemas y, según los estudios empíricos citados por Eric S. Roberts , los estudiantes de programación tenían 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, la solución correcta fue dada por solo el 20% de los sujetos, mientras que ningún sujeto escribió un código incorrecto para este problema si se le permitía escribir un retorno de la en medio de un bucle.

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. 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 por cada entero n , existe un programa que contiene una ruptura multinivel de profundidad n que no se puede reescribir como programa con rupturas multinivel de profundidad menor que n (sin introducir variables adicionales). Kosaraju cita la construcción de ruptura multinivel del lenguaje de programación BLISS . Las pausas multinivel, en forma de palabra clave, se introdujeron en realidad en la versión BLISS-11 de ese idioma; el BLISS original solo tenía descansos de un solo nivel. La familia de idiomas BLISS no proporcionó un goto sin restricciones. Más tarde, el lenguaje de programación Java también seguiría este enfoque. leave label

Un resultado más simple del artículo de Kosaraju es que un programa se puede reducir a un programa estructurado (sin agregar variables) si y solo si no contiene un bucle con dos salidas distintas. La reducibilidad fue definida por Kosaraju, vagamente hablando, como calcular la misma función y usar las mismas "acciones primitivas" y predicados que el programa original, pero posiblemente usando diferentes estructuras de flujo de control. (Esta es una noción de reducibilidad más estrecha que la que utilizó Böhm-Jacopini). Inspirado por este resultado, en la sección VI de su artículo muy citado 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 esté estructurado. Estos subgrafos tienen una muy buena descripción en lenguaje natural. 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. ramificación de una decisión

McCabe en realidad descubrió 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 no esté 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 subgráficos, debe contener otro distinto del conjunto de cuatro. Este último resultado ayuda a explicar cómo el flujo de control del 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 .

La caracterización de McCabe de los gráficos prohibidos para la programación estructurada puede considerarse incompleta, al menos si las estructuras D de Dijkstra se consideran los bloques de construcción.

Hasta 1990 se propusieron bastantes métodos para eliminar los gotos de los programas existentes, conservando 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 de 1988 del JACM de Lyle Ramshaw examina el campo hasta ese momento, además de proponer su propio método. 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 bifurcación con objetivos expresados ​​como compensaciones, pero el lenguaje Java de alto nivel solo tiene declaraciones breaky de varios niveles continue. Ammarguellat (1992) propuso un método de transformación que se remonta a la aplicación de una salida única.

Aplicación a Cobol

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

  1. Identifique 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 única 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 no conectada restante, agregue una declaración que establezca L al valor de la etiqueta en esa ruta.
  7. Combinar los programas resultantes en una declaración de selección que ejecuta el programa con la etiqueta de ruta de entrada indicada por L
  8. Construya un ciclo que ejecute esta instrucción de selección siempre que L no sea 0.
  9. Construya una secuencia que inicialice L en 1 y ejecute el ciclo.

Tenga en cuenta que esta construcción se puede mejorar convirtiendo algunos casos de la declaración de selección en subprocedimientos.

Ver también

Referencias

Otras lecturas

Material aún no cubierto arriba: