Control Table - Examples of Control Tables

Examples of Control Tables

The following examples are arbitrary (and based upon just a single input for simplicity), however the intention is merely to demonstrate how control flow can be effected via the use of tables instead of regular program statements. It should be clear that this technique can easily be extended to deal with multiple inputs, either by increasing the number of columns or utilizing multiple table entries (with optional and/or operator). Similarly, by using (hierarchical) 'linked' control tables, structured programming can be accomplished (optionally using indentation to help highlight subordinate control tables).

"CT1" is an example of a control table that is a simple lookup table. The first column represents the input value to be tested (by an implied 'IF input1 = x') and, if TRUE, the corresponding 2nd column (the 'action') contains a subroutine address to perform by a call (or jump to - similar to a SWITCH statement). It is, in effect, a multiway branch with return (a form of "dynamic dispatch"). The last entry is the default case where no match is found.

CT1

input 1	pointer
A	-->Add
S	-->Subtract
M	-->Multiply
D	-->Divide
?	-->Default

For programming languages that support pointers within data structures alongside other data values, the above table (CT1) can be used to direct control flow to an appropriate subroutines according to matching value from the table (without a column to indicate otherwise, equality is assumed in this simple case).

Assembly language example for IBM/360 (maximum 16Mb address range) or Z/Architecture

No attempt is made to optimize the lookup in coding for this first example, and it uses instead a simple linear search technique - purely to illustrate the concept and demonstrate fewer source lines. To handle all 256 different input values, approximately 265 lines of source code would be required (mainly single line table entries) whereas multiple 'compare and branch' would have normally required around 512 source lines (the size of the binary is also approximately halved, each table entry requiring only 4 bytes instead of approximately 8 bytes for a series of 'compare immediate'/branch instructions (For larger input variables, the saving is even greater).

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

improving the performance of the interpreter in above example

To make a selection in the example above, the average instruction path length (excluding the subroutine code) is '4n/2 +3', but can easily be reduced, where n = 1 to 64, to a constant time with a path length of '5' with zero comparisons, if a 256 byte translate table is first utilized to create a direct index to CT1 from the raw EBCDIC data. Where n = 6, this would then be equivalent to just 3 sequential compare & branch instructions. However, where n<=64, on average it would need approximately 13 times less instructions than using multiple compares. Where n=1 to 256, on average it would use approximately 42 times less instructions - since, in this case, one additional instruction would be required (to multiply the index by 4).

Improved interpreter (up to 26 times less executed instructions than the above example on average, where n= 1 to 64 and up to 13 times less than would be needed using multiple comparisons).

To handle 64 different input values, approximately 85 lines of source code (or less) are required (mainly single line table entries) whereas multiple 'compare and branch' would require around 128 lines (the size of the binary is also almost halved - despite the additional 256 byte table required to extract the 2nd index).

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

Further improved interpreter (up to 21 times less executed instructions (where n>=64) than the first example on average and up to 42 times less than would be needed using multiple comparisons).

To handle 256 different input values, approximately 280 lines of source code or less, would be required (mainly single line table entries), whereas multiple 'compare and branch' would require around 512 lines (the size of the binary is also almost halved once more).

* ------------------ 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 language example This example in C uses two tables, the first (CT1) is a simple linear search one-dimensional lookup table - to obtain an index by matching the input (x), and the second, associated table (CT1p), is a table of addresses of labels to jump to.

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) goto *CT1p; } /* found --> appropriate label */ goto *CT1p; /* not found --> default label */

This can be made more efficient if a 256 byte table is used to translate the raw ASCII value (x) directly to a dense sequential index value for use in directly locating the branch address from CT1p (i.e. "index mapping" with a byte-wide array). It will then execute in constant time for all possible values of x (If CT1p contained the names of functions instead of labels, the jump could be replaced with a dynamic function call, eliminating the switch-like goto - but decreasing performance by the additional cost of function housekeeping).

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; /* goto (Switch to) the label corresponding to the index (0=default,1= Add,2= Subtract,.) - see CT1p */

The next example below illustrates how a similar effect can be achieved in languages that do not support pointer definitions in data structures but do support indexed branching to a subroutine - contained within a (0-based) array of subroutine pointers. The table (CT2) is used to extract the index (from 2nd column) to the pointer array (CT2P). If pointer arrays are not supported, a SWITCH statement or equivalent can be used to alter the control flow to one of a sequence of program labels (e.g.: case0,case1,case2,case3,case4) which then either process the input directly, or else perform a call (with return) to the appropriate subroutine (default,Add,Subtract,Multiply or Divide,..) to deal with it.

CT2

input 1	subr #
A	1
S	2
M	3
D	4
?	0

As in above examples, it is possible to very efficiently translate the potential ASCII input values (A,S,M,D or unknown) into a pointer array index without actually using a table lookup, but is shown here as a table for consistency with the first example.

CT2P pointer array

pointer array
-->default
-->Add
-->Subtract
-->Multiply
-->Divide
-->?other

Multi-dimensional control tables can be constructed (i.e. customized) that can be 'more complex' than the above examples that might test for multiple conditions on multiple inputs or perform more than one 'action', based on some matching criteria. An 'action' can include a pointer to another subordinate control table. The simple example below has had an implicit 'OR' condition incorporated as an extra column (to handle lower case input, however in this instance, this could equally have been handled simply by having an extra entry for each of the lower case characters specifying the same subroutine identifier as the upper case characters). An extra column to count the actual run-time events for each input as they occur is also included.

CT3

input 1	alternate	subr #	count
A	a	1	0
S	s	2	0
M	m	3	0
D	d	4	0
?	?	0	0

The control table entries are then much more similar to conditional statements in procedural languages but, crucially, without the actual (language dependent) conditional statements (i.e. instructions) being present (the generic code is physically in the interpreter that processes the table entries, not in the table itself - which simply embodies the program logic via its structure and values).

In tables such as these, where a series of similar table entries defines the entire logic, a table entry number or pointer may effectively take the place of a program counter in more conventional programs and may be reset in an 'action', also specified in the table entry. The example below (CT4) shows how extending the earlier table, to include a 'next' entry (and/or including an 'alter flow' (jump) subroutine) can create a loop (This example is actually not the most efficient way to construct such a control table but, by demonstrating a gradual 'evolution' from the first examples above, shows how additional columns can be used to modify behaviour.) The fifth column demonstrates that more than one action can be initiated with a single table entry - in this case an action to be performed after the normal processing of each entry ('-' values mean 'no conditions' or 'no action').

Structured programming or "Goto-less" code, (incorporating the equivalent of 'DO WHILE' or 'for loop' constructs), can also be accommodated with suitably designed and 'indented' control table structures.

CT4 (a complete 'program' to read input1 and process, repeating until 'E' encountered)

input 1	alternate	subr #	count	jump
-	-	5	0	-
E	e	7	0	-
A	a	1	0	-
S	s	2	0	-
M	m	3	0	-
D	d	4	0	-
?	?	0	0	-
-	-	6	0	1

CT4P pointer array

pointer array
-->Default
-->Add
-->Subtract
-->Multiply
-->Divide
-->Read Input1
-->Alter flow
-->End