Teorema del programa estructurado
Teorema del programa estructurado. (Corrado Böhm, Giuseppe Jacopini, 1966). Teorema que soporta la posibilidad que tiene la programación estructurada de expresar un algoritmo computable cualquiera mediante un lenguaje basado solo en secuencias de instrucciones, alternativas y ciclos tipo "while".
Teorema del programa estructurado
La teoría de lenguajes de programación tiene varios hitos en su desarrollo, el presente teorema es uno de ellos. Su definición más acertada se centra en el trabajo de 1966 de Corrado Böhm y Giuseppe Jacopini, quienes plantean que toda función computable puede ser implementada solo tres tipos de estructuras de programación:
- Las instrucciones son o una instrucción simple o una secuencia ordenada de instrucciones (estructura secuencial).
- Según el resultado de una expresión lógica se ejecuta una instrucción u otra (estructura condicional o alternativa).
- Mientras una condición se mantenga verdadera ejecutar una instrucción (estructura iterativa, ciclica o de bucle).
La demostración se realizó sobre las los diagramas de flujo y P, el lenguaje diseñado por Böhm.
La 2da y 3ra esctructuras propuestas se corresponden a las clásicas IF...THEN...ELSE y WHILE, respectivamente.
Implicaciones
Del Teorema del Programa Estructurado se establece que todos los algoritmos que se pueden desarrollar en una computadora pueden escribirse de siguiendo lo que luego se conocería como uno de los paradigmas dentro de la programación imperativa, la programación estructurada y con él se demostraba la capacidad expresiva de ésta para el desarrollo de soluciones computacionales.
En su demostración se probaba que todo diagrama de flujo puede transcribirse a uno estructurado y se establecía un método formal para realizar la conversión aunque después el programador pudiera refinarla.
También daba una idea de las tres estructuras que serían indispensables a la hora de diseñar un lenguaje estructurado: secuencial, condicional y cíclica; aunque es evidente que puede extenderse a otras estructuras derivadas de estas que enriquezcan la expresión semántica y sintáctica del lenguaje en cuestión.
Lo que sí el artículo donde aparece el teorema no deja claro es cuándo es más pertinente el uso de la programación estructurada por sobre otros paradigmas.
Y como dato interesante, después de esta formalización se generó el fuerte debate sobre la existencia o no de la instrucción de salto GOTO, que ha llegado hasta nuestros días; sin embargo, existe el consenso acerca de que la misma no es necesaria en los lenguajes de alto nivel y que su presencia solo entorpece la legibilidad y elegancia del código, aunque todavía aparece la implementación de GOTO en muchos lenguajes modernos. El debate comenzó con Edsger Dijkstra quien escribió "La sentencia Go To considerada dañina" (1968), una carta considerada hoy un clásico, como la mayoría de los trabajos del científico.
Debates acerca del teorema
Normalmente la originalidad de la idea se data oficial del artículo "Flow diagrams, Turing Machines and Languages with only Two Formation Rules" (Comm. of the ACM, 9(5): 366-371,1966), de Corrado Böhm y Giuseppe Jacopini; aunque otros especialistas como David Harel argumentan haber encontrado los rastros en trabajos clasicos de cientistas anteriores como las definiciones formales de la arquitectura de computadoras de von Newmann y las formas normales de Kleene.
Fuentes
- Corrado Böhm y Giuseppe Jacopini, "Flow diagrams, Turing Machines and Languages with only Two Formation Rules". Comm. of the ACM, 9(5): 366-371,1966. http://portal.acm.org/citation.cfm?id=365646&jmp=cit&dl=GUIDE&dl=ACM#CIT
- CSE 111, Fall 2004. http://www.cse.buffalo.edu/~rapaport/111F04/greatidea3.html
- Dijkstra, Edsger W. (1968), "Go To Statement Considered Harmful" (Letter to the Editor), Communications of the ACM 11(3) (March): 147-148. http://www.acm.org/classics/oct95/
- Wikipedia en Espanol, http://es.wikipedia.org/wiki/Teorema_del_programa_estructurado
