Entrada y salida únicas

Las regiones de entrada y salida únicas (SESE) son un concepto fundamental en la programación estructurada y el análisis del flujo de control . Una región SESE es una porción de un programa con un único punto de entrada y un único punto de salida, lo que permite el razonamiento modular, la verificación formal y la optimización del compilador. Si bien el término SESE se popularizó a finales de la década de 1980, las ideas subyacentes se remontan a los orígenes de la programación estructurada y al desarrollo de la teoría de grafos de flujo en la década de 1970.

En un grafo de flujo de control (CFG), una región SESE se define típicamente como un subgrafo con: ^{[ 1 ] [ 2 ]}

1. Un único enlace de entrada que domina todos los nodos de la región;
2. Un único borde de salida que postdomina todos los nodos de la región;
3. No hay otras aristas que entren o salgan del subgrafo.

Se dice que un nodo x domina a un nodo y en un grafo dirigido si cada camino desde el inicio hasta y incluye a x . Se dice que un nodo x postdomina a un nodo y si cada camino desde y hasta el final incluye a x .

• La primera condición garantiza que cada ruta desde el inicio del CFG hacia la región pase por el borde de entrada designado de la región.
• La segunda condición garantiza que cada ruta desde dentro de la región hasta el final del CFG pase por el borde de salida designado de la región.
• Las dos primeras condiciones son necesarias pero no suficientes para caracterizar las regiones SESE: la dominancia y la postdominancia por sí solas no prohíben que los bordes (incluidos los bordes invertidos) entren o salgan de la región sin pasar por la entrada o salida designada.
• La tercera condición garantiza la integridad de los límites: ninguna arista puede entrar en la región salvo por la arista de entrada designada, y ninguna arista puede salir de la región salvo por la arista de salida designada. Esto excluye las entradas laterales, las salidas laterales y las aristas posteriores que, de otro modo, cumplirían con los criterios de dominancia y postdominancia.

Esta definición permite identificar mecánicamente las regiones SESE y las hace aptas para el análisis estático.

Las raíces conceptuales de SESE se encuentran en la programación estructurada, desarrollada en la década de 1960 para abordar la complejidad causada por los saltos no restringidos ( goto ). En 1964, Böhm definió un lenguaje de programación primitivo — P′′ — que se basaba explícitamente en la propiedad SESE:

a) Solo es posible entrar en un ciclo desde su primera instrucción, ... b) Solo es posible salir de un ciclo desde su última instrucción.

Böhm y Jacopini (1966) demostraron que cualquier programa puede escribirse utilizando secuencia, selección e iteración . ^{[ 4 ]} Dijkstra (1968) argumentó que los programas deben tener una estructura de control clara para ser comprensibles y demostrablemente correctos. ^{[ 5 ]} Hoare (1969), al definir una lógica para la corrección de programas, asumió puntos de entrada y salida bien definidos. ^{[ 6 ]}

Todas las estructuras de control estructuradas introducidas en este período obedecen naturalmente a la disciplina de entrada única y salida única.

Los primeros trabajos sobre el análisis del flujo de control sentaron las bases para las representaciones de grafos de flujo utilizadas en las regiones SESE. El grafo de flujo de control (CFG) fue introducido por primera vez en el contexto de la optimización de compiladores por Frances E. Allen, quien formalizó los CFG como representaciones de bloques básicos y flujo de control, proporcionando una base para el análisis de dominancia y otras técnicas estructurales utilizadas en la identificación de SESE. ^{[ 7 ]}

Kosaraju utilizó estas representaciones CFG para dar a las regiones SESE su caracterización formal desde la teoría de grafos. ^{[ 8 ]} Definió regiones de entrada y salida únicas dentro de los grafos de flujo de control y mostró cómo los programas estructurados pueden descomponerse en regiones SESE jerárquicamente anidadas que corresponden a construcciones de control estándar como condicionales y bucles. Este trabajo demostró que la estructura SESE no es simplemente una guía estilística, sino una propiedad que permite la descomposición sistemática de programas y facilita el análisis y el razonamiento formal de los mismos.

A principios y mediados de la década de 1970, Aho , Hopcroft y Ullman (AHU) ampliaron estas ideas, desarrollando marcos formales para: ^{[ 9 ]}

• CFG
• Teoría del dominador
• Intervalos y regiones reducibles

Los intervalos definen regiones de entrada única dentro de un CFG. Si bien AHU no utilizó explícitamente el término SESE, su marco proporcionó la base matemática para identificar regiones con un comportamiento de entrada y salida disciplinado.

El término Entrada Única Salida Única (SESE, por sus siglas en inglés) fue explícitamente nombrado y popularizado por Ferrante, Ottenstein y Warren (1987). ^{[ 1 ]}

Sus contribuciones incluyen:

• Una definición precisa de SESE utilizando dominación y postdominación.
• Descomposición sistemática de programas en regiones SESE
• Uso de regiones SESE como base estructural para grafos de dependencia de programas (PDG).

Ferrante et al. atribuyeron explícitamente a AHU la teoría subyacente del diagrama de flujo.

Las regiones SESE son fundamentales para:

• Segmentación de programas
• Refactorización de código
• Optimización del compilador
• Análisis de paralelización y dependencia
• Verificación formal

Debido a que las regiones SESE aíslan el flujo de control, permiten que las transformaciones y el razonamiento se realicen localmente, preservando al mismo tiempo la corrección global.

• Gráfico de flujo de control
• Segmentación de programas
• Grafo de dependencia del programa
• Programación estructurada
• Teorema del programa estructurado