Las tablas de control son tablas que controlan el flujo de control o desempeñan un papel importante en el control del programa. No existen reglas rígidas sobre la estructura o el contenido de una tabla de control; su atributo calificador es su capacidad de dirigir el flujo de control de alguna manera a través de la "ejecución" por parte de un procesador o intérprete . El diseño de dichas tablas a veces se denomina diseño impulsado por tablas [1] [2] (aunque esto generalmente se refiere a generar código automáticamente a partir de tablas externas en lugar de tablas de tiempo de ejecución directas). En algunos casos, las tablas de control pueden ser implementaciones específicas de programación basada en autómatas basados en máquinas de estados finitos . Si hay varios niveles jerárquicos de tabla de control, pueden comportarse de manera equivalente a las máquinas de estados UML [3].
Las tablas de control suelen tener el equivalente de expresiones condicionales o referencias de funciones incorporadas, generalmente implícitas en su posición relativa en la columna de la lista de asociaciones . Las tablas de control reducen la necesidad de programar estructuras o declaraciones de programas similares una y otra vez. La naturaleza bidimensional de la mayoría de las tablas hace que sea más fácil verlas y actualizarlas que la naturaleza unidimensional del código del programa.
En algunos casos, se puede asignar a personas que no sean programadoras la tarea de mantener el contenido de las tablas de control. Por ejemplo, si una frase de búsqueda introducida por el usuario contiene una frase determinada, se puede asignar una URL (dirección web) en una tabla que controle a dónde se dirige al usuario que realiza la búsqueda. Si la frase contiene "falda", la tabla puede dirigir al usuario a "www.shopping.example/catalogs/faldas", que es la página del catálogo de productos de faldas. (La URL de ejemplo no funciona en la práctica). El personal de marketing puede gestionar una tabla de este tipo en lugar de los programadores.
Las tablas pueden tener múltiples dimensiones, longitudes fijas o variables y, por lo general, son portables entre plataformas informáticas , requiriendo solo un cambio en el intérprete, no en el algoritmo en sí, cuya lógica está esencialmente incorporada en la estructura y el contenido de la tabla. La estructura de la tabla puede ser similar a una matriz asociativa de mapas múltiples , donde un valor de datos (o una combinación de valores de datos) puede asignarse a una o más funciones que se realizarán.
En su implementación más simple, una tabla de control puede ser a veces una tabla unidimensional para traducir directamente un valor de datos sin procesar a un desplazamiento de subrutina correspondiente , índice o puntero utilizando el valor de datos sin procesar directamente como índice de la matriz o realizando alguna aritmética básica en los datos de antemano. Esto se puede lograr en tiempo constante (sin una búsqueda lineal o una búsqueda binaria utilizando una tabla de búsqueda típica en una matriz asociativa ). En la mayoría de las arquitecturas , esto se puede lograr en dos o tres instrucciones de máquina , sin comparaciones ni bucles. La técnica se conoce como " función hash trivial " o, cuando se usa específicamente para tablas de ramificación, " doble envío ". Para que esto sea factible, el rango de todos los valores posibles de los datos debe ser pequeño (por ejemplo, un valor de carácter ASCII o EBCDIC que tenga un rango hexadecimal de '00' a 'FF'. Si se garantiza que el rango real sea menor que esto, la matriz se puede truncar a menos de 256 bytes).
Tabla para traducir valores ASCII sin procesar (A, D, M, S) a un nuevo índice de subrutina (1, 4, 3, 2) en tiempo constante utilizando una matriz unidimensional
(los espacios en el rango se muestran como '..' para este ejemplo, lo que significa 'todos los valores hexadecimales hasta la siguiente fila'. Las primeras dos columnas no son parte de la matriz)
En la programación basada en autómatas y el procesamiento de transacciones pseudoconversacionales , si el número de estados de programa distintos es pequeño, se puede utilizar una variable de control de "secuencia densa" para dictar de manera eficiente todo el flujo del bucle principal del programa.
Un valor de datos sin procesar de dos bytes requeriría un tamaño de tabla mínimo de 65.536 bytes (para manejar todas las posibilidades de entrada), mientras que solo se permiten 256 valores de salida diferentes. Sin embargo, esta técnica de traducción directa proporciona una validación y conversión extremadamente rápidas a un puntero de subrutina (relativo) si la heurística , junto con suficiente memoria de acceso rápido, permite su uso.
Una tabla de ramificaciones es una "matriz" unidimensional de instrucciones de salto/ramificación de código de máquina contiguas para efectuar una ramificación multidireccional a una etiqueta de programa cuando se ramifica mediante una ramificación inmediatamente anterior e indexada. A veces, un compilador optimizador la genera para ejecutar una sentencia switch , siempre que el rango de entrada sea pequeño y denso, con pocos espacios vacíos (como el creado por el ejemplo de matriz anterior) [1].
Aunque son bastante compactas (en comparación con las Ifinstrucciones equivalentes múltiples), las instrucciones de bifurcación aún tienen cierta redundancia, ya que el código de operación de bifurcación y la máscara del código de condición se repiten junto con los desplazamientos de bifurcación. Se pueden construir tablas de control que contengan solo los desplazamientos de las etiquetas del programa para superar esta redundancia (al menos en lenguajes ensambladores) y, aun así, requerir solo una sobrecarga de tiempo de ejecución menor en comparación con una tabla de bifurcación convencional.
Más habitualmente, una tabla de control puede considerarse como una tabla de verdad o como una implementación ejecutable ("binaria") de una tabla de decisiones impresa (o un árbol de tablas de decisiones, en varios niveles). Contienen proposiciones (a menudo implícitas), junto con una o más "acciones" asociadas. Estas acciones suelen ser realizadas por subrutinas genéricas o personalizadas que son llamadas por un programa " intérprete ". El intérprete en este caso funciona efectivamente como una máquina virtual , que "ejecuta" las entradas de la tabla de control y, por lo tanto, proporciona un mayor nivel de abstracción que el código subyacente del intérprete.
Se puede construir una tabla de control de forma similar a una sentencia switch dependiente del lenguaje , pero con la posibilidad añadida de probar combinaciones de valores de entrada (utilizando condiciones AND / OR de estilo booleano ) y potencialmente invocar múltiples subrutinas (en lugar de un único conjunto de valores y etiquetas de programa 'de ramificación a'). (En cualquier caso, la construcción de la sentencia switch puede no estar disponible, o tener implementaciones confusamente diferentes en lenguajes de alto nivel ( HLL ). El concepto de tabla de control, en comparación, no tiene dependencias intrínsecas del lenguaje, pero podría, no obstante, implementarse de forma diferente según las características de definición de datos disponibles del lenguaje de programación elegido).
Una tabla de control esencialmente incorpora la " esencia " de un programa convencional, despojada de su sintaxis de lenguaje de programación y componentes dependientes de la plataforma (por ejemplo, IF/THEN DO.., FOR.., DO WHILE.., SWITCH, GOTO, CALL) y "condensada" a sus variables (por ejemplo, entrada1), valores (por ejemplo, "A", "S", "M" y "D"), e identidades de subrutinas (por ejemplo, "Add", "subtract,.." o #1, #2,..). La estructura de la tabla en sí misma típicamente implica las operaciones lógicas (predeterminadas) involucradas - tales como "probar la igualdad", realizar una subrutina y "próxima operación" o seguir la secuencia predeterminada (en lugar de que estas se indiquen explícitamente dentro de las declaraciones del programa - como se requiere en otros paradigmas de programación ).
Una tabla de control multidimensional normalmente contendrá, como mínimo, pares valor/acción y puede contener además operadores e información de tipo , como la ubicación, el tamaño y el formato de los datos de entrada o salida, si se requiere la conversión de datos (u otros matices de procesamiento en tiempo de ejecución ) antes o después del procesamiento (si no está ya implícita en la función misma). La tabla puede o no contener índices o punteros relativos o absolutos a primitivas genéricas o personalizadas o subrutinas que se ejecutarán en función de otros valores en la "fila".
La tabla ilustrada a continuación se aplica solo a 'input1' ya que no se especifica ninguna entrada específica en la tabla.
Condiciones y acciones implícitas en la estructura
(Esta combinación de valor y acción tiene similitudes con las construcciones de la programación basada en eventos , a saber, "detección de eventos" y "manejo de eventos", pero sin (necesariamente) la naturaleza asincrónica del evento en sí)
La variedad de valores que se pueden codificar dentro de una tabla de control depende en gran medida del lenguaje de programación utilizado. El lenguaje ensamblador proporciona el alcance más amplio para los tipos de datos , incluida (para las acciones), la opción de código de máquina ejecutable directamente . Normalmente, una tabla de control contendrá valores para cada posible clase coincidente de entrada junto con un puntero correspondiente a una subrutina de acción. Algunos lenguajes afirman que no admiten punteros (directamente), pero sin embargo pueden admitir un índice que se puede utilizar para representar un "número de subrutina relativo" para realizar una ejecución condicional, controlada por el valor en la entrada de la tabla (por ejemplo, para su uso en una declaración SWITCH optimizada , diseñada con cero espacios (es decir, una rama multidireccional )).
Los comentarios ubicados sobre cada columna (o incluso documentación textual incrustada) pueden hacer que una tabla de decisiones sea "legible para humanos" incluso después de "reducirla" (codificarla) a sus elementos esenciales (y que siga estando en línea con la especificación del programa original, especialmente si se crea una tabla de decisiones impresa, que enumera cada acción única, antes de que comience la codificación). Las entradas de la tabla también pueden contener opcionalmente contadores para recopilar estadísticas de tiempo de ejecución para la optimización "en vuelo" o posterior.
Las tablas de control pueden residir en un almacenamiento estático , en un almacenamiento auxiliar , como un archivo plano o en una base de datos , o pueden construirse de forma dinámica, total o parcialmente, en el momento de inicialización del programa a partir de parámetros (que pueden residir en una tabla). Para lograr una eficiencia óptima, la tabla debe residir en la memoria cuando el intérprete comience a utilizarla.
El intérprete puede escribirse en cualquier lenguaje de programación adecuado, incluido un lenguaje de alto nivel . Un intérprete genérico diseñado adecuadamente , junto con un conjunto bien elegido de subrutinas genéricas (capaces de procesar las primitivas más comunes ), requeriría codificación convencional adicional solo para nuevas subrutinas personalizadas (además de especificar la tabla de control en sí). El intérprete, opcionalmente, solo puede aplicarse a algunas secciones bien definidas de un programa de aplicación completo (como el bucle de control principal ) y no a otras secciones "menos condicionales" (como la inicialización del programa, la terminación, etc.).
El intérprete no necesita ser excesivamente complejo, ni ser producido por un programador con el conocimiento avanzado de un escritor de compiladores, y puede ser escrito como cualquier otro programa de aplicación, excepto que generalmente está diseñado con la eficiencia en mente. Su función principal es "ejecutar" las entradas de la tabla como un conjunto de "instrucciones". No es necesario que haya un requisito de análisis de las entradas de la tabla de control y, por lo tanto, estas deben diseñarse, en la medida de lo posible, para que estén "listas para la ejecución", requiriendo solo la "conexión" de variables de las columnas apropiadas al código genérico ya compilado del intérprete. Las instrucciones del programa son, en teoría, infinitamente extensibles y constituyen valores (posiblemente arbitrarios) dentro de la tabla que son significativos solo para el intérprete. El flujo de control del intérprete normalmente se realiza mediante el procesamiento secuencial de cada fila de la tabla, pero puede modificarse mediante acciones específicas en las entradas de la tabla.
Estos valores arbitrarios pueden diseñarse teniendo en cuenta la eficiencia , seleccionando valores que puedan usarse como índices directos a datos o punteros de función . Para plataformas o lenguajes específicos , pueden diseñarse específicamente para minimizar las longitudes de las rutas de instrucciones utilizando valores de tablas de ramificación o incluso, en algunos casos como en los compiladores JIT , pueden consistir en " fragmentos " de código de máquina directamente ejecutables (o punteros a ellos).
Las subrutinas pueden codificarse en el mismo lenguaje que el intérprete mismo o en cualquier otro lenguaje de programa compatible (siempre que existan mecanismos de enlace de 'llamada' entre lenguajes adecuados). La elección del lenguaje para el intérprete y/o las subrutinas dependerá normalmente de lo portable que deba ser entre varias plataformas . Puede haber varias versiones del intérprete para mejorar la portabilidad de una tabla de control. Un puntero de tabla de control subordinada puede sustituir opcionalmente a un puntero de subrutina en las columnas de 'acción' si el intérprete admite esta construcción, lo que representa una 'caída' condicional a un nivel lógico inferior, imitando una estructura de programa estructurada convencional .
A primera vista, el uso de tablas de control parecería añadir bastante a la sobrecarga de un programa , ya que requiere, como lo hace, un proceso de interpretación antes de que se ejecuten las sentencias del lenguaje de programación "nativo". Sin embargo, esto no siempre es así. Al separar (o "encapsular") la codificación ejecutable de la lógica, tal como se expresa en la tabla, se puede orientar más fácilmente para que realice su función de manera más eficiente. Esto se puede experimentar de manera más obvia en una aplicación de hoja de cálculo , donde el software de hoja de cálculo subyacente convierte de manera transparente "fórmulas" lógicas complejas de la manera más eficiente que puede, para mostrar sus resultados.
Los ejemplos que se muestran a continuación se han elegido en parte para ilustrar posibles mejoras de rendimiento que no solo pueden compensar significativamente el nivel adicional de abstracción, sino que también pueden mejorar lo que de otro modo podría haber sido un código menos eficiente, menos mantenible y más extenso. Aunque los ejemplos que se dan son para un lenguaje ensamblador de "bajo nivel" y para el lenguaje C , se puede ver, en ambos casos, que se requieren muy pocas líneas de código para implementar el enfoque de tabla de control y, sin embargo, se pueden lograr mejoras de rendimiento de tiempo constante muy significativas , reducir la codificación fuente repetitiva y ayudar a la claridad, en comparación con las construcciones de lenguaje de programación convencional verbosa . Véanse también las citas de Donald Knuth , sobre las tablas y la eficiencia de la ramificación multidireccional en este artículo.
Los siguientes ejemplos son arbitrarios (y se basan en una única entrada para simplificar), sin embargo, la intención es simplemente demostrar cómo se puede lograr un flujo de control mediante el uso de tablas en lugar de instrucciones de programa regulares. Debe quedar claro que esta técnica se puede extender fácilmente para manejar múltiples entradas, ya sea aumentando el número de columnas o utilizando múltiples entradas de tabla (con el operador y/o opcional). De manera similar, al usar tablas de control "vinculadas" (jerárquicas), se puede lograr una programación estructurada (opcionalmente, utilizando sangría para ayudar a resaltar las tablas de control subordinadas).
"CT1" es un ejemplo de una tabla de control que es una tabla de búsqueda simple . La primera columna representa el valor de entrada que se va a probar (mediante un 'IF input1 = x' implícito) y, si es VERDADERO, la segunda columna correspondiente (la 'acción') contiene una dirección de subrutina que se va a ejecutar mediante una llamada (o saltar a ella, similar a una instrucción SWITCH ). Es, en efecto, una bifurcación multidireccional con retorno (una forma de " despacho dinámico "). La última entrada es el caso predeterminado en el que no se encuentra ninguna coincidencia.
CT1
Para los lenguajes de programación que admiten punteros dentro de estructuras de datos junto con otros valores de datos, la tabla anterior (CT1) se puede utilizar para dirigir el flujo de control a subrutinas apropiadas según el valor coincidente de la tabla (sin una columna que indique lo contrario, se supone igualdad en este caso simple).
Ejemplo de lenguaje ensamblador para IBM/360 (rango de dirección máximo de 16 Mb) o Z/Architecture
No se ha hecho ningún intento de optimizar la búsqueda en la codificación para este primer ejemplo, y en su lugar se utiliza una técnica de búsqueda lineal simple , puramente para ilustrar el concepto y demostrar menos líneas de código fuente. Para manejar los 256 valores de entrada diferentes, se requerirían aproximadamente 265 líneas de código fuente (principalmente entradas de tabla de una sola línea), mientras que varias "comparaciones y ramificaciones" normalmente habrían requerido alrededor de 512 líneas de código fuente (el tamaño del binario también se reduce aproximadamente a la mitad, cada entrada de tabla requiere solo 4 bytes en lugar de aproximadamente 8 bytes para una serie de instrucciones de "comparación inmediata"/ramificación (para variables de entrada más grandes, el ahorro es aún mayor).
* ------------------ intérprete --------------------------------------------* LM R14,R0,=A(4,CT1,N) Establezca R14=4, R15--> tabla y R0 = número de entradas en la tabla (N) TRY CLC INPUT1,0(R15) ********* ¿Se encontró valor en la entrada de la tabla? SER ACCIÓN * bucle * SÍ, Cargar puntero de registro a subrutina desde la tabla AR R15,R14 * * NO, Señale la siguiente entrada en CT1 agregando R14 (=4) BCT R0, TRY ********* Regresa hasta agotar el conteo, luego pasa al siguiente paso . acción predeterminada... ninguno de los valores de la tabla coincide, haga otra cosa LA R15,4(R15) apunta a la entrada predeterminada (más allá del final de la tabla) ACCIÓN L R15,0(R15) lleva el puntero a R15, desde donde apunta R15 BALR R14,R15 Ejecutar la subrutina ("CALL" y regresar) B END va a terminar este programa * ------------------ tabla de control -----------------------------------------* * | esta columna de valores EBCDIC o ASCII permitidos se prueba '=' contra la variable 'input1' * | | esta columna es la dirección de 3 bytes de la subrutina apropiada * vv CT1 DC C'A',AL3(ADD) INICIO de la tabla de control (longitud de entrada de 4 bytes) DC C'S',AL3(RESTAR) DC C'M',AL3(MULTIPLICAR) DC C'D',AL3(DIVIDIR) N EQU (*-CT1)/4 número de entradas válidas en la tabla (longitud total / longitud de la entrada) DC C'?',AL3(DEFAULT) entrada predeterminada: se utiliza en el menú desplegable para capturar todos INPUT1 DS C La variable de entrada está en esta variable * ------------------ subrutinas ------------------------------------------* AGREGAR subrutina CSECT N.° 1 (se muestra aquí como CSECT separada, pero podría . alternativamente, puede ser código en línea) . instrucción(es) para agregar Retorno BR R14 Subrutina SUBTRACT CSECT #2 . instrucción(es) para restar Retorno BR R14 . etc..Mejorar el rendimiento del intérprete en el ejemplo anterior
Intérprete mejorado (hasta 26 veces menos instrucciones ejecutadas en promedio que el ejemplo anterior, donde n = 1 a 64 y hasta 13 veces menos de lo que se necesitaría utilizando comparaciones múltiples).
Para manejar 64 valores de entrada diferentes, se requieren aproximadamente 85 líneas de código fuente (o menos) (principalmente entradas de tabla de una sola línea), mientras que varias 'comparaciones y bifurcaciones' requerirían alrededor de 128 líneas (el tamaño del binario también se reduce casi a la mitad, a pesar de la tabla adicional de 256 bytes requerida para extraer el segundo índice).
* ------------------ intérprete --------------------------------------------* SR R14,R14 ********* Establecer R14=0 CALC IC R14,INPUT1 * calc * coloca el byte EBCDIC en los bits de orden bajo (24–31) de R14 IC R14,CT1X(R14) * * use el valor EBCDIC como índice en la tabla 'CT1X' para obtener el nuevo índice ENCONTRADO L R15,CT1(R14) ********* obtener puntero a subrutina usando índice (0,4, 8 etc.) BALR R14,R15 Ejecutar la subrutina ("CALL" y regresar o Default) B END va a terminar este programa * --------------- tabla de traducción adicional (EBCDIC --> tabla de puntero ÍNDICE) 256 bytes----* CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 conjuntos idénticos de 16 bytes de x'00 * representando X'00 – x'BF' DC AL1(00, 04 ,00,00, 16 ,00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF' DC AL1(00,00,00,00, 12 ,00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF' DC AL1(00,00, 08 ,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF' DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF' * El ensamblador se puede utilizar para calcular automáticamente los valores del índice y hacer que los valores sean más fáciles de usar. * (por ejemplo, '04' podría reemplazarse con la expresión simbólica 'PADD-CT1' en la tabla CT1X anterior) * CT1 modificado (se agregó una acción predeterminada cuando el índice = 00, dimensión única, dirección completa de 31 bits) CT1 DC A(PREDETERMINADO) índice = 00 INICIO de la tabla de control (constantes de dirección de 4 bytes) PADD DC A(AGREGAR) = 04 PSUB DC A(RESTAR) = 08 PMUL DC A(MULTIPLICAR) = 12 PDIV DC A(DIVIDIR) = 16 * el resto del código sigue siendo el mismo que el primer ejemploIntérprete aún más mejorado (hasta 21 veces menos instrucciones ejecutadas (donde n>=64) que el primer ejemplo en promedio y hasta 42 veces menos de lo que se necesitaría utilizando comparaciones múltiples).
Para manejar 256 valores de entrada diferentes, se requerirían aproximadamente 280 líneas de código fuente o menos (principalmente entradas de tabla de una sola línea), mientras que varias 'comparaciones y bifurcaciones' requerirían alrededor de 512 líneas (el tamaño del binario también se reduce casi a la mitad una vez más).
* ------------------ intérprete --------------------------------------------* SR R14,R14 ********* Establecer R14=0 CALC IC R14,INPUT1 * calc * coloca el byte EBCDIC en los bits de orden bajo (24–31) de R14 IC R14,CT1X(R14) * * use el valor EBCDIC como índice en la tabla 'CT1X' para obtener el nuevo índice SLL R14,2 * * multiplicar el índice por 4 (instrucción adicional) ENCONTRADO L R15,CT1(R14) ********* obtener puntero a subrutina usando índice (0,4, 8 etc.) BALR R14,R15 Ejecutar la subrutina ("CALL" y regresar o Default) B END va a terminar este programa * --------------- tabla de traducción adicional (EBCDIC --> tabla de puntero ÍNDICE) 256 bytes----* CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 conjuntos idénticos de 16 bytes de x'00' * representando X'00 – x'BF' DC AL1(00, 01 ,00,00, 04 ,00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF' DC AL1(00,00,00,00, 03 ,00,00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF' DC AL1(00,00, 02 ,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF' DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF' * El ensamblador se puede utilizar para calcular automáticamente los valores del índice y hacer que los valores sean más fáciles de usar. * (por ejemplo, '01' podría reemplazarse con la expresión simbólica 'PADD-CT1/4' en la tabla CT1X anterior) * CT1 modificado (el índice ahora se basa en 0,1,2,3,4 y no en 0,4,8,12,16 para permitir las 256 variaciones) CT1 DC A(PREDETERMINADO) índice = 00 INICIO de la tabla de control (constantes de dirección de 4 bytes) PADD DC A(ADD) = 01 PSUB DC A(RESTAR) = 02 PMUL DC A(MULTIPLICAR) = 03 PDIV DC A(DIVIDIR) = 04 * el resto del código sigue siendo el mismo que el segundo ejemploEjemplo en lenguaje C Este ejemplo en C utiliza dos tablas, la primera (CT1) es una tabla de búsqueda lineal unidimensional simple – para obtener un índice haciendo coincidir la entrada (x), y la segunda, tabla asociada (CT1p), es una tabla de direcciones de etiquetas a las que saltar.
static const char CT1 [] = { "A" , "S" , "M" , "D" }; /* valores de entrada permitidos */ static const void * CT1p [] = { && Sumar , && Restar , && Multiplicar , && Dividir , && Predeterminado }; /* etiquetas a las que ir a & predeterminado*/ for ( int i = 0 ; i < sizeof ( CT1 ); i ++ ) /* recorrer valores ASCII */ { if ( x == CT1 [ i ]) goto * CT1p [ i ]; } /* encontrado --> etiqueta apropiada */ goto * CT1p [ i + 1 ]; /* no encontrado --> etiqueta predeterminada */ Esto se puede hacer más eficiente si se utiliza una tabla de 256 bytes para traducir el valor ASCII sin procesar (x) directamente a un valor de índice secuencial denso para su uso en la localización directa de la dirección de la rama desde CT1p (es decir, " mapeo de índice " con una matriz de ancho de byte). Luego se ejecutará en tiempo constante para todos los valores posibles de x (si CT1p contuviera los nombres de funciones en lugar de etiquetas, el salto podría reemplazarse con una llamada de función dinámica, eliminando el goto tipo switch, pero disminuyendo el rendimiento por el costo adicional de mantenimiento de funciones ).
static const void * CT1p [] = { && Predeterminado , && Sumar , && Restar , && Multiplicar , && Dividir }; /* la tabla de 256 bytes, a continuación, contiene los valores (1, 2, 3, 4), en las posiciones ASCII correspondientes (A, S, M, D), todos los demás se establecen en 0x00 */ static const char CT1x [ ] = { '\x00' , ' \x00' , ' \x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', ' \ x00 ' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , ' \x00', ' \x00' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' ,'\x00' , '\x00' , '\ x00 ' , '\x00' , '\x00' , '\x00' , '\x01' , '\x00' , ' \x00' , ' \ x04' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , '\x00' , '\x03' , '\x00' , '\x00' , '\ x00 ' , '\x00' , ' \x00' , '\x02' , '\x00 ' , ' \x00' , ' \ x00' , '\x00' , '\x00 ' , '\x00' , ' \ x00 ' , '\ x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , '\x00' , '\ x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , ' \x00' , '\x00' , '\ x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\ x00', '\x00' , ' \x00 ' , '\x00', '\x00' , ' \ x00' , ' \x00' , '\x00' , '\x00', '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' ,'\x00' , '\x00' , '\ x00 ' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00 ' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', ' \ x00 ' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , ' \x00', ' \x00' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\ x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , ' \x00' , '\x00' , '\ x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' , ' \x03' , '\x00' , '\x00 ' , '\x00', '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' ,'\x00' , '\x00' , '\ x00 ' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00 ' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' }; /* el siguiente código se ejecutará en tiempo constante, independientemente del valor del carácter de entrada (x) */ i = CT1x ( x ); /* extraer el índice de subrutina correcto de la tabla CT1x utilizando su valor ASCII como índice inicialmente */ goto * CT1p [ i ]; /* goto (cambiar a) la etiqueta correspondiente al índice (0=predeterminado, 1=sumar, 2=restar,.) - ver CT1p */ El siguiente ejemplo ilustra cómo se puede lograr un efecto similar en lenguajes que no admiten definiciones de punteros en estructuras de datos pero sí admiten ramificaciones indexadas a una subrutina, contenida dentro de una matriz ( basada en 0 ) de punteros de subrutina. La tabla (CT2) se utiliza para extraer el índice (de la segunda columna) a la matriz de punteros (CT2P). Si no se admiten matrices de punteros, se puede utilizar una instrucción SWITCH o equivalente para alterar el flujo de control a una de una secuencia de etiquetas de programa (por ejemplo: case0, case1, case2, case3, case4) que luego procesan la entrada directamente o realizan una llamada (con retorno) a la subrutina adecuada (predeterminada, Agregar, Restar, Multiplicar o Dividir,..) para tratarla.
CT2
Como en los ejemplos anteriores, es posible traducir de manera muy eficiente los posibles valores de entrada ASCII (A, S, M, D o desconocidos) en un índice de matriz de puntero sin utilizar realmente una búsqueda en la tabla, pero se muestra aquí como una tabla para mantener la coherencia con el primer ejemplo.
Se pueden construir tablas de control multidimensionales (es decir, personalizarlas) que pueden ser "más complejas" que los ejemplos anteriores, que pueden probar múltiples condiciones en múltiples entradas o realizar más de una "acción", en función de algunos criterios coincidentes. Una "acción" puede incluir un puntero a otra tabla de control subordinada. El ejemplo simple a continuación tiene una condición "OR" implícita incorporada como una columna adicional (para manejar la entrada en minúsculas, sin embargo, en este caso, esto podría haberse manejado igualmente simplemente con una entrada adicional para cada uno de los caracteres en minúscula que especifique el mismo identificador de subrutina que los caracteres en mayúsculas). También se incluye una columna adicional para contar los eventos de tiempo de ejecución reales para cada entrada a medida que ocurren.
CT3
Las entradas de la tabla de control son entonces mucho más similares a las declaraciones condicionales en lenguajes procedimentales pero, fundamentalmente, sin que estén presentes las declaraciones condicionales reales (es decir, las instrucciones) que dependen del lenguaje (el código genérico está físicamente en el intérprete que procesa las entradas de la tabla, no en la tabla misma, que simplemente incorpora la lógica del programa a través de su estructura y valores).
En tablas como estas, donde una serie de entradas de tabla similares define toda la lógica, un número de entrada de tabla o un puntero pueden reemplazar efectivamente a un contador de programa en programas más convencionales y pueden restablecerse en una "acción", también especificada en la entrada de tabla. El ejemplo siguiente (CT4) muestra cómo la extensión de la tabla anterior, para incluir una entrada "siguiente" (y/o incluir una subrutina de "alteración de flujo" ( salto )) puede crear un bucle (este ejemplo en realidad no es la forma más eficiente de construir una tabla de control de este tipo pero, al demostrar una "evolución" gradual a partir de los primeros ejemplos anteriores, muestra cómo se pueden usar columnas adicionales para modificar el comportamiento). La quinta columna demuestra que se puede iniciar más de una acción con una sola entrada de tabla; en este caso, una acción que se realizará después del procesamiento normal de cada entrada (los valores "-" significan "sin condiciones" o "sin acción").
La programación estructurada o el código "sin Goto" (que incorpora el equivalente de construcciones " DO WHILE " o " for loop ") también se pueden adaptar con estructuras de tabla de control adecuadamente diseñadas y "sangradas".
CT4 (un 'programa' completo para leer la entrada 1 y procesarla, repitiendo hasta que se encuentre 'E')
En el campo especializado de la tarificación de las telecomunicaciones (que se ocupa de determinar el coste de una llamada en particular), las técnicas de tarificación basadas en tablas ilustran el uso de tablas de control en aplicaciones en las que las reglas pueden cambiar con frecuencia debido a las fuerzas del mercado. En muchos casos, las tablas que determinan los cargos pueden ser modificadas con poca antelación por personas que no sean programadores. [4] [5]
Si los algoritmos no están incorporados previamente en el intérprete (y, por lo tanto, requieren una interpretación en tiempo de ejecución adicional de una expresión contenida en la tabla), se conoce como "calificación basada en reglas" en lugar de calificación basada en tablas (y, en consecuencia, consume significativamente más sobrecarga).
Una hoja de cálculo puede considerarse como una tabla de control bidimensional, en la que las celdas que no están vacías representan datos para el programa de hoja de cálculo subyacente (el intérprete). Las celdas que contienen fórmulas suelen tener como prefijo un signo igual y simplemente designan un tipo especial de entrada de datos que dicta el procesamiento de otras celdas a las que se hace referencia, alterando el flujo de control dentro del intérprete. Es la externalización de fórmulas desde el intérprete subyacente lo que identifica claramente tanto las hojas de cálculo como el ejemplo de "clasificación basada en reglas" citado anteriormente como casos fácilmente identificables del uso de tablas de control por parte de personas que no son programadoras.
Si se pudiera decir que la técnica de las tablas de control pertenece a algún paradigma de programación en particular , la analogía más cercana podría ser la programación basada en autómatas o "reflexiva" (una forma de metaprogramación , ya que se podría decir que las entradas de la tabla "modifican" el comportamiento del intérprete). Sin embargo, el intérprete en sí mismo y las subrutinas se pueden programar utilizando cualquiera de los paradigmas disponibles o incluso una combinación de ellos. La tabla en sí puede ser esencialmente una colección de valores de " datos sin procesar " que ni siquiera necesitan compilarse y podrían leerse desde una fuente externa (excepto en implementaciones específicas, dependientes de la plataforma, que utilizan punteros de memoria directamente para una mayor eficiencia).
Una tabla de control multidimensional tiene algunas similitudes conceptuales con el código de bytes que opera en una máquina virtual , en el sentido de que generalmente se requiere un programa "intérprete" dependiente de la plataforma para realizar la ejecución real (que está determinada en gran medida de manera condicional por el contenido de las tablas). También existen algunas similitudes conceptuales con el reciente lenguaje intermedio común (CIL) en el objetivo de crear un "conjunto de instrucciones" intermedio común que sea independiente de la plataforma (pero a diferencia de CIL, sin pretensiones de ser utilizado como un recurso común para otros lenguajes). El código P también puede considerarse una implementación similar pero anterior con orígenes que se remontan a 1966.
Cuando se utiliza una tabla de control multidimensional para determinar el flujo del programa, la función de contador de programa "de hardware" normal se simula de manera efectiva con un puntero a la primera (o siguiente) entrada de la tabla o un índice a la misma. "Obtener" la instrucción implica decodificar los datos en esa entrada de la tabla, sin copiar necesariamente todos o algunos de los datos dentro de la entrada primero. Los lenguajes de programación que pueden usar punteros tienen la doble ventaja de que se involucra menos sobrecarga , tanto en el acceso al contenido como en el avance del contador para que apunte a la siguiente entrada de la tabla después de la ejecución. El cálculo de la siguiente dirección de "instrucción" (es decir, entrada de la tabla) incluso se puede realizar como una acción adicional opcional de cada entrada de la tabla individual, lo que permite bucles o instrucciones de salto en cualquier etapa.
El programa intérprete puede guardar opcionalmente el contador del programa (y otros detalles relevantes dependiendo del tipo de instrucción) en cada etapa para registrar un seguimiento completo o parcial del flujo real del programa con fines de depuración , detección de puntos críticos , análisis de cobertura de código y análisis de rendimiento (ver los ejemplos CT3 y CT4 anteriores).
Opcionalmente:-
Lo siguiente se aplica principalmente a su uso en tablas multidimensionales, no a las tablas unidimensionales analizadas anteriormente.
La ramificación multidireccional es una técnica de programación importante que, con demasiada frecuencia, se sustituye por una secuencia ineficiente de pruebas if. Peter Naur me escribió recientemente que considera el uso de tablas para controlar el flujo del programa como una idea básica de la informática que casi se ha olvidado, pero que espera que esté lista para ser redescubierta en cualquier momento. Es la clave de la eficiencia en todos los mejores compiladores que he estudiado.
— Donald Knuth , Programación estructurada con instrucciones go to
Existe otra forma de considerar un programa escrito en lenguaje interpretativo. Puede considerarse como una serie de llamadas a subrutinas, una tras otra. De hecho, un programa de este tipo puede ampliarse hasta convertirse en una larga secuencia de llamadas a subrutinas y, a la inversa, dicha secuencia puede empaquetarse normalmente en una forma codificada que se interprete fácilmente. Las ventajas de las técnicas interpretativas son la compacidad de la representación, la independencia de la máquina y la mayor capacidad de diagnóstico. A menudo, un intérprete puede escribirse de modo que la cantidad de tiempo empleado en la interpretación del código en sí y en la derivación a la rutina adecuada sea insignificante.
— Donald Knuth , El arte de la programación informática, volumen 1, 1997, página 202
El espacio necesario para representar un programa se puede reducir con frecuencia mediante el uso de intérpretes en los que se representan secuencias comunes de operaciones de forma compacta. Un ejemplo típico es el uso de una máquina de estados finitos para codificar un protocolo complejo o un formato léxico en una tabla pequeña.
— Jon Bentley , Cómo escribir programas eficientes
Las tablas de salto pueden ser especialmente eficientes si se pueden omitir las pruebas de rango. Por ejemplo, si el valor de control es un tipo enumerado (o un carácter), entonces solo puede contener un pequeño rango fijo de valores y una prueba de rango es redundante siempre que la tabla de salto sea lo suficientemente grande para manejar todos los valores posibles.
— David.A. SPULER, Generación de código de compilador para sentencias de ramificación de múltiples vías como un problema de búsqueda estática
Los programas deben escribirse para que la gente los lea y sólo incidentalmente para que las máquinas los ejecuten.
— "Estructura e interpretación de programas informáticos", prefacio a la primera edición, Abelson & Sussman
Muéstrame tu diagrama de flujo y oculta tus tablas, y seguiré desconcertado. Muéstrame tus tablas y, por lo general, no necesitaré tu diagrama de flujo; será obvio.
— "El mítico mes del hombre: ensayos sobre ingeniería de software", Fred Brooks
{{cite web}}: CS1 maint: copia archivada como título ( enlace )