Control table: Difference between revisions

Revision as of 01:03, 16 August 2025

Latest revision as of 03:20, 23 August 2025

(10 intermediate revisions by the same user not shown)

Line 1:

{{Short description |Data table used to control program flow}}

{{Refimprove|date=February 2009}}

[[File:Control table.png|thumb|220px|A simple controlControl table that directs program flow according to the value of a single input value. Each entry holds a possible input value and ana associated subroutinereference to invokean associated function.]]

A '''control table''' is a table [[data structure]] (i.e. [[Array (data structure)|array]] of [[Record (computer science)|record]]s) used to direct the [[control flow]] of a [[computer program]]. [[Software]] that uses a control table is said to be ''table-driven''.<ref>''Programs from decision tables'', Humby, E., 2007,Macdonald, 1973 ... Biggerstaff, Ted J. Englewood Cliffs, NJ : Prentice-Hall {{ISBN|0-444-19569-6}}</ref><ref>{{Cite web |url=http://www.dkl.com/wp-content/uploads/2016/05/DataKinetics-Table-Driven-Design.pdf |title=Archived copy |access-date=17 May 2016 |archive-date=10 June 2016 |archive-url=https://web.archive.org/web/20160610160908/http://www.dkl.com/wp-content/uploads/2016/05/DataKinetics-Table-Driven-Design.pdf |url-status=dead }}</ref> A control table encodes both the [[Parameter (computer programming)|parameters]] to a [[conditional (programming)|conditional expression]] and a [[Function (computer programming)|function]] [[reference (computer science)|reference]]. An [[interpreter (computing)|interpreter]] processes a table by applying input data toevaluating 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. The two-dimensional nature of most tables makes them easier to view and update than the one-dimensional nature of program code.

In general, the mapping of input parameters can be via any data structure. A common data structure is the [[lookup table |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.

Typical uses for a control table include:

* Transform an input value to an [[associative array |index]], for branching or [[pointer (computer programming)|pointer]] [[lookup table |lookup]]

* Transform an input value to a program name, relative [[subroutine]] number, [[label (programming language)|program label]] or program [[offset (computer science)|offset]], to alter [[control flow]]

* Control a [[main loop]] in [[event-driven programming]] using a [[control variable (programming)|control variable]] for [[state transition]]s

* Control the program cycle for [[online transaction processing]] applications

How the associated behavior is referenced varies. Some languages provide a direct function reference (i.e. [[pointer (computer programming)|pointer]]) that can be used to invoke a function directly, but some languages do not. Some languages provide for [[goto |jumping]] to a ___location (i.e.[[label (programming language)|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 relatively advanced use as instructions for a [[virtual machine]] processed by an interpreter {{endash}} similar to [[bytecode]] but usually with operations implied by the table structure itself.

A control table is often used as part of a higher-level algorithm. It can control the [[main loop]] of an [[event-driven programming |event-driven program]]. A relatively advanced use asis instructions for a [[virtual machine]] processed by an interpreter {{endash}} similar to [[bytecode]] but usually with operations implied by the table structure itself insteaad 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 code |variable length]]. The structure of the table may be similar to a [[multimap (data structure)|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 [[software portability |portable]] between [[computer platform]]s as long as a compatible interpreter exists on each platform.

===TrivalTrivial hash function===

A relatively simple implementation consists of a [[sparse file |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; preventing an error that might otherwise occur for an unused index value. The lookup is achieved in [[constant time]]; without searching. In most [[computer architecture |architecture]]s, this can be accomplished in two or three [[machine instruction]]s. 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 {{endash}} which might consume more memory than is considered worth the value it provides.

{| class="wikitable" style="text-align:center; "

Line 56 ⟶ 54:

===Decision table===

Often, a control table isimplements a [[truthdecision table]] orwhich an implementation oflike a [[decisioncontrol table]] or a [[tree (data structure)|tree]] of decision tables. The tables contains (often implied) [[propositional formula |propositions]], together withand one or more associated actions. The actions are usually performed by generic or custom-built [[subroutine]]s that are called by an interpreter. The interpreter, a [[virtual machine]], executes the control table entries and thus provides a higher level of [[abstraction (computer science)|abstraction]] than the interpreter.

A control table can act like a [[switch statement]] or more generally as a nested [[if-then-else]] construct that includes [[logical predicate]]s (using [[Boolean algebra (logic)|boolean]] style [[logical conjunction |AND]]/[[logical disjunction |OR]] conditions) for each case. Such as 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; condensed to data and implied logic. The meaning of the table includes implied operations instead of being explicit as in a more typical a [[programming paradigm]].

Typically, a two-dimensional control table contains value/action pairs and may additionally contain operators and [[type system |type]] information such as the ___location, size and format of input or output data, whether [[data conversion]] is required. The table may contain [[array index |indexes]] or relative or absolute [[pointer (computer programming)|pointer]]s to generic or customized primitives or [[subroutine]]sfunctions to be executed depending upon other values in the row.

The type of values used to 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 subroutinefunction. For a language without [[pointer (computer programming)|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==

Line 68 ⟶ 66:

==Interpreter==

A control table interpreter executes operations defined by the tableoperations as aselected setby ofinput instructionsparameters. ControlThe table entriesand shouldresulting beruntime designedbehavior tocan be execution ready,modified requiringwithout onlymodifying the plugging-ininterpreter. ofAn variablesinterpreter fromcan therequire appropriate[[software columnsmaintenance |maintenance]] to thechange alreadyits compiledbehavior, genericbut code ofhopefully the interpreter. Theis programdesigned instructionsto aresupport [[extensible]].future Oncefunctionality complete,via an interpreter would require [[software maintenance |maintenance]] only for newtable customchanges subroutinesinstead.

The handlerHandler subroutinesfunctions often are coded in the same language as the interpreter, but could be in another language provided a suitable inter-language call-linkage mechanisms exists. The choice of language for the interpreter and subroutineshandler functions usually depends on how portable it needs to be across various [[Platform (computing)|platform]]s. There may be several versions of the interpreter to support [[Porting |portability]]. A subordinate control table pointer may optionally substitute for a subroutinefunction pointer in the action column if the interpreter supports this construct; representing a conditional drop to a lower logical level, mimicking [[structured programming]].

==Performance considerations==

Line 79 ⟶ 77:

==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 input1input = x') and, if TRUEso, the correspondingaction 2nd columnin (the 'action')corresponding contains2nd acolumn subroutineis address to perform by a [[System call|call]] (or [[goto|jump]] to – similar to a [[Switch statement|SWITCH]] statement)invoked. It is, in effect,like a [[multiway branch]] with return; (a form of "[[dynamic dispatch]]"). The last entry is the default case where no match is found. For a programming language that supports pointers within [[data structure]]s, CT1 can be used to direct [[control flow]] to an [[subroutine]] according to matching value from the table.

:{| class="wikitable"

|+ CT1

! input !! action

! input 1!! !! [[pointer (computer programming)|pointer]]

|-

| {{mono|A}} || &rarr; ||Add

|-

| {{mono|S}} || &rarr; ||Subtract

|-

| {{mono|M}} || &rarr; ||Multiply

|-

| {{mono|D}} || &rarr; ||Divide

|-

| {{mono|?}} || &rarr; ||Default

|}

The next example illustrates how a similar effect can be achieved in languagesa language that dodoes not support pointer definitions in data structures but dodoes support indexed branching to a subroutinefunction – contained within a ([[zero-based numbering|0-based]]) array of subroutinefunction 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 itfunction.

:{| class="wikitable"

|+ CT2

! input 1!! {{mono|subr #}}

|-

| {{mono|A}} || {{mono|1}}

|-

| {{mono|S}}A || {{mono|2}}1

|-

| {{mono|M}}S || {{mono|3}}2

|-

| {{mono|D}}M || {{mono|4}}3

|-

| {{mono|?}}D || {{mono|0}}4

|}

As in above examples, it is possible to efficiently translate the potential [[ASCII]] input values (A, S, M,D or unknownD) 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

|+ CT2P<br/>{{nobold|pointer array}}

! index || array

! !! [[pointer (computer programming)|pointer]] [[Array data structure|array]]

|-

| &rarr;1 || {{mono|default}}Add

|-

| &rarr;2 || {{mono|Add}}Subtract

|-

| &rarr;3 || {{mono|Subtract}}Multiply

|-

| &rarr;4 || {{mono|Multiply}}Divide

|-

| &rarr; || {{mono|Divide}}

|-

| &rarr; || {{mono|?other}}

|}

A two-dimensional control table could be used to support testing multiple conditions or performing 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 subroutinefunction 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!! {{mono|subr #}} !! {{mono|count}}

|-

| {{mono|A}} ||{{mono| a}} || {{mono|1}} || {{mono|0}}

|-

| {{mono|S}} ||{{mono| s}} || {{mono|2}} || {{mono|0}}

|-

| {{mono|M}} ||{{mono| m}} || {{mono|3}} || {{mono|0}}

|-

| {{mono|D}} ||{{mono| d}} || {{mono|4}} || {{mono|0}}

|-

| {{mono|?}} ||{{mono|?}}|| {{mono|0}}|| {{mono|0}}

|}

The control table entries are then much more similar to conditional statements in [[procedural language]]s 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' ([[branch (computer science)|jump]]) subroutinefunction) can create a [[program loop|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 [[structured programming|"Goto-less" code]], (incorporating the equivalent of '[[do while loop|DO WHILE]]' or '[[for loop]]' constructs), can also be accommodated with suitably designed and 'indented' control table structures.

Line 156 ⟶ 145:

|

{| class="wikitable"

|+ CT4

|+ CT4<br/>{{nobold|(a complete 'program' to read input1 and process, repeating until 'E' encountered)}}

! input 1!!alternate!! subr # !! count !! jump

|-

| {{sdash}} || {{sdash}} || {{mono|5}}|| {{mono|0}} || {{sdash}}

|-

| {{mono|E}} ||{{mono|e}}|| {{mono|7}}|| {{mono|0}} || {{sdash}}

|-

| {{mono|A}}E ||{{mono|a}} e || {{mono|1}}7 || {{mono|0}} || {{sdash}}

|-

| {{mono|S}}A ||{{mono|s}} a || {{mono|2}}1 || {{mono|0}} || {{sdash}}

|-

| {{mono|M}}S ||{{mono|m}} s || {{mono|3}}2 || {{mono|0}} || {{sdash}}

|-

| {{mono|D}}M ||{{mono|d}} m || {{mono|4}}3 || {{mono|0}} || {{sdash}}

|-

| {{mono|?}}D ||{{mono|?}} d || {{mono|0}}4 || {{mono|0}} || {{sdash}}

|-

| {{sdash}} || {{sdash}} || {{mono|6}} || {{mono|0}} || {{mono|1}}

|}

|

{| class="wikitable"

|+ CT4P {{nobold|pointer array}}

! index || pointer

! !! [[pointer (computer programming)|pointer]] [[array data structure|array]]

|-

| &rarr;0 || {{mono|Default}}

|-

| &rarr;1 || {{mono|Add}}

|-

| &rarr;2 || {{mono|Subtract}}

|-

| &rarr;3 || {{mono|Multiply}}

|-

| &rarr;4 || {{mono|Divide}}

|-

| &rarr;5 || {{mono|Read Input1}}

|-

| &rarr;6 || {{mono|Alter flow}}

|-

| &rarr;7 || {{mono|End}}

|}

|}

Line 244 ⟶ 231:

==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 [[reflection (computer science)|"reflective"]] (a form of [[metaprogramming]] – since the table entries could be said to 'modify' the behaviour of the interpreter). The interpreter itself however, and the subroutinesfunctions, 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 (except in specific, platform dependent, implementations using memory pointers directly for greater efficiency).

==Virtual machine==

Line 260 ⟶ 247:

; Portability: can be designed to be language and platform independent {{endash}} except for the interpreter

; Flexibility: ability to execute either [[language primitive |primitives]] or [[subroutine]]sfunctions transparently and be custom designed to suit the problem

; Compactness: table usually shows condition/action pairing side-by-side (without the usual platform/language implementation dependencies), often also resulting in reduced binary file size due to less duplication of instructions, reduced source code size due to eliminating conditional statements and reduced program load (or download) speeds

Line 268 ⟶ 255:

; Locality of reference: compact tables structures result in tables remaining in [[cache (computing)|cache]]

; Code re-use: the interpreter is usually reusable. Frequently it can be daptedadapted to new programming tasks using the same technique and can grow organically, becoming, in effect, a [[standard library]] of tried and tested [[subroutines]]functions, controlled by the table definitions.

; Efficiency: system wide optimization possible. Any performance improvement to the interpreter usually improves ''all'' applications using it (see examples in 'CT1' above).

Line 289 ⟶ 276:

; [[Computational overhead]]: some increase because of extra level of [[indirection (programming)|indirection]] caused by virtual instructions having to be 'interpreted' (this however can usually be more than offset by a well designed generic interpreter taking full advantage of efficient direct translate, search and conditional testing techniques that may not otherwise have been utilized)

; Complexity: Complex [[expression (programming)|expression]]s cannot always be used ''directly'' in data table entries for comparison purposes. These intermediate values can however be calculated beforehand instead within a subroutinefunction and their values referred to in the conditional table entries. Alternatively, a subroutinefunction can perform the complete complex conditional test (as an unconditional 'action') and, by setting a [[truth bit |truth flag]] as its result, it can then be tested in the next table entry. See [[Structured program theorem]]

==Quotations==

Line 309 ⟶ 296:

* {{Annotated link |Keyword-driven testing}}

* {{Annotated link |Threaded code}}

* {{Annotated link |Truth table}}

==Notes==