Implement the Universal Machine emulator

The goal is to write a full program that emulates the Universal Machine from ICFP 2006 with the shortest code. The Universal Machine has a very simple instruction set explained here. The emulator has to read a filename from command-line argument, and run the file as the program, so your language has to support command-line arguments and stdin/out in some way. The emulator has to complete the sandmark within a reasonable time (not decades). Here's a short explanation of the instruction set:

The machine has eight registers each holding an 32-bit unsigned integer.
The machine holds an indexed set of arrays of 32-bit unsigned integer cells.
Shortly speaking, the allocation instruction returns an opaque 32-bit uint which is the handle to the created array, which has a static size, and holds 32-bit uint elements.
The 0'th array denotes the program. It is loaded from a big-endian file on startup.
There is also an Instruction Pointer which points to a cell in the 0 array.
On each step, an instruction is read from the cell the Pointer points to, and the Pointer is inceremented before anything is done.
The 4 most significant bits represent the opcode.
If the opcode is 13, then the next 3 bits represent the register, and the other 25 represent the number that is written into the said register.
Otherwise the 9 least significant bits represent three registers, say, A, B, and C, where C is represented by the 3 least significant bits.
Then depending on the opcode, the following happens:
0. A = B unless C == 0
1. A = B[C]
2. A[B] = C
3. A = B + C
4. A = B * C
5. A = B / C
6. A = ~(B & C)
7. The emulator exits
8. B = allocate(C)
9. deallocate(C)
10. output a character from C to stdout
11. input a character from stdin into C
12. copy the array B into the 0 array and set the Pointer to C

I have written a needlessly complex but totally fast implementation (ab)using x86_64 jitted assembly (the fun starts in emit()), which would for sure help you if you misunderstand some of the Machine's aspects.

• You have to decide if this should be code-golf or popularity-contest. They are exclusive. – Howard Dec 28 '13 at 18:44
• @Howard I see, thanks – mniip Dec 28 '13 at 18:45
• If I'm not mistaken, the machine is described as being Big Endian, not Little Endian. – Hasturkun Jan 15 '14 at 13:55
• @Hasturkun d'oh I always mess these up, I keep thinking Big Endian stands for "ending in the bigger byte" – mniip Jan 15 '14 at 15:32
• @mniip Big Endian and Little Endian are terms borrowed from Gulliver's Travels. The small people of Lilliput were at war with the small people of Blefuscu, because the Lilliputians were "Big Endians" who believed you should eat the big end of a boiled egg first, and the Blefuscans believed the reverse. The original Gulliver's Travels was a serious novel by Jonathan swift. The author was commenting on the stupidity of going to war over political and religious differences. Gulliver was forced to leave after being charged with treason for refusing to help out in the war. – Level River St Feb 10 '14 at 17:38

PHP: 443 416  384 bytes

<?php @eval(ereg_replace('[U-Z]','$\0',strtr('for(Y=[unpack("N*",join(file($argv[1])))];;A|=0){{W=Y[V=0][++U]
C&&A=B
A=Y[B][C+1]
Y[A][B+1]=C
A=B+C
A=B*C
A=bcdiv(PB),PC))*1
A=~B|~C
die
B=++Z
unset(Y[C])
echo chr(C)
C=fgetc(STDIN);C=ord(C)-(C=="")
Y[0]=Y[B|0];U=C
X[W>>25&7]=W&33554431;}}',['
'=>';}if((W>>28&15)==V++){',A=>'X[W>>6&7]',B=>'X[W>>3&7]',C=>'X[W&7]',P=>'sprintf("%u",'])));


*Revamped again*. It's as small as I can possibly get it now. I kept some variables down the far end of the alphabet so that the regex that inserts the $signs doesn't mangle the STDIN constant, so here's a little glossary: • U: instruction pointer • V: index of opcode that's currently being tested • W: current instruction word • X: the 8 general purpose registers • Y: main memory (each block is 1-based, since that's how unpack() returns arrays) • Z: id of next free memory block (will eventually overflow, but the sandmark only uses ~92 million) • A,B,C are the registers of the current instruction as in the spec Unsigned division is a subtle nuisance (the *1 is needed to ensure that large numbers cast back to the correct int) but the rest of the arithmetic is easy to keep 32-bit by ORing the arithmetic register with 0 (A|=0) after each instruction. I found this project really interesting but striving to minimize the character count made it slow and inelegant, so I also made a simple (not golfed) Java version, that can complete the sandmark in a few minutes instead of taking all day: import java.io.*; import java.util.HashMap; public class UniversalMachine { public static void main(String[] args) throws IOException { if (args.length == 0) { System.err.println("Program not specified."); System.exit(1); } int[] program; try (RandomAccessFile raf = new RandomAccessFile(args[0], "r")) { program = new int[(int)(raf.length() / 4)]; for (int i = 0; i < program.length; i++) { program[i] = raf.readInt(); } } HashMap<Integer,int[]> memory = new HashMap<>(); memory.put(0, program); int nextMemKey = 1; int[] R = new int[8]; // Registers int IP = 0; // Execution Finger (Instruction Pointer) loop: for (;;) { int ins = program[IP++]; int op = ins >>> 28; if (op == 13) { // Orthography int A = (ins >> 25) & 7; int num = ins & 0x01FF_FFFF; R[A] = num; } else { final int A = (ins >> 6) & 7; final int B = (ins >> 3) & 7; final int C = (ins >> 0) & 7; switch (op) { case 0: // Conditional Move if (R[C] != 0) R[A] = R[B]; break; case 1: // Array Index R[A] = memory.get(R[B])[R[C]]; break; case 2: // Array Amendment memory.get(R[A])[R[B]] = R[C]; break; case 3: // Addition R[A] = R[B] + R[C]; break; case 4: // Multiplication R[A] = R[B] * R[C]; break; case 5: // Division R[A] = (int)((R[B] & 0xFFFF_FFFFL) / (R[C] & 0xFFFF_FFFFL)); break; case 6: // Not-And R[A] = ~(R[B] & R[C]); break; case 7: // Halt break loop; case 8: // Allocation // note: must use C before setting B, as they may be the same reg memory.put(nextMemKey, new int[R[C]]); R[B] = nextMemKey++; break; case 9: // Abandonment memory.remove(R[C]); break; case 10: // Output System.out.print((char)R[C]); break; case 11: // Input R[C] = System.in.read(); break; case 12: // Load Program IP = R[C]; if (R[B] != 0) { memory.put(0, program = memory.get(R[B]).clone()); } break; } } } } }  • i don't think you need to adjust result of division to 32 bits because it is always smaller-than-or-equal-to the dividend, which is adjusted already – mniip Jan 17 '14 at 2:11 • Just out of curiosity, what does it look like ungolfed? – Tim Seguine Jan 17 '14 at 11:07 • @mniip It's a bit differently laid out now, but I do need to be careful with division because during the division the numbers are unsigned, and at every other moment they're signed. – Boann Jan 17 '14 at 15:03 Perl, 407 It looks like the question might seem too complex, actually it's very simple. I'm still very new to perl though, anyway here it is open$f,shift;binmode$f;push@{$m[0]},unpack'N',$b while read$f,$b,4;$z=2**32;while(){$o=$m[0][$p++];$a=$r[o>>6&7];b=$r[$o>>3&7];$c=\$r[$o&7];eval qw,$$a=($$b)if$$c$$a=$m[$$b][$$c]$m[$$a][$$b]=$$c$$a=($$b+$$c)%$z $$a=$$b*$$c%z$$a=$==$$b/$$c $$a=$$b&$$c^(z-1) exit$$b=scalar@m;$m[$$b]=[] undefm[$$c] print(chr$$c)$$c=ord(getc)$m[0]=[@{$m[$$b]}]if$$b;$p=c $r[$o>>25&7]=$o&33554431,[$o>>28].";";}


It runs really slow, probably 800x slower than the JITed x86_64 one.
Also, a friend of mine made a reference C implementation

• Is this a problem in the reference C code?: if(((Memory[++PC]>>28)&15) == 13) { Registers[(Memory[PC]>>25)&7] = (Memory[PC]&0x01ffffff); the instruction isn't cached, so any opcodes not 13 would pre-execute the next instruction, no? – luser droog Jan 18 '14 at 9:20

C, 924838825696646 623

I store a "pointer" (byte-offset) in the register designated b in the instruction, and use whatever register designates an array in the pseudocode in the same manner (or reverse, rather, to reconstitute a pointer) to access that array later. Still need to try the test program...

Edit: fixed instruction 12. change the pointer, not the instruction in memory. Count is with all comments, indents, and newlines removed.

Edit: It appears to be running now, assuming I'm interpreting the results correctly. :) The final realization was that the 0 array is indeed referenced by the handle 0, which may be found in an uninitialized register. A very twisted little machine! :)

Edit: rewrote debugging apparatus to use write instead of printf.... The idea here is to remove bugs. :) Edit: putchar() and getchar() are also no-nos with sbrk. It now works, and appears quite fast.

#define O(_)*a=*b _*c;B
#define B break;case
#define U unsigned
U*m,r[8],*p,*z,f,x,*a,*b,*c;main(int n,char**v){U char
u[4];z=m=p=sbrk(4);f=n>1?open(v[1],0):0;\
for(;x=*p++,1;){c=r+(x&7);b=r+((x>>3)&7);a=r+((x>>6)&7);switch(x>>28){case
0:*c?*a=*b:0;B
1:*a=(*b?m+*b:z)[*c];B
2:(*a?m+*a:z)[*b]=*c;B
3:O(+)4:O(*)5:O(/)6:*a=~(*b&*c);B
7:return 0;case
8:*b=1+(U*)sbrk(4*(1+*c))-m;(m+*b)[-1]=*c;B
9:B
10:*u=*c;write(1,u,1);B
12:*b?memcpy(z=sbrk(4*(m+*b)[-1]),m+*b,4*(m+*b)[-1]):0;p=&z[*c];B
13:a=r+((x>>25)&7);*a=x&0x1ffffff;}}}


For little-endian only, there's a 611 character version.

#define O(_)*a=*b _*c;B
#define B break;case
#define U unsigned
U*m,r[8],*p,*z,f,x,*a,*b,*c;main(int n,char**v){U char
0:*c?*a=*b:0;B
1:*a=(*b?m+*b:z)[*c];B
2:(*a?m+*a:z)[*b]=*c;B
3:O(+)4:O(*)5:O(/)6:*a=~(*b&*c);B
7:return 0;case
8:*b=1+(U*)sbrk(4*(1+*c))-m;(m+*b)[-1]=*c;B
9:B
//10:*u=*c;write(1,u,1);B //generic
10:write(1,c,1);B //little-endian
12:*b?memcpy(z=sbrk(4*(m+*b)[-1]),m+*b,4*(m+*b)[-1]):0;p=&z[*c];B
13:a=r+((x>>25)&7);*a=x&0x1ffffff;}}}


Indented and commented, with (extended) commented debugging apparatus.

//#define DEBUG 1
#include <fcntl.h> // open
#include <signal.h> // signal
#include <stdio.h> // putchar getchar
#include <string.h> // memcpy
#include <sys/types.h> // open
#include <sys/stat.h> // open
unsigned long r[8],*m,*p,*z,f,x,o,*a,*b,*c; // registers memory pointer zero file working opcode A B C
char alpha[] = "0123456789ABCDEF";
//void S(int x){signal(SIGSEGV,S);sbrk(9);} // autogrow memory while reading program
void writeword(int fd, unsigned long word){
char buf[8];
unsigned long m=0xF0000000;
int off;
for (off = 28; off >= 0; m>>=4, off-=4) {
buf[7-(off/4)]=alpha[(word&m)>>off];
}
write(fd, buf, 8);
write(fd, " ", 1);
}
int main(int n,char**v){
#ifdef DEBUG
int fdlog;
#endif
unsigned char u[4]; // 4-byte buffer for reading big-endian 32bit words portably
int cnt;

#ifdef DEBUG
fdlog = open("sandlog",O_WRONLY|O_CREAT|O_TRUNC, 0777);
#endif
z=m=p=sbrk(4); // initialize memory and pointer
//signal(SIGSEGV,S); // invoke autogrowing memory -- no longer needed
f=n>1?open(v[1],O_RDONLY):0; // open program
*m++=(((((*u<<8)|u[1])<<8)|u[2])<<8)|u[3]; // pack 4 bytes into 32bit unsigned in mem
sbrk(4); // don't snip the end of the program
}
sbrk(4);
for(cnt=0;x=*p++,1;cnt++){ // working = *ptr; ptr+=1
c=r+(x&7); // interpret C register field
b=r+((x>>3)&7); // interpret B register field
a=r+((x>>6)&7); // interpret A register field
#ifdef DEBUG
{int i;write(fdlog,"{",1);for(i=0;i<8;i++)writeword(fdlog, r[i]);
write(fdlog,"} ",2);
}
write(fdlog, alpha+(x), 1);
write(fdlog, alpha+(x>>28), 1);
#endif
switch(o=x>>28){ // interpret opcode
case 0:
#ifdef DEBUG
write(fdlog, "if(rX)rX=rX\n", 12);
#endif
*c?*a=*b:0;
break; // Conditional Move A=B unless C==0
case 1:
#ifdef DEBUG
write(fdlog, "rX=rX[rX]\n", 10);
#endif
*a=(*b?m+*b:z)[*c];
break; // Array Index A=B[C]
case 2:
#ifdef DEBUG
write(fdlog, "rX[rX]=rX\n", 10);
#endif
(*a?m+*a:z)[*b]=*c;
break; // Array Amendment A[B] = C
case 3:
#ifdef DEBUG
write(fdlog, "rX=rX+rX\n", 9);
#endif
*a=*b+*c;
break; // Addition A = B + C
case 4:
#ifdef DEBUG
write(fdlog, "rX=rX*rX\n", 9);
#endif
*a=*b**c;
break; // Multiplication A = B * C
case 5:
#ifdef DEBUG
write(fdlog, "rX=rX/rX\n", 9);
#endif
*a=*b/ *c;
break; // Division A = B / C
case 6:
#ifdef DEBUG
write(fdlog, "rX=~(rX&rX)\n", 12);
#endif
*a=~(*b&*c);
break; // Not-And A = ~(B & C)
case 7:
#ifdef DEBUG
write(fdlog, "halt\n", 5);
#endif
return 0; // Halt
case 8:
#ifdef DEBUG
write(fdlog, "rX=alloc(rX)\n", 13);
#endif
*b=1+(unsigned long*)sbrk(4*(1+*c))-m;
(m+*b)[-1]=*c;

break; // Allocation B = allocate(C)
case 9:
#ifdef DEBUG
write(fdlog, "free(rX)\n", 9);
#endif
break; // Abandonment deallocate(C)
case 10:
#ifdef DEBUG
write(fdlog, "output(rX)\n", 11);
#endif
//putchar(*c);
//*u=u[1]=u[2]=' ';
u[3]=(char)*c;
write(fileno(stdout), u+3, 1);
break; // Output char from C to stdout
case 11:
#ifdef DEBUG
write(fdlog, "rX=input()\n", 11);
#endif
//x=getchar();*c=x;
*c=u[3];
break; // Input char from stdin into C
case 12:
#ifdef DEBUG
#endif
*b?memcpy(z=sbrk(4*(m+*b)[-1]),m+*b,4*(m+*b)[-1]):0;
p=&z[*c];
break; // Load Program copy the array B into the 0 array, Ptr=C
case 13:
#ifdef DEBUG
write(fdlog, "rX=X\n", 5);
#endif
a=r+((x>>25)&7);*a=x&0x1ffffff; // Orthography REG=immediate-25bit
}
}
}

• Array handles are 100% opaque. No matter what you pass it, the program is supposed to use the same value when accessing arrays. P.S. i just tried compiling it, you're missing a couple includes. P.P.S. did you ever compile it? what's lbreak and how can you unary-* an int – mniip Jan 17 '14 at 10:40
• Yes. A little too eager. :) Updated code compiles with gcc on Cygwin. – luser droog Jan 17 '14 at 11:01
• @mniip So it's only array 0 that's designated by "number"? – luser droog Jan 17 '14 at 11:11
• just compiled it, it only executes 2 instructions out of sandmark: d000108f c0000030 and then exits – mniip Jan 17 '14 at 13:49
• I fixed one bug. It executes 7 instructions now before halting. – luser droog Jan 18 '14 at 8:35