Kontroltabel - Control table

Denne enkle kontroltabel styrer programflow i henhold til værdien af ​​den enkelte inputvariabel. Hver tabelpost indeholder en mulig inputværdi, der kan testes for lighed (underforstået) og en relevant subrutine, der skal udføres i handlingssøjlen. Navnet på subrutinen kan erstattes af et relativt subrutinenummer, hvis markører ikke understøttes

Kontroltabeller er tabeller, der styrer kontrolflowet eller spiller en vigtig rolle i programstyringen. Der er ingen stive regler om strukturen eller indholdet af en kontroltabel - dens kvalificerende attribut er dens evne til at styre kontrolflow på en eller anden måde gennem "udførelse" af en processor eller tolk . Designet af sådanne tabeller kaldes undertiden borddrevet design (selvom det typisk refererer til generering af kode automatisk fra eksterne tabeller snarere end direkte kørselstabeller). I nogle tilfælde kan kontroltabeller være specifikke implementeringer af finite-state-machine- baserede automata-baserede programmering . Hvis der er flere hierarkiske niveauer af kontroltabellen, kan de opføre sig på samme måde som UML-tilstandsmaskiner

Kontrol tabeller har ofte svarer til betingede udtryk eller funktion referencer indlejret i dem, som regel underforstået af deres relative kolonne position i foreningen listen . Kontroltabeller reducerer behovet for at programmere lignende strukturer eller programerklæringer igen og igen. Den todimensionale karakter af de fleste tabeller gør dem lettere at se og opdatere end den endimensionelle karakter af programkoden. I nogle tilfælde kan ikke-programmører tildeles til at vedligeholde kontroltabellerne.

Typisk brug

• Transformation af inputværdier til:
  • et indeks , for senere forgrening eller pointer opslag
  • et programnavn, relativ underrutine nummer, programmærke eller programforskydning for at ændre kontrolflowet
• Styring af en hovedsløjfe i hændelsesdrevet programmering ved hjælp af en kontrolvariabel til tilstandsovergange
• Styring af programcyklussen til applikationer til behandling af online transaktioner

Mere avanceret brug

• Fungerer som virtuelle instruktioner til en virtuel maskine, der behandles af en tolk

svarer til bytecode - men normalt med operationer, der er underforstået af selve bordstrukturen

Bordstruktur

Tabellerne kan have flere dimensioner med faste eller variable længder og er normalt bærbare mellem computerplatforme , hvilket kun kræver en ændring af tolken, ikke selve algoritmen - hvis logik i det væsentlige er inkorporeret i tabelstrukturen og indholdet. Tabellens struktur kan svare til et multimap- associerende array , hvor en dataværdi (eller en kombination af dataværdier) kan kortlægges til en eller flere funktioner, der skal udføres.

Endimensionelle tabeller

I måske dens simpleste implementering, kan en kontrol tabel undertiden være en endimensional tabel for direkte at oversætte en rå data værdi til en tilsvarende subrutine offset , indeks eller pointer hjælp rådataværdien enten direkte som indekset til arrayet, eller ved at udføre nogle grundlæggende aritmetiske data på forhånd. Dette kan opnås i konstant tid (uden en lineær søgning eller binær søgning ved hjælp af en typisk opslagstabel i et associerende array ). I de fleste arkitekturer kan dette opnås i to eller tre maskininstruktioner - uden sammenligninger eller sløjfer. Teknikken er kendt som en " triviel hash-funktion " eller, når den anvendes specifikt til grenborde, " dobbelt forsendelse ". For at dette skal være muligt, skal rækkevidden af ​​alle mulige værdier i dataene være lille (f.eks. En ASCII- eller EBCDIC-tegnværdi , der har et interval på hexadecimal '00' - 'FF'. Hvis det faktiske område garanteres at være mindre end dette, kan arrayet afkortes til mindre end 256 byte).

Tabel til oversættelse af rå ASCII-værdier (A, D, M, S) til nyt subrutineindeks (1,4,3,2) i konstant tid ved hjælp af et-dimensionelt array

(huller i området vises som '..' i dette eksempel, hvilket betyder 'alle hex-værdier op til næste række'. De to første kolonner er ikke en del af arrayet)

I automatisk-baseret programmering og pseudokonversationel transaktionsbehandling , hvis antallet af forskellige programtilstande er lille, kan en "tæt sekvens" -styringsvariabel anvendes til effektivt at diktere hele strømmen af ​​hovedprogrammets sløjfe.

En to-bit rå dataværdi ville kræve en minimumstabelstørrelse på 65.536 byte - for at håndtere alle inputmuligheder - samtidig med at der kun er 256 forskellige outputværdier. Imidlertid tilvejebringer denne direkte oversættelsesteknik en ekstremt hurtig validering og konvertering til en (relativ) subrutinemarkør, hvis heuristikken sammen med tilstrækkelig hurtigadgangshukommelse tillader dens anvendelse.

Gren tabeller

En forgreningstabel er et endimensionelt 'array' af sammenhængende maskinkodeforgrenings- / springinstruktioner for at påvirke en flervejsforgrening til et programmærke, når det er forgrenet med en umiddelbart forudgående og indekseret gren. Det genereres undertiden af ​​en optimeringscompiler til at udføre en switch-sætning - forudsat at inputområdet er lille og tæt med få huller (som oprettet af det foregående matrixeksempel) [2] .

Selvom det er ret kompakt - sammenlignet med flere ækvivalente Ifudsagn - har greninstruktionerne stadig en vis redundans, da grenopkoden og tilstandskodemasken gentages sammen med grenforskydningerne. Kontroltabeller, der kun indeholder forskydninger til programetiketterne, kan konstrueres til at overvinde denne redundans (i det mindste på samlingssprog) og alligevel kun kræve mindre udførelsestid overhead sammenlignet med en konventionel filialtabel.

Multidimensionelle tabeller

Mere almindeligt kan en kontroltabel betragtes som en sandhedstabel eller som en eksekverbar ("binær") implementering af en trykt beslutningstabel (eller et træ med beslutningstabeller på flere niveauer). De indeholder (ofte underforståede) forslag sammen med en eller flere tilknyttede 'handlinger'. Disse handlinger udføres normalt af generiske eller specialbyggede underrutiner , der kaldes af et " tolkeprogram ". Tolken fungerer i dette tilfælde effektivt som en virtuel maskine , der 'udfører' kontroltabelindgange og dermed giver et højere abstraktionsniveau end den underliggende kode for tolken.

En kontroltabel kan konstrueres efter lignende linjer som en sprogafhængig switch-sætning, men med den ekstra mulighed for at teste for kombinationer af inputværdier (ved hjælp af boolsk stil OG / ELLER betingelser) og potentielt kalde flere subrutiner (i stedet for kun et enkelt sæt værdier og 'filial til' programetiketter). (Switch-sætningskonstruktionen er under alle omstændigheder muligvis ikke tilgængelig eller har forvirrende forskellige implementeringer på sprog på højt niveau ( HLL ). Kontroltabelkonceptet har til sammenligning ingen iboende sprogafhængigheder, men kan alligevel implementeres forskelligt i henhold til den tilgængelige datadefinitionsfunktioner for det valgte programmeringssprog.)

Tabelindhold

En kontroltabel inkorporerer i det væsentlige ' essensen ' af et konventionelt program, fjernet fra dets programmeringssprogssyntaks og platformafhængige komponenter (f.eks. HVIS / DAN GØR .., FOR .., DO WHILE .., SWITCH, GOTO, CALL) og ' kondenseret 'til dets variabler (f.eks. input1), værdier (f.eks.' A ',' S ',' M 'og' D ') og subrutine-identiteter (f.eks.' Tilføj ',' træk, .. 'eller # 1, # 2, ..). Selve tabellens struktur indebærer typisk de involverede (standard) logiske operationer - såsom 'test for lighed', udførelse af en underrutine og 'næste operation' eller efter standardsekvensen (snarere end at disse udtrykkeligt angives i programudtalelser - efter behov i andre programmeringsparadigmer ).

En flerdimensionel kontroltabel vil normalt som minimum indeholde værdi / handlingspar og kan desuden indeholde operatører og typeoplysninger såsom placering, størrelse og format for input- eller outputdata, hvad enten datakonvertering (eller anden kørselstid) behandlingsnuancer) kræves før eller efter behandling (hvis ikke allerede implicit i selve funktionen). Tabellen kan muligvis ikke indeholde indekser eller relative eller absolutte henvisninger til generiske eller tilpassede primitiver eller underrutiner, der skal udføres afhængigt af andre værdier i "rækken".

Tabellen illustreret nedenfor gælder kun for 'input1', da der ikke er angivet nogen specifik input i tabellen.

betingelser og handlinger underforstået af struktur

(underforstået) HVIS =	(underforstået) udføre
værdi	handling
værdi	handling

(Denne side-ved-side-parring af værdi og handling har ligheder med konstruktioner i begivenhedsdrevet programmering , nemlig 'hændelsesregistrering' og 'hændelseshåndtering' men uden (nødvendigvis) selve begivenhedens asynkrone natur)

De mange forskellige værdier, der kan kodes i en kontroltabel, afhænger stort set af det anvendte computersprog . Samlingssprog giver det bredeste anvendelsesområde for datatyper inklusive (for handlingerne), muligheden for direkte eksekverbar maskinkode . Typisk vil en kontroltabel indeholde værdier for hver mulig matchende inputklasse sammen med en tilsvarende markør til en handlingsundervisning. Nogle sprog hævder ikke at understøtte pegepinde (direkte), men alligevel kan de i stedet understøtte et indeks, der kan bruges til at repræsentere et 'relativt subrutinetal' til at udføre betinget udførelse, styret af værdien i tabelindgangen (f.eks. Til brug i et optimeret SWITCH erklæring - designet med nul huller (dvs. en flervejsfilial )).

Kommentarer placeret over hver kolonne (eller endog indlejret tekstdokumentation) kan gøre en beslutningstabel 'menneskelig læsbar' selv efter 'kondensering' (kodning) til dets væsentlige (og stadig stort set i tråd med den originale programspecifikation - især hvis en trykt beslutningstabel, der tæller hver unikke handling, oprettes inden kodningen begynder). Tabelindgangene kan også valgfrit indeholde tællere til indsamling af kørselsstatistikker til 'in-flight' eller senere optimering

Tabelplacering

Styretabeller kan opholde sig i statisk opbevaring, på hjælpelageret , såsom en flad fil eller på en database eller kan alternativt være delvist eller helt bygget dynamisk på programmet initialisering tid fra parametre (der selv kan opholde sig i en tabel). For optimal effektivitet skal bordet være i hukommelsen, når tolk begynder at bruge det.

Tolken og subrutiner

Tolken kan skrives på et hvilket som helst egnet programmeringssprog inklusive et sprog på højt niveau . En passende designet generisk tolk sammen med et velvalgt sæt generiske subrutiner (i stand til at behandle de mest almindeligt forekommende primitiver ) vil kun kræve yderligere konventionel kodning for nye brugerdefinerede subrutiner (ud over at specificere selve kontroltabellen). Tolken kan eventuelt kun gælde for nogle veldefinerede sektioner i et komplet applikationsprogram (såsom hovedkontrolsløjfen ) og ikke andre, 'mindre betingede' sektioner (såsom programinitialisering, afslutning og så videre).

Tolken behøver ikke at være unødigt kompleks eller produceret af en programmør med avanceret viden fra en kompilatorforfatter og kan skrives ligesom ethvert andet applikationsprogram - bortset fra at det normalt er designet med effektivitet i tankerne. Dens primære funktion er at "udføre" tabelindgangene som et sæt "instruktioner". Der behøves ikke noget krav til parsing af kontroltabelposter, og disse skal derfor så vidt muligt være designet til at være 'eksekveringsklar', hvilket kun kræver "tilslutning" af variabler fra de relevante kolonner til den allerede kompilerede generiske kode for tolken. De instruktioner programmet er, i teorien, uendeligt Extensible og udgør (muligvis vilkårlige) værdier i tabellen, som giver mening kun at tolken. Tolkenes kontrolflow er normalt ved sekventiel behandling af hver tabelrække, men kan ændres ved specifikke handlinger i tabelindgangene.

Disse vilkårlige værdier kan således designes med tanke på effektivitet - ved at vælge værdier, der kan bruges som direkte indekser til data eller funktionsmarkører . For bestemte platforme / sprog kan de være specielt designet til at minimere instruktionssti-længder ved hjælp af grentabelværdier eller endda, i nogle tilfælde, såsom i JIT- kompilatorer, bestå af direkte eksekverbare maskinkode " uddrag " (eller henvisninger til dem).

Underrutinerne kan være kodet enten på det samme sprog som selve tolken eller ethvert andet understøttet programsprog (forudsat at der findes egnede inter-sproglige 'Call' koblingsmekanismer). Valget af sprog for tolk og / eller subrutiner afhænger normalt af, hvor bærbart det skal være på tværs af forskellige platforme . Der kan være flere versioner af tolken for at forbedre bærbarheden af en kontroltabel. En underordnet kontroltabelmarkør kan eventuelt erstatte en underrutinemarkør i kolonnerne 'handling', hvis tolken understøtter denne konstruktion, der repræsenterer en betinget 'drop' til et lavere logisk niveau, der efterligner en konventionel struktureret programstruktur .

Ydelsesovervejelser

Ved første øjekast ser det ud til, at brugen af ​​kontroltabeller tilføjer en hel del til et programs overhead , hvilket som det kræver en tolkeproces, før de 'native' programmeringssprogsætninger udføres. Dette er dog ikke altid tilfældet. Ved at adskille (eller 'indkapsle') den eksekverbare kodning fra logikken, som udtrykt i tabellen, kan det lettere målrettes mod at udføre sin funktion mest effektivt. Dette kan opleves mest tydeligt i et regnearksapplikation - hvor den underliggende regnearkssoftware konverterer komplekse logiske 'formler' på den mest effektive måde, den er i stand til, for at vise resultaterne.

Eksemplerne nedenfor er valgt dels for at illustrere potentielle præstationsgevinster, der måske ikke kun kompenserer væsentligt for det ekstra abstraktionsniveau, men også forbedrer - hvad ellers kunne have været - mindre effektiv, mindre vedligeholdelig og længerevarende kode. Selvom de givne eksempler er for et 'lavt niveau' forsamlingssprog og for C-sproget , kan det ses i begge tilfælde, at der kræves meget få linier med kode for at implementere kontroltabellen og alligevel kan opnå meget betydelig konstant tid forbedring af ydeevnen, reducerer gentagen kildekodning og hjælper med klarhed sammenlignet med detaljerede konventionelle programsprogkonstruktioner. Se også citaterne fra Donald Knuth vedrørende tabeller og effektiviteten af flervejsforgrening i denne artikel.

Eksempler på kontroltabeller

De følgende eksempler er vilkårlige (og er baseret på kun et enkelt input for enkelhedens skyld), men hensigten er blot at demonstrere, hvordan kontrolflow kan udføres ved hjælp af tabeller i stedet for regelmæssige programerklæringer. Det skal være klart, at denne teknik let kan udvides til at håndtere flere input, enten ved at øge antallet af kolonner eller bruge flere tabelindgange (med valgfri og / eller operator). På samme måde kan struktureret programmering udføres ved hjælp af (hierarkiske) 'sammenkædede' kontroltabeller (valgfrit ved hjælp af indrykning til at fremhæve underordnede kontroltabeller).

"CT1" er et eksempel på en kontroltabel, der er en simpel opslagstabel . Den første kolonne repræsenterer den inputværdi, der skal testes (ved en stiltiende 'IF input1 = x'), og hvis SAND, den tilsvarende 2. kolonne ('handlingen') indeholder en underrutine adresse, der skal udføres ved et opkald (eller spring til - svarende til et SWITCH- udsagn). Det er faktisk en flervejsfilial med retur (en form for " dynamisk forsendelse "). Den sidste post er standardtilfældet, hvor der ikke findes noget match.

CT1

indgang 1	markør
EN	-> Tilføj
S	-> Træk
M	-> Multiplicer
D	- Opdel
?	-> Standard

For programmeringssprog, der understøtter markører inden for datastrukturer sammen med andre dataværdier, kan ovenstående tabel (CT1) bruges til at styre kontrolflow til en passende underrutiner i henhold til matchende værdi fra tabellen (uden en kolonne for at indikere andet, antages lighed i denne enkle sag).

Eksempel på monteringssprog til IBM / 360 (maksimalt 16Mb adresseområde) eller Z / arkitektur

Der gøres ikke noget forsøg på at optimere opslaget i kodning til dette første eksempel, og det bruger i stedet en simpel lineær søgeteknik - rent for at illustrere konceptet og demonstrere færre kildelinjer. For at håndtere alle 256 forskellige inputværdier ville der kræves cirka 265 linjer med kildekode (hovedsageligt enkeltlinjetabelindgange), mens flere 'sammenligne og forgrene' normalt ville have krævet omkring 512 kildelinjer (størrelsen af binæret er også ca. hver tabelpost kræver kun 4 byte i stedet for ca. 8 byte for en række 'sammenligne øjeblikkelige' / greninstruktioner (For større inputvariabler er besparelsen endnu større).

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

forbedring af tolkens ydeevne i ovenstående eksempel

For at foretage et valg i eksemplet ovenfor er den gennemsnitlige instruktionssti-længde (eksklusive underrutinkoden) '4n / 2 +3', men kan let reduceres, hvor n = 1 til 64, til en konstant tid med en kurllængde af '5' med nul sammenligninger , hvis en 256 byte-oversættelsestabel først anvendes til at skabe et direkte indeks til CT1 ud fra de rå EBCDIC-data. Hvor n = 6, svarer dette til kun 3 sekventielle sammenlignings- og forgreningsinstruktioner. Imidlertid, hvor n <= 64, ville det i gennemsnit have brug for ca. 13 gange færre instruktioner end at bruge flere sammenligninger. Hvor n = 1 til 256, i gennemsnit ville det bruge cirka 42 gange færre instruktioner - da det i dette tilfælde ville være nødvendigt med en yderligere instruktion (for at multiplicere indekset med 4).${\ displaystyle O (1) \,}$

Forbedret tolk (op til 26 gange færre udførte instruktioner end det ovenstående eksempel i gennemsnit, hvor n = 1 til 64 og op til 13 gange mindre, end der ville være brug for ved brug af flere sammenligninger).

For at håndtere 64 forskellige inputværdier kræves cirka 85 linjer med kildekode (eller mindre) (hovedsageligt enkeltlinjetabelindgange), mens flere 'sammenligne og forgrene' ville kræve omkring 128 linjer (størrelsen af binæret er også næsten halveret - på trods af den yderligere 256 byte-tabel, der kræves for at udtrække 2. indeks).

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

Yderligere forbedret tolk (op til 21 gange mindre udførte instruktioner (hvor n> = 64) end det første eksempel i gennemsnit og op til 42 gange mindre, end der ville være brug for ved brug af flere sammenligninger).

For at håndtere 256 forskellige inputværdier, cirka 280 linjer med kildekode eller mindre, ville være påkrævet (hovedsageligt enkeltlinjetabelindgange), mens flere 'sammenligne og forgrene' ville kræve omkring 512 linjer (størrelsen af binæren er også næsten halveret en gang mere).

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

C-sprog eksempel Dette eksempel i C benytter to tabeller, hvoraf den første (CT1) er en simpel lineær søge endimensional opslagstabel - at opnå et indeks ved at matche input (x), og den anden, tilhørende tabel (CT1p), er en tabel med adresser på etiketter, du kan springe til.

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

Dette kan gøres mere effektivt, hvis en 256 byte-tabel bruges til at oversætte den rå ASCII-værdi (x) direkte til en tæt sekventiel indeksværdi til brug til direkte lokalisering af grenadressen fra CT1p (dvs. " indeksmapping " med en byte-bred array). Det vil derefter udføre i konstant tid for alle mulige værdier af x (Hvis CT1p indeholdt navnene på funktioner i stedet for etiketter, kunne springet erstattes med et dynamisk funktionsopkald, hvilket eliminerer den switch-lignende goto - men reducerer ydeevnen med de ekstra omkostninger af funktion husholdning ).

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

Det næste eksempel nedenfor illustrerer, hvordan en lignende effekt kan opnås på sprog, der ikke understøtter markørdefinitioner i datastrukturer, men som understøtter indekseret forgrening til en subrutine - indeholdt i en ( 0-baseret ) række subrutinemarkører. Tabellen (CT2) bruges til at udtrække indekset (fra 2. kolonne) til markørarrayet (CT2P). Hvis markørarrays ikke understøttes, kan en SWITCH-sætning eller tilsvarende bruges til at ændre kontrolflowet til en af ​​en række af programetiketter (f.eks .: case0, case1, case2, case3, case4), som derefter enten behandler input direkte, eller ellers foretager du et opkald (med tilbagevenden) til den relevante subrutine (standard, Add, Subtract, Multiply or Divide, ..) for at håndtere det.

CT2

indgang 1	subr #
EN	1
S	2
M	3
D	4
?	0

Som i eksemplerne ovenfor er det muligt at meget effektivt oversætte de potentielle ASCII- inputværdier (A, S, M, D eller ukendt) til et pointer array-indeks uden faktisk at bruge et tabelopslag, men vises her som en tabel for sammenhæng med det første eksempel.

CT2P- pointerarray

pointer array
-> standard
-> Tilføj
-> Træk
-> Multiplicer
- Opdel
->? andet

Multidimensionelle kontroltabeller kan konstrueres (dvs. tilpasses), der kan være 'mere komplekse' end ovenstående eksempler, der kan teste for flere betingelser på flere indgange eller udføre mere end en 'handling' baseret på nogle matchende kriterier. En 'handling' kan omfatte en markør til en anden underordnet kontroltabel. Det enkle eksempel nedenfor har haft en implicit 'ELLER'-tilstand inkorporeret som en ekstra kolonne (for at håndtere små bogstaver, men i dette tilfælde kunne dette ligeledes have været håndteret ved blot at have en ekstra post for hvert af de små bogstaver, der specificerer samme underrutine-id som store bogstaver). En ekstra kolonne til at tælle de aktuelle kørselstidsbegivenheder for hver input, når de forekommer, er også inkluderet.

CT3

indgang 1	skifte	subr #	tælle
EN	-en	1	0
S	s	2	0
M	m	3	0
D	d	4	0
?	?	0	0

Kontroltabelposterne ligner så meget mere betingede udsagn på proceduremæssige sprog, men afgørende uden, at de faktiske (sprogafhængige) betingede udsagn (dvs. instruktioner) er til stede (den generiske kode er fysisk i tolken, der behandler tabelindgange, ikke i selve tabellen - som simpelthen inkorporerer programlogikken via dens struktur og værdier).

I tabeller som disse, hvor en serie af lignende tabelindgange definerer hele logikken, kan et tabelindgangsnummer eller -markør effektivt tage plads til en programtæller i mere konventionelle programmer og kan nulstilles i en 'handling', også specificeret i tabelindgangen. Eksemplet nedenfor (CT4) viser, hvordan udvidelse af den tidligere tabel til at omfatte en 'næste' post (og / eller med en 'ændre flow' ( spring ) subrutine) kan skabe en loop (Dette eksempel er faktisk ikke den mest effektive måde at konstruer en sådan kontroltabel, men ved at demonstrere en gradvis 'udvikling' fra de første eksempler ovenfor viser, hvordan yderligere kolonner kan bruges til at ændre adfærd.) Den femte kolonne viser, at mere end en handling kan startes med en enkelt tabelindgang - i dette tilfælde en handling, der skal udføres efter den normale behandling af hver post ('-' værdier betyder 'ingen betingelser' eller 'ingen handling').

Struktureret programmering eller "Goto-less" kode (der indeholder ækvivalent med ' DO WHILE ' eller ' for loop ' -konstruktioner) kan også rummes med passende designet og 'indrykket' kontrolbordstrukturer.

CT4 (et komplet 'program' til at læse input1 og proces, gentages indtil 'E' er stødt)

indgang 1	skifte	subr #	tælle	hoppe
-	-	5	0	-
E	e	7	0	-
EN	-en	1	0	-
S	s	2	0	-
M	m	3	0	-
D	d	4	0	-
?	?	0	0	-
-	-	6	0	1

CT4P- pointerarray

pointer array
-> Standard
-> Tilføj
-> Træk
-> Multiplicer
- Opdel
-> Læs input1
-> Ændr flow
-> Afslut

Tabelbaseret vurdering

Inden for specialområdet inden for klassificering af telekommunikation (beskæftiger sig med at bestemme omkostningerne ved et bestemt opkald) illustrerer borddrevne klassificeringsteknikker brugen af ​​kontroltabeller i applikationer, hvor reglerne ofte kan ændre sig på grund af markedskræfter. Tabellerne, der bestemmer gebyrerne, kan i mange tilfælde ændres med kort varsel af ikke-programmører.

Hvis algoritmerne ikke er indbygget i tolken (og derfor kræver yderligere fortolkning af runtime af et udtryk, der er indeholdt i tabellen), er det kendt som "Regelbaseret vurdering" snarere end borddrevet vurdering (og bruger derfor betydeligt mere overhead ).

Regneark

Et regnearkdatablad kan betragtes som en todimensional kontroltabel, hvor de ikke tomme celler repræsenterer data til det underliggende regnearksprogram (tolken). Cellerne, der indeholder formlen, er normalt præfikset med et ligetegn og betegner simpelthen en speciel type dataindgang, der dikterer behandlingen af ​​andre refererede celler - ved at ændre kontrolflowet i tolken. Det er eksternaliseringen af ​​formler fra den underliggende tolk, der tydeligt identificerer begge regneark, og det ovennævnte citerede "regelbaserede klassificering" -eksempel som let identificerbare tilfælde af brug af kontroltabeller af ikke-programmører.

Programmeringsparadigme

Hvis man kunne sige, at kontroltableteknikken tilhører et bestemt programmeringsparadigme , kan den nærmeste analogi være Automatabaseret programmering eller "reflekterende" (en form for metaprogrammering - da tabelindgangene kan siges at 'ændre' opførelsen af tolk). Tolken selv og underrutinerne kan dog programmeres ved hjælp af et hvilket som helst af de tilgængelige paradigmer eller endda en blanding. Selve tabellen kan i det væsentlige være en samling af " rådata " -værdier, der ikke engang behøver at blive kompileret og kunne læses ind fra en ekstern kilde (undtagen i specifikke, platformafhængige implementeringer, der bruger hukommelsespegere direkte for større effektivitet).

Analogi til bytecode / instruktionssæt til virtuel maskine

En flerdimensionel kontroltabel har nogle konceptuelle ligheder med bytecode, der fungerer på en virtuel maskine , idet et platformafhængigt "fortolker" -program normalt kræves for at udføre den faktiske udførelse (det bestemmes stort set betinget af tabellenes indhold). Der er også nogle begrebsmæssige ligheder med det nylige Common Intermediate Language (CIL) med det formål at skabe et fælles mellemliggende 'instruktionssæt', der er uafhængigt af platformen (men i modsætning til CIL er der ingen pretentioner, der skal bruges som en fælles ressource for andre sprog) . P-kode kan også betragtes som en lignende, men tidligere implementering med oprindelse så langt tilbage som i 1966.

Hentning af instruktion

Når en flerdimensionel kontroltabel bruges til at bestemme programflow, simuleres den normale "hardware" Programtæller- funktion effektivt med enten en markør til den første (eller næste) tabelindgang eller ellers et indeks til den. "Henter" instruktionen involverer afkodning af dataene i den pågældende tabelindgang - uden nødvendigvis at kopiere alle eller nogle af dataene inden for indgangen først. Programmeringssprog, der er i stand til at bruge pegepinde, har den dobbelte fordel, at der er mindre omkostninger involveret, både ved at få adgang til indholdet og også fremme tælleren for at pege på næste tabelindgang efter udførelse. Beregning af den næste 'instruktions'-adresse (dvs. tabelindtastning) kan endda udføres som en valgfri yderligere handling for hver enkelt tabelindgang, der tillader sløjfer og / eller springinstruktioner på ethvert trin.

Overvågning af udførelse af kontroltabellen

Tolkeprogrammet kan valgfrit gemme programtælleren (og andre relevante detaljer afhængigt af instruktionstypen) på hvert trin for at registrere et helt eller delvist spor af den aktuelle programflow til fejlfindingsformål , hotspot- detektion, kodedækningsanalyse og ydeevne-analyse (se eksempler CT3 & CT4 ovenfor).

Fordele

• klarhed - Informationstabeller er allestedsnærværende og for det meste i sig selv forstået af offentligheden (især fejldiagnosticeringstabeller i produktguider )
• bærbarhed - kan designes til at være 100% sproguafhængig (og platformuafhængig - bortset fra tolk)
• fleksibilitet - evne til at udføre enten primitiver eller subrutiner transparent og være specialdesignet, så det passer til problemet
• kompakthed - tabel viser normalt betingelse / handling parring side om side (uden de sædvanlige platform / sprog implementeringsafhængigheder), hvilket ofte også resulterer i
  • binær fil - reduceret i størrelse gennem mindre dobbeltarbejde
  • kildefil - reduceret i størrelse gennem eliminering af flere betingede udsagn
  • forbedrede programbelastningshastigheder (eller download)
• vedligeholdelsesevne - tabeller reducerer ofte antallet af kildelinjer, der er nødvendige for at blive opretholdt v. flere sammenligninger
• reference-lokalitet - kompakte tabeller strukturer resulterer i tabeller tilbage i cachen
• genbrug af kode - "tolk" kan normalt genbruges. Ofte kan den let tilpasses til nye programmeringsopgaver ved hjælp af nøjagtig den samme teknik og kan vokse 'organisk' og i virkeligheden blive et standardbibliotek af afprøvede og testede underrutiner , der styres af tabeldefinitionerne.
• effektivitet - systemomspændende optimering mulig. Enhver ydeevne forbedring af tolken forbedrer normalt alle applikationer, der bruger den (se eksempler i 'CT1' ovenfor).
• udvidelig - nye 'instruktioner' kan tilføjes - simpelthen ved at udvide tolken
• tolk kan skrives som et ansøgningsprogram

Valgfrit: -

• tolken kan være indadvendt og "selv optimere " ved hjælp runtime målinger indsamlet inden selve tabellen (se CT3 og CT4 - med poster, der kunne periodisk Weaver faldende count). Tolken kan også valgfrit vælge den mest effektive opslagsteknik dynamisk blandt metrics indsamlet ved kørselstid (f.eks. Størrelse af array, værdiområde, sorteret eller usorteret)
• dynamisk forsendelse - almindelige funktioner kan forudindlæses, og mindre almindelige funktioner hentes kun ved første møde for at reducere hukommelsesforbruget . Memoization i tabellen kan bruges til at opnå dette.
• Tolken kan have indbyggede fejlfindings-, sporings- og overvågningsfunktioner - som derefter kan tændes eller slukkes efter ønske i henhold til test- eller 'live' -tilstand
• kontroltabeller kan bygges 'on-the-fly' (i henhold til nogle brugerindtastninger eller fra parametre) og derefter udføres af tolk (uden bogstavelig talt bygningskode).

Ulemper

• uddannelseskrav - applikationsprogrammerere er normalt ikke uddannet til at producere generiske løsninger

Følgende gælder hovedsageligt for deres anvendelse i flerdimensionelle tabeller, ikke de endimensionelle tabeller, der er diskuteret tidligere.

• overhead - nogle stiger på grund af ekstra grad af indirektion forårsaget af virtuelle instruktioner, der skal 'fortolkes' (dette kan dog normalt mere end opvejes af en veldesignet generisk tolk, der drager fuld fordel af effektiv direkte oversættelse, søgning og betinget testteknik, der kan ikke ellers er blevet brugt)
• Komplekse udtryk kan ikke altid bruges direkte i datatabelposter til sammenligningsformål

(disse 'mellemliggende værdier' ​​kan dog beregnes på forhånd i stedet for i en subrutine og deres værdier henvist til i de betingede tabelindgange. Alternativt kan en subrutine udføre den komplette komplekse betingede test (som en ubetinget 'handling') og ved at indstille en sandhedsflag som resultat, kan det derefter testes i næste tabelindgang. Se struktureret programteorem )

Citater

Flervejsforgrening er en vigtig programmeringsteknik, som alt for ofte erstattes af en ineffektiv rækkefølge af if-test. Peter Naur skrev for nylig, at han betragter brugen af ​​tabeller til at kontrollere programgennemstrømningen som en grundlæggende idé inden for datalogi, der næsten er glemt; men han forventer, at det vil være modent til genopdagelse enhver dag nu. Det er nøglen til effektivitet i alle de bedste kompilatorer, jeg har studeret.

-  Donald Knuth , struktureret programmering med gå til udsagn

Der er en anden måde at se på et program skrevet på et fortolkende sprog. Det kan betragtes som en række subrutineopkald, den ene efter den anden. Et sådant program kan faktisk udvides til en lang række opkald til subrutiner, og omvendt kan en sådan sekvens normalt pakkes i en kodet form, der let fortolkes. Fordelen ved fortolkningsteknikker er kompakt repræsentation, maskinuafhængighed og øget diagnostisk kapacitet. En tolk kan ofte skrives, så den tid, der er brugt på fortolkning af selve koden og forgrening til den passende rutine, er ubetydelig

-  Donald Knuth , The Art of Computer Programming Volume 1, 1997, side 202

Den nødvendige plads til at repræsentere et program kan ofte formindskes ved hjælp af tolke, hvor almindelige sekvenser af operationer er repræsenteret kompakt. Et typisk eksempel er brugen af ​​en finite-maskine til at kode en kompleks protokol eller et leksikalt format i en lille tabel

-  Jon Bentley , der skriver effektive programmer

Hoptabeller kan være særligt effektive, hvis rækkeviddetestene kan udelades. For eksempel, hvis kontrolværdien er en opregnet type (eller et tegn), kan den kun indeholde et lille fast værdiområde, og en områdetest er overflødig, forudsat at springtabellen er stor nok til at håndtere alle mulige værdier

-  David.A. SPULER, generering af kompilerkode til flervejsfilialer som et statisk søgningsproblem

Programmer skal skrives, så folk kan læse dem, og kun tilfældigt for maskiner, der skal udføres.

-  "Structure and Interpretation of Computer Programs", forord til den første udgave, Abelson & Sussman

Vis mig dit flowchart og skjul dine tabeller, så bliver jeg fortsat mystificeret. Vis mig dine tabeller, og jeg har normalt ikke brug for dit flowchart; det vil være indlysende.

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

Se også

• Automatabaseret programmering
• Databasecentreret arkitektur
• Datadrevet test
• Beslutningstabel
• Finite-state maskine
• Søgeordsdrevet test
• Markør (computerprogrammering)
• Skift sætning - flervejsforgrening til et af et antal programetiketter afhængigt af en enkelt inputvariabel
• Gevindkode
• Token threading

Bemærkninger

Referencer

• Beslutningstabelbaseret metode
• Struktureret programmering med go to Statements af Donald Knuth
• Generering af kompilerkode til flervejsfilialer som et statisk søgningsproblem 1I994 af David A. Spuler

eksterne links

• Switch-sætning i Windows PowerShell beskriver udvidelser til standard switch-sætning (giver nogle lignende funktioner til kontroltabeller)
• Kontroltabeleksempel på "C" -sprog ved hjælp af pekere, af Christopher Sawtell c1993, Institut for Computervidenskab, University of Auckland
• Borddrevet design af Wayne Cunneyworth fra DataKinetics
• Fra krav til tabeller til kode og test af George Brooke
• Nogle kommentarer til brugen af ​​tvetydige beslutningstabeller og deres konvertering til computerprogrammer af PJH King og RG Johnson, Univ. i London, London, Storbritannien
• Tvetydighed i PJH Kings tabeller med begrænset beslutning
• Konvertering af beslutningstabeller til computerprogrammer ved hjælp af regelmaske- teknikker af PJH King
• En Superoptimizer-analyse af generering af flerevejsfilialkodeafdeling, afsnit 3.9, side 16, indeksmapping
• Spring tabeller via funktionsmarkørarrays i C / C ++ Jones, Nigel. "Arrays af pointer til funktioner [3] " Integreret systemprogrammering, maj 1999.
• Sidevisningsstatistikker for denne artikel i december 2009

• Modelleringssoftware med finite state-maskiner - en praktisk tilgang
• Finite State Tables for General Computer Programming Applications januar 1988 af Mark Leininger
• MSDN: Triggerbaseret hændelsesbehandling
• Kontroltabel i c2.com