Counter machine reference model

From Wikipedia, the free encyclopedia

The Counter machine's reference model is a set of choices and conventions to be used with the Counter machine and other model variants of the Register machine concept. It permits comparisons between models, and serves a didactic function with regards to examples and descriptions.

It is based on conventional models, labels and terminology. The reference (base) model is intended to preserve consistency between articles.

[edit] Introduction

In counter machine models the reader will observe, and may be bewildered by, the plethora of instruction sets defined by their authors. This reference will use the symbolism defined below to provide a standarized presentation format (syntax) to facilitate comparison of the sets and help give them definition.

The base model is derived from Minsky (1967), Lambek (1961) and in particular Shepherdson-Sturgis (1963 p. 225).

[edit] Formal Definition

The Counter machine reference model consists of a finite set of registers r₁ ... r_n, each of which can hold a non-negative integer, r₀ (always zero), and a finite list of instructions I₁ ... I_m. Each of the instructions in this list is one of the following:

• INC(j) — increment the value of register r_j by 1; go to the successor instruction (e.g. instruction that is numerically next-in-sequence).
• DEC(j) — If the contents of r is not 0 (not empty) then decrement the value of register r_j by 1, else the contents of r=0; go to the successor instruction.
• JZ (j, z) — If the contents of register r_j equals Zero then Jump to instruction I_z else go to the successor instruction.
• HALT — halts the computation.

Formal Semantic:

[edit] Reference Library (RefLib)

The "Counter machine reference model" library, or RefLib, is a set of conventions chosen to:

• Specify the "instruction labels";
• Specify the syntax (effective symbol-strings) of these labels;
• Specify the semantics (meaning, content) of the labels and demonstrate equivalences.

Through the RefLib other instruction sets from similar register machine models can be emulated. In a sense the new instructions become "subroutines" of the "base" instructions -- Shepherdson-Sturgis (1963) used this stratgy in their demonstration that the three base instructions form a set that is equivalent to the primitive recursive functions. The RefLib may be seen also as a microcoded implementation strategy: the same counter machine is augmented by new instructions from instruction set; it is not a new machine.

The RefLib scripts (instruction implementations) are "near to formal". For a precise demonstration imagine the use of a C preprocessor to expand the RefLib script templates into standard instructions.

[edit] Counter machine instructions

The various Counter machine instruction sets are like "ultra-RISC instruction sets". And, as is the case for different RISC machine builders, even for very similar machines, different authors have used different instruction sets. The "basic instructions" are used map these differences on the relevant Counter machine variant models.

1 CLR(rY)
2 JZ (rX,*+4)
3 INC(rY)
4 DEC(rX)         
5 J  (*-4)
6 CONTINUE

1 CLR(rY)            9 JZ (rW,13) 
2 CLR(rW)           10 INC(rX)   
3 JZ (rX,8)         11 DEC(rW)   
4 INC(rY)           12 J (9) 
5 INC(rW)           13 CONTINUE
6 DEC(rX)          
7 J  (3)
8 ??

1 CPY(rX,r)       6 JZ(r0,3) 
2 CPY(rY,rW)      7 JZ(rW,9) 
3 JZ(r,7)         8 INC(r) 
4 DEC(r)          9 CONTINUE
5 DEC(rW)

[edit] Complex instructions

The Counter machine analysis on instruction sets preceded, and was a "theoretical laboratory" for, the RISC vs CISC features.

Many authors have augmented the basic counter machine model instruction set, with a more complex instructions, for this kind of studies.

[edit] Overloading

See Talk page.

[edit] NOTES

[edit] Reference Table Syntax

The symbols { [ ], → } and the syntax can be found in Boolos-Burgess-Jeffrey (2002) (pp.45ff). The meaning of the symbol → is derived from Melzak (1961) and used by Boolos-Burgess-Jeffrey (2002). For a discussion of the if-then-else construction see Footnote|IF-THEN-ELSE operator:

• [ ] =_def the phrase "the contents of"
• r =_def register with address/name/number "r". A "register" includes both an address/name/number and a contents [ ]:

Example: [ 3 ] =_def "contents of register with address/name/number '3' "

• → =_def the "arrow" denotes "replaces" in the sense of "delete/empty/zero present contents then copy into".

This is different than, for example "add to" (as in: throw a pebble into a hole) and "pick up and move to". For example: the two-variable instruction INC (r_j, r_j) might be defined as [ r_j ] +1 → [ r_k ], to be read as, "The contents of register r_j plus one replaces the original contents of register r_k, and the contents of register r_j remains the same. This is different than [ r_j ] +1 → [ r_k ], and 0 → [ r_j ] which signifies that the contents of register r_j was actually taken from r_j and moved into register r_k, thus cleaning out r_j, and then 1 added to r_k.

• IC =_def Instruction Counter-Register, the finite-state machine's state-register

Example: "[ IR ] + 1 → IR " is read in prose: "The contents of the finite-state machine's Instruction Register plus 1 is 'replaces the (previous) contents of' the Instruction Counter Register (ICR) ".

Example: " I_z → IR " means "Instruction number Iz replaces the (previous) contents of the Instruction Register."

• +1 =_def successor function S(a) = a' = a+1 (See Footnote|Successor model)
• -1 =_def predecessor function pd(a') = a (See Footnote|Successor model)

[edit] Choice of "Reference (Base) model"

This model does not use indirect addressing; see Random Access Machine reference model.

From either of two 3-instruction base sets all the other counter machine instructions can be derived. Both have advantages and disadvantages.

The model {INC, DEC, JZ} was chosen because a survey of the literature indicates it is more common, and its use is (arguably) easier.

In a historical and theoretical sense the second (the so-called "successor"-model) is arguably "more basic" because it closely resembles the Peano axioms, the operators of the primitive recursive functions, and the McCarthy Formalism. For more, see Footnote|Successor model; this footnote shows how the DECrement and JZ (Jump-if-Zero) instruction can be derived from the "successor" model.

[edit] Choice of instruction mnemonics

There is no conventional set of instruction names (mnemonics). Boolos-Burgess-Jeffrey (2002) do not bother with mnemonics at all. Minsky 1967 uses symbols such as " [ ' ] ". For the conditional and unconditional instructions, some authors such as Stone (1972) use "branch" in place of "jump". Branch sometimes is used "relatively" ('branch back three instructions') as opposed to "absolutely" ('jump to instruction #5'). Most authors use "goto" interchangeably with "jump". This reference will follow Knuth (1971) and use "Jump" (Jx, where x indicates the type of test)

Knuth's abbreviations-as-mnemonics are of particular interest to this reference model. Even without their definition, the reader may be able to guess the rough meaning of the mnemonics/abbreviations.

In Knuth's following list, n is actually a parameter specifying a particular register e.g. LD2, ST3, INC1. Their formation-principle seems to be (i) the use of English, (ii) no more than 3-4 letters, (iii) preferably not vowels (N_OPeration, MOVE are exceptions). "A" appended indicates a specific "accumulator register" e.g. LDA, STA, CMPA, INCA.

{ NOP, ADD, SUB, LDA, LDAN, LDn, STA, STn, J, CMP, CMPA, IN, OUT, MUL, DIV, HLT, MOVE, JMP, INCA, INCn }.

Note that DECrement (DEC), nor CoPY (CPY) are on in the list { DEC, DECA, CPY }. These will be added. A few more { JZ, JNZ, JE, JNE } will necessary and are formed using the initials Jump, Z, Not, Equals.

Compound instructions e.g. "JZDEC" will be the concatenation of the two simpler mnemonics.

[edit] Footnotes

Footnote|Successor model:

Some readers may argue that the "successor model" -- counter machine with instructions, where "JE" means "Jump if Equal", i.e.

{ CLR (r), INC(r), JE (r_j, r_k, z) }

is "more basic", because it closely resembles the Peano axioms and the operators of theprimitive recursive functions. Indeed the model can be found in Minsky (1967) (p. 192ff) in his discussion of a Turing equivalent set of operators called the McCarthy Formalism.

Minsky shows how to derive DEC (r) from the three-instruction successor-set (cf. p. 211) -- JZ is trivial --and he proceeds to use this second model in his discussion of its equivalence to the primitive recursive functions and the general-recursive functions (cf p. 212ff).

With this "successor" set the problem of the first set { INC, DEC, JZ } around what happens when DEC occurs on an empty register does not occur; however, the model requires JE to have a 3-parameter format: JE(r₁, r₂, z).

Formal Syntax:

In the following, the letter "r" will be put in front of a register number e.g. r0 in place of "0" to avoid confusion of "zero" with the register named "0", for example to avoid ambiguous symbolism such as "0 → 3". "z" is a number of an instruction I_z.

The following shows how the successor set { CLR (r), INC (r), JE (rj, rk, z) } creates the instruction set { INC (r), DEC (r), JZ (r, z) }. A similar treatment can be found in Minsky (p. 211) excepting that Minsky uses JNE -- Jump if Not Equal --rather than JE.

• (1) INC (r) is the same for both sets.

• (2) JZ (r_k, z) = JE (r0, r_k, z) ; contents of register "r0" must be 0

• (3) DEC (r5) requires the use of two scratch-pad registers #r2 & #r3. The algorithm proceeds by first clearing a scratch pad and testing input #r5 for 0, then (ii) clearing scratchpad #r3 and then, while contents of #r2 ≠ contents of #r5, incrementing #r2 so that #r3 is always one behind #r3, (iii) when #r2 is equal to #r5 (#r3 is one less than both), then clearing #r5 and copying #r3 back into #r5, (v) cleaning up the mess leaving only #r5 with contents.

NOTE: In the following example of "DEC (r5), rather than use a "free_variable" such as "r", we declare explicit register #r5. This emphasizes the point that each instance of DEC must be built separately with its own explicit register declared. This is because "DEC (r5)" is not "calling a subroutine" called DEC and "passing 5" to it, but rather "DEC (r5)" is its own little piece of 14-line "code" to be inserted (by hand or compiler) wherever it is desired (DEC (r4) would be its own piece of code, etc). This example emphasizes the fact that, once fixed, an instruction set such as { CLR, INC, JE } for a counter machine specifies hardware of the state machine, not "software patches". In the case of a RAM or RASP, indirect addressing would allow for true subroutines.

Footnote|IF-THEN-ELSE operator:

From Minsky (1967):

" f = (if p₁ then e₁ else e₁)

"This expression means

"See if p₁ is true; if so the value of f is given by e₁. If p₁ is false, the value of f is given by e₂." (Minsky 1967 pp. 192ff: Conditional Expressions; The McCarthy Formalism)

This type of operator can also be found as the CASE function defined in Kleene (1952) p. 229 #F ("mutually-exclusive predicates").

[edit] See also

• Counter machine the "main user" of RefLib.
• Register machine the "hub article" for other models. There are another "augmented models", and the respectives "reference models":
  • Pointer machine:Reference model (or RAMrefModel): augment the indirect addressing and the RefLib for it. Is used also on the Random access program machine.
  • Random access stored program machine:Reference model: base on the RAMrefModel.