Tabela sterująca - Control table

Ta prosta tabela sterująca kieruje przebiegiem programu zgodnie z wartością pojedynczej zmiennej wejściowej. Każdy wpis w tabeli zawiera możliwą wartość wejściową do przetestowania pod kątem równości (domniemaną) oraz odpowiedni podprogram do wykonania w kolumnie akcji. Nazwę podprogramu można zastąpić względnym numerem podprogramu, jeśli wskaźniki nie są obsługiwane

Tabele sterujące to tabele, które kontrolują przepływ sterowania lub odgrywają główną rolę w sterowaniu programem. Nie ma sztywnych reguł dotyczących struktury lub zawartości tabeli sterującej — jej atrybutem kwalifikującym jest zdolność do kierowania przepływem sterowania w pewien sposób przez „wykonywanie” przez procesor lub interpreter . Projektowanie takich tabel jest czasami określane jako projektowanie oparte na tabelach (chociaż zwykle odnosi się to do automatycznego generowania kodu z tabel zewnętrznych, a nie bezpośrednich tabel czasu wykonywania). W niektórych przypadkach tabele sterujące mogą być specyficznymi implementacjami programowania opartego na automatach na maszynach skończonych . Jeśli istnieje kilka hierarchicznych poziomów tabeli sterującej, mogą one zachowywać się w sposób równoważny z automatami stanu UML

Tabele sterujące często zawierają osadzone w nich odpowiedniki wyrażeń warunkowych lub odwołań do funkcji , zwykle implikowanych przez ich względną pozycję kolumny na liście asocjacji . Tabele sterujące zmniejszają potrzebę ciągłego programowania podobnych struktur lub instrukcji programu. Dwuwymiarowy charakter większości tabel ułatwia ich przeglądanie i aktualizowanie niż jednowymiarowy charakter kodu programu. W niektórych przypadkach do obsługi tabel sterowania można przypisać osoby nie będące programistami.

Typowe użycie

Bardziej zaawansowane użycie

podobny do kodu bajtowego – ale zwykle z operacjami wynikającymi z samej struktury tabeli

Struktura tabeli

Tabele mogą mieć wiele wymiarów, o stałej lub zmiennej długości i zwykle można je przenosić między platformami komputerowymi , wymagając jedynie zmiany interpretera, a nie samego algorytmu – którego logika jest zasadniczo zawarta w strukturze i treści tabeli. Struktura tabeli może być podobna do MultiMap asocjacyjnej , w których wartości danych (lub kombinacja wartości danych), mogą być przypisane do jednego lub więcej, które mają być wykonywane.

Stoły jednowymiarowe

W prawdopodobnie najprostszej implementacji, tabela sterująca może czasami być tabelą jednowymiarową do bezpośredniego tłumaczenia surowych wartości danych na odpowiednie przesunięcie podprogramu , indeks lub wskaźnik przy użyciu surowej wartości danych bezpośrednio jako indeksu tablicy lub poprzez wykonanie trochę podstawowej arytmetyki na danych wcześniej. Można to osiągnąć w stałym czasie (bez wyszukiwania liniowego lub wyszukiwania binarnego przy użyciu typowej tabeli przeglądowej w tablicy asocjacyjnej ). W większości architektur można to osiągnąć za pomocą dwóch lub trzech instrukcji maszynowych – bez żadnych porównań czy pętli. Technika ta jest znana jako „ trywialna funkcja mieszająca ” lub, gdy jest używana specjalnie dla tabel rozgałęzień, „ podwójna wysyłka ”. Aby było to możliwe, zakres możliwych wartości danych musi być mały (np ASCII lub EBCDIC wartość znaków, które mają zasięg szesnastkowym „00” - „FF” Jeżeli rzeczywisty zakres jest. Gwarantowane być mniejszy poza tym tablica może zostać skrócona do mniej niż 256 bajtów).

Tabela do tłumaczenia nieprzetworzonych wartości ASCII (A,D,M,S) na nowy indeks podprogramu (1,4,3,2) w stałym czasie przy użyciu tablicy jednowymiarowej

(luki w zakresie są pokazane jako „..” w tym przykładzie, co oznacza „wszystkie wartości szesnastkowe do następnego wiersza”. Pierwsze dwie kolumny nie są częścią tablicy)

ASCII Klątwa Szyk
zero 00 00
... ... 00
@ 40 00
ZA 41 01
... ... 00
re 44 04
... ... 00
M 4D 03
... ... 00
S 53 02

W programowaniu opartym na automatach i przetwarzaniu transakcji pseudokonwersacyjnych , jeśli liczba odrębnych stanów programu jest niewielka, zmienna sterująca „gęstej sekwencji” może być użyta do skutecznego dyktowania całego przepływu głównej pętli programu.

Dwubajtowa wartość surowych danych wymagałaby minimalnego rozmiaru tabeli 65 536 bajtów – aby obsłużyć wszystkie możliwości wejściowe – przy jednoczesnym umożliwieniu tylko 256 różnych wartości wyjściowych. Jednak ta technika tłumaczenia bezpośredniego zapewnia niezwykle szybką walidację i konwersję na (względny) wskaźnik podprogramu, jeśli heurystyka wraz z wystarczającą pamięcią szybkiego dostępu pozwala na jego użycie.

Stoły oddziałowe

Tablica rozgałęzień jest jednowymiarową "tablicą" ciągłych instrukcji rozgałęzienia/skoku kodu maszynowego, które powodują rozgałęzienie wielokierunkowe do etykiety programu, gdy jest rozgałęzione przez bezpośrednio poprzedzającą i indeksowaną gałąź. Czasami jest generowany przez optymalizujący kompilator w celu wykonania instrukcji switch — pod warunkiem, że zakres wejściowy jest mały i gęsty, z kilkoma przerwami (jak utworzono w poprzednim przykładzie tablicy) [2] .

Chociaż dość zwarte – w porównaniu do wielu równoważnych Ifinstrukcji – instrukcje rozgałęzień nadal mają pewną nadmiarowość, ponieważ kod operacji rozgałęzienia i maska ​​kodu warunku są powtarzane wraz z przesunięciami rozgałęzień. Tabele sterujące zawierające tylko przesunięcia do etykiet programu mogą być skonstruowane w celu przezwyciężenia tej nadmiarowości (przynajmniej w językach asemblerowych) i wymagają jedynie niewielkiego narzutu czasu wykonania w porównaniu z konwencjonalną tablicą rozgałęzień.

Stoły wielowymiarowe

Częściej tablica sterująca może być traktowana jako tablica prawdy lub jako wykonywalna ("binarna") implementacja drukowanej tablicy decyzyjnej (lub drzewa tablic decyzyjnych na kilku poziomach). Zawierają (często dorozumiane) propozycje wraz z jednym lub kilkoma powiązanymi „działaniami”. Te akcje są zwykle wykonywane przez ogólne lub niestandardowe podprogramy, które są wywoływane przez program " interpretera ". Interpreter w tym przypadku skutecznie działa jako maszyna wirtualna , która „wykonuje” wpisy tabeli sterującej, a tym samym zapewnia wyższy poziom abstrakcji niż podstawowy kod interpretera.

Tabela sterująca może byćstworzona w podobny sposób jak instrukcja switch zależna od języka, ale z dodaną możliwością testowania kombinacji wartości wejściowych (przy użyciu warunków AND / OR w stylu logicznym ) i potencjalnie wywoływania wielu podprogramów (zamiast pojedynczego zestawu wartości oraz etykiety programu „odgałęzienie do”). (Konstrukcja instrukcji switch w każdym przypadku może nie być dostępna lub ma myląco różne implementacje w językach wysokiego poziomu ( HLL ). Dla porównania koncepcja tabeli sterującej nie ma wewnętrznych zależności językowych, ale mimo to może być zaimplementowana w różny sposób w zależności od dostępnych funkcje definicji danych wybranego języka programowania).

Zawartość tabeli

Tabela sterująca zasadniczo ucieleśnia „ istotę ” konwencjonalnego programu, pozbawioną składni języka programowania i komponentów zależnych od platformy (np. IF/THEN DO…, FOR…, DO WHILE…, SWITCH, GOTO, CALL) oraz „ skondensowane” do jego zmiennych (np. input1), wartości (np. „A”, „S”, „M” i „D”) oraz tożsamości podprogramów (np. „Dodaj”, „Odejmij,..” lub #1, # 2,..). Sama struktura tabeli zazwyczaj implikuje zaangażowane (domyślne) operacje logiczne – takie jak „testowanie pod kątem równości”, wykonywanie podprogramu i „następnej operacji” lub wykonywanie domyślnej sekwencji (zamiast wyraźnie określonych w instrukcjach programu – zgodnie z wymaganiami w innych paradygmatach programowania ).

Multi-wymiarowej tabeli sterowania normalnie jako minimum zawiera pary / wartość, i mogą zawierać dodatkowo operatorów i typu informacji, takich jak, położenie, wielkość i format danych wejściowych i wyjściowych, czy konwersji danych (lub innego wykonywalna przetwarzanie niuansów) jest wymagane przed lub po przetwarzaniu (jeśli nie jest już ukryte w samej funkcji). Tabela może zawierać lub nie zawierać wskaźniki lub względną lub bezwzględną wskazówek na ogólne lub dostosowane pierwotnych lub podprogramy być realizowane zależnie od innych wartości z „rzędzie”.

Poniższa tabela ma zastosowanie tylko do „wejścia1”, ponieważ nie określono w niej żadnego konkretnego wejścia.

warunki i działania wynikające ze struktury

(domniemane) JEŻELI = (domniemany) wykonać
wartość akcja
wartość akcja

(To równoległe połączenie wartości i działania ma podobieństwa do konstrukcji w programowaniu sterowanym zdarzeniami , a mianowicie „wykrywanie zdarzeń” i „obsługa zdarzeń”, ale bez (koniecznie) asynchronicznej natury samego zdarzenia)

Różnorodność wartości, które można zakodować w tabeli sterującej, w dużej mierze zależy od używanego języka komputerowego . Język asemblerowy zapewnia najszerszy zakres typów danych, w tym (dla akcji), opcję bezpośrednio wykonywalnego kodu maszynowego . Zazwyczaj tabela sterująca zawiera wartości dla każdej możliwej pasującej klasy danych wejściowych wraz z odpowiednim wskaźnikiem do podprogramu akcji. Niektóre języki twierdzą, że nie obsługują wskaźników (bezpośrednio), ale mimo to mogą zamiast tego obsługiwać indeks który może byćużyty do reprezentowania 'względnego numeru podprogramu' do wykonania warunkowego wykonania kontrolowanego przez wartośćwpisu w tabeli (np. do użycia w zoptymalizowanym SWITCH oświadczenie – zaprojektowane z zerowymi przerwami (tj. gałąź wielokierunkowa ) ).

Komentarze umieszczone nad każdą kolumną (lub nawet osadzoną dokumentacją tekstową) mogą sprawić, że tabela decyzyjna będzie „czytelna dla człowieka” nawet po „skondensowaniu” (zakodowaniu) do jej zasadniczych elementów (i nadal zasadniczo zgodnych z oryginalną specyfikacją programu – zwłaszcza jeśli wydrukowany stół decyzja, wyliczając każdą wyjątkową akcję, zostanie utworzony przed rozpoczęciem kodowania). Wpisy tabeli mogą również opcjonalnie zawierać liczniki do zbierania statystyk czasu wykonywania w celu optymalizacji „w locie” lub późniejszej

Lokalizacja stołu

Tabele sterujące mogą znajdować się w pamięci statycznej , w pamięci dyskowej , takiej jak płaski plik lub w bazie danych, lub alternatywnie mogą być częściowo lub całkowicie budowane dynamicznie w czasie inicjalizacji programu na podstawie parametrów (które same mogą znajdować się w tabeli). W celu uzyskania optymalnej wydajności, tabela powinna znajdować się w pamięci, gdy interpreter zaczyna z niej korzystać.

Tłumacz i podprogramy

Interpreter może być napisany w dowolnym odpowiednim języku programowania, w tym w języku wysokiego poziomu . Odpowiednio zaprojektowany generyczny interpreter, wraz z dobrze dobranym zestawem ogólnych podprogramów (zdolnych do przetwarzania najczęściej występujących prymitywów ), wymagałby dodatkowego konwencjonalnego kodowania tylko dla nowych niestandardowych podprogramów (oprócz określenia samej tabeli sterującej). Opcjonalnie interpreter może mieć zastosowanie tylko do niektórych dobrze zdefiniowanych sekcji pełnego programu użytkowego (takich jak główna pętla sterowania ), a nie do innych, „mniej warunkowych” sekcji (takich jak inicjalizacja programu, zakończenie itd.).

Interpreter nie musi być nadmiernie skomplikowany ani tworzony przez programistę z zaawansowaną wiedzą twórcy kompilatora i może być napisany tak jak każdy inny program użytkowy - poza tym, że jest zwykle projektowany z myślą o wydajności. Jego podstawową funkcją jest "wykonywanie" wpisów tabeli jako zestawu "instrukcji". Nie ma wymogu parsowania wpisów w tabeli sterującej i dlatego powinny one być zaprojektowane, o ile to możliwe, tak, aby były „gotowe do wykonania”, wymagając jedynie „podłączenia” zmiennych z odpowiednich kolumn do już skompilowanego kodu generycznego tłumacz. Te instrukcje programu są teoretycznie nieskończenie rozszerzalny i stanowią (ewentualnie) arbitralnych wartości w tabeli, które mają znaczenie tylko dla tłumacza. Sterowania przepływem interpretera jest zwykle przez kolejne przetwarzanie każdego wiersza tabeli, ale może być modyfikowany przez specyficzne działania w pozycji tabeli.

Te dowolne wartości można zatem zaprojektować z myślą o wydajności — wybierając wartości, które mogą być używane jako bezpośrednie indeksy do wskaźników danych lub funkcji . W przypadku określonych platform/ języków mogą one być specjalnie zaprojektowane tak, aby zminimalizować długość ścieżki instrukcji przy użyciu wartości tabeli rozgałęzień lub nawet, w niektórych przypadkach, takich jak kompilatory JIT , składać się z bezpośrednio wykonywalnych „ fragmentówkodu maszynowego (lub wskaźników do nich).

Podprogramy mogą być kodowane w tym samym języku co sam tłumacz lub w dowolnym innym obsługiwanym języku programu (pod warunkiem, że istnieją odpowiednie międzyjęzykowe mechanizmy połączeń „Call”). Wybór języka dla tłumacza i/lub podprogramów będzie zwykle zależał od tego, jak przenośny musi być na różnych platformach . Może istnieć kilka wersji interpretera w celu zwiększenia przenośności tabeli sterującej. Wskaźnik podrzędnej tabeli sterującej może opcjonalnie zastąpić wskaźnik podprogramu w kolumnach „akcja”, jeśli interpreter obsługuje tę konstrukcję, reprezentującą warunkowe „zejście” na niższy poziom logiczny, naśladując konwencjonalną strukturę programu strukturalnego.

Rozważania dotyczące wydajności

Na pierwszy rzut oka wydaje się, że użycie tabel sterujących znacznie zwiększa obciążenie programu , wymagając, jak to się dzieje, procesu interpretera przed wykonaniem instrukcji „natywnego” języka programowania. Jednak nie zawsze tak jest. Dzięki oddzieleniu (lub „zahermetyzowaniu”) kodu wykonywalnego od logiki, jak wyrażono w tabeli, można go łatwiej ukierunkować na najefektywniejsze wykonywanie swojej funkcji. Najwyraźniej można tego doświadczyć w aplikacji arkusza kalkulacyjnego – gdzie oprogramowanie arkusza kalkulacyjnego w przejrzysty sposób przekształca złożone logiczne „wzory” w najbardziej efektywny sposób, aby wyświetlić wyniki.

Poniższe przykłady zostały wybrane częściowo, aby zilustrować potencjalny wzrost wydajności, który może nie tylko znacząco zrekompensować dodatkowy poziom abstrakcji, ale także ulepszyć – co w przeciwnym razie mogłoby być – mniej wydajny, mniej konserwowalny i dłuższy kod. Chociaż podane przykłady dotyczą języka asemblerowego "niskiego poziomu" i języka C , można zauważyć, w obu przypadkach, że bardzo niewiele wierszy kodu jest wymaganych do zaimplementowania podejścia z tabelą sterującą, a jednak może osiągnąć bardzo znaczący stały czas poprawa wydajności, zmniejszenie powtarzające źródło kodowania i przejrzystość pomocy, w porównaniu z gadatliwy konwencjonalnymi konstrukcjami językowymi programu. Zobacz także cytaty , których autorem jest Donald Knuth , dotyczące tabel i efektywności wieloosobowej rozgałęzienia w tym artykule.

Przykłady tabel kontrolnych

Poniższe przykłady są arbitralne (i dla uproszczenia opierają się tylko na pojedynczym wejściu), jednak intencją jest jedynie pokazanie, w jaki sposób można uzyskać przepływ sterowania za pomocą tabel zamiast zwykłych instrukcji programu. Powinno być jasne, że technikę tę można łatwo rozszerzyć, aby obsłużyć wiele danych wejściowych, zwiększając liczbę kolumn lub wykorzystując wiele wpisów w tabeli (z opcjonalnymi i/lub operatorami). Podobnie, używając (hierarchicznych) „połączonych” tabel sterujących, można zrealizować programowanie strukturalne (opcjonalnie używając wcięć, aby pomóc wyróżnić podrzędne tabele sterujące).

„CT1” to przykład tabeli sterującej, która jest prostą tabelą przeglądową . Pierwsza kolumna reprezentuje testowaną wartość wejściową (przez dorozumiany „IF input1 = x”), a jeśli TRUE, odpowiadająca jej druga kolumna („akcja”) zawiera adres podprogramu do wykonania przez wywołanie (lub przeskok do – podobne do instrukcji SWITCH ). Jest to w efekcie odgałęzienie wielokierunkowe ze zwrotem (forma „ dynamicznej wysyłki ”). Ostatni wpis jest przypadkiem domyślnym, w którym nie znaleziono dopasowania.

CT1

wejście 1 wskaźnik
ZA --> Dodaj
S --> Odejmij
M --> Pomnóż
re -->Podziel
? -->Domyślne

W przypadku języków programowania, które obsługują wskaźniki w strukturach danych wraz z innymi wartościami danych, powyższa tabela (CT1) może służyć do kierowania przepływu sterowania do odpowiednich podprogramów zgodnie z pasującą wartością z tabeli (bez kolumny, aby wskazać inaczej, zakłada się równość w ten prosty przypadek).

Przykład języka asemblera dla IBM/360 (maksymalny zakres adresów 16Mb) lub Z/Architecture

W tym pierwszym przykładzie nie podjęto żadnych prób optymalizacji wyszukiwania w kodowaniu, a zamiast tego zastosowano prostą technikę wyszukiwania liniowego – wyłącznie w celu zilustrowania koncepcji i zademonstrowania mniejszej liczby wierszy źródłowych. Aby obsłużyć wszystkie 256 różnych wartości wejściowych, wymagane byłoby około 265 wierszy kodu źródłowego (głównie jednowierszowe wpisy w tabeli), podczas gdy wielokrotne „porównanie i rozgałęzienie” wymagałoby zwykle około 512 wierszy źródłowych (rozmiar pliku binarnego jest również w przybliżeniu o połowę mniejszy , każdy wpis w tabeli wymaga tylko 4 bajtów zamiast około 8 bajtów dla serii instrukcji „porównaj natychmiast”/rozgałęzień (dla większych zmiennych wejściowych oszczędność jest jeszcze większa).

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

usprawnienie pracy tłumacza w powyższym przykładzie

Aby dokonać wyboru w powyższym przykładzie, średnia długość ścieżki instrukcji (z wyłączeniem kodu podprogramu) wynosi '4n/2 +3', ale można ją łatwo zredukować, gdzie n = 1 do 64, do stałego czasu o długości ścieżki '5' przy zerowych porównaniach , jeżeli 256-bajtowa tablica translacji jest najpierw wykorzystywana do utworzenia bezpośredniego indeksu do CT1 z nieprzetworzonych danych EBCDIC. Gdzie n = 6, byłoby to równoważne tylko 3 sekwencyjnym instrukcjom porównania i rozgałęzienia. Jednak gdy n<=64, średnio wymagałoby to około 13 razy mniej instrukcji niż przy użyciu wielokrotnych porównań. Gdy n=1 do 256, to zużyłoby średnio około 42 razy mniej instrukcji – gdyż w tym przypadku wymagana byłaby jedna dodatkowa instrukcja (aby pomnożyć indeks przez 4).

Ulepszony interpreter ( średnio do 26 razy mniej wykonywanych instrukcji niż w powyższym przykładzie, gdzie n=1 do 64 i do 13 razy mniej niż byłoby to potrzebne przy wielokrotnych porównaniach).

Aby obsłużyć 64 różne wartości wejściowe, potrzeba około 85 wierszy kodu źródłowego (lub mniej) (głównie jednowierszowe wpisy w tabeli), podczas gdy wielokrotne „porównanie i rozgałęzienie” wymagałoby około 128 wierszy (rozmiar pliku binarnego jest również prawie o połowę zmniejszony – pomimo dodatkowa tablica 256 bajtów wymagana do wyodrębnienia drugiego indeksu).

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

Dalszy ulepszony interpreter (do 21 razy mniej wykonywanych instrukcji (gdzie n>=64) niż średnio w pierwszym przykładzie i do 42 razy mniej niż byłoby to potrzebne przy użyciu wielokrotnych porównań).

Aby obsłużyć 256 różnych wartości wejściowych, wymagane byłoby około 280 wierszy kodu źródłowego lub mniej (głównie jednowierszowe wpisy w tabeli), podczas gdy wielokrotne „porównanie i rozgałęzienie” wymagałoby około 512 wierszy (rozmiar pliku binarnego jest również prawie o połowę mniejszy jeszcze).

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

Przykład języka C Ten przykład w C wykorzystuje dwie tabele, pierwsza (CT1) jest prostąjednowymiarową tabelą wyszukiwania liniowego – w celu uzyskania indeksu przez dopasowanie danych wejściowych (x), a druga, powiązana tabela (CT1p) jest tabela adresów etykiet, do których można przejść.

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

Może to byćbardziej wydajne, jeśli do translacji nieprzetworzonej wartości ASCII (x) bezpośrednio na gęstą sekwencyjną wartość indeksu do użycia w bezpośrednim lokalizowaniu adresu gałęzi z CT1p (tj. " mapowanie indeksu " z szerokością bajtów) jest używana tablica 256 bajtów szyk). Następnie będzie wykonywany w stałym czasie dla wszystkich możliwych wartości x (jeśli CT1p zawierał nazwy funkcji zamiast etykiet, skok mógłby zostać zastąpiony dynamicznym wywołaniem funkcji, eliminując podobne do przełącznika goto – ale zmniejszając wydajność przez dodatkowy koszt funkcji sprzątania ).

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

Następny przykład ilustruje sposób podobny efekt można osiągnąć w językach, które mają nie obsługują definicje wskaźnik w strukturach danych, ale zrobienia wsparcie indeksowanych rozgałęzienia do podprogramu - zawartych w ( 0 opartej ) tablicy wskaźników podprogramów. Tabela (CT2) służy do wyodrębnienia indeksu (z drugiej kolumny) do tablicy wskaźników (CT2P). Jeśli tablice wskaźników nie są obsługiwane, można użyć instrukcji SWITCH lub jej odpowiednika do zmiany przepływu sterowania na jedną z sekwencji etykiet programu (np.: case0, case1, case2, case3, case4), które następnie przetwarzają dane wejściowe bezpośrednio lub w przeciwnym razie wykonaj wywołanie (z powrotem) do odpowiedniego podprogramu (domyślnie, Dodaj, Odejmij, Pomnóż lub Podziel,...), aby sobie z tym poradzić.

CT2

wejście 1 podrzędny #
ZA 1
S 2
M 3
re 4
? 0

Jak w powyższych przykładach, możliwe jest bardzo wydajne przetłumaczenie potencjalnych wartości wejściowych ASCII (A,S,M,D lub nieznane) na indeks tablicy wskaźników bez faktycznego używania wyszukiwania tabeli, ale jest pokazany tutaj jako tabela dla spójności z pierwszy przykład.

Tablica wskaźników CT2P
tablica wskaźników
--> domyślna
--> Dodaj
--> Odejmij
--> Pomnóż
-->Podziel
-->?inne

Można konstruować wielowymiarowe tabele kontrolne (tj. dostosowywać), które mogą być „bardziej złożone” niż powyższe przykłady, które mogą testować wiele warunków na wielu danych wejściowych lub wykonywać więcej niż jedno „działanie”, w oparciu o pewne kryteria dopasowania. „Akcja” może zawierać wskaźnik do innej podrzędnej tabeli sterującej. Poniższy prosty przykład zawiera niejawny warunek 'LUB' włączony jako dodatkową kolumnę (aby obsłużyć dane wejściowe małymi literami, jednak w tym przypadku można to równie dobrze obsłużyć przez dodanie dodatkowego wpisu dla każdego z małych znaków określających taki sam identyfikator podprogramu jak wielkie litery). Uwzględniono również dodatkową kolumnę do zliczania rzeczywistych zdarzeń w czasie wykonywania dla każdego wejścia w miarę ich występowania.

CT3

wejście 1 alternatywny podrzędny # liczyć
ZA za 1 0
S s 2 0
M m 3 0
re re 4 0
? ? 0 0

Wpisy w tabeli sterującej są wtedy znacznie bardziej podobne do instrukcji warunkowych w językach proceduralnych, ale, co najważniejsze, bez rzeczywistych (zależnych od języka) instrukcji warunkowych (tj. instrukcji) (kod ogólny znajduje się fizycznie w interpreterze przetwarzającym wpisy tabeli, a nie w samej tabeli – która po prostu ucieleśnia logikę programu poprzez swoją strukturę i wartości).

W tabelach takich jak te, w których szereg podobnych wpisów w tabeli definiuje całą logikę, numer wpisu tabeli lub wskaźnik może skutecznie zastąpić licznik programu w bardziej konwencjonalnych programach i może zostać zresetowany w ramach „działania”, również określonego w wpis tabeli. Poniższy przykład (CT4) pokazuje, jak rozszerzenie wcześniejszej tabeli w celu włączenia „następnego” wpisu (i / lub włączenia procedury „alter flow” ( skok )) może stworzyć pętlę (ten przykład nie jest w rzeczywistości najbardziej wydajnym sposobem skonstruować taką tabelę sterującą, ale demonstrując stopniową `` ewolucję '' z pierwszych przykładów powyżej, pokazuje, w jaki sposób można użyć dodatkowych kolumn do zmiany zachowania). Piąta kolumna pokazuje, że więcej niż jedno działanie może być zainicjowane jednym wpisem w tabeli w tym przypadku działanie, które ma zostać wykonane po normalnym przetworzeniu każdego wpisu (wartości „-” oznaczają „brak warunków” lub „brak działania”).

Strukturalne programowanie lub kod „bez przechodzenia” (zawierający odpowiednik konstrukcji „ DO WHILE ” lub „ for loop ”) może być również dostosowany do odpowiednio zaprojektowanych i „wciętych” struktur tablic sterujących.

CT4 (kompletny „program” do odczytu input1 i przetwarzania, powtarzany aż do napotkania „E”)

wejście 1 alternatywny podrzędny # liczyć skok
- - 5 0 -
mi mi 7 0 -
ZA za 1 0 -
S s 2 0 -
M m 3 0 -
re re 4 0 -
? ? 0 0 -
- - 6 0 1
Tablica wskaźników CT4P
tablica wskaźników
-->Domyślne
--> Dodaj
--> Odejmij
--> Pomnóż
-->Podziel
-->Odczytaj wejście1
-> Zmień przepływ
--> Koniec

Ocena oparta na tabeli

W specjalistycznej dziedzinie ratingu telekomunikacyjnego (związanego z określaniem kosztu konkretnego połączenia) techniki ratingowe oparte na tablicach ilustrują zastosowanie tablic kontrolnych w aplikacjach, w których reguły mogą się często zmieniać z powodu sił rynkowych. Tabele określające opłaty mogą w wielu przypadkach zostać szybko zmienione przez osoby nie będące programistami.

Jeśli algorytmy nie są wstępnie wbudowane w interpreter (i dlatego wymagają dodatkowej interpretacji wyrażenia przechowywanego w tabeli w czasie wykonywania), jest to określane jako „ocena oparta na regułach” zamiast oceny opartej na tabeli (i w konsekwencji zużywa znacznie więcej narzutów ).

Arkusze kalkulacyjne

Arkusz blachy dane mogą być traktowane jako dwuwymiarowej tabeli kontroli w związku z brakiem pustych komórek reprezentujących dane do arkusza kalkulacyjnego programu bazowego (interpreter). Komórki zawierające formułę są zwykle poprzedzone znakiem równości i po prostu wyznaczają specjalny typ danych wejściowych, który dyktuje przetwarzanie innych komórek, do których się odwołuje – poprzez zmianę przepływu sterowania w interpreterze. To właśnie eksternalizacja formuł z bazowego interpretera wyraźnie identyfikuje oba arkusze kalkulacyjne oraz cytowany powyżej przykład „oceny opartej na regułach” jako łatwe do zidentyfikowania przypadki użycia tabel kontrolnych przez nieprogramistów.

Paradygmat programowania

Jeśli można by powiedzieć, że technika tablic sterujących należy do dowolnego określonego paradygmatu programowania , najbliższą analogią może być programowanie oparte na automatach lub „refleksyjne” (forma metaprogramowania – ponieważ można powiedzieć, że wpisy w tabeli „modyfikują” zachowanie interpretator). Jednak sam interpreter i podprogramy mogą być zaprogramowane przy użyciu dowolnego z dostępnych paradygmatów lub nawet ich mieszanki. Sama tabela może być zasadniczo zbiorem wartości „ surowych danych ”, które nawet nie muszą być kompilowane i mogą być odczytywane z zewnętrznego źródła (z wyjątkiem konkretnych, zależnych od platformy implementacji wykorzystujących wskaźniki pamięci bezpośrednio dla większej wydajności).

Analogia do zestawu instrukcji kodu bajtowego / maszyny wirtualnej

Wielowymiarowa tabela sterująca ma pewne podobieństwa koncepcyjne do kodu bajtowego działającego na maszynie wirtualnej , ponieważ do wykonania rzeczywistego wykonania zwykle wymagany jest program „interpreter” zależny od platformy (jest to w dużej mierze warunkowe określone przez zawartość tabeli). Istnieją również pewne podobieństwa koncepcyjne do niedawnego Common Intermediate Language (CIL) w celu stworzenia wspólnego pośredniego „zestawu instrukcji”, który jest niezależny od platformy (ale w przeciwieństwie do CIL, nie ma pretensji do wykorzystania jako wspólne źródło dla innych języków) . Kod P można również uznać za podobną, ale wcześniejszą implementację, której początki sięgają 1966 roku.

Pobieranie instrukcji

Kiedy wielowymiarowa tablica sterująca jest używana do określenia przepływu programu, normalna "sprzętowa" funkcja licznika programów jest skutecznie symulowana albo ze wskaźnikiem do pierwszego (lub następnego) wpisu tablicy, albo z indeksem do niego. „Pobieranie” instrukcji obejmuje dekodowanie danych w tym wpisie tabeli – bez konieczności wcześniejszego kopiowania wszystkich lub niektórych danych we wpisie. Języki programowania, które są w stanie używać wskaźników, mają podwójną zaletę polegającą na mniejszym nakładzie pracy , zarówno w dostępie do zawartości, jak i przesunięciu licznika do następnego wpisu w tabeli po wykonaniu. Obliczenie następnego adresu „instrukcji” (tj. wpisu w tabeli) może być nawet wykonane jako opcjonalna dodatkowa akcja każdego pojedynczego wpisu w tabeli, umożliwiając wykonywanie pętli i/lub instrukcji skoku na dowolnym etapie.

Monitorowanie wykonania tabeli sterującej

Program interpretera może opcjonalnie zapisać licznik programu (i inne istotne szczegóły w zależności od typu instrukcji) na każdym etapie, aby zarejestrować pełny lub częściowy ślad rzeczywistego przepływu programu w celu debugowania , wykrywania gorących punktów , analizy pokrycia kodu i analizy wydajności (patrz przykłady CT3 i CT4 powyżej).

Zalety

  • przejrzystość – tabele informacyjnewszechobecne i w większości z natury zrozumiałe nawet przez ogół społeczeństwa (zwłaszcza tabele diagnostyki usterek w przewodnikach po produktach )
  • przenośność – może być zaprojektowana tak, aby była w 100% niezależna od języka (i platformy – z wyjątkiem tłumacza)
  • elastyczność – możliwość przejrzystego wykonywania prymitywów lub podprogramów i dostosowywania się do problemu the
  • zwartość – tabela zwykle pokazuje parowanie warunków/akcji obok siebie (bez typowych zależności implementacji platformy/języka), często również skutkujące
    • plik binarny – zmniejszony przez mniejsze powielanie instrukcji
    • plik źródłowy – zmniejszony rozmiar poprzez eliminację wielu instrukcji warunkowych
    • ulepszone prędkości ładowania (lub pobierania) programu
  • łatwość utrzymania – tabele często zmniejszają liczbę wierszy źródłowych potrzebnych do utrzymania w porównaniu z wielokrotnymi porównaniami
  • lokalizacja odniesienia – kompaktowe struktury tabel powodują, że tabele pozostają w pamięci podręcznej
  • ponowne wykorzystanie kodu – „interpreter” jest zwykle wielokrotnego użytku. Często można go łatwo dostosować do nowych zadań programistycznych przy użyciu dokładnie tej samej techniki i może się rozwijać „organicznie”, stając się w rezultacie standardową biblioteką wypróbowanych i przetestowanych podprogramów , kontrolowaną przez definicje tabel.
  • wydajność - możliwa optymalizacja w całym systemie. Każde zwiększenie wydajności interpretera zwykle poprawia wszystkie aplikacje, które go używają (patrz przykłady w „CT1” powyżej).
  • rozszerzalny – można dodawać nowe „instrukcje” – po prostu rozszerzając tłumacza
  • interpreter można napisać jak program użytkowy

Opcjonalnie:-

  • interpreter może być introspekcji i „self Optymalizacja ” przy użyciu środowiska wykonawczego dane zebrane w samej tabeli (patrz CT3 i CT4 - z zapisów, które mogą być okresowo posortowanych według malejącej liczby). Interpreter może również opcjonalnie wybrać najbardziej efektywną technikę wyszukiwania dynamicznie z metryk zebranych w czasie wykonywania (np. rozmiar tablicy, zakres wartości, posortowane lub nieposortowane)
  • dynamiczna wysyłka — typowe funkcje mogą być wstępnie ładowane, a mniej popularne funkcje pobierane tylko przy pierwszym kontakcie, aby zmniejszyć zużycie pamięci . W tym celu można zastosować zapamiętywanie w tabeli .
  • Interpreter może mieć wbudowane funkcje debugowania, śledzenia i monitorowania – które można następnie dowolnie włączać lub wyłączać w zależności od trybu testowego lub „na żywo”
  • tabele sterujące mogą być budowane w locie (na podstawie danych wprowadzonych przez użytkownika lub na podstawie parametrów), a następnie wykonywane przez interpretera (dosłownie bez kodu budowania).

Niedogodności

  • wymóg szkolenia – programiści aplikacji zwykle nie są szkoleni w zakresie tworzenia ogólnych rozwiązań

Poniższe informacje dotyczą głównie ich użycia w tabelach wielowymiarowych, a nie w omówionych wcześniej tabelach jednowymiarowych.

  • narzut – pewien wzrost ze względu na dodatkowy poziom niebezpośredniości spowodowany koniecznością „zinterpretowania” instrukcji wirtualnych (jednak zwykle może to zostać z nawiązką zrekompensowane przez dobrze zaprojektowany interpreter generyczny, w pełni wykorzystujący wydajne techniki bezpośredniego tłumaczenia, wyszukiwania i testowania warunkowego, które mogą inaczej nie zostały wykorzystane)
  • Złożone wyrażenia nie zawsze mogą być używane bezpośrednio we wpisach tabeli danych do celów porównawczych
(te „wartości pośrednie” można jednak obliczyć wcześniej w ramach podprogramu, a ich wartości są określone we wpisach w tabeli warunkowej. Alternatywnie, podprogram może wykonać pełny złożony test warunkowy (jako bezwarunkowe „działanie”) i ustawiając flagę prawdy jako wynik, można ją następnie przetestować w następnym wpisie w tabeli.Zobacz Twierdzenie o programie strukturalnym )

Cytaty

Rozgałęzienia wielowątkowe to ważna technika programowania, która zbyt często jest zastępowana nieefektywną sekwencją testów if. Peter Naur niedawno napisał do mnie, że uważa użycie tabel do sterowania przepływem programu za podstawową ideę informatyki, która została prawie zapomniana; ale spodziewa się, że lada dzień będzie dojrzała do ponownego odkrycia. Jest to klucz do wydajności we wszystkich najlepszych kompilatorach, jakie studiowałem.

—  Donald Knuth , Programowanie strukturalne z przejdź do Oświadczenia

Istnieje inny sposób spojrzenia na program napisany w języku interpretacyjnym. Można to traktować jako serię wywołań podprogramów, jeden po drugim. Taki program może w rzeczywistości zostać rozszerzony do długiej sekwencji wywołań podprogramów i odwrotnie, taka sekwencja może być zwykle spakowana do zakodowanej postaci, która jest łatwa do interpretacji. Zaletą technik interpretacyjnych jest zwartość reprezentacji, niezależność maszyny oraz zwiększona zdolność diagnostyczna. Interpreter często można napisać tak, że ilość czasu spędzonego na interpretacji samego kodu i rozgałęzieniu do odpowiedniej procedury jest znikoma

—  Donald Knuth , Sztuka programowania komputerowego, tom 1, 1997, strona 202

Przestrzeń wymagana do reprezentowania programu często może zostać zmniejszona przez użycie interpreterów, w których typowe sekwencje operacji są reprezentowane w sposób zwięzły. Typowym przykładem jest użycie maszyny skończonej do zakodowania złożonego protokołu lub formatu leksykalnego w małej tabeli

—  Jon Bentley , Pisanie wydajnych programów

Tabele skoków mogą być szczególnie skuteczne, jeśli można pominąć testy zasięgu. Na przykład, jeśli wartość kontrolna jest typem wyliczanym (lub znakiem), może zawierać tylko mały stały zakres wartości, a test zakresu jest zbędny pod warunkiem, że tabela skoków jest wystarczająco duża, aby obsłużyć wszystkie możliwe wartości

—  David.A. SPULER, generowanie kodu kompilatora dla instrukcji rozgałęzień wielokierunkowych jako problem wyszukiwania statycznego

Programy muszą być napisane, aby ludzie mogli je czytać, a jedynie przypadkowo, aby mogły się uruchamiać maszyny.

—  „Struktura i interpretacja programów komputerowych”, przedmowa do pierwszego wydania, Abelson & Sussman

Pokaż mi swój schemat blokowy i ukryj swoje stoły, a będę nadal zdumiony. Pokaż mi swoje tabele, a zwykle nie będę potrzebować twojego schematu; to będzie oczywiste.

—  „Mityczny człowiek-miesiąc: eseje o inżynierii oprogramowania”, Fred Brooks

Zobacz też

Uwagi

Bibliografia

Linki zewnętrzne