A control table is a table used to direct the control flow of a computer program. Software that uses a control table is said to be table-driven.Programs from decision tables, Humby, E., 2007, Macdonald, 1973 ... Biggerstaff, Ted J. Englewood Cliffs, NJ : Prentice-Hall A control table encodes both the parameters to a conditional expression and a function reference. An interpreter processes a table by evaluating the conditional expression for input data and invoking the selected function. Using a control table can reduce the need for repetitive code that implements the same logic.
In general, the mapping of input parameters can be via any data structure. A common data structure is the lookup, which provides relatively high performance but at a relatively high memory footprint. An associative array can minimize memory use at the cost of more lookup time.
How the associated behavior is referenced varies. Some languages provide a direct function reference (i.e. pointer) that can be used to invoke a function directly, but some languages do not. Some languages provide for jumping to a location (i.e.label). As a fallback, any language allows for mapping input to an index that can then be used to branch to a particular part of the code.
A control table is often used as part of a higher-level algorithm. It can control the main loop of an event-driven program. A relatively advanced use is instructions for a virtual machine similar to bytecode but usually with operations implied by the table structure itself instead of encoded in the table data.
Data structure A table can be structured in a variety of ways. It may have one or multiple dimensions and be of fixed or variable length. The structure of the table may be similar to a multimap associative array, where a data value (or combination of data values) may be mapped to one or more functions to be performed. Often, the structure allows tabular data is portable between computer platforms as long as a compatible interpreter exists on each platform.
Trivial hash function A relatively simple implementation consists of a sparse, one-dimensional array of values. The index space is fully covered by the array such that lookup involves indexing into the array by the input value, and a value is found even for an index that is not intended to be used; this prevents an error that might otherwise occur for an unused index value. The lookup is achieved in constant time, without searching. In most architectures, this can be accomplished in two or three machine instructions. The technique is known as a "trivial hash function" or, when used specifically for branch tables, "double dispatch".
To be feasible, the range of index values should be relatively small. In the example below, the control table is indexed by ASCII value so it has 256 entries (an entry for each ASCII value); omitted entries are shown as '...'. Only the values for the letter A, D, M, and S are important. All other values are uninteresting and set to 0. A two-byte index would require a minimum of 65,536 entries to handle all input possibilities which might consume more memory than is considered worth the value it provides.
+ index(ASCII) Array 0 0 ... 0 (A) 1 ... 0 (D) 4 ... 0 (M) 3 ... 0 (S) 2 ... 0 255 0
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.
Branch table A branch table is a one-dimensional array of 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.http://www.netrino.com/node/137 (as created by the previous array example)
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 (at least in assembly languages) and yet requiring only minor execution time overhead compared to a conventional branch table.
Decision table Often, a control table implements a decision table, which like a control table contains (often implied) propositions, and one or more associated actions.
A control table can act like a switch statement or more generally as a nested if-then-else construct that includes logical predicates (using boolean style AND/OR conditions) for each case. Such a control table provides for a language-independent implementation of what otherwise is a language-dependent construct. The table embodies the essence of a program, stripped of programming language syntax and platform dependent aspects, and condensed to data and implied logic. The meaning of the table includes implied operations instead of being explicit as in a more typical programming paradigm.
Typically, a two-dimensional control table contains 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. The table may contain indexes or relative or absolute pointers to generic or customized primitives or functions to be executed depending upon other values in the row.
The type of values used in a control table depends on the computer language used for the interpreter. Assembly language provides the widest scope for data types including machine code for lookup values. Typically, a control table contains values for each possible matching class of input together with a corresponding pointer to an action function. For a language without pointer support, the table can encode an index which can imply an offset value that can be used to accomplish the same as a pointer.
Storage A control table can be stored in a variety of ways. It can be stored as part of a program, for example as a static variable. It can be stored in the file system, for example as a flat file or in a database. It can be built dynamically by the program. For efficiency, the table should be resident in program memory when the interpreter uses it.
Interpreter A control table interpreter executes the operations as selected by input parameters. The table and resulting runtime behavior can be modified without modifying the interpreter. An interpreter can require maintenance to change its behavior, but hopefully the interpreter is designed to support future functionality via table changes instead.
Handler functions often are coded in the same language as the interpreter, but could be in another language provided a suitable inter-language call-linkage mechanism exists. The choice of language for the interpreter and handler functions usually depends on how portable it needs to be across various platforms. There may be several versions of the interpreter to support portability. A subordinate control table pointer may optionally substitute for a function pointer in the action column if the interpreter supports this construct. This represents a conditional drop to a lower logical level, mimicking structured programming.
Performance considerations Even though using a control table entails the development cost and deployment size of an interpreter, by separating (encapsulating) the executable coding from the logic, as expressed in the table, it can be more readily targeted to perform its function. This may be experienced 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.
Examples General CT1 is a control table that is a simple lookup table. The first column represents the input value to be tested (by an implied 'IF input = x') and, if so, the action in the corresponding 2nd column is invoked. It is like a multiway branch with return, a form of dynamic dispatch.
{| class="wikitable" |+ CT1 ! input !! action |- | A || Add |- | S || Subtract |- | M || Multiply |- | D || Divide
The next example illustrates how a similar effect can be achieved in a language that does not support pointer definitions in data structures but does support indexed branching to a function – contained within a (0-based) array of function 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 function.
{| class="wikitable" |+ CT2 ! input!! subr # |- | A || 1 |- | S || 2 |- | M || 3 |- | D || 4 |} As in above examples, it is possible to efficiently translate the potential ASCII input values (A, S, M, D) into a pointer array index without actually using a table lookup, but is shown here as a table for consistency with the first example.
{| class="wikitable" |+ CT2P ! index || array |- | 1 || Add |- | 2 || Subtract |- | 3 || Multiply |- | 4 || Divide
A two-dimensional control table could be used to support testing multiple conditions or performing more than one action. 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 by having an extra entry for each of the lower case characters specifying the same function 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.
{| class="wikitable" |+ CT3 ! input 1!!alternate!! subr # !! count |- | A || a || 1 || 0 |- | S || s || 2 || 0 |- | M || m || 3 || 0 |- | D || d || 4 || 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).