Home Row

Home Row is a language by User:PuzzleHunter84 that uses only the non-shifted symbols on the home row of a US PC keyboard: a,s,d,f,j,k,l, and ; to make programs incredibly quick and easy to type. The symbols perform functions similar but not identical to bf:

a	"Add" 1 to the selected memory spot.
s	"Subtract" 1 from the selected memory spot.
d	move the memory pointer "Down" one memory spot.
f	move the memory pointer "Forward" one memory spot.
j	"Jump" over the next instruction if the current memory spot is zero.
k	"Kill and print" the current memory spot reseting it to 0 and printing the value as an ASCII character.
l	begin and end a "Loop" that runs if the current memory spot is nonzero and reruns after the second l each time if the current memory spot is nonzero.
;	end the program.

The memory values are stored in a 5x5 grid of memory spots that all initialize at 0 and the current memory spot is designated by a memory pointer that initializes in the top-left spot. If the memory pointer moves off the end of a row it goes to the beginning of that row and the same with columns, so essentially the memory grid is a 5x5 torus where the memory counter can potentially initialize anywhere.

Hello World Program

could be optimized

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak
aaaaaaaaaak;

Computational class

Home Row is Turing complete as a Minsky machine with at least 8 registers (2 are enough) can be compiled into it.

This construction uses the following grid layout:

S  t  t  0  ?
R0 t  R1 t  ?
R2 t  R3 t  ?
R4 t  R5 t  ?
R6 t  R7 t  ?

• S is the skip counter, which counts down command blocks to skip. When it is nonzero, other commands become rerouted to only affect the trash spots.
• t are trash spots, which become munged by rerouted commands.
• Rn are registers of the Minsky machine.
• The lone 0 spot is used to reset position to a known spot, with the help of the trash spots to its left, which will be kept nonzero.
• ? are spots whose contents are not used, although they may still be passed over.

The emulated Minsky machine program is represented as a sequence of assembly-like commands. This sequence is implicitly divided into command blocks by splitting after unconditional SKIP or HALT commands.

Overall encoded program structure:

afafafff l s <cmd>... s <cmd>... ... l

The first part of the program by default initializes S and the trash spots to its right to the value 1. This makes all the MM registers 0 and starts execution with the first command block.

The rest of the program consists of the encoding of each command block between the ls of the main program loop.

Each command block is encoded as s (to decrement the skip counter) followed by the encodings of each of its commands.

Execution of a command starts with the memory pointer at S, with the intent that it should have no effect on non-trash spots if S is nonzero.

SKIP n: jf an ffjfff

Skips ahead n command blocks, with the end of the program considered to wrap around back to the start.

HALT: jf ffj; ff
HALT (last command in program only): 

Halts the MM program. Normally this immediately halts Home Row as well. The second encoding (as nothing) instead causes the Home Row program to fall through the end of the main loop, which may be useful if you want to add something to the end of it.

ADD R0,k: jf d ak dddd ffjfff
SUB R0,k: jf d sk dddd ffjfff

Adds or subtracts a constant from a register. We use the upper left register as example, for others adjust the movement commands back and forth from S.

SKIP n IF R0==0: jf d jf dddd ak fjfjfff

Skips ahead n command blocks if register is zero.

Extension to 22 registers

It is possible to adjust the construction to fit as many as 22 Minsky machine registers.

S   T   0   R0  R1
R2  R3  R4  R5  R6
R7  R8  R9  R10 R11
R12 R13 R14 R15 R16
R17 R18 R19 R20 R21

However, this requires a more complicated construction and navigation. For example, with the register at the center:

SUB R9,1: faffff jff jdjdjfjf ffff s f jfjfjfjfjdjdjd fff
SKIP 2 IF R9==0: ddff s dddfff jf ddff jf ddd jd ddddfff jfjd ffff aa fjf dd a dddfff

In particular:

• Register spots normally store a value one higher than the emulated MM register.
• The exception to this is any register that is currently being branched on.
• Decrementing a MM register below zero is undefined behavior (the simpler construction above doesn't care about this).
• This ensures that all but a few of the spots in the grid are known to be nonzero at any given time, which keeps navigation manageable.

To describe the construction we need some notation:

• A+d and A+f are the spots below and to the right of the spot A, respectively.
• p(A,B) is a sequence of df commands moving from spot A to spot B.
  • When applied at an arbitrary starting spot, this works as a (wrapping) translation parallel to the AB one.
• q(A,B) is a sequence of conditional jd and jf commands moving from spot A to spot B, without ever starting at spots S or 0 (all other spots are assumed nonzero).
  • This is used when we know that the memory pointer is either at 0 or A, and we want to change it from A to B without moving the 0 case.

We can now describe the overall program structure and command encodings:

afaffafa d afafafafa d afafafafa d afafafafa d afafafafa l s <cmd>... s <cmd>... ... l

All spots except for 0 are initialized to 1.

SKIP n: jf an fjffff
HALT: jff j; jffff (or nothing for the last block)

ADD R,k: jff q(T,R+f) ffff ak f q(R+f,0) fff
SUB R,k: f ak ffff jff q(T,R+f) ffff sk f q(R+f,0) fff

For the upper right register R1, R1+f = S, so q(R1+f,0) does not exist. It can be replaced by ff q(R1,0).

SKIP n IF R==0:
 p(S,R) s p(R,S) jf p(S,R) jf p(R,0) jd p(R6,0) jfjd ffff an fjf p(0,R) a p(R,S)
 or
 p(S,R) s p(R,S) jd p(S,R) jd p(R,R14) jddjfjdjdjdjd ff an fjf p(0,R) a p(R,S)

The first option does testing with horizontal branching, the second with vertical branching. Each works for a different subset of the registers:

Horizontal         Vertical
S  T  0  +         S  T  0  *  *
*  *  *  *  *      *  *        *
*  *  *  *  *      *  *  +     *
*  *  *  *  *      *  *        *
      *  *  *      *  *  +     *

As the three cases S==0, R==0; S==0, R>0; S>0 are separated (into consecutive positions) by the initial branching, each of the above can be simply modified to reverse the test (this only breaks for the registers marked + in the above tables):

SKIP n IF R>0:
 p(S,R) s p(R,S) jf p(S,R) jf p(R,0) jfjfff jd p(R6,0) jfjd ffff an fjf p(0,R) a p(R,S)
 or
 p(S,R) s p(R,S) jd p(S,R) jd p(R,0) jdjd jddjfjdjdjdjd ff an fjf p(0,R) a p(R,S)

One-dimensional construction

Home Row may be useful for proving other languages Turing complete, especially ones with limited nesting of loops. The following construction tries to facilitate this:

• Only one row of the grid is used.
• The construction can be used with a non-wrapping grid, if backwards movement can be supported, at the cost of an extra zero spot.
• The width of the grid can be increased to fit more MM registers, which can avoid an extra level of exponential time blowup from using only 2 registers.
• Only non-negative values are used (as long as the Minsky machine has the same property).
• The only commands used are a, s, f, a backwards movement command "b" if the grid is non-wrapping, two ls, and the combination jf.

A similar notation as in the previous section will be used, with some adjustment:

• p(A,B) is a sequence of f and possibly "b" commands to move from spot A to B, or the same distance and direction from any other spot.
• q(A,B) is a sequence of jf commands that will move from A to B (always to the right of A) assuming all spots started from are nonzero.
• @{A} or @{A,B}: Because the usage of p and q got even more confusing than in previous sections, I have annotated on lines below what are the possible positions for the memory pointer at certain execution points.

The grid row's layout is:

Z0 S R0 ... Rn T (Z1)

Z0 and Z1 are permanently zero spots, which can be identified with each other if on a wrapping grid. The other spots are as in the previous sections.

Overall program structure:

f af af ... af a p(T,S) l s <cmd>... s <cmd>... ... l

Similar to the 22 register construction, all spots other than Z0 and Z1 are initialized to 1.

SKIP n: q(S,T) an p(T,Z1) q(R0,Z1) p(Z1,S)
     @{S}    @{S,T}  @{R0,Z1}   @{Z1}   @{S}
HALT: only by running off the final block

ADD R,k: q(R,T) p(S,R) ak p(T,Z1) q(R,T) p(Z1,S)
      @{S}           @{R,T}          @{Z1}    @{S}
SUB R,k: p(S,T) ak p(T,S) q(R,T) p(S,R) sk p(T,Z1) q(R,T) p(Z1,S)
      @{S}     @{T}    @{S}           @{R,T}           @{Z1}   @{S}

For conditional branching, we need the following subcommand:

r(R,C): a p(S,R) s q(R,T) a p(R,Z0) q(S,R) p(Z0,S) C p(T,Z1) q(S,R) p(Z1,T) s p(T,Z1) q(R,T) p(Z1,R) a p(R,S) s
      @{S}      @{R}    @{R,T}                  @{S,T}                   @{R,T}           @{Z1}    @{R}     @{S}

r(R,a) and r(R,s) add or subtract 1 from S, respectively, if MM register R is zero (i.e. the spot value is 1). This happens regardless of the (non-negative) value of S, i.e. even if the current command block isn't "running".

SKIP n IF R==0: r(R,a) (SKIP n) r(R,s)
SKIP n IF R>0: a r(R,s) (SKIP n) r(R,a) s

Implementations

• An x86 assembly compiler by User:Bangyen.
• A Python interpreter by User:BoundedBeans
  • It also has an input command (g) and the ability to use sizes other than 5x5 with simple commandline arguments.