## Friday, July 16, 2010

### A Two-Instruction Virtual RISC

One of my favorite hobbies is building really tiny virtual computers. The experience has even paid off a time or two when I needed to create a compact domain-specific language (DSL). This post shows a really, really tiny virtual computer that is nevertheless capable of computing square roots using the method in the previous post, and checking the result using multiplication.

How tiny is this computer? So tiny that it has only two instructions:

inc i = Increment the value in register i by one and increment the instruction pointer (ip).

jzd i j = If the value in register i is zero, set the instruction pointer to j. If the value is not zero, decrement the value in register i by one and increment the instruction pointer.

The basic operation is simple: starting at ip=0, retrieve and execute an instruction. Continue until the ip is either less than zero or greater than the index of the last instruction. When complete, return as a result the value of a specified register.

Below is an implementation in F#. Note that the registers are implemented as indices into an array of integers. A single-step function, “step” is provided for debugging. Note that “run” has a basic safety check against infinite loops. The code also shows some basic operations and a test. (As always, all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

` `
`/// Increment register i and `
`/// advance the instruction pointer.`
`let inc i (d:int []) ip = `
`  d.[i]<-d.[i]+1`
`  ip+1`
` `
`/// If register i is zero, jump to ipj,`
`/// else, decrement register i and`
`/// advance the instruction pointer.`
`let jzd i j (d:int []) ip =`
`  match d.[i] with `
`  | 0 -> j`
`  | _ -> `
`    d.[i]<-d.[i]-1`
`    ip+1`
` `
`/// Single-step and instruction.`
`/// Returns the new ip, or`
`/// -1 on under/overrun or halt.`
`let step (d:int [])`
`         (p:(int []->int->int)[]) `
`         ip =`
`  match (ip<0) || (ip>=p.Length) with `
`  | true -> -1`
`  | _ -> p.[ip] d ip`
` `
`/// Run a program.`
`/// Halts on an ip of -1 or`
`/// when safety limit is reached.`
`/// Returns the value of register rtn.`
`let run (d:int []) `
`        (p:(int []->int->int)[]) `
`        rtn = `
`  let rec run0 count ip = `
`    match count>=System.Int32.MaxValue with`
`    | true -> failwith "Loop safty exceeded."`
`    | _ ->`
`    match step d p ip with `
`    | -1 -> d.[rtn]`
`    | ip0 -> run0 (count+1) ip0 `
`  run0 0 0`
` `
` `
`/// Five register memory.`
`let d5 = [|0;100;0;0;|]   `
` `
`/// Zero out register 1.`
`let pZero1 = `
`  [|`
`    (*00*) jzd 1 -1 `
`    (*01*) jzd 0 0  `
`  |]`
` `
`/// Set the value in register 1 to 5.`
`let pSet1To5 = `
`  [|`
`    // Zero out 1.`
`    (*00*) jzd 1 2 `
`    (*01*) jzd 0 0 `
`    // Increment 5 times.`
`    (*02*) inc 1   `
`    (*03*) inc 1`
`    (*04*) inc 1`
`    (*05*) inc 1`
`    (*06*) inc 1`
`  |]`
` `
`/// Copy the value in register 1 to `
`/// register 2.`
`let pCopy1To2 = `
`  [|`
`    (*00*) jzd 2 2  `
`    (*01*) jzd 0 0  `
`    (*02*) jzd 3 4  `
`    (*03*) jzd 0 2  `
`    (*04*) jzd 1 8  `
`    (*05*) inc 2     `
`    (*06*) inc 3     `
`    (*07*) jzd 0 4  `
`    (*08*) jzd 3 -1  `
`    (*09*) inc 1     `
`    (*10*) jzd 0 8   `
`  |]`
` `
`// Tests.`
`let x0 = run d5 pZero1 1`
`let x1 = run d5 pSet1To5 1`
`let x2 = run d5 pCopy1To2 2`
` `

Now here is the integer square root program. (In order to make the program more readable, I define some constants and macros which do not alter the basic operation of the machine.)

`/// Six register memory.`
`let d6 = [|0;0;0;0;0;0;|]   `
` `
`/// Give the registers labels.`
`let zero = 0         `
`let n = 1         `
`let odd = 2         `
`let sqrt = 3         `
`let tmp0 = 4         `
`let tmp1 = 5   `
` `
`// Jumping to -1 will halt.`
`let halt = -1   `
` `
`/// Define jmp macro.`
`// Note: this is just a macro`
`// dependent on there being a `
`// register with a constant value`
`// of zero.  It does not increase`
`// the size of the instruction set.`
`let jmp = jzd zero`
` `
`/// Compute the integer square root `
`/// of the value in register n, `
`/// and return the result in register sqrt.      `
`let pSqrt = `
`  [|`
`    // Set odd to 1.`
`    (*00*) jzd odd 2   `
`    (*01*) jmp 0  `
`    (*02*) inc odd   `
`    // Set tmp0 to zero.   `
`    (*03*) jzd tmp0 5  `
`    (*04*) jmp 3  `
`    // Set tmp1 to zero.`
`    (*05*) jzd tmp1 7  `
`    (*06*) jmp 5  `
`    // Copy odd to tmp0 and tmp1.`
`    (*07*) jzd odd 11`
`    (*08*) inc tmp0`
`    (*09*) inc tmp1`
`    (*10*) jmp 7  `
`    // Subtract tmp0 from n.`
`    (*11*) jzd tmp0 14`
`    (*12*) jzd n halt`
`    (*13*) jzd zero 11`
`    // Copy tmp1 to odd`
`    (*14*) jzd tmp1 17`
`    (*15*) inc odd`
`    (*16*) jmp 14`
`    // Next odd.`
`    (*17*) inc odd`
`    (*18*) inc odd`
`    // Increment Sqrt.`
`    (*19*) inc sqrt`
`    // Loop.`
`    (*20*) jmp 7`
`  |]`
` `
`// This is cheating a bit,`
`// but it beats looking at`
`// 80K copies of "inc n", lol.`
`// 80K is convenient because its `
`// square root is Sqrt(2)*100.`
`let test = 80000`
`d6.[n]<-test`
` `
`// Find the square root. `
`// Prints are formatted weird to fit in blog.`
`printf "The largest integer not exceeding "`
`printf "the square root of %i is " test`
`printfn "%i." (run d6 pSqrt sqrt)`
` `

And below is an extension of the above, being a multiplication program which computes the square of the result from above. (A good exercise would be to preserve some remainder from the previous program and add it back in here.)

` `
`// To check the answer, here is a `
`// multiplication routine. `
` `
`// Alias the older labels.`
`let mul0 = n`
`let mul1 = sqrt`
`let prod = odd`
` `
`/// Copy the value in mul1 (sqrt) to mul0 (n).`
`let pCopyMul1ToMul0 = `
`  [|`
`    // Zero out mul0.`
`    (*00*) jzd mul0 2  `
`    (*01*) jmp 0`
`    // Zero out tmp0.`
`    (*02*) jzd tmp0 4;  `
`    (*03*) jmp 2;  `
`    // Move mul1 to mul0,tmp0`
`    (*04*) jzd mul1 8;  `
`    (*05*) inc mul0    `
`    (*06*) inc tmp0     `
`    (*07*) jmp 4;  `
`    // Move tmp0 back to mul1.`
`    (*08*) jzd tmp0 halt  `
`    (*09*) inc mul1     `
`    (*10*) jmp 8   `
`  |]`
` `
` `
`/// Mutliply mul0 by mul1.`
`let pMul0TimesMul1 =`
`  [|`
`    // Zero out tmp0.`
`    (*00*) jzd tmp0 2;  `
`    (*01*) jmp 0;  `
`    // Zero out prod.`
`    (*02*) jzd prod 4;  `
`    (*03*) jmp 2; `
`    // Main loop on mul1.`
`    (*04*) jzd mul1 halt`
`    // Move mul0 to tmp0 and add to prod.`
`    (*05*) jzd mul0 9`
`    (*06*) inc tmp0`
`    (*07*) inc prod`
`    (*08*) jmp 5`
`    // Move tmp0 to mul0.`
`    // Loop back when done.`
`    (*09*) jzd tmp0 4`
`    (*10*) inc mul0`
`    (*12*) jmp 9`
`  |]`
` `
`// Mutlipy the square root by itself. `
`// Prints are formatted weird to fit in blog.`
` `
`run d6 pCopyMul1ToMul0 zero |> ignore`
` `
`printf "The largest perfect square not exceeding "`
`printf "%i is %i." test (run d6 pMul0TimesMul1 prod)`
` `

So simple that one could probably construct a programmable machine in wood and metal for programs such as the above! It is easy to imagine how it might work: simple counters that can always be incremented, but which will stop when decremented to zero. Something to transfer these stops at zero to program jumps. A program perhaps stored on a wheel that rotates from ip to ip. Etc.

It almost makes me want to head down to the workshop after dinner, lol.

-Neil

p.s. The above virtual machine programs may not be minimal. They were the obvious approaches.

p.p.s. Isn't it neat how F# allows the creation of a domain-specific language using arrays that looks almost like source code for a real assembly language program?