Mesa de control - Control table

Esta sencilla tabla de control dirige el flujo del programa de acuerdo con el valor de la variable de entrada única. Cada entrada de la tabla contiene un posible valor de entrada para comprobar la igualdad (implícito) y una subrutina relevante para realizar en la columna de acción. El nombre de la subrutina podría reemplazarse por un número de subrutina relativo si no se admiten punteros

Las tablas de control son tablas que controlan el flujo de control o juegan 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 de calificación es su capacidad para 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 tales tablas a veces se denomina diseño basado en tablas (aunque normalmente se refiere a generar código automáticamente a partir de tablas externas en lugar de tablas de tiempo de ejecución directo). 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 la tabla de control, pueden comportarse de manera equivalente a las máquinas de estado UML.

Las tablas de control a menudo tienen el equivalente de expresiones condicionales o referencias de funciones incrustadas en ellas, generalmente implícitas por su posición de columna relativa en la lista de asociación . Las tablas de control reducen la necesidad de programar estructuras o sentencias de programa similares una y otra vez. La naturaleza bidimensional de la mayoría de las tablas hace que sean más fáciles de ver y actualizar que la naturaleza unidimensional del código del programa. En algunos casos, se pueden asignar no programadores para mantener las tablas de control.

Uso típico

• Transformación de valores de entrada a:
  • un índice , para bifurcación posterior o búsqueda de puntero
  • un nombre de programa, número de subrutina relativo , etiqueta de programa o compensación de programa , para alterar el flujo de control
• Controlar un bucle principal en la programación impulsada por eventos mediante una variable de control para las transiciones de estado
• Control del ciclo del programa para aplicaciones de procesamiento de transacciones en línea

Uso más avanzado

• Actuar como instrucciones virtuales para una máquina virtual procesada por un intérprete

similar al código de bytes , pero generalmente con operaciones implícitas en la estructura de la tabla

Estructura de la mesa

Las tablas pueden tener múltiples dimensiones, de longitud fija o variable y, por lo general, son portátiles entre plataformas informáticas , lo que requiere solo un cambio en el intérprete, no en el algoritmo en sí, cuya lógica está esencialmente incorporada dentro de la estructura y el contenido de la tabla. La estructura de la tabla puede ser similar a una matriz asociativa de múltiples mapas, donde un valor de datos (o una combinación de valores de datos) se puede asignar a una o más funciones a realizar.

Tablas unidimensionales

Quizás en su implementación más simple, una tabla de control a veces puede ser una tabla unidimensional para traducir directamente un valor de datos sin procesar a un desplazamiento de subrutina correspondiente , índice o puntero usando el valor de datos sin procesar, ya sea directamente como el índice de la matriz, o realizando algo de aritmética básica sobre los datos de antemano. Esto se puede lograr en tiempo constante (sin una búsqueda lineal o binaria usando 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 ciclos. La técnica se conoce como una " función hash trivial " o, cuando se usa específicamente para tablas de sucursales, " 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 '00' - 'FF'. Si se garantiza que el rango real es 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 usando 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 dos primeras columnas no forman parte de la matriz)

En la programación basada en autómatas y el procesamiento de transacciones pseudoconversacionales , si el número de estados distintos del programa es pequeño, se puede usar 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, al tiempo que permite solo 256 valores de salida diferentes. Sin embargo, esta técnica de traducción directa proporciona una validación y conversión extremadamente rápida a un puntero de subrutina (relativo) si la heurística , junto con suficiente memoria de acceso rápido, permite su uso.

Tablas de sucursales

Una tabla de bifurcaciones es una 'matriz' unidimensional de instrucciones de bifurcación / salto de código de máquina contiguas para efectuar una bifurcación de múltiples vías a una etiqueta de programa cuando se bifurca en una bifurcación indexada e inmediatamente anterior. A veces es generado por un compilador de optimización para ejecutar una instrucción de cambio , siempre que el rango de entrada sea pequeño y denso, con pocos espacios (como se creó en el ejemplo de matriz anterior) [2] .

Aunque son bastante compactas, en comparación con las múltiples Ifdeclaraciones equivalentes , las instrucciones de la rama todavía tienen algo de redundancia, ya que el código de operación de la rama y la máscara del código de condición se repiten junto con las compensaciones de la rama. Se pueden construir tablas de control que contengan solo las compensaciones de las etiquetas del programa para superar esta redundancia (al menos en lenguajes ensambladores) y, sin embargo, solo requieren una sobrecarga de tiempo de ejecución menor en comparación con una tabla de rama convencional.

Mesas multidimensionales

Más habitualmente, una tabla de control se puede considerar 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 generalmente se realizan mediante 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 a lo largo de líneas similares a una declaración de cambio dependiente del idioma , pero con la posibilidad adicional de probar combinaciones de valores de entrada (usando condiciones Y / O de estilo booleano ) y potencialmente llamar a múltiples subrutinas (en lugar de un solo conjunto de valores y etiquetas de programa 'ramificar a'). (En cualquier caso, la construcción de la declaración de cambio puede no estar disponible, o tiene 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 manera diferente según la disponibilidad características de definición de datos del lenguaje de programación elegido.)

Contenido de la tabla

Una tabla de control encarna esencialmente la ' esencia ' de un programa convencional, despojado 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 ' condensado 'a sus variables (por ejemplo, entrada1), valores (por ejemplo,' A ',' S ',' M 'y' D ') e identidades de subrutina (por ejemplo,' Sumar ',' restar, .. 'o # 1, # 2, ..). La estructura de la tabla en sí misma generalmente implica las operaciones lógicas (predeterminadas) involucradas, como 'probar la igualdad', realizar una subrutina y la 'siguiente operación' o seguir la secuencia predeterminada (en lugar de que se indiquen explícitamente en las declaraciones del programa, según sea necesario) en otros paradigmas de programación ).

Una tabla de control multidimensional normalmente contendrá, como mínimo, pares de valor / acción y, además, puede contener operadores e información de tipo , como la ubicación, el tamaño y el formato de los datos de entrada o salida, ya sea conversión de datos (u otro tiempo de ejecución matices de procesamiento) es necesario antes o después del procesamiento (si no está implícito en la función en sí). La tabla puede contener o no índices o punteros relativos o absolutos a primitivas o subrutinas genéricas o personalizadas que se ejecutarán dependiendo 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

(implícito) SI =	(implícito) realizar
valor	acción
valor	acción

(Este emparejamiento lado a lado de valor y acción tiene similitudes con las construcciones en la programación impulsada por 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 informático 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 directamente ejecutable . Normalmente, una tabla de control contendrá valores para cada posible clase de entrada coincidente junto con un puntero correspondiente a una subrutina de acción. Algunos lenguajes afirman no admitir punteros (directamente) pero, sin embargo, pueden admitir un índice que se puede usar 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 usar en un SWITCH optimizado declaración: diseñada con cero espacios (es decir, una rama de múltiples vías )).

Los comentarios colocados encima de cada columna (o incluso la documentación textual incrustada) pueden hacer que una tabla de decisiones sea 'legible por humanos' incluso después de 'condensar' (codificar) a sus elementos esenciales (y aún ampliamente en línea con la especificación del programa original, especialmente si se imprime La tabla de decisiones, que enumera cada acción única, se crea 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

Ubicación de la mesa

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, alternativamente, pueden construirse parcial o totalmente de forma dinámica en el momento de la inicialización del programa a partir de parámetros (que a su vez pueden residir en una tabla). Para una eficiencia óptima, la mesa debe estar residente en la memoria cuando el intérprete comience a usarla.

El intérprete y las subrutinas

El intérprete puede estar escrito en cualquier lenguaje de programación adecuado, incluido un lenguaje de alto nivel . Un intérprete genérico adecuadamente diseñado , 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.).

No es necesario que el intérprete sea excesivamente complejo, o que lo haya producido un programador con el conocimiento avanzado de un escritor de compiladores, y puede escribirse como cualquier otro programa de aplicación, excepto que generalmente está diseñado pensando en la eficiencia. Su función principal es "ejecutar" las entradas de la tabla como un conjunto de "instrucciones". No es necesario que exista un requisito para el 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 "conectar" las variables de las columnas apropiadas al código genérico ya compilado de el interprete. Las instrucciones del programa son, en teoría, infinitamente extensibles y constituyen valores (posiblemente arbitrarios) dentro de la tabla que solo son significativos 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.

Por lo tanto, estos valores arbitrarios pueden diseñarse teniendo en cuenta la eficiencia , mediante la selección de valores que se pueden usar como índices directos de datos o punteros de función . Para plataformas / lenguajes particulares , pueden diseñarse específicamente para minimizar las longitudes de ruta de instrucción utilizando valores de tabla de rama o incluso, en algunos casos como en compiladores JIT , constar de " fragmentos " de código de máquina directamente ejecutables (o punteros a ellos).

Las subrutinas pueden codificarse en el mismo idioma que el propio intérprete o en cualquier otro lenguaje de programa soportado (siempre que existan mecanismos de enlace de 'llamada' entre idiomas adecuados). La elección del idioma para el intérprete y / o las subrutinas generalmente dependerá de cuán portátil debe ser en varias plataformas . Puede haber varias versiones del intérprete para mejorar la portabilidad de una mesa de control. Un puntero de tabla de control subordinado puede sustituir opcionalmente a un puntero de subrutina en las columnas de "acción" si el intérprete admite esta construcción, que representa una "caída" condicional a un nivel lógico inferior, imitando una estructura de programa estructurado convencional .

Consideraciones de rendimiento

A primera vista, el uso de tablas de control parecería agregar mucho a la sobrecarga de un programa , requiriendo, como lo hace, un proceso de interpretación antes de que se ejecuten las declaraciones del lenguaje de programación 'nativo'. Esto, sin embargo, no siempre es el caso. Al separar (o "encapsular") la codificación ejecutable de la lógica, como se expresa en la tabla, se puede apuntar más fácilmente para realizar su función de la 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 posible, para mostrar sus resultados.

Los ejemplos a continuación se han elegido en parte para ilustrar las posibles ganancias de rendimiento que pueden no solo compensar significativamente el nivel adicional de abstracción, sino también mejorar , lo que de otro modo podría haber sido, un código menos eficiente, menos mantenible y más extenso. Aunque los ejemplos dados 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 la tabla de control y, sin embargo, se puede lograr un tiempo constante muy significativo. mejoras en el rendimiento, reducen la codificación de fuentes repetitivas y ayudan a la claridad, en comparación con construcciones de lenguaje de programa convencionales prolijas . Véanse también las citas de Donald Knuth sobre tablas y la eficiencia de la ramificación de múltiples vías en este artículo.

Ejemplos de tablas de control

Los siguientes ejemplos son arbitrarios (y se basan en una sola entrada para simplificar), sin embargo, la intención es simplemente demostrar cómo el flujo de control se puede realizar mediante el uso de tablas en lugar de declaraciones de programa normales. Debe quedar claro que esta técnica puede extenderse fácilmente para tratar con múltiples entradas, ya sea aumentando el número de columnas o utilizando múltiples entradas de tabla (con opcional y / o operador). De manera similar, mediante el uso de tablas de control 'vinculadas' (jerárquicas), se puede realizar 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 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 para realizar mediante una llamada (o saltar a - similar a una instrucción SWITCH ). Es, en efecto, una rama de múltiples vías con retorno (una forma de " envío dinámico "). La última entrada es el caso predeterminado donde no se encuentra ninguna coincidencia.

CT1

entrada 1	puntero
A	-> Agregar
S	-> Restar
METRO	-> Multiplicar
D	-> Dividir
?	-> Predeterminado

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 una subrutina adecuada de acuerdo con el valor coincidente de la tabla (sin una columna que indique lo contrario, se asume la igualdad en este simple caso).

Ejemplo de lenguaje ensamblador para IBM / 360 (rango de direcciones máximo de 16Mb) o Z / Architecture

No se intenta optimizar la búsqueda en la codificación de este primer ejemplo y, en cambio, utiliza una técnica de búsqueda lineal simple, simplemente para ilustrar el concepto y demostrar menos líneas de origen. 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 múltiples 'comparar y bifurcar' normalmente habrían requerido alrededor de 512 líneas fuente (el tamaño del binario también se reduce aproximadamente a la mitad, cada entrada de la tabla requiere solo 4 bytes en lugar de aproximadamente 8 bytes para una serie de instrucciones de 'comparar inmediata' / bifurcación (para variables de entrada más grandes, el ahorro es aún mayor).

  * ------------------ interpreter --------------------------------------------*
           LM     R14,R0,=A(4,CT1,N)               Set R14=4, R15 --> table, and R0 =no. of entries in table (N)
  TRY      CLC    INPUT1,0(R15)         *********  Found value in table entry ?
           BE     ACTION                * loop  *  YES, Load register pointer to sub-routine from table
           AR     R15,R14               *       *  NO, Point to next entry in CT1 by adding R14 (=4)
           BCT    R0,TRY                *********  Back until count exhausted, then drop through
  .             default action                          ... none of the values in table match, do something else
           LA     R15,4(R15)                       point to default entry (beyond table end)
  ACTION   L      R15,0(R15)                       get pointer into R15,from where R15 points
           BALR   R14,R15                          Perform the sub-routine ("CALL" and return)
           B      END                              go terminate this program
  * ------------------ control table -----------------------------------------*
  *                 | this column of allowable EBCDIC or ASCII values is tested '=' against variable 'input1'
  *                 |      | this column is the 3-byte address of the appropriate subroutine
  *                 v      v
  CT1      DC     C'A',AL3(ADD)                    START of Control Table (4 byte entry length)
           DC     C'S',AL3(SUBTRACT)
           DC     C'M',AL3(MULTIPLY)
           DC     C'D',AL3(DIVIDE)
  N        EQU    (*-CT1)/4                        number of valid entries in table (total length / entry length)
           DC     C'?',AL3(DEFAULT)                default entry – used on drop through to catch all
  INPUT1   DS     C                                input variable is in this variable
  * ------------------ sub-routines ------------------------------------------*
  ADD      CSECT                                   sub-routine #1 (shown as separate CSECT here but might
  .                                                                alternatively be in-line code)
  .            instruction(s) to add
           BR     R14                              return
  SUBTRACT CSECT                                   sub-routine #2
  .            instruction(s) to subtract
           BR     R14                              return
  . etc..

mejorar el rendimiento del intérprete en el ejemplo anterior

Para hacer una selección en el ejemplo anterior, la longitud de ruta de instrucción promedio (excluyendo el código de subrutina) es '4n / 2 +3', pero se puede reducir fácilmente, donde n = 1 a 64, a un tiempo constante con una longitud de ruta de '5' con comparaciones de cero , si primero se utiliza una tabla de traducción de 256 bytes para crear un índice directo a CT1 a partir de los datos EBCDIC sin procesar. Donde n = 6, esto sería equivalente a solo 3 instrucciones secuenciales de comparación y bifurcación. Sin embargo, donde n <= 64, en promedio se necesitarían aproximadamente 13 veces menos instrucciones que el uso de comparaciones múltiples. Donde n = 1 a 256, en promedio usaría aproximadamente 42 veces menos instrucciones, ya que, en este caso, se requeriría una instrucción adicional (para multiplicar el índice por 4).${\ Displaystyle O (1) \,}$

Intérprete mejorado (hasta 26 veces menos instrucciones ejecutadas que el ejemplo anterior en promedio, donde n = 1 a 64 y hasta 13 veces menos de lo que se necesitaría usando 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 múltiples 'comparar y bifurcar' 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 necesaria para extraer el segundo índice).

  * ------------------ interpreter --------------------------------------------*
           SR     R14,R14               *********  Set R14=0
  CALC     IC     R14,INPUT1            * calc  *  put EBCDIC byte into lo order bits (24–31) of R14
           IC     R14,CT1X(R14)         *       *  use EBCDIC value as index on table 'CT1X' to get new index
  FOUND    L      R15,CT1(R14)          *********  get pointer to subroutine using index (0,4, 8 etc.)
           BALR   R14,R15                          Perform the sub-routine ("CALL" and return or Default)
           B      END                              go terminate this program
  * --------------- additional translate table (EBCDIC --> pointer table INDEX)  256 bytes----*
  CT1X     DC     12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)   12 identical sets of 16 bytes of x'00
  *                                                                        representing 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)      ..x'E0' – X'EF'
           DC     AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)      ..x'F0' – X'FF'
  * the assembler can be used to automatically calculate the index values and make the values more user friendly
  * (for e.g. '04' could be replaced with the symbolic expression 'PADD-CT1' in table CT1X above)
  * modified CT1 (added a default action when index = 00, single dimension, full 31 bit address)
  CT1      DC     A(DEFAULT)          index       =00      START of Control Table (4 byte address constants)
  PADD     DC     A(ADD)                          =04
  PSUB     DC     A(SUBTRACT)                     =08
  PMUL     DC     A(MULTIPLY)                     =12
  PDIV     DC     A(DIVIDE)                       =16
  * the rest of the code remains the same as first example

Intérprete aún más mejorado (hasta 21 veces menos instrucciones ejecutadas (donde n> = 64) en promedio que el primer ejemplo y hasta 42 veces menos de lo que se necesitaría usando 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 múltiples 'comparar y bifurcar' requerirían alrededor de 512 líneas (el tamaño del binario también se reduce casi a la mitad una vez). más).

  * ------------------ interpreter --------------------------------------------*
           SR     R14,R14               *********  Set R14=0
  CALC     IC     R14,INPUT1            * calc  *  put EBCDIC byte into lo order bits (24–31) of R14
           IC     R14,CT1X(R14)         *       *  use EBCDIC value as index on table 'CT1X' to get new index
           SLL    R14,2                 *       *  multiply index by 4 (additional instruction)
  FOUND    L      R15,CT1(R14)          *********  get pointer to subroutine using index (0,4, 8 etc.)
           BALR   R14,R15                          Perform the sub-routine ("CALL" and return or Default)
           B      END                              go terminate this program
  * --------------- additional translate table (EBCDIC --> pointer table INDEX)  256 bytes----*
  CT1X     DC     12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)   12 identical sets of 16 bytes of x'00'
  *                                                                        representing 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)      ..x'D0' – X'DF'
           DC     AL1(00,00,02,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)      ..x'F0' – X'FF'
  * the assembler can be used to automatically calculate the index values and make the values more user friendly
  * (for e.g. '01' could be replaced with the symbolic expression 'PADD-CT1/4' in table CT1X above)
  * modified CT1 (index now based on 0,1,2,3,4  not 0,4,8,12,16 to allow all 256 variations)
  CT1      DC     A(DEFAULT)          index       =00      START of Control Table (4 byte address constants)
  PADD     DC     A(ADD)                          =01
  PSUB     DC     A(SUBTRACT)                     =02
  PMUL     DC     A(MULTIPLY)                     =03
  PDIV     DC     A(DIVIDE)                       =04
  * the rest of the code remains the same as the 2nd example

Ejemplo de lenguaje C Este ejemplo en C usa dos tablas, la primera (CT1) es unatabla de búsqueda unidimensional de búsqueda lineal simple- para obtener un índice haciendo coincidir la entrada (x), y la segunda, la tabla asociada (CT1p), es una tabla de direcciones de etiquetas a las que saltar.

 static const char  CT1[] = {  "A",   "S",        "M",        "D" };                          /* permitted input  values */
 static const void *CT1p[] = { &&Add, &&Subtract, &&Multiply, &&Divide, &&Default};           /* labels to goto & default*/
 for (int i = 0; i < sizeof(CT1); i++)      /* loop thru ASCII values                                                    */
   {if (x==CT1[i]) goto *CT1p[i]; }       /* found --> appropriate label                                               */
 goto *CT1p[i+1];                           /* not found --> default label                                               */

Esto se puede hacer más eficiente si se usa una tabla de 256 bytes para traducir el valor ASCII sin procesar (x) directamente a un valor de índice secuencial denso para usarlo en la ubicación directa de la dirección de la rama de CT1p (es decir, " mapeo de índice " con un byte de ancho formación). Luego se ejecutará en tiempo constante para todos los valores posibles de x (si CT1p contiene los nombres de funciones en lugar de etiquetas, el salto podría reemplazarse con una llamada de función dinámica, eliminando el goto similar a un interruptor, pero disminuyendo el rendimiento por el costo adicional de la función de limpieza ).

 static const void *CT1p[] = {&&Default, &&Add, &&Subtract, &&Multiply, &&Divide};
 /* the 256 byte table, below, holds values (1,2,3,4), in corresponding ASCII positions (A,S,M,D), all others set to 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', '\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', '\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'};
 /* the following code will execute in constant time, irrespective of the value of the input character (x)                    */
 i = CT1x(x);            /* extract the correct subroutine index from table CT1x using its ASCII value as an index initially  */
 goto *CT1p[i];          /* goto (Switch to) the label corresponding to the index (0=default, 1=Add, 2=Subtract,.) - see CT1p */

El siguiente ejemplo a continuación ilustra cómo se puede lograr un efecto similar en lenguajes que no admiten definiciones de puntero en estructuras de datos, pero sí admiten bifurcaciones 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 las matrices de punteros no son compatibles, se puede usar 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 de lo contrario, realice una llamada (con retorno) a la subrutina apropiada (por defecto, Sumar, Restar, Multiplicar o Dividir, ..) para tratarlo.

CT2

entrada 1	subr #
A	1
S	2
METRO	3
D	4
?	0

Como en los ejemplos anteriores, es posible traducir de manera muy eficiente los valores de entrada ASCII potenciales (A, S, M, D o desconocidos) en un índice de matriz de punteros sin usar realmente una búsqueda de tabla, pero se muestra aquí como una tabla para mantener la coherencia con el primer ejemplo.

Matriz de punteros CT2P

matriz de puntero
-> predeterminado
-> Agregar
-> Restar
-> Multiplicar
-> Dividir
->? otro

Se pueden construir (es decir, personalizar) tablas de control multidimensionales 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', según algunos criterios de coincidencia. Una 'acción' puede incluir un puntero a otra tabla de control subordinada. El ejemplo simple a continuación ha tenido una condición 'O' 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 especificando la mismo identificador de subrutina que los caracteres en mayúsculas). También se incluye una columna adicional para contar los eventos reales en tiempo de ejecución para cada entrada a medida que ocurren.

CT3

entrada 1	alterno	subr #	contar
A	a	1	0
S	s	2	0
METRO	metro	3	0
D	D	4	0
?	?	0	0

Las entradas de la tabla de control son mucho más similares a las declaraciones condicionales en los lenguajes de procedimiento pero, fundamentalmente, sin las declaraciones condicionales reales (dependientes del idioma) (es decir, instrucciones) presentes (el código genérico está físicamente en el intérprete que procesa las entradas de la tabla, no en la propia tabla, 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 la lógica completa, un número de entrada de tabla o un puntero puede tomar efectivamente el lugar de un contador de programa en programas más convencionales y puede reiniciarse en una 'acción', también especificada en la entrada de la tabla. El siguiente ejemplo (CT4) muestra cómo extender la tabla anterior, para incluir una entrada 'siguiente' (y / o incluir una subrutina de 'alterar 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 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 "Goto-less" , (que incorpora el equivalente de las construcciones ' DO WHILE ' o ' for loop '), también se puede acomodar con estructuras de tabla de control adecuadamente diseñadas y 'indentadas'.

CT4 (un 'programa' completo para leer input1 y procesar, repitiendo hasta que se encuentre 'E')

entrada 1	alterno	subr #	contar	saltar
-	-	5	0	-
mi	mi	7	0	-
A	a	1	0	-
S	s	2	0	-
METRO	metro	3	0	-
D	D	4	0	-
?	?	0	0	-
-	-	6	0	1

Matriz de punteros CT4P

matriz de puntero
-> Predeterminado
-> Agregar
-> Restar
-> Multiplicar
-> Dividir
-> Leer Input1
-> Alterar el flujo
-> Fin

Calificación basada en tablas

En el campo especializado de la calificación de telecomunicaciones (relacionado con la determinación del costo de una llamada en particular), las técnicas de calificación basadas en tablas ilustran el uso de tablas de control en aplicaciones donde las reglas pueden cambiar con frecuencia debido a las fuerzas del mercado. Las tablas que determinan los cargos pueden ser modificadas con poca antelación por personas que no son programadores en muchos casos.

Si los algoritmos no están predefinidos en el intérprete (y, por lo tanto, requieren una interpretación adicional en tiempo de ejecución 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 una sobrecarga significativamente mayor ).

Hojas de cálculo

Una hoja de datos de una hoja de cálculo se puede considerar como una tabla de control bidimensional, con las celdas no vacías que representan datos para el programa de hoja de cálculo subyacente (el intérprete). Las celdas que contienen la fórmula generalmente tienen el prefijo de un signo igual y simplemente designan un tipo especial de entrada de datos que dicta el procesamiento de otras celdas referenciadas, al alterar el flujo de control dentro del intérprete. Es la externalización de fórmulas del intérprete subyacente lo que claramente identifica ambas hojas de cálculo y el ejemplo de "calificación basada en reglas" citado anteriormente como instancias fácilmente identificables del uso de tablas de control por parte de no programadores.

Paradigma de programación

Si se pudiera decir que la técnica de las tablas de control pertenece a cualquier 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 de la Interprete). Sin embargo, el propio intérprete y las subrutinas pueden programarse utilizando cualquiera de los paradigmas disponibles o incluso una combinación. 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 usan punteros de memoria directamente para una mayor eficiencia).

Analogía a código de bytes / conjunto de instrucciones de máquina virtual

Una tabla de control multidimensional tiene algunas similitudes conceptuales con el código de bytes que opera en una máquina virtual , ya que generalmente se requiere un programa "intérprete" dependiente de la plataforma para realizar la ejecución real (que está determinada en gran medida condicionalmente por el contenido de las tablas). También existen algunas similitudes conceptuales con el reciente Common Intermediate Language (CIL) con el objetivo de crear un 'conjunto de instrucciones' intermedio común que sea independiente de la plataforma (pero, a diferencia de CIL, no se pretende utilizar como 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.

Búsqueda de instrucciones

Cuando se usa una tabla de control multidimensional para determinar el flujo del programa, la función de contador de programa "hardware" normal se simula efectivamente con un puntero a la primera (o siguiente) entrada de la tabla o bien con un índice . "Obtener" la instrucción implica decodificar los datos en esa entrada de la tabla, sin necesariamente copiar todos o algunos de los datos dentro de la entrada primero. Los lenguajes de programación que son capaces de utilizar punteros tienen la doble ventaja de que implican menos gastos generales , tanto para acceder a los contenidos como para hacer avanzar el 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, la entrada de la tabla) se puede realizar incluso como una acción adicional opcional de cada entrada de la tabla individual, lo que permite bucles o instrucciones de salto en cualquier etapa.

Supervisión de la ejecución de la tabla de control

El programa del intérprete puede, opcionalmente, guardar el contador del programa (y otros detalles relevantes según el tipo de instrucción) en cada etapa para registrar una traza total o parcial del flujo real del programa con fines de depuración , detección de puntos calientes , análisis de cobertura de código y análisis de rendimiento (ver ejemplos CT3 y CT4 anteriores).

Ventajas

• Claridad: las tablas de información son omnipresentes y, en su mayoría, las comprende de forma inherente incluso el público en general (especialmente las tablas de diagnóstico de fallas en las guías de productos ).
• portabilidad: puede diseñarse para ser 100% independiente del idioma (e independiente de la plataforma, excepto el intérprete)
• Flexibilidad: capacidad para ejecutar primitivas o subrutinas de forma transparente y personalizarse para adaptarse al problema.
• compacidad: la tabla generalmente muestra el emparejamiento de condición / acción en paralelo (sin las dependencias habituales de implementación de plataforma / lenguaje), lo que a menudo también da como resultado
  • archivo binario : tamaño reducido gracias a una menor duplicación de instrucciones
  • archivo de origen : tamaño reducido mediante la eliminación de múltiples declaraciones condicionales
  • velocidades mejoradas de carga (o descarga) del programa
• mantenibilidad: las tablas a menudo reducen la cantidad de líneas de origen que se deben mantener v. comparaciones múltiples
• localidad de referencia: las estructuras de tablas compactas dan como resultado que las tablas permanezcan en la caché
• reutilización de código: el "intérprete" suele ser reutilizable. Con frecuencia, se puede adaptar fácilmente a nuevas tareas de programación utilizando precisamente la misma técnica y puede crecer "orgánicamente" convirtiéndose, en efecto, en una biblioteca estándar de subrutinas probadas y comprobadas , controladas por las definiciones de la tabla.
• eficiencia - optimización de todo el sistema posible. Cualquier mejora en el rendimiento del intérprete generalmente mejora todas las aplicaciones que lo utilizan (consulte los ejemplos en 'CT1' más arriba).
• extensible - se pueden agregar nuevas 'instrucciones' - simplemente extendiendo el intérprete
• El intérprete se puede escribir como un programa de aplicación.

Opcionalmente: -

• el intérprete puede ser introspectivo y " optimizarse automáticamente " utilizando métricas de tiempo de ejecución recopiladas dentro de la tabla misma (consulte CT3 y CT4, con entradas que podrían ordenarse periódicamente por recuento descendente). El intérprete también puede elegir opcionalmente la técnica de búsqueda más eficiente de forma dinámica a partir de las métricas recopiladas en tiempo de ejecución (por ejemplo, tamaño de la matriz, rango de valores, ordenados o no ordenados).
• Despacho dinámico : las funciones comunes se pueden precargar y las funciones menos comunes se pueden recuperar solo en el primer encuentro para reducir el uso de la memoria . Se puede emplear la memorización en la mesa para lograr esto.
• El intérprete puede tener funciones de depuración, seguimiento y monitoreo integradas, que luego se pueden encender o apagar a voluntad según el modo de prueba o 'en vivo'
• Las tablas de control se pueden construir 'sobre la marcha' (de acuerdo con alguna entrada del usuario o de parámetros) y luego ejecutadas por el intérprete (sin código de construcción literalmente).

Desventajas

• Requisito de capacitación: los programadores de aplicaciones generalmente no están capacitados para producir soluciones genéricas.

Lo siguiente se aplica principalmente a su uso en tablas multidimensionales, no a las tablas unidimensionales discutidas anteriormente.

• sobrecarga : algunos aumentan debido al nivel adicional de direccionamiento indirecto causado por instrucciones virtuales que tienen que ser 'interpretadas' (esto, sin embargo, generalmente puede ser más que compensado por un intérprete genérico bien diseñado que aproveche al máximo las eficientes técnicas de traducción directa, búsqueda y pruebas condicionales que pueden no se han utilizado de otra manera)
• Las expresiones complejas no siempre se pueden usar directamente en las entradas de la tabla de datos para fines de comparación.

(Sin embargo, estos 'valores intermedios' se pueden calcular de antemano en lugar de dentro de una subrutina y sus valores se mencionan en las entradas de la tabla condicional. Alternativamente, una subrutina puede realizar la prueba condicional compleja completa (como una 'acción' incondicional) y, mediante el establecimiento de un indicador de verdad como resultado, se puede probar en la siguiente entrada de la tabla. Consulte el teorema del programa estructurado )

Citas

La ramificación de múltiples vías es una técnica de programación importante que con demasiada frecuencia se reemplaza por una secuencia ineficiente de pruebas if. Peter Naur me escribió recientemente que considera el uso de tablas para controlar el flujo de programas como una idea básica de la informática que ha sido casi olvidada; pero espera que esté listo para redescubrirlo en cualquier momento. Es la clave de la eficiencia en todos los mejores compiladores que he estudiado.

-  Donald Knuth , Programación estructurada con ir a Declaraciones

Hay otra forma de ver 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 se puede expandir en una secuencia larga de llamadas a subrutinas y, a la inversa, dicha secuencia normalmente se puede empaquetar en una forma codificada que se interprete fácilmente. La ventaja de las técnicas interpretativas es la compacidad de la representación, la independencia de la máquina y la mayor capacidad de diagnóstico. A menudo, se puede escribir un intérprete de modo que la cantidad de tiempo invertida en la interpretación del código en sí y la derivación a la rutina adecuada sea insignificante

-  Donald Knuth , The Art of Computer Programming Volume 1, 1997, página 202

El espacio necesario para representar un programa a menudo se puede reducir mediante el uso de intérpretes en los que las secuencias comunes de operaciones se representan de forma compacta. Un ejemplo típico es el uso de una máquina de estados finitos para codificar un protocolo complejo o formato léxico en una pequeña tabla.

-  Jon Bentley , escribiendo 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 del compilador para declaraciones de rama de múltiples vías como problema de búsqueda estática

Los programas deben estar escritos para que las personas los lean y solo de manera incidental para que los ejecuten las máquinas.

-  "Estructura e interpretación de programas informáticos", prefacio de la primera edición, Abelson & Sussman

Muéstrame tu diagrama de flujo y oculta tus tablas, y seguiré desconcertado. Muéstreme sus tablas y normalmente no necesitaré su diagrama de flujo; será obvio.

-  "El mes del hombre mítico: ensayos sobre ingeniería de software", Fred Brooks

Ver también

• Programación basada en autómatas
• Arquitectura centrada en bases de datos
• Pruebas basadas en datos
• Tabla de decisiones
• Máquina de estados finitos
• Pruebas basadas en palabras clave
• Puntero (programación de computadoras)
• Sentencia de cambio : bifurcación de múltiples vías a una de varias etiquetas de programa , dependiendo de una única variable de entrada
• Código enhebrado
• Subprocesamiento de tokens

Notas

Referencias

• Metodología basada en tablas de decisión
• Programación estructurada con declaraciones de Donald Knuth
• Generación de código del compilador para declaraciones de rama de múltiples vías como un problema de búsqueda estática 1I994, por David A. Spuler

enlaces externos

• La instrucción Switch en Windows PowerShell describe las extensiones de la instrucción Switch estándar (que proporciona algunas características similares a las tablas de control)
• Ejemplo de tabla de control en lenguaje "C" usando punteros , por Christopher Sawtell c1993, Departamento de Ciencias de la Computación, Universidad de Auckland
• Diseño basado en tablas de Wayne Cunneyworth de DataKinetics
• De los requisitos a las tablas, al código y las pruebas por George Brooke
• Algunos comentarios sobre el uso de tablas de decisión ambiguas y su conversión a programas de computadora por PJH King y RG Johnson, Univ. de Londres, Londres, Reino Unido
• Ambigüedad en las tablas de decisión de entrada limitada por PJH King
• Conversión de tablas de decisión a programas de computadora mediante técnicas de máscara de reglas por PJH King
• Un análisis superoptimizador de la generación de código de rama de múltiples vías sección 3.9, página 16 mapeo de índices
• Tablas de salto a través de matrices de punteros de función en C / C ++ Jones, Nigel. "Arrays of Pointers to Functions [3] " Programación de sistemas integrados, mayo de 1999.
• Estadísticas de visitas a la página de este artículo en diciembre de 2009

• Software de modelado con máquinas de estados finitos: un enfoque práctico
• Tablas de estados finitos para aplicaciones generales de programación informática, enero de 1988 por Mark Leininger
• MSDN: procesamiento de eventos basado en disparadores
• Tabla de control en c2.com