EDITAR: INTRODUCCIÓN

Para llegar a un público más amplio, reformulé mi pregunta original a través de un ejemplo elaborado (y algo tedioso) de la vida real. La pregunta original se muestra (lejos) a continuación.

Tom acaba de ser contratado (dependiendo de su desempeño durante sus primeros dos días hábiles) para Acme Inc. como ingeniero de software junior. Su trabajo es implementar algoritmos diseñados por los desarrolladores de software senior, en el lenguaje de programación Acme ++. La compañía sigue un estricto "nogoto"política por orden exclusiva del CEO. En caso de que Tom pueda desempeñarse excepcionalmente en su tiempo de prueba, se le ofrecerá un trabajo a tiempo completo en la empresa.

El día 1, Tom recibe el siguiente algoritmo para ser implementado.

Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 4 otherwise goto Step 5
Step 4. Set x=-x
Step 5. Output x
Step 6. END

Tom siente que la tarea es muy complicada y cree que se beneficiaría de estudiar la estructura abstracta del programa, al representarla como un diagrama de flujo. Después de dibujar el siguiente diagramaDiagrama de flujo del primer día se da cuenta rápidamente de que se le pidió que calcule el valor absoluto de x, y que puede implementarlo con una simple declaración if-then-else. Tom está muy feliz y termina su tarea al final del día.

El día 2, Tom recibe el siguiente algoritmo para ser implementado.

Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 2 otherwise goto Step 4
Step 4. Output x
Step 5. END

Tom, siendo un novato, siente que nuevamente sería mejor entender el algoritmo de manera abstracta, por lo que dibuja el siguiente diagrama de flujoDiagrama de flujo del día dos.

La inspección del diagrama de flujo revela que se le pidió a Tom que implementara un ciclo while que esperara la primera entrada no negativa. Tom está muy feliz y termina su tarea al final del día.

Basado en su desempeño sobresaliente, Tom ha sido contratado para la compañía.

En el día 3, sin embargo, Tom está siendo arrojado al fondo cuando recibe un algoritmo de 1000 líneas con 1996goto saltos, diseñados por un ex empleado de la compañía, y no queda nadie más que sepa qué hace el algoritmo, cómo lo hace y por qué fue diseñado de esa manera en primer lugar. Sin embargo, esto no le concierne a Tom en absoluto, ya que su única tarea es implementar el algoritmo independientemente de lo que sea. Armado con los dos días previos de experiencia, dibuja el diagrama de flujo en 1000 nodos con bordes dirigidos en 1997. Tom, muy desesperado, pregunta en stackoverflow qué diablos hacer con tal desorden, donde los programadores experimentados le aconsejan repetidamente que

divida el programa en pedazos más pequeños; yse aseguró de que en ciertos casos está bien usargoto; yse le dice que "reestructura" el programa.

Tom, siendo muy diligente, considera estos consejos, y su idea es la siguiente:

se da cuenta de que si un componente conectado del diagrama de flujo tiene exactamente un grado de entrada y exactamente un grado de salida, entonces eso puede considerarse como un "sub-algoritmo" que puede desarrollarse de forma independiente, para que él pueda romper su tarea de esta forma. Él, sin embargo, no tiene idea de cómo encontrar dichos componentes en primer lugar, y si hay otras formas inteligentes de resolver el problema aún más.A Tom no le importa si usargoto es una buena o mala práctica de programación (ver¿GOTO todavía se considera dañino?), lo que le preocupa es que hay ciertas pautas de programación en su empresa que debe seguir en todo momento.De hecho, Tom puede tocar el algoritmo en el sentido de que podría reemplazar ciertas instrucciones que conducen a un algoritmo equivalente a su propia discreción. Sin embargo, Tom no tiene idea de qué parte del programa requiere reestructuración y, lo que es más importante, no comprende por qué es necesaria la reestructuración. Tom mira nerviosamente su gráfico de 1000 vértices, y realmente no sabe cómo comenzar a implementarlo en primer lugar.Las preguntas sobre esta publicación (editada) son las siguientes:

¿Puedes ayudar a Tom a descubrir cómo comenzar a implementar algo que no es "obvio en dos líneas"? En particular, ¿está claro que en qué orden se deben implementar las tareas descritas por los nodos del diagrama de flujo? ¿Está claro que en qué orden deben venir ciertos bucles anidados uno tras otro?

¿Cuáles son los "átomos" más pequeños del diagrama de flujo que no se pueden dividir en pedazos más pequeños? Es decir, ¿cuándo puede Tom responder con confianza al desbordamiento de pila que "ya he dividido mi algoritmo en partes más pequeñas"? ¿Es cierto que todo es esencialmente un bucle while y / o un punto binario de ramificación (las tareas de los días uno y dos)?

¿Cómo implementar tal "átomo" automáticamente, más o menos de la misma manera que Tom lo hizo en los días uno y dos ya?

¿Puede Tom discutir con el CEO que usandogoto en ciertos casos es esencial, es decir, o lo usan para implementar cierto algoritmo o no hay absolutamente ninguna otra manera de implementarlo de acuerdo con las pautas de la compañía (es decir, sin el uso degoto)?

¿Qué partes del diagrama de flujo son problemáticas y requieren reestructuración, y por qué? Por ejemplo, una rama de tres vías podría reemplazarse por una declaración anidada de dos vías si-entonces-otra, es decir, Tom podría asumir con seguridad que cada nodo en su diagrama de flujo tiene un grado máximo de dos. Pero, ¿qué otras reestructuraciones se deben hacer para lidiar con todos los bucles anidados causados porgoto declaraciones? ¿Qué propiedad gráfica hace necesaria la reestructuración? Quizás, ¿alto grado?

¿Cuál es la teoría matemática (gráfica) detrás del diagrama de flujo de un algoritmo propuesto originalmente (por el equipo de desarrollo de software), y el diagrama de flujo reestructurado y desglosado del algoritmo (s) cuál (digamos Tom) en realidad más -o menosautomáticamente ¿implementos?

PREGUNTA ORIGINAL

Supongamos que tengo algún algoritmo que usa decisiones binarias ygoto declaraciones. El algoritmo se describe en N> = 2 (finitos) pasos de la siguiente manera de alto nivel, y debe ejecutarse secuencialmente (un paso tras otro):

ALGORITMO CUALQUIERA

Step 1. START
Step 2. Do something. If condition in Step 2 holds goto Step X else goto Step Y.
Step 3. Do something. If condition in Step 3 holds goto Step U else goto Step V.
Step 4. Do something.
Step 5. Do something. If condition in Step 5 holds goto...
Step 6. ...
...
Step N. END

Tienes la idea. Por ejemplo, Knuth describe los algoritmos en sus libros de una manera independiente de lenguaje de programación de alto nivel.

La pregunta ahora es cómo transformar una descripción de tan alto nivel congoto declaraciones en una implementación real con bucles while y declaraciones if / else? ¿Es posible eliminar completamente todos losgoto declaraciones y reemplazarlas por un ciclo while? Si es así, ¿cómo se debe hacer esto?en general?

Según la descripción del algoritmo, es posible construir el diagrama de flujo correspondiente y, por lo tanto, el gráfico de flujo (dirigido). En otras palabras, la pregunta es "Cómo implementar un código basado en su diagrama de flujo singoto declaracionesen general? ".

Hay dos formas de responder esta pregunta. Preferiblemente, y con suerte, estoy buscando una forma algorítmica de implementar ALGORITHM LO QUE SEA. Si ALGORITMO LO QUE ESmuy simple, entonces es intuitivamente claro lo que uno debe hacer, pero me parece que las cosas se complican bastante una vez que se visita un paso con frecuencia (hay muchas declaraciones de goto saltando allí), o, en otras palabras, cuando uno de los nodos de El diagrama de flujo tiene un gran grado. Entonces no veo exactamente en qué orden particular deben anidarse los bucles while. Por otro lado, es muy posible que uno simplemente no pueda hacer lo que quiero en general, y tal respuesta debería estar respaldada por una descripción de alto nivel de ALGORITMO IMPOSIBLE que demuestre claramente que pase lo que pase, simplemente no puede evitar el uso degoto salta en una implementación real.

Me parece que la implementación de transformación en diagramas de flujo se preguntó varias veces:Herramienta de diagrama de flujo automático y aquíAlgoritmo para crear un diagrama de flujo [¿Un poco de guía?]. El programacode2flow Parece ser un buen punto de partida para visualizar un código.

Sin embargo, aquí estoy interesado en la otra dirección. Una simple búsqueda reveló queDRAKON (ver tambiénhttps://en.wikipedia.org/wiki/DRAKON yhttp://drakon-editor.sourceforge.net/) podría estar haciendo exactamente lo que estoy preguntando. Desde esta perspectiva, la pregunta es, ¿cómo podría funcionar un programa de diagrama de flujo a código tan automático bajo el supuesto adicional de que no utiliza elgoto ¿declaración?