Counter machine reference model

Counter machine reference model

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.

Contents

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).

Formal Definition

The Counter machine reference model consists of a finite set of registers r1 ... rn, each of which can hold a non-negative integer, r0 (always zero), and a finite list of instructions I1 ... Im. Each of the instructions in this list is one of the following:

  • INC(j) — increment the value of register rj 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 rj by 1, else the contents of r=0; go to the successor instruction.
  • JZ (j, z) — If the contents of register rj equals Zero then Jump to instruction Iz else go to the successor instruction.
  • HALT — halts the computation.

Formal Semantic:

Instruction Effect on register Effect on Instruction Counter (IC)
INC ( j ) [ j ] + 1 → j [IC] + 1 → IC
DEC ( j ) IF [ j ] > 0 THEN [ j ] - 1 → j ELSE 0 → j [ IC ] + 1 → IC
JZ ( j, z ) IF [ j ] =0 THEN Iz → IC ELSE [ IC ] + 1 ) → IC

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 strategy 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.

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.

Emulated instruction Implementation (script) Comments
J (i)

JZ (r0,i)

Go to i (unconditional jump); register #0 must contain 0.
JZ(rX, i1,i2)
  1. JZ (rX,i1)
  2. JZ (r0,i2)
IF rX=0 THEN i1 ELSE i2
DECJZ(r,i)
  1. JZ (r,*i)
  2. DEC(r)
Test r=0; if r = 0 then DEC
INCJ(r,i)
  1. INC(r)
  2. J (i)
INC and J.
CLR(r)
  1. JZ (r,*+3)
  2. DEC(r)
  3. J (*-2)
If r=0 goto *+3; if not then DEC and goto *-2
MOV(rX,rY)
1 CLR(rY)
2 JZ (rX,*+4)
3 INC(rY)
4 DEC(rX)         
5 J  (*-4)
6 CONTINUE
Move rX to rY, clearing contents of rX.
CPY(rX,rY)
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 ??
Copy rX into rY, rW must be free (at end rW=0).
CPY (k,r)
  1. CLR (r)
  2. ( INC (r) )k
Immediate (explicit) copy constant k from instructions into R: Clear R and ( INC(r) )1 ,..., ( INC(r) )k i.e. do k times. Alternatively: put constant in register #K: CPY (K, r1)
CMP(rX,rY,r)
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)
Compare rX with rY and returns on r (r=0 if rX equal rY).
ADD(rX,rX,r) ... in terms of JZ, DEC, J, CLR, INC, CPY. r=rX+rY; perhaps preserving the contents of rX and rY.
MUL(rX,rY,r) ... in terms of JZ, DEC, J, CLR, INC, CPY, ADD. MULtiply, r=rX*rY; perhaps preserving the contents of rX and rY.
SUB(rX,rY,r) ... in terms of ... SUBtract, r=rX-rY; perhaps preserving the contents of rX and rY.

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.

Emulated instruction Implementation (script) Comments
EXP(rX,rY,r) ... in terms of JZ, DEC, J, CLR, INC, CPY, ADD, MUL. EXPonential, r=rX**rY; perhaps preserving the contents of rX and rY.
... ... other "complex instructions".

Overloading

See Talk page.

NOTES

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 from, 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 (rj, rj) might be defined as [ rj ] +1 → [ rk ], to be read as, "The contents of register rj plus one replaces the original contents of register rk, and the contents of register rj remains the same. This is different from [ rj ] +1 → [ rk ], and 0 → [ rj ] which signifies that the contents of register rj was actually taken from rj and moved into register rk, thus cleaning out rj, and then 1 added to rk.
  • 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: " Iz → 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)

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.

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.

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 (rj, rk, z) }

is "more basic", because it closely resembles the Peano axioms and the operators of the primitive 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(r1, r2, 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 Iz.
Instruction Effect on register Effect on state-machine's Instruction Counter Register ICR
CLR ( r ) 0 → r [ IR ] + 1 → IR
INC ( r ) [ r ] + 1 → r [ IR ] + 1 → IR
JE ( rj, rk, z) If [ rj ] = [ rk ] THEN z → IR ELSE [IR] + 1 → IR

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 (rk, z) = JE (r0, rk, 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.

Label: Instr. #: Instruction: Formal equivalence: Comment
DEC (5): target register #5 contains n or 0
initialize: 1 CLR (r2) 0 → r2 clear scratch-pad register #r2
test_for zero: r2 JE (r5,r2,13) If [ r5 ] = [ r2 ] then 13 → IR else [ IR ] +1 → ICR If contents of target register=0 then done
3 CLR (r3) Ø → r3 clear scratch-pad register #3
increment_loop: 4 INC (r2) [ r2 ] +1 → 2 Increment register #2 until contents of #2= contents of #5
5 JE (r5,r2,8) If [ r5 ] = [ r2 ] then 8→ IR else [ IR ] +1 → IR
6 INC (r3) [ r3 ] +1 → r3 Contents of #3 will be one less than contents of #2
7 JE (r5,r5,4) If [ r5 ] = [ r5 ] then 4 → ICR else [ ICR ] +1 = ICR Unconditional jump
move(3,1):
8 CLR (r5) 0 → r5 clear target register #5
move(3,1)_loop: 9 JE (r5,r3, 12) If [ r5 ] = [ r3 ] then 12 → IR else [ IR ] +1 → IR clear scratch-pad register #2
10 INC (r5) [ r5 ] +1 → r5 Increment contents of register #5
11 JE (r5,r5,9) If [ r5 ] = [ r5 ] then 9→ IR else [ IR ] +1 → IR Unconditional jump to instruction 9
12 JE (r5,r5,10) If [ r5 ] = [ r5 ] then 10 → IR else [ IR ] +1 → IR Unconditional jump to instruction 10
13 CLR (r2) 0 → r2 clear scratch-pad register #2
clean_up: 14 CLR (r3) 0 → r3 clear scratch-pad register #3
done: 15 etc. etc. target register #5 contains n-1 or Ø

Footnote|IF-THEN-ELSE operator:

From Minsky (1967):

" f = (if p1 then e1 else e1)
"This expression means
"See if p1 is true; if so the value of f is given by e1. If p1 is false, the value of f is given by e2." (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").

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.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Counter machine — A counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded… …   Wikipedia

  • Counter machine models — This page supplements counter machine. Although some authors use the name register machine synonymously with counter machine , this article will give details and examples of only of the most primitive species the counter machine of the genus… …   Wikipedia

  • Register machine — In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent. Contents 1 Overview 2 Formal definition 3 …   Wikipedia

  • Random access machine — In computer science, random access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of indirect addressing of its registers. Like the… …   Wikipedia

  • Machine pistol — This article is about full auto or burst capable pistols. For semi automatic weapons, see semi automatic pistol. A fully automatic Steyr M1912, which was used as a side arm by the Austro Hungarian Army A machine pistol is a handgun style,[1]… …   Wikipedia

  • Model checking — This article is about checking of models in computer science. For the checking of models in statistics, see regression model validation. In computer science, model checking refers to the following problem: Given a model of a system, test… …   Wikipedia

  • Machine Robo Mugenbine — The current logo of the Machine Robo Mugenbine toyline. Machine Robo Mugenbine (マシンロボムゲンバイン?), also called Multiple General Node Combine System …   Wikipedia

  • Pointer machine — In theoretical computer science a pointer machine is an atomistic abstract computational machine model akin to the Random access machine.Depending on the type, a pointer machine may be called a linking automaton, a KU machine, an SMM, an… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Beechcraft Model 18 — Model 18 Instructor and pilot in a Beechcraft AT 7 doing navigation training at Kelly Field, TX. Role Trainer …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”