Control table


Control tables are tables that control the control flow or play a major part in program control. There are no rigid rules about the structure or content of a control table—its qualifying attribute is its ability to direct control flow in some way through "execution" by a processor or interpreter. The design of such tables is sometimes referred to as table-driven design. In some cases, control tables can be specific implementations of finite-state-machine-based automata-based programming. If there are several hierarchical levels of control table they may behave in a manner equivalent to UML state machines
Control tables often have the equivalent of conditional expressions or function references embedded in them, usually implied by their relative column position in the association list. Control tables reduce the need for programming similar structures or program statements over and over again. The two-dimensional nature of most tables makes them easier to view and update than the one-dimensional nature of program code. In some cases, non-programmers can be assigned to maintain the control tables.

Typical usage

The tables can have multiple dimensions, of fixed or variable lengths and are usually portable between computer platforms, requiring only a change to the interpreter, not the algorithm itself - the logic of which is essentially embodied within the table structure and content. The structure of the table may be similar to a multimap associative array, where a data value may be mapped to one or more functions to be performed.

One-dimensional tables

In perhaps its simplest implementation, a control table may sometimes be a one-dimensional table for directly translating a raw data value to a corresponding subroutine offset, index or pointer using the raw data value either directly as the index to the array, or by performing some basic arithmetic on the data beforehand. This can be achieved in constant time. In most architectures, this can be accomplished in two or three machine instructions - without any comparisons or loops. The technique is known as a "trivial hash function" or, when used specifically for branch tables, "double dispatch".
For this to be feasible, the range of all possible values of the data needs to be small.
Table to translate raw ASCII values to new subroutine index in constant time using one-dimensional array
ASCIIHexArray
null0000
....00
@4000
A4101
....00
D4404
....00
M4D03
....00
S5302

In automata-based programming and pseudoconversational transaction processing, if the number of distinct program states is small, a "dense sequence" control variable can be used to efficiently dictate the entire flow of the main program loop.
A two byte raw data value would require a minimum table size of 65,536 bytes - to handle all input possibilities - whilst allowing just 256 different output values. However, this direct translation technique provides an extremely fast validation & conversion to a subroutine pointer if the heuristics, together with sufficient fast access memory, permits its use.

Branch tables

A branch table is a one-dimensional 'array' of contiguous machine code branch/jump instructions to effect a multiway branch to a program label when branched into by an immediately preceding, and indexed branch. It is sometimes generated by an optimizing compiler to execute a switch statement - provided that the input range is small and dense, with few gaps .
Although quite compact - compared to the multiple equivalent If statements - the branch instructions still carry some redundancy, since the branch opcode and condition code mask are repeated alongside the branch offsets. Control tables containing only the offsets to the program labels can be constructed to overcome this redundancy and yet requiring only minor execution time overhead compared to a conventional branch table.

Multi-dimensional tables

More usually, a control table can be thought of as a Truth table or as an executable implementation of a printed decision table. They contain propositions, together with one or more associated 'actions'. These actions are usually performed by generic or custom-built subroutines that are called by an "interpreter" program. The interpreter in this instance effectively functions as a virtual machine, that 'executes' the control table entries and thus provides a higher level of abstraction than the underlying code of the interpreter.
A control table can be constructed along similar lines to a language dependent switch statement but with the added possibility of testing for combinations of input values and potentially calling multiple subroutines.

Table content

A control table essentially embodies the 'essence' of a conventional program, stripped of its programming language syntax and platform dependent components and 'condensed' to its variables, values, and subroutine identities. The structure of the table itself typically implies the logical operations involved - such as 'testing for equality', performing a subroutine and 'next operation' or following the default sequence.
A multi-dimensional control table will normally, as a minimum, contain value/action pairs and may additionally contain operators and type information such as, the location, size and format of input or output data, whether data conversion is required before or after processing. The table may or may not contain indexes or relative or absolute pointers to generic or customized primitives or subroutines to be executed depending upon other values in the "row".
The table illustrated below applies only to 'input1' since no specific input is specified in the table.
conditions and actions implied by structure
The variety of values that can be encoded within a control table is largely dependent upon the computer language used. Assembly language provides the widest scope for data types including, the option of directly executable machine code. Typically a control table will contain values for each possible matching class of input together with a corresponding pointer to an action subroutine. Some languages claim not to support pointers but nevertheless can instead support an index which can be used to represent a 'relative subroutine number' to perform conditional execution, controlled by the value in the table entry.
Comments positioned above each column can render a decision table 'human readable' even after 'condensing down' to its essentials.
The table entries can also optionally contain counters to collect run-time statistics for 'in-flight' or later optimization

Table location

Control tables can reside in static storage, on auxiliary storage, such as a flat file or on a database or may alternatively be partially or entirely built dynamically at program initialization time from parameters. For optimum efficiency, the table should be memory resident when the interpreter begins to use it.

The interpreter and subroutines

The interpreter can be written in any suitable programming language including a high level language. A suitably designed generic interpreter, together with a well chosen set of generic subroutines, would require additional conventional coding only for new custom subroutines. The interpreter, optionally, may only apply to some well-defined sections of a complete application program and not other, 'less conditional', sections.
The interpreter does not need to be unduly complex, or produced by a programmer with the advanced knowledge of a compiler writer, and can be written just as any other application program - except that it is usually designed with efficiency in mind. Its primary function is to "execute" the table entries as a set of "instructions". There need be no requirement for parsing of control table entries and these should therefore be designed, as far as possible, to be 'execution ready', requiring only the "plugging in" of variables from the appropriate columns to the already compiled generic code of the interpreter. The program instructions are, in theory, infinitely extensible and constitute values within the table that are meaningful only to the interpreter. The control flow of the interpreter is normally by sequential processing of each table row but may be modified by specific actions in the table entries.
These arbitrary values can thus be designed with efficiency in mind - by selecting values that can be used as direct indexes to data or function pointers. For particular platforms/language, they can be specifically designed to minimize instruction path lengths using branch table values or even, in some cases such as in JIT compilers, consist of directly executable machine code "snippets".
The subroutines may be coded either in the same language as the interpreter itself or any other supported program language. The choice of language for the interpreter and/or subroutines will usually depend upon how portable it needs to be across various platforms. There may be several versions of the interpreter to enhance the portability of a control table. A subordinate control table pointer may optionally substitute for a subroutine pointer in the 'action' column if the interpreter supports this construct, representing a conditional 'drop' to a lower logical level, mimicking a conventional structured program structure.

Performance considerations

At first sight, the use of control tables would appear to add quite a lot to a program's overhead, requiring, as it does, an interpreter process before the 'native' programming language statements are executed. This however is not always the case. By separating the executable coding from the logic, as expressed in the table, it can be more readily targeted to perform its function most efficiently. This may be experienced most obviously in a spreadsheet application - where the underlying spreadsheet software transparently converts complex logical 'formulae' in the most efficient manner it is able, in order to display its results.
The examples below have been chosen partly to illustrate potential performance gains that may not only compensate significantly for the additional tier of abstraction, but also improve upon - what otherwise might have been - less efficient, less maintainable and lengthier code. Although the examples given are for a 'low level' assembly language and for the C language, it can be seen, in both cases, that very few lines of code are required to implement the control table approach and yet can achieve very significant constant time performance improvements, reduce repetitive source coding and aid clarity, as compared with verbose conventional program language constructs. See also the quotations by Donald Knuth, concerning tables and the efficiency of multiway branching in this article.

Examples of control tables

The following examples are arbitrary, 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. Similarly, by using 'linked' control tables, structured programming can be accomplished.
"CT1" is an example of a control table that is a simple lookup table. The first column represents the input value to be tested and, if TRUE, the corresponding 2nd column contains a subroutine address to perform by a call. It is, in effect, a multiway branch with return. The last entry is the default case where no match is found.
CT1
For programming languages that support pointers within data structures alongside other data values, the above table can be used to direct control flow to an appropriate subroutines according to matching value from the table.
Assembly language example for IBM/360 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 whereas multiple 'compare and branch' would have normally required around 512 source lines.
* ------------------ interpreter --------------------------------------------*
LM R14,R0,=A Set R14=4, R15 --> table, and R0 =no. of entries in table
TRY CLC INPUT1,0 ********* 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
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 point to default entry
ACTION L R15,0 get pointer into R15,from where R15 points
BALR R14,R15 Perform the sub-routine
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 START of Control Table
DC C'S',AL3
DC C'M',AL3
DC C'D',AL3
N EQU /4 number of valid entries in table
DC C'?',AL3 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
. instruction to add
BR R14 return
SUBTRACT CSECT sub-routine #2
. instruction to subtract
BR R14 return
. etc..
improving the performance of the interpreter in above example
Improved interpreter.
To handle 64 different input values, approximately 85 lines of source code are required whereas multiple 'compare and branch' would require around 128 lines.
* ------------------ interpreter --------------------------------------------*
SR R14,R14 ********* Set R14=0
CALC IC R14,INPUT1 * calc * put EBCDIC byte into lo order bits of R14
IC R14,CT1X * * use EBCDIC value as index on table 'CT1X' to get new index
FOUND L R15,CT1 ********* get pointer to subroutine using index
BALR R14,R15 Perform the sub-routine
B END go terminate this program
* --------------- additional translate table 256 bytes----*
CT1X DC 12AL1 12 identical sets of 16 bytes of x'00
* representing X'00 - x'BF'
DC AL1 ..x'C0' - X'CF'
DC AL1 ..x'D0' - X'DF'
DC AL1 ..x'E0' - X'EF'
DC AL1 ..x'F0' - X'FF'
* the assembler can be used to automatically calculate the index values and make the values more user friendly
*
* modified CT1
CT1 DC A index =00 START of Control Table
PADD DC A =04
PSUB DC A =08
PMUL DC A =12
PDIV DC A =16
* the rest of the code remains the same as first example
Further improved interpreter.
To handle 256 different input values, approximately 280 lines of source code or less, would be required, whereas multiple 'compare and branch' would require around 512 lines.
* ------------------ interpreter --------------------------------------------*
SR R14,R14 ********* Set R14=0
CALC IC R14,INPUT1 * calc * put EBCDIC byte into lo order bits of R14
IC R14,CT1X * * use EBCDIC value as index on table 'CT1X' to get new index
SLL R14,2 * * multiply index by 4
FOUND L R15,CT1 ********* get pointer to subroutine using index
BALR R14,R15 Perform the sub-routine
B END go terminate this program
* --------------- additional translate table 256 bytes----*
CT1X DC 12AL1 12 identical sets of 16 bytes of x'00'
* representing X'00 - x'BF'
DC AL1 ..x'C0' - X'CF'
DC AL1 ..x'D0' - X'DF'
DC AL1 ..x'E0' - X'EF'
DC AL1 ..x'F0' - X'FF'
* the assembler can be used to automatically calculate the index values and make the values more user friendly
*
* modified CT1
CT1 DC A index =00 START of Control Table
PADD DC A =01
PSUB DC A =02
PMUL DC A =03
PDIV DC A =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 is a simple linear search one-dimensional lookup table - to obtain an index by matching the input, and the second, associated table, is a table of addresses of labels to jump to.

static const char CT1 = ; /* permitted input values */
static const void *CT1p = ; /* labels to goto & default*/
for /* loop thru ASCII values */
/* 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 directly to a dense sequential index value for use in directly locating the branch address from CT1p. It will then execute in constant time for all possible values of x.

static const void *CT1p = ;
/* the 256 byte table, below, holds values, in corresponding ASCII positions, all others set to 0x00 */
static const char CT1x=;
/* the following code will execute in constant time, irrespective of the value of the input character */
i = CT1x; /* extract the correct subroutine index from table CT1x using its ASCII value as an index initially */
goto *CT1p; /* goto the label corresponding to the index - 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 array of subroutine pointers. The table is used to extract the index to the pointer array. 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 which then either process the input directly, or else perform a call to the appropriate subroutine to deal with it.
CT2
As in above examples, it is possible to very efficiently translate the potential ASCII input values into a pointer array index without actually using a table lookup, but is shown here as a table for consistency with the first example.
Multi-dimensional control tables can be constructed 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. An extra column to count the actual run-time events for each input as they occur is also included.
CT3
The control table entries are then much more similar to conditional statements in procedural languages but, crucially, without the actual conditional statements being present.
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 shows how extending the earlier table, to include a 'next' entry can create a loop 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.
Structured programming or "Goto-less" code,, can also be accommodated with suitably designed and 'indented' control table structures.
CT4

Table-driven rating

In the specialist field of telecommunications rating,
table-driven rating techniques illustrate the use of control tables in applications where the rules may change frequently because of market forces. The tables that determine the charges may be changed at short notice by non-programmers in many cases.
If the algorithms are not pre-built into the interpreter, it is known as "Rule-based Rating" rather than table-driven rating.

Spreadsheets

A spreadsheet data sheet can be thought of as a two dimensional control table, with the non empty cells representing data to the underlying spreadsheet program. The cells containing formula are usually prefixed with an equals sign and simply designate a special type of data input that dictates the processing of other referenced cells - by altering the control flow within the interpreter. It is the externalization of formulae from the underlying interpreter that clearly identifies both spreadsheets, and the above cited "rule based rating" example as readily identifiable instances of the use of control tables by non programmers.

Programming paradigm

If the control tables technique could be said to belong to any particular programming paradigm, the closest analogy might be Automata-based programming or "reflective". The interpreter itself however, and the subroutines, can be programmed using any one of the available paradigms or even a mixture. The table itself can be essentially a collection of "raw data" values that do not even need to be compiled and could be read in from an external source.

Analogy to bytecode / virtual machine instruction set

A multi-dimensional control table has some conceptual similarities to bytecode operating on a virtual machine, in that a platform dependent "interpreter" program is usually required to perform the actual execution. There are also some conceptual similarities to the recent Common Intermediate Language in the aim of creating a common intermediate 'instruction set' that is independent of platform. P-code can also be considered a similar but earlier implementation with origins as far back as 1966.

Instruction fetch

When a multi-dimensional control table is used to determine program flow, the normal "hardware" Program Counter function is effectively simulated with either a pointer to the first table entry or else an index to it. "Fetching" the instruction involves decoding the data in that table entry - without necessarily copying all or some of the data within the entry first. Programming languages that are able to use pointers have the dual advantage that less overhead is involved, both in accessing the contents and also advancing the counter to point to the next table entry after execution. Calculating the next 'instruction' address can even be performed as an optional additional action of every individual table entry allowing loops and or jump instructions at any stage.

Monitoring control table execution

The interpreter program can optionally save the program counter at each stage to record a full or partial trace of the actual program flow for debugging purposes, hot spot detection, code coverage analysis and performance analysis.

Advantages

Optionally:-
The following mainly apply to their use in multi-dimensional tables, not the one-dimensional tables discussed earlier.