Mesa de controle - Control table

Esta tabela de controle simples direciona o fluxo do programa de acordo com o valor da variável de entrada única. Cada entrada da tabela contém um possível valor de entrada a ser testado quanto à igualdade (implícita) e uma sub-rotina relevante a ser executada na coluna de ação. O nome da sub-rotina pode ser substituído por um número de sub-rotina relativo se os ponteiros não forem suportados

Tabelas de controle são tabelas que controlam o fluxo de controle ou desempenham um papel importante no controle do programa. Não há regras rígidas sobre a estrutura ou o conteúdo de uma tabela de controle - seu atributo de qualificação é sua capacidade de direcionar o fluxo de controle de alguma forma por meio da "execução" por um processador ou intérprete . O design de tais tabelas é às vezes referido como design baseado em tabela (embora isso normalmente se refira à geração de código automaticamente a partir de tabelas externas, em vez de tabelas diretas de tempo de execução). Em alguns casos, as tabelas de controle podem ser implementações específicas de programação baseada em autômatos baseados em máquinas de estados finitos . Se houver vários níveis hierárquicos de tabela de controle, eles podem se comportar de maneira equivalente às máquinas de estado UML

As tabelas de controle geralmente têm o equivalente a expressões condicionais ou referências de função incorporadas a elas, geralmente implícitas por sua posição de coluna relativa na lista de associação . As tabelas de controle reduzem a necessidade de programar estruturas semelhantes ou instruções de programa repetidamente. A natureza bidimensional da maioria das tabelas as torna mais fáceis de visualizar e atualizar do que a natureza unidimensional do código do programa. Em alguns casos, os não programadores podem ser designados para manter as tabelas de controle.

Uso típico

Uso mais avançado

semelhante ao bytecode - mas geralmente com operações implícitas pela própria estrutura da tabela

Estrutura da tabela

As tabelas podem ter dimensões múltiplas, de comprimento fixo ou variável e geralmente são portáteis entre plataformas de computador , exigindo apenas uma alteração do intérprete, não do próprio algoritmo - cuja lógica é essencialmente incorporada na estrutura e conteúdo da tabela. A estrutura da tabela pode ser semelhante a uma matriz associativa multimapa , onde um valor de dados (ou combinação de valores de dados) pode ser mapeado para uma ou mais funções a serem realizadas.

Tabelas unidimensionais

Talvez em sua implementação mais simples, uma tabela de controle às vezes pode ser uma tabela unidimensional para traduzir diretamente um valor de dados brutos para um deslocamento de sub-rotina correspondente , índice ou ponteiro usando o valor de dados brutos diretamente como o índice para a matriz, ou executando alguma aritmética básica sobre os dados de antemão. Isso pode ser alcançado em tempo constante (sem uma pesquisa linear ou binária usando uma tabela de pesquisa típica em uma matriz associativa ). Na maioria das arquiteturas , isso pode ser realizado em duas ou três instruções de máquina - sem quaisquer comparações ou loops. A técnica é conhecida como " função hash trivial " ou, quando usada especificamente para tabelas de ramificação, " envio duplo ". Para que isso seja viável, o intervalo de todos os valores possíveis dos dados precisa ser pequeno (por exemplo, um valor de caractere ASCII ou EBCDIC que tem um intervalo de hexadecimal '00' - 'FF'. Se o intervalo real for garantidamente menor além disso, a matriz pode ser truncada para menos de 256 bytes).

Tabela para traduzir os valores ASCII brutos (A, D, M, S) para o novo índice de sub-rotina (1,4,3,2) em tempo constante usando matriz unidimensional

(as lacunas no intervalo são mostradas como '..' para este exemplo, significando 'todos os valores hexadecimais até a próxima linha'. As primeiras duas colunas não fazem parte da matriz)

ASCII Hex Variedade
nulo 00 00
.. .. 00
@ 40 00
UMA 41 01
.. .. 00
D 44 04
.. .. 00
M 4D 03
.. .. 00
S 53 02

Na programação baseada em autômatos e no processamento de transações pseudoconversacionais , se o número de estados distintos do programa for pequeno, uma variável de controle de "sequência densa" pode ser usada para ditar com eficiência todo o fluxo do loop principal do programa.

Um valor de dados brutos de dois bytes exigiria um tamanho mínimo de tabela de 65.536 bytes - para lidar com todas as possibilidades de entrada - enquanto permite apenas 256 valores de saída diferentes. No entanto, esta técnica de tradução direta fornece uma validação e conversão extremamente rápida para um ponteiro de sub-rotina (relativo) se a heurística , juntamente com memória de acesso rápido suficiente, permitir seu uso.

Mesas de ramificação

Uma tabela de ramificação é uma 'matriz' unidimensional de instruções de ramificação / salto de código de máquina contíguas para efetuar uma ramificação de múltiplas vias para um rótulo de programa quando ramificada por uma ramificação imediatamente anterior e indexada. Às vezes, é gerado por um compilador otimizado para executar uma instrução switch - desde que o intervalo de entrada seja pequeno e denso, com poucas lacunas (conforme criado pelo exemplo de array anterior) [2] .

Embora bastante compactas - em comparação com as várias Ifinstruções equivalentes - as instruções de desvio ainda carregam alguma redundância, uma vez que o código de operação do desvio e a máscara do código de condição são repetidos junto com os desvios do desvio. Tabelas de controle contendo apenas os deslocamentos para os rótulos de programa podem ser construídos para superar esta redundância (pelo menos em linguagens assembly) e ainda necessitando apenas de tempo de execução menor sobrecarga em comparação com uma tabela ramo convencional.

Tabelas multidimensionais

Mais comumente, uma tabela de controle pode ser considerada uma tabela Verdade ou uma implementação executável ("binária") de uma tabela de decisão impressa (ou uma árvore de tabelas de decisão, em vários níveis). Eles contêm proposições (frequentemente implícitas) , junto com uma ou mais 'ações' associadas. Essas ações são geralmente executadas por sub - rotinas genéricas ou personalizadas que são chamadas por um programa " interpretador ". O interpretador nesta instância funciona efetivamente como uma máquina virtual , que 'executa' as entradas da tabela de controle e, portanto, fornece um nível mais alto de abstração do que o código subjacente do interpretador.

Uma tabela de controle pode ser construída ao longo de linhas semelhantes a uma instrução switch dependente de idioma , mas com a possibilidade adicional de testar combinações de valores de entrada (usando condições AND / OR de estilo booleano ) e potencialmente chamar várias sub-rotinas (em vez de apenas um único conjunto de valores e 'ramificar para' rótulos de programa). (A construção da instrução switch em qualquer caso pode não estar disponível ou ter implementações confusamente diferentes em linguagens de alto nível ( HLL ). O conceito de tabela de controle, por comparação, não tem dependências de linguagem intrínsecas, mas pode, no entanto, ser implementado de forma diferente de acordo com o disponível recursos de definição de dados da linguagem de programação escolhida.)

Conteúdo da tabela

Uma tabela de controle incorpora essencialmente a ' essência ' de um programa convencional, despojado de sua sintaxe de linguagem de programação e componentes dependentes da plataforma (por exemplo, IF / THEN DO .., FOR .., DO WHILE .., SWITCH, GOTO, CALL) e ' condensado 'em suas variáveis ​​(por exemplo, entrada1), valores (por exemplo,' A ',' S ',' M 'e' D ') e identidades de sub-rotina (por exemplo,' Adicionar ',' subtrair, .. 'ou # 1, # 2, ..). A estrutura da própria tabela normalmente implica nas operações lógicas (padrão) envolvidas - como 'teste de igualdade', execução de uma sub-rotina e 'próxima operação' ou seguindo a sequência padrão (em vez de estas serem explicitamente declaradas nas instruções do programa - conforme necessário em outros paradigmas de programação ).

Uma tabela de controle multidimensional normalmente conterá, no mínimo, pares de valor / ação e pode conter adicionalmente operadores e informações de tipo , como localização, tamanho e formato dos dados de entrada ou saída, seja a conversão de dados (ou outro tempo de execução nuances de processamento) é necessário antes ou depois do processamento (se ainda não estiver implícito na própria função). A tabela pode ou não pode conter índices ou relativas ou absolutas ponteiros para genéricos ou personalizados primitivas ou sub-rotinas para ser executado dependendo outros valores na "linha".

A tabela ilustrada abaixo se aplica apenas a 'entrada1', uma vez que nenhuma entrada específica é especificada na tabela.

condições e ações implícitas na estrutura

(implícito) IF = (implícito) executar
valor açao
valor açao

(Este emparelhamento lado a lado de valor e ação tem semelhanças com construções na programação orientada a eventos , ou seja, 'detecção de evento' e 'tratamento de evento', mas sem (necessariamente) a natureza assíncrona do próprio evento)

A variedade de valores que podem ser codificados em uma tabela de controle depende muito da linguagem de computador usada. A linguagem assembly fornece o escopo mais amplo para tipos de dados, incluindo (para as ações), a opção de código de máquina executável diretamente . Normalmente, uma tabela de controle conterá valores para cada classe de correspondência possível de entrada junto com um ponteiro correspondente para uma sub-rotina de ação. Algumas linguagens afirmam não oferecer suporte a ponteiros (diretamente), mas, no entanto, podem suportar um índice que pode ser usado para representar um 'número de sub-rotina relativo' para realizar a execução condicional, controlada pelo valor na entrada da tabela (por exemplo, para uso em um SWITCH otimizado declaração - projetado com zero gaps (ou seja, uma ramificação multiway )).

Comentários posicionados acima de cada coluna (ou até mesmo documentação textual incorporada) podem tornar uma tabela de decisão 'legível por humanos' mesmo depois de 'condensar' (codificação) em seus fundamentos (e ainda em linha com a especificação original do programa - especialmente se for impressa a tabela de decisão, enumerando cada ação única, é criada antes do início da codificação). As entradas da tabela também podem conter contadores para coletar estatísticas de tempo de execução para otimização "em andamento" ou posterior

Localização da mesa

As tabelas de controle podem residir em armazenamento estático , em armazenamento auxiliar , como um arquivo simples ou em um banco de dados ou podem, alternativamente, ser parcialmente ou totalmente construídas dinamicamente no momento da inicialização do programa a partir de parâmetros (que podem residir em uma tabela). Para obter a eficiência ideal, a tabela deve ser residente na memória quando o intérprete começa a usá-la.

O intérprete e as sub-rotinas

O intérprete pode ser escrito em qualquer linguagem de programação adequada, incluindo uma linguagem de alto nível . Um interpretador genérico adequadamente projetado , junto com um conjunto bem escolhido de sub-rotinas genéricas (capaz de processar as primitivas que ocorrem mais comumente ), exigiria codificação convencional adicional apenas para novas sub-rotinas personalizadas (além de especificar a própria tabela de controle). O intérprete, opcionalmente, pode se aplicar apenas a algumas seções bem definidas de um programa de aplicativo completo (como o loop de controle principal ) e não a outras seções 'menos condicionais' (como inicialização, encerramento do programa e assim por diante).

O interpretador não precisa ser excessivamente complexo ou produzido por um programador com o conhecimento avançado de um redator de compilador e pode ser escrito como qualquer outro programa de aplicação - exceto que geralmente é projetado com eficiência em mente. Sua função principal é "executar" as entradas da tabela como um conjunto de "instruções". Não há necessidade de nenhum requisito para a análise das entradas da tabela de controle e estas devem, portanto, ser projetadas, na medida do possível, para estar 'prontas para execução', exigindo apenas o "plug-in" de variáveis ​​das colunas apropriadas ao código genérico já compilado o intérprete. As instruções do programa são, em teoria, infinitamente extensíveis e constituem valores (possivelmente arbitrários) dentro da tabela que são significativos apenas para o intérprete. O fluxo de controle do interpretador é normalmente por processamento sequencial de cada linha da tabela, mas pode ser modificado por ações específicas nas entradas da tabela.

Esses valores arbitrários podem, portanto, ser projetados com eficiência em mente - selecionando valores que podem ser usados ​​como índices diretos para dados ou ponteiros de função . Para plataformas / linguagem específicas , eles podem ser projetados especificamente para minimizar o comprimento do caminho de instrução usando valores de tabela de ramificação ou mesmo, em alguns casos como em compiladores JIT , consistem em " fragmentos " de código de máquina diretamente executáveis (ou ponteiros para eles).

As sub-rotinas podem ser codificadas na mesma linguagem do próprio intérprete ou em qualquer outra linguagem de programa suportada (desde que existam mecanismos de ligação de 'Chamada' inter-linguagens adequados). A escolha do idioma para o intérprete e / ou sub-rotinas geralmente dependerá de quão portátil ele precisa ser em várias plataformas . Pode haver várias versões do interpretador para melhorar a portabilidade de uma mesa de controle. Um ponteiro de tabela de controle subordinado pode opcionalmente substituir um ponteiro de sub-rotina nas colunas de 'ação' se o interpretador suportar esta construção, representando uma 'queda' condicional para um nível lógico inferior, imitando uma estrutura de programa estruturada convencional .

Considerações de desempenho

À primeira vista, o uso de tabelas de controle pareceria adicionar bastante à sobrecarga de um programa , exigindo, como faz, um processo de interpretação antes que as instruções da linguagem de programação 'nativa' sejam executadas. No entanto, nem sempre é o caso. Ao separar (ou 'encapsular') a codificação executável da lógica, conforme expresso na tabela, ela pode ser mais prontamente direcionada para desempenhar sua função de forma mais eficiente. Isso pode ser experimentado mais obviamente em um aplicativo de planilha - onde o software de planilha subjacente converte de forma transparente 'fórmulas' lógicas complexas da maneira mais eficiente possível, a fim de exibir seus resultados.

Os exemplos abaixo foram escolhidos parcialmente para ilustrar ganhos de desempenho em potencial que podem não apenas compensar significativamente a camada adicional de abstração, mas também melhorar - o que de outra forma poderia ter sido - código menos eficiente, menos sustentável e mais extenso. Embora os exemplos dados sejam para uma linguagem de montagem de 'baixo nível' e para a linguagem C , pode ser visto, em ambos os casos, que muito poucas linhas de código são necessárias para implementar a abordagem da tabela de controle e ainda pode atingir um tempo constante muito significativo melhorias de desempenho, reduzem a codificação de fonte repetitiva e ajudam a clareza, em comparação com construções verbosas de linguagem de programa convencional. Veja também as citações de Donald Knuth , sobre tabelas e a eficiência da ramificação multiway neste artigo.

Exemplos de tabelas de controle

Os exemplos a seguir são arbitrários (e baseados em apenas uma única entrada para simplificar), no entanto, a intenção é meramente demonstrar como o fluxo de controle pode ser efetuado por meio do uso de tabelas em vez de instruções regulares do programa. Deve ficar claro que essa técnica pode ser facilmente estendida para lidar com várias entradas, aumentando o número de colunas ou utilizando várias entradas de tabela (com opcional e / ou operador). Da mesma forma, usando tabelas de controle "vinculadas" (hierárquicas), a programação estruturada pode ser realizada (opcionalmente, usando recuo para ajudar a destacar as tabelas de controle subordinadas).

"CT1" é um exemplo de uma tabela de controle que é uma tabela de consulta simples . A primeira coluna representa o valor de entrada a ser testado (por um 'IF input1 = x' implícito) e, se TRUE, a 2ª coluna correspondente (a 'ação') contém um endereço de sub-rotina a ser executado por uma chamada (ou salto para - semelhante a uma instrução SWITCH ). É, com efeito, um ramal de múltiplas vias com retorno (uma forma de " envio dinâmico "). A última entrada é o caso padrão em que nenhuma correspondência é encontrada.

CT1

entrada 1 ponteiro
UMA -> Adicionar
S -> Subtrair
M -> Multiplicar
D -> Divide
? -> Padrão

Para linguagens de programação que suportam ponteiros dentro de estruturas de dados junto com outros valores de dados, a tabela acima (CT1) pode ser usada para direcionar o fluxo de controle para uma sub-rotina apropriada de acordo com o valor correspondente da tabela (sem uma coluna para indicar o contrário, a igualdade é assumida em neste caso simples).

Exemplo de linguagem assembly para IBM / 360 (intervalo máximo de endereços de 16 Mb) ou Z / Architecture

Nenhuma tentativa é feita para otimizar a pesquisa na codificação para este primeiro exemplo e, em vez disso, ele usa uma técnica de pesquisa linear simples - puramente para ilustrar o conceito e demonstrar menos linhas de origem. Para lidar com todos os 256 valores de entrada diferentes, seriam necessárias cerca de 265 linhas de código-fonte (principalmente entradas de tabela de linha única), ao passo que várias 'comparar e ramificar' normalmente teriam exigido cerca de 512 linhas de origem (o tamanho do binário também é dividido pela metade, cada entrada da tabela requer apenas 4 bytes em vez de aproximadamente 8 bytes para uma série de instruções de 'comparação imediata' / desvio (para variáveis ​​de entrada maiores, a economia é ainda maior).

  * ------------------ 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..

melhorando o desempenho do intérprete no exemplo acima

Para fazer uma seleção no exemplo acima, o comprimento médio do caminho da instrução (excluindo o código da sub-rotina) é '4n / 2 +3', mas pode ser facilmente reduzido, onde n = 1 a 64, a um tempo constante com um comprimento do caminho de '5' com comparações de zero , se uma tabela de conversão de 256 bytes for utilizada pela primeira vez para criar um índice direto para CT1 a partir dos dados EBCDIC brutos. Onde n = 6, isso seria equivalente a apenas 3 instruções sequenciais de comparação e desvio. No entanto, onde n <= 64, em média, seriam necessárias aproximadamente 13 vezes menos instruções do que o uso de comparações múltiplas. Onde n = 1 a 256, em média ele usaria aproximadamente 42 vezes menos instruções - uma vez que, neste caso, uma instrução adicional seria necessária (para multiplicar o índice por 4).

Intérprete aprimorado (até 26 vezes menos instruções executadas do que o exemplo acima, em média, onde n = 1 a 64 e até 13 vezes menos do que seria necessário usando comparações múltiplas).

Para lidar com 64 valores de entrada diferentes, são necessárias cerca de 85 linhas de código-fonte (ou menos) (principalmente entradas de tabela de linha única), enquanto várias 'comparar e ramificar' exigiriam cerca de 128 linhas (o tamanho do binário também é quase reduzido pela metade - apesar a tabela adicional de 256 bytes necessária para extrair o 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 aprimorado ainda mais (até 21 vezes menos instruções executadas (onde n> = 64) do que o primeiro exemplo em média e até 42 vezes menos do que seria necessário usando comparações múltiplas).

Para lidar com 256 valores de entrada diferentes, seriam necessárias aproximadamente 280 linhas de código-fonte ou menos (principalmente entradas de tabela de linha única), enquanto várias 'comparar e ramificar' exigiriam cerca de 512 linhas (o tamanho do binário também é quase reduzido pela metade uma vez mais).

  * ------------------ 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

Exemplo de linguagem C Este exemplo em C usa duas tabelas, a primeira (CT1) é umatabela de pesquisa linear simples de pesquisa unidimensional - para obter um índice combinando a entrada (x), e a segunda, a tabela associada (CT1p), é uma tabela de endereços de rótulos para onde ir.

 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                                               */

Isso pode ser mais eficiente se uma tabela de 256 bytes for usada para traduzir o valor ASCII bruto (x) diretamente para um valor de índice sequencial denso para uso na localização direta do endereço do ramal de CT1p (ou seja, " mapeamento de índice " com um byte-wide variedade). Em seguida, ele será executado em tempo constante para todos os valores possíveis de x (Se CT1p contiver os nomes das funções em vez de rótulos, o salto pode ser substituído por uma chamada de função dinâmica, eliminando o goto semelhante a um switch - mas diminuindo o desempenho pelo custo adicional da função de limpeza ).

 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 */

O próximo exemplo ilustra como a seguir um efeito semelhante pode ser alcançado em idiomas que não suportam definições ponteiro em estruturas de dados, mas fazer apoio indexados ramificação para uma sub-rotina - contidos dentro de um ( baseado em 0 ) matriz de ponteiros de sub-rotinas. A tabela (CT2) é usada para extrair o índice (da 2ª coluna) para o array de ponteiros (CT2P). Se as matrizes de ponteiro não forem suportadas, uma instrução SWITCH ou equivalente pode ser usada para alterar o fluxo de controle para uma de uma sequência de rótulos de programa (por exemplo: case0, case1, case2, case3, case4) que então processam a entrada diretamente, ou caso contrário, execute uma chamada (com retorno) para a sub-rotina apropriada (padrão, Adicionar, Subtrair, Multiplicar ou Dividir, ..) para lidar com isso.

CT2

entrada 1 subr #
UMA 1
S 2
M 3
D 4
? 0

Como nos exemplos acima, é possível traduzir de forma muito eficiente os valores de entrada ASCII potenciais (A, S, M, D ou desconhecido) em um índice de matriz de ponteiro sem realmente usar uma consulta de tabela, mas é mostrado aqui como uma tabela para consistência com o primeiro exemplo.

Array de ponteiro CT2P
array de ponteiros
-> padrão
-> Adicionar
-> Subtrair
-> Multiplicar
-> Divide
->? outro

As tabelas de controle multidimensionais podem ser construídas (ou seja, personalizadas) que podem ser 'mais complexas' do que os exemplos acima, que podem testar várias condições em várias entradas ou executar mais de uma 'ação', com base em alguns critérios de correspondência. Uma 'ação' pode incluir um ponteiro para outra tabela de controle subordinada. O exemplo simples abaixo teve uma condição 'OU' implícita incorporada como uma coluna extra (para lidar com a entrada em minúsculas, no entanto, neste caso, isso poderia igualmente ter sido tratado simplesmente por ter uma entrada extra para cada um dos caracteres minúsculos especificando o mesmo identificador de sub-rotina dos caracteres maiúsculos). Uma coluna extra para contar os eventos de tempo de execução reais para cada entrada conforme eles ocorrem também está incluída.

CT3

entrada 1 alternar subr # contar
UMA uma 1 0
S s 2 0
M m 3 0
D d 4 0
? ? 0 0

As entradas da tabela de controle são, então, muito mais semelhantes às declarações condicionais em linguagens procedurais, mas, crucialmente, sem as declarações condicionais reais (dependentes da linguagem) (ou seja, instruções) presentes (o código genérico está fisicamente no interpretador que processa as entradas da tabela, não na própria tabela - que simplesmente incorpora a lógica do programa por meio de sua estrutura e valores).

Em tabelas como essas, onde uma série de entradas de tabela semelhantes define toda a lógica, um número de entrada de tabela ou ponteiro pode efetivamente tomar o lugar de um contador de programa em programas mais convencionais e pode ser redefinido em uma 'ação', também especificada em a entrada da tabela. O exemplo abaixo (CT4) mostra como estender a tabela anterior, para incluir uma entrada 'próxima' (e / ou incluir uma sub-rotina 'alter flow' ( salto )) pode criar um loop (Este exemplo não é realmente a maneira mais eficiente de construir tal tabela de controle, mas, ao demonstrar uma 'evolução' gradual dos primeiros exemplos acima, mostra como colunas adicionais podem ser usadas para modificar o comportamento.) A quinta coluna demonstra que mais de uma ação pode ser iniciada com uma única entrada da tabela - neste caso, uma ação a ser executada após o processamento normal de cada entrada ('-' valores significam 'nenhuma condição' ou 'nenhuma ação').

A programação estruturada ou código "Goto-less" , (incorporando o equivalente a ' DO WHILE ' ou ' for loop ' construções), também pode ser acomodada com estruturas de tabela de controle adequadamente projetadas e 'recuadas'.

CT4 (um 'programa' completo para ler a entrada1 e processar, repetindo até que 'E' seja encontrado)

entrada 1 alternar subr # contar pular
- - 5 0 -
E e 7 0 -
UMA uma 1 0 -
S s 2 0 -
M m 3 0 -
D d 4 0 -
? ? 0 0 -
- - 6 0 1
Array de ponteiro CT4P
array de ponteiros
-> Padrão
-> Adicionar
-> Subtrair
-> Multiplicar
-> Divide
-> Ler entrada1
-> Alterar o fluxo
-> Fim

Classificação baseada na tabela

No campo especializado de classificação de telecomunicações (preocupada com a determinação do custo de uma chamada específica), as técnicas de classificação baseadas em tabelas ilustram o uso de tabelas de controle em aplicações onde as regras podem mudar frequentemente devido às forças do mercado. As tabelas que determinam os encargos podem ser alteradas a curto prazo por não programadores em muitos casos.

Se os algoritmos não forem pré-construídos no interpretador (e, portanto, requerem interpretação adicional de tempo de execução de uma expressão mantida na tabela), é conhecido como "Classificação baseada em regras" em vez de classificação baseada em tabela (e, conseqüentemente, consome significativamente mais sobrecarga )

Planilhas

Uma folha de dados de planilha pode ser considerada uma tabela de controle bidimensional, com as células não vazias representando dados para o programa de planilha subjacente (o intérprete). As células que contêm a fórmula são geralmente prefixadas com um sinal de igual e simplesmente designam um tipo especial de entrada de dados que determina o processamento de outras células referenciadas - alterando o fluxo de controle dentro do interpretador. É a externalização de fórmulas do interpretador subjacente que identifica claramente ambas as planilhas e o exemplo de "classificação baseada em regras" citado acima como instâncias prontamente identificáveis ​​do uso de tabelas de controle por não programadores.

Paradigma de programação

Se a técnica das tabelas de controle pudesse pertencer a qualquer paradigma de programação em particular , a analogia mais próxima poderia ser a programação baseada em autômatos ou "reflexiva" (uma forma de metaprogramação - uma vez que as entradas da tabela poderiam 'modificar' o comportamento do intérprete). O próprio intérprete, entretanto, e as sub-rotinas, podem ser programados usando qualquer um dos paradigmas disponíveis ou mesmo uma mistura. A própria tabela pode ser essencialmente uma coleção de valores de " dados brutos " que nem precisam ser compilados e podem ser lidos de uma fonte externa (exceto em implementações específicas, dependentes de plataforma, usando ponteiros de memória diretamente para maior eficiência).

Analogia com conjunto de instruções de bytecode / máquina virtual

Uma tabela de controle multidimensional tem algumas semelhanças conceituais com o bytecode operando em uma máquina virtual , em que um programa "interpretador" dependente de plataforma geralmente é necessário para realizar a execução real (que é amplamente determinada condicionalmente pelo conteúdo das tabelas). Existem também algumas semelhanças conceituais com a recente Common Intermediate Language (CIL) no objetivo de criar um 'conjunto de instruções' intermediário comum que seja independente da plataforma (mas ao contrário do CIL, sem pretensões de ser usado como um recurso comum para outras línguas) . O código P também pode ser considerado uma implementação semelhante, mas anterior, com origens que remontam a 1966.

Busca de instrução

Quando uma tabela de controle multidimensional é usada para determinar o fluxo do programa, a função normal do Contador de Programa de "hardware" é efetivamente simulada com um ponteiro para a primeira (ou próxima) entrada da tabela ou então um índice para ela. "Buscar" a instrução envolve decodificar os dados dessa entrada da tabela - sem necessariamente copiar todos ou alguns dos dados da entrada primeiro. Linguagens de programação que são capazes de usar ponteiros têm a dupla vantagem de que menos sobrecarga está envolvida, tanto no acesso ao conteúdo quanto no avanço do contador para apontar para a próxima entrada da tabela após a execução. O cálculo do próximo endereço de 'instrução' (ou seja, entrada de tabela) pode até ser executado como uma ação adicional opcional de cada entrada de tabela individual, permitindo loops e / ou instruções de salto em qualquer estágio.

Monitorando a execução da tabela de controle

O programa interpretador pode, opcionalmente, salvar o contador do programa (e outros detalhes relevantes, dependendo do tipo de instrução) em cada estágio para registrar um rastreamento completo ou parcial do fluxo real do programa para fins de depuração , detecção de ponto de acesso , análise de cobertura de código e análise de desempenho (consulte exemplos CT3 e CT4 acima).

Vantagens

  • clareza - as tabelas de informações são onipresentes e, em sua maioria, inerentemente compreendidas até mesmo pelo público em geral (especialmente tabelas de diagnóstico de falhas em guias de produtos )
  • portabilidade - pode ser projetado para ser 100% independente do idioma (e independente da plataforma - exceto para o intérprete)
  • flexibilidade - capacidade de executar primitivas ou sub - rotinas de forma transparente e ser projetado de acordo com o problema
  • compactação - a tabela geralmente mostra o emparelhamento de condição / ação lado a lado (sem as dependências usuais de implementação de plataforma / linguagem), muitas vezes também resultando em
    • arquivo binário - reduzido em tamanho por meio de menos duplicação de instruções
    • arquivo de origem - reduzido em tamanho por meio da eliminação de várias instruções condicionais
    • velocidades aprimoradas de carregamento (ou download) do programa
  • manutenibilidade - as tabelas muitas vezes reduzem o número de linhas de origem que precisam ser mantidas v. comparações múltiplas
  • localidade de referência - estruturas de tabelas compactas resultam em tabelas remanescentes no cache
  • reutilização de código - o "interpretador" geralmente é reutilizável. Freqüentemente, pode ser facilmente adaptado a novas tarefas de programação usando precisamente a mesma técnica e pode crescer 'organicamente' tornando-se, com efeito, uma biblioteca padrão de sub-rotinas testadas e comprovadas , controlada pelas definições da tabela.
  • eficiência - é possível a otimização de todo o sistema. Qualquer melhoria de desempenho do interpretador geralmente melhora todos os aplicativos que o utilizam (consulte os exemplos em 'CT1' acima).
  • extensível - novas 'instruções' podem ser adicionadas - simplesmente estendendo o interpretador
  • intérprete pode ser escrito como um programa de aplicação

Opcionalmente: -

  • o intérprete pode ser introspectivo e "auto- otimizado " usando métricas de tempo de execução coletadas na própria tabela (consulte CT3 e CT4 - com entradas que podem ser classificadas periodicamente por contagem decrescente). O intérprete também pode, opcionalmente, escolher a técnica de pesquisa mais eficiente dinamicamente a partir das métricas coletadas em tempo de execução (por exemplo, tamanho da matriz, intervalo de valores, classificado ou não)
  • despacho dinâmico - funções comuns podem ser pré-carregadas e funções menos comuns buscadas apenas no primeiro encontro para reduzir o uso de memória . A memoização na mesa pode ser empregada para conseguir isso.
  • O intérprete pode ter recursos de depuração, rastreamento e monitoramento integrados - que podem ser ligados ou desligados à vontade de acordo com o modo de teste ou 'ao vivo'
  • as tabelas de controle podem ser construídas 'on-the-fly' (de acordo com alguma entrada do usuário ou de parâmetros) e então executadas pelo interpretador (sem construir o código literalmente).

Desvantagens

  • requisito de treinamento - os programadores de aplicativos geralmente não são treinados para produzir soluções genéricas

O seguinte se aplica principalmente ao seu uso em tabelas multidimensionais, não as tabelas unidimensionais discutidas anteriormente.

  • sobrecarga - algum aumento por causa do nível extra de indireção causado por instruções virtuais tendo que ser 'interpretadas' (isso, no entanto, pode geralmente ser mais do que compensado por um interpretador genérico bem projetado aproveitando todas as vantagens da tradução direta eficiente, pesquisa e técnicas de teste condicional que podem não foram utilizados de outra forma)
  • As expressões complexas nem sempre podem ser usadas diretamente nas entradas da tabela de dados para fins de comparação
(esses 'valores intermediários' podem, no entanto, ser calculados de antemão em uma sub-rotina e seus valores referidos nas entradas da tabela condicional. Como alternativa, uma sub-rotina pode realizar o teste condicional complexo completo (como uma 'ação' incondicional) e, ao definir um sinalizador de verdade como seu resultado, ele pode então ser testado na próxima entrada da tabela. Consulte o teorema do programa estruturado )

Citações

A ramificação multiway é uma técnica de programação importante que é freqüentemente substituída por uma sequência ineficiente de testes if. Peter Naur escreveu-me recentemente que considera o uso de tabelas para controlar o fluxo do programa como uma ideia básica da ciência da computação que foi quase esquecida; mas ele espera que esteja maduro para ser redescoberto a qualquer momento. É a chave para a eficiência em todos os melhores compiladores que estudei.

-  Donald Knuth , programação estruturada com go to Statements

Existe outra maneira de ver um programa escrito em linguagem interpretativa. Pode ser considerado como uma série de chamadas de sub-rotina, uma após a outra. Tal programa pode de fato ser expandido em uma longa sequência de chamadas em sub-rotinas e, inversamente, tal sequência pode geralmente ser compactada em uma forma codificada que é prontamente interpretada. As vantagens das técnicas interpretativas são a compactação da representação, a independência da máquina e o aumento da capacidade de diagnóstico. Um intérprete pode muitas vezes ser escrito de forma que a quantidade de tempo gasto na interpretação do próprio código e na ramificação para a rotina apropriada seja insignificante

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

O espaço necessário para representar um programa pode frequentemente ser diminuído pelo uso de intérpretes nos quais sequências comuns de operações são representadas de forma compacta. Um exemplo típico é o uso de uma máquina de estado finito para codificar um protocolo complexo ou formato léxico em uma pequena mesa

-  Jon Bentley , escrevendo programas eficientes

As tabelas de salto podem ser especialmente eficientes se os testes de intervalo puderem ser omitidos. Por exemplo, se o valor de controle for um tipo enumerado (ou um caractere), ele pode conter apenas um pequeno intervalo fixo de valores e um teste de intervalo é redundante, desde que a tabela de salto seja grande o suficiente para lidar com todos os valores possíveis

-  David.A. SPULER, Geração de código do compilador para declarações de ramificação multifacetada como um problema de pesquisa estática

Os programas devem ser escritos para que as pessoas leiam e apenas incidentalmente para que as máquinas os executem.

-  "Estrutura e Interpretação de Programas de Computador", prefácio à primeira edição, Abelson & Sussman

Mostre-me seu fluxograma e oculte suas tabelas, e continuarei perplexo. Mostre-me suas tabelas e geralmente não precisarei de seu fluxograma; será óbvio.

-  "The Mythical Man-Month: Essays on Software Engineering", Fred Brooks

Veja também

Notas

Referências

links externos