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 " testprintfn "%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 |> ignoreprintf "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?
No comments:
Post a Comment