Talk:Counter machine

From Wikipedia, the free encyclopedia

[edit] Sugestion for Referencial model

A reference model is necessary to:

• Simplify model comparations;
• To be didactic on examples and comparations;
• To be objective and "clean".
• To fix a "standard style" (and reader "see the same as the same") for the algorithms and examples into the articles.

Is this a good idea? Others have tried to do something like this on wikipedia for a computer "pseudocode" and failed. They gave it up. We will just end up in argument. Do the mnemonics really matter? For example, I usually use D ("Down") for "Decrement" and U ("Up") for "Increment". But I changed them because they are easier to remember as DEC and INC, Knuth used them in his MIX computer, they are common, as is CLR and CPY. Some folks use DCR for decrement. What is really important is to define them in more primitive terms (somehow) before you use them in the text. This is touched on in the algorithm characterizations article. See the four-variable table of "func(i/d,rS,i/d,rD)" below. wvbaileyWvbailey 04:57, 25 October 2006 (UTC)

Also, if I had a choice I would prefer to use the authors' original mnemonics, rather than a standard set. But, a standard table would help translate them.

I would prefer < rS > or < rD > (Source and Destination) where < > means "contents of". If you write < rS > then you can write, for immediate constants, "k → rS" or better "k → <rS>" means "constant k replaces contents of rS." I have also seen [ ] used in a similar way in a textbook (Boolos-Burgess-Jeffrey 2002). Except they write "[ rS ] → rD".

The "RefTable", if used, probably should go on register machine, perhaps on a separate page if it gets too big. wvbaileyWvbailey 04:43, 25 October 2006 (UTC)

The "Counter machine's referencial model" (for wikipedia articles) consists of a finite set of registers r₁ ... r_n, each of which can hold a non-negative integer, r₀=0 (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, then go to the next instruction.
• DEC(j) — decrement the value of register r_j by 1, then go to the next instruction.
• JZ (j, z) — check if the value of r_j is zero. If so, jump to instruction I_z; otherwise go to the next instruction.
• HALT — halts the computation.

[edit] Algorithm presentation style (scripting style)

Here we can fix "(for articles) standards". They are like on Assembly language articles. There are optional "clean styles".

[edit] "Ease to write" std styles

The simplest and ease to write (using wiki "#" mark for auto-addres):

1. DEC (2)
2. JZ (2,5)
3. INC (1)
4. JZ (0,1)
5. HALT

Or, for arbitrary address (and to use optional "goto labels")

10    DEC (2)
20    JZ  (2,50)
30    INC (1)
40    JZ  (0,10) 
50    HALT

[edit] "Better layout" std style

For a better layout and OPTIONAL use of "goto labels":

[edit] Referential Library

With the "referential library" (RefLib), the "referential model" can implement ALL other instruction sets from similar register machine models.

Indirect addressing must be dealt with. Any instruction can be turned into an indirect, even an unconditional jump. Here S denotes "Source-"register and "D" denotes "Destination-"register, A denotes accumulator or any other special register, "i" (or "iD", "iS") denotes "indirect", "d"= NOT(i) (or "dD", "dS") denotes direct. We might have to use e.g. "c" or "k" or something for "immediate constant", where "func" is some 2-parameter function such as ADD or COPY or INC r:

• func( iS, rS, iD, rD) e.g.
• func( d, rs, i, rD) e.g. CPY (d, A, i, rD) = STAi rD,
• func( i, rs, i, rD) e.g.
• func( d, rs, d, rD) e.g. CPY (rS,rD), INC (d,r,d,r) = INC r; DEC (d,r,d,r)= DEC r
• func( i, A, i, rD) ??
• func( i, A, d, rD) ??
• func( d, A, i, rD) e.g. STAi rD CPY (<A>,<<rD>>)
• func( d, A, d, rD) e.g. STA rD
• func( i, rS, i, A) ??
• func( i, rS, d, A) e.g. STAi rS
• func( d, rs, i, A) ??
• func( d, rS, d, A) e.g. LDAi rS
• func( d, A, d, A) e.g. INCA, DECA, CLRA, LDAA = nop,
• func( i, A, i, A) e.g. LDAiA (this is used by Schonhage!)

this is "irregular"

• func( d, A, k) e.g. LDA k; ADDA k; SUBA k; etc. CPY (d,k,A)= LDA k

The reason I have not used parenthesis is because the assemblers I have used for microcontrollers do not use them. But maybe parentheses are okay, like a function in EXCEL.

I find the following is much more expressive: <rS> means "contents of register S", <<rS>> indicates indirect addressing. But the "i" and "d" are pretty good because they act like parameters too. And they are Boolean (i.e. for example, perhaps "i"=1, "d"=0). I have simulated this on a spreadsheet recently -- all four parameters describe the functions nicely. wvbaileyWvbailey 04:19, 25 October 2006 (UTC)

Different register machine models (ex. with stack or accumulator) may be fix, with simple changes, different "referential models".

I have not seen a stack in any models. Some other accumulator instructions are:

{ LDA r; STA r; INCA; DECA; CLRA; CPYAN (copy accum to address pointer/iNdex register; ADA r (ADD (r,A)), etc., etc. } wvbaileyWvbailey 04:19, 25 October 2006 (UTC)

The "referential library" is a sinple list of "new instructions" implementarions, they may be see as microcoded instructions for a emulator strategy: each similar model with a different instruction set may be "emulated" by the RefLib.

The scripts are "near to formal". For formal ones we can imagine the use of a C preprocessor to expand the RefLib script templates into standard instructions. The scripts are for explaination and demonstration.

1 CLR(rY)
2 JZ (rX,6)
3 INC(rY)
4 DEC(rX)         
5 J  (2)
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)

Notes:

• <<r>> indicates indirect addressing; <r> indicates direct addressing; k indicates immediate adddressing (constant derived from instruction)
• The CONTINUE instruction is a "template instruction" for continuing into the context where the RefLib will be used.
• A convention may be to fix a "reserved register" for use as rW (wasting).

[edit] Working

Sugestions:

1. Create a Counter machine:Reference model article.
2. Transfer basic to there
3. Update Counter machine article with style (tables) and examples compatible with the recommendations fixed (to be consensus) here.

[edit] Clean Lead section

See Wikipedia:Lead section.

[edit] Style for Algorithms!

See Wikipedia:Algorithms on Wikipedia.

Sorry, but the above is bogus. I am sticking with the convention in Boolos-Burgess-Jeffrey (2002) because it is a convention to be found in a published text. wvbaileyWvbailey 20:56, 13 November 2006 (UTC)