Counter machine reference model

From Wikipedia, the free encyclopedia
  (Redirected from Counter machine:Reference model)
Jump to: navigation, search

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.

Introduction[edit]

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[edit]

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)[edit]

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[edit]

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, i,i)
1 JZ (rX,i)
2 JZ (r0,i)
IF rX=0 THEN i ELSE i
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,*+)
2  DEC(r)
3  J (*-)
If r=0 goto *+; if not then DEC and goto *-
MOV(rX,rY)
1  CLR(rY)
2  JZ (rX,*+)
3  INC(rY)
4  DEC(rX)         
5  J  (*-)
6  CONTINUE
Move rX to rY, clearing contents of rX.
CPY(rX,rY)
 1  CLR(rY)         
 2  CLR(rW)          
 3  JZ (rX,)       
 4  INC(rY)        
 5  INC(rW)	    
 6  DEC(rX)          
 7  J  ()
 8  ??
 9  JZ (rW,)
10  INC(rX) 
11  DEC(rW)   
12  J () 
13  CONTINUE
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) ), ..., ( INC(r) )k i.e. do k times. Alternatively: put constant in register #K: CPY (K, r)
CMP(rX,rY,r)
1  CPY(rX,r) 	  
2  CPY(rY,rW)   
3  JZ(r,) 	  
4  DEC(r) 	  
5  DEC(rW)
6  JZ(r0,) 
7  JZ(rW,) 
8  INC(r) 
9  CONTINUE
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[edit]

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[edit]

See Talk page.

NOTES[edit]

Reference Table Syntax[edit]

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"[edit]

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[edit]

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[edit]

Successor model[edit]

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[edit]

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: 2 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 Ø

IF-THEN-ELSE operator[edit]

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[edit]