13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You have to decide if this should be code-golf or popularity-contest. They are exclusive. \$\endgroup\$ – Howard Dec 28 '13 at 18:44
  • \$\begingroup\$ @Howard I see, thanks \$\endgroup\$ – mniip Dec 28 '13 at 18:45
  • \$\begingroup\$ If I'm not mistaken, the machine is described as being Big Endian, not Little Endian. \$\endgroup\$ – Hasturkun Jan 15 '14 at 13:55
  • \$\begingroup\$ @Hasturkun d'oh I always mess these up, I keep thinking Big Endian stands for "ending in the bigger byte" \$\endgroup\$ – mniip Jan 15 '14 at 15:32
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Level River St Feb 10 '14 at 17:38
6
\$\begingroup\$

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;
                }
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – mniip Jan 17 '14 at 2:11
  • \$\begingroup\$ Just out of curiosity, what does it look like ungolfed? \$\endgroup\$ – Tim Seguine Jan 17 '14 at 11:07
  • \$\begingroup\$ @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. \$\endgroup\$ – Boann Jan 17 '14 at 15:03
3
\$\begingroup\$

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]=[] undef$m[$$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

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – luser droog Jan 18 '14 at 9:20
2
\$\begingroup\$

C, 924 838 825 696 646 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: added comments.

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;\
while(read(f,u,4)){*m++=(((((*u<<8)|u[1])<<8)|u[2])<<8)|u[3];sbrk(4);}sbrk(4);\
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 
11:read(0,u,1);*c=*u;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
u[4];z=m=p=sbrk(4);f=n>1?open(v[1],0):0;while(read(f,u,4)){*m++=(((((*u<<8)|u[1])<<8)|u[2])<<8)|u[3];sbrk(4);}sbrk(4);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 //generic
10:write(1,c,1);B //little-endian
//11:read(0,u,1);*c=*u;B //generic
11:read(0,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
#include <unistd.h> // sbrk read
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
    while(read(f,u,4)){ // read 4 bytes
        *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;
                   read(fileno(stdin), u+3, 1);
                   *c=u[3];
                   break; // Input char from stdin into C
            case 12:
#ifdef DEBUG
                   write(fdlog, "load(rX)[rX]\n", 13);
#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
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – mniip Jan 17 '14 at 10:40
  • \$\begingroup\$ Yes. A little too eager. :) Updated code compiles with gcc on Cygwin. \$\endgroup\$ – luser droog Jan 17 '14 at 11:01
  • \$\begingroup\$ @mniip So it's only array 0 that's designated by "number"? \$\endgroup\$ – luser droog Jan 17 '14 at 11:11
  • \$\begingroup\$ just compiled it, it only executes 2 instructions out of sandmark: d000108f c0000030 and then exits \$\endgroup\$ – mniip Jan 17 '14 at 13:49
  • \$\begingroup\$ I fixed one bug. It executes 7 instructions now before halting. \$\endgroup\$ – luser droog Jan 18 '14 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.