Control table: Difference between revisions

Revision as of 08:38, 12 August 2025

Latest revision as of 03:20, 23 August 2025

(20 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 is instructions for a [[virtual machine]] {{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 function. 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.

The table below is a prototype of a control table that implies an action based on a single input value.

{| class="wikitable"

|+

! (implied) IF = || (implied) perform

|-

| value|| action

|-

| value|| action

|}

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 subroutine. 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==

A control table can be stored a variety of ways. It can be stored as part of a program; for example as a [[static variable]]. It can stored in the [[file system]]; for example as [[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==

==The interpreter and subroutines==

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 [[software maintenance |maintenance]] to change its behavior, but hopefully the interpreter is designed to support future functionality via table changes instead.

The interpreter can be written in any suitable programming language including a [[high level language]]. A suitably designed [[generic programming|generic]] interpreter, together with a well chosen set of generic subroutines (able to process the most commonly occurring primitives), would require additional conventional coding only for new custom subroutines (in addition to specifying the control table itself). The interpreter, optionally, may only apply to some well-defined sections of a complete application program (such as the [[main loop|main control loop]]) and not other, 'less conditional', sections (such as program initialization, termination and so on).

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 mechanisms exists. The choice of language for the interpreter and handler 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 function pointer in the action column if the interpreter supports this construct; representing a conditional drop to a lower logical level, mimicking [[structured programming]].

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 [[instruction (computer science)|program instructions]] are, in theory, infinitely [[extensible]] and constitute (possibly arbitrary) 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 [[algorithmic efficiency|efficiency]] in mind – by selecting values that can be used as direct indexes to data or [[function pointers]]. For particular platforms/[[computer language|language]], they can be specifically designed to minimize [[instruction path length]]s using [[branch table]] values or even, in some cases such as in [[Just-in-time compilation|JIT]] compilers, consist of directly executable [[machine code]] "[[Snippet (programming)|snippets]]" (or pointers to them).

The subroutines may be coded either in the same language as the interpreter itself or any other supported program language (provided that suitable inter-language 'Call' linkage mechanisms exist). The choice of language for the interpreter and/or subroutines will usually depend upon how portable it needs to be across various [[Platform (computing)|platform]]s. There may be several versions of the interpreter to enhance the [[Porting|portability]] of a control table. A subordinate control table pointer may optionally substitute for a subroutine pointer in the 'action' columns if the interpreter supports this construct, representing a conditional 'drop' to a lower logical level, mimicking a conventional [[Structured programming|structured program]] structure.

==Performance considerations==

AtEven firstthough sight,using the use ofa control tablestable wouldentails appearthe todevelopment addcost quiteand adeployment lotsize to a program's [[Computational overhead|overhead]], requiring, as it does,of an interpreter, process before the 'native' programming language statements are executed. This however is not always the case. Byby separating (or 'encapsulating') 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)|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 [[Control table#Quotations|quotations]] by [[Donald Knuth]], concerning tables and the efficiency of [[multiway branch]]ing in this article.

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

|-

| A || Add

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

|-

| S || Subtract

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

|-

| M || Multiply

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

|-

| D || 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}} || {{mono|2}}

|-

| {{mono|M}} || {{mono|3}}

|-

| {{mono|D}} || {{mono|4}}

|-

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

|}

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

|}

MultiA two-dimensional control tablestable cancould be constructedused thatto cansupport be more complex than the above examples that might test fortesting multiple conditions on multiple inputs or performperforming 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 171 ⟶ 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}} ||{{mono| a}} || {{mono|1}} || {{mono|0}} || {{sdash}}

|-

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

|-

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

|-

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

|-

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

|-

| {{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}}

|}

|}

=== Assembly language ===

No attempt is made to optimize the lookup in coding for this first example (for [[IBM/360]] maximum 16Mb address range or [[Z/Architecture]]), 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 file|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 [[Linear time|constant time]] <math>O(1)\,</math> 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 file|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 file|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 ===

Line 355 ⟶ 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).

==Analogy to bytecode / virtualVirtual machine instruction set==

A multitwo-dimensional control table hasis somesimilar conceptualto similaritiesintermediate to[[executable code]] (i.e. [[bytecode]]) operatingrunning on a [[virtual machine]], in that a [[platform dependent |platform-dependent]] [[Interpreter (computing)|"interpreter"]] program is usually required to perform the actual execution (that is largely conditionally determined by the tablestable content). There are also some conceptual similarities to the recent [[Common Intermediate Language]] (CIL) in the aim of creating a common intermediate 'instruction set' that is independent of platform (but unlike CIL, no pretensions to be used as a common resource for other languages). [[p-code machine |P-code]] can also be considered a similar but earlier implementation with origins as far back as 1966.

==Instruction fetch==

When a multitwo-dimensional control table is used to determine program flow, the normal "hardware" [[program counter]] function is effectively simulated with either a [[Pointer (computer programming)|pointer]] to the first (or next) table entry or else an [[array index |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 [[Pointer (computer programming)|pointer]]s have the dual advantage that less [[Computational overhead|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 (i.e. table entry) can even be performed as an optional additional action of every individual table entry allowing [[Program loops|loops]] and or [[Branch (computer science)|jump]] instructions at any stage.

==Monitoring control table execution==

Line 367 ⟶ 243:

==Advantages==

*; clarity –Clarity: [[table (information)|information tables]] are [[ubiquitous computing|ubiquitous]] and mostly [[inherently]] [[understanding|understood]] even by the [[general public]] (especially [[fault diagnosis|fault diagnostic]] tables in [[user guide|product guides]])

* portability – can be designed to be 100% language independent (and platform independent – except for the interpreter)

; 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]]s 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

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

** [[binary file]] – reduced in size through less duplication of instructions

** [[Source code|source]] file – reduced in size through elimination of multiple conditional statements

; 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

** improved program load (or download) speeds

* maintainability – tables often reduce the number of source lines needed to be maintained v. multiple compares

; Maintainability: tables often reduce the number of source lines needed to be maintained v. multiple compares

* 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 easily adapted to new programming tasks using precisely the same technique and can grow 'organically' becoming, in effect, a [[standard library]] of tried and tested [[subroutines]], controlled by the table definitions.

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

* efficiency – systemwide optimization possible. Any performance improvement to the interpreter usually improves ''all'' applications using it (see examples in 'CT1' above).

* extensible – new 'instructions' can be added – simply by extending the interpreter

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

* interpreter can be written like an application program

Optionally:-

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

* the interpreter can be [[introspection|introspective]] and "self [[optimization (computer science)|optimize]]" using runtime [[software metric|metrics]] collected within the table itself (see CT3 and CT4 – with entries that could be periodically sorted by descending count). The interpreter can also optionally choose the most efficient lookup technique dynamically from metrics gathered at run-time (e.g. size of array, range of values, sorted or unsorted)

* [[dynamic dispatch]] – common functions can be pre-loaded and less common functions fetched only on first encounter to reduce [[memory]] usage. In-table [[memoization]] can be employed to achieve this.

; Extensible: new instructions can be added by extending the interpreter

Optionally:

* Interpreter can be [[introspection |introspective]] and "self [[optimization (computer science)|optimize]]" using runtime [[software metric |metrics]] collected within the table itself (see CT3 and CT4 – with entries that could be periodically sorted by descending count). The interpreter can also optionally choose the most efficient lookup technique dynamically from metrics gathered at run-time (e.g. size of array, range of values, sorted or unsorted)

* [[Dynamic dispatch]]: common functions can be pre-loaded and less common functions fetched only on first encounter to reduce [[memory]] usage. In-table [[memoization]] can be employed to achieve this.

* The interpreter can have debugging, trace and monitor features built-in – that can then be switched on or off at will according to test or 'live' mode

* control tables can be built 'on-the-fly' (according to some user input or from parameters) and then executed by the interpreter (without building code literally).

* Control tables can be built 'on-the-fly' (according to some user input or from parameters) and then executed by the interpreter (without building code literally).

==Disadvantages==

*; training requirement –Training: application programmers are not usually trained to produce generic solutions

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

*; [[Computational overhead|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)

* Complex [[expression (programming)|expression]]s cannot always be used ''directly'' in data table entries for comparison purposes

; Complexity: Complex [[expression (theseprogramming)|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 411 ⟶ 296:

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

* {{Annotated link |Threaded code}}

* {{Annotated link |Truth table}}

==Notes==