Terapkan emulator Mesin Universal

13

Tujuannya adalah untuk menulis program lengkap yang mengemulasi Mesin Universal dari ICFP 2006 dengan kode terpendek. Mesin Universal memiliki set instruksi yang sangat sederhana yang dijelaskan di sini . Emulator harus membaca nama file dari argumen command-line, dan menjalankan file sebagai program, sehingga bahasa Anda harus mendukung argumen command-line dan stdin / out dalam beberapa cara. Emulator harus menyelesaikan tanda pasir dalam waktu yang wajar (bukan dekade). Berikut ini penjelasan singkat tentang set instruksi:

Mesin memiliki delapan register masing-masing memegang bilangan bulat 32-bit unsigned.
Mesin ini menyimpan kumpulan array yang diindeks dari sel integer 32-bit yang tidak ditandai.
Singkatnya, instruksi alokasi mengembalikan uint 32-bit buram yang merupakan pegangan ke array yang dibuat, yang memiliki ukuran statis, dan memegang elemen uint 32-bit.
Array 0'th menunjukkan program. Itu diambil dari file big-endian saat startup.
Ada juga Pointer Instruksi yang menunjuk ke sel dalam array 0.
Pada setiap langkah, instruksi dibaca dari sel yang ditunjuk Pointer, dan Pointer dinaikkan sebelum ada sesuatu yang dilakukan.
4 bit paling signifikan mewakili opcode.
Jika opcode adalah 13, maka 3 bit berikutnya mewakili register, dan 25 bit lainnya mewakili nomor yang dituliskan ke register tersebut.
Kalau tidak, 9 bit paling signifikan mewakili tiga register, katakanlah, A, B, dan C, di mana C diwakili oleh 3 bit paling tidak signifikan.
Kemudian tergantung pada opcode, yang berikut ini terjadi:
0. A = B kecuali 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. Emulator keluar
8. B = mengalokasikan (C)
9. Deallocate (C)
10. mengeluarkan karakter dari C ke stdout
11. memasukkan karakter dari stdin ke C
12. salin array B ke dalam array 0 dan atur Pointer ke C

Saya telah menulis implementasi yang tidak perlu tapi sangat cepat (ab) menggunakan x86_64 assembly yang di-jitted (kesenangan dimulai di emit ()) , yang pasti akan membantu Anda jika Anda salah paham beberapa aspek Mesin.

mniip
sumber
Anda harus memutuskan apakah ini kontes kode-golf atau popularitas. Mereka eksklusif.
Howard
@Howard saya mengerti, terima kasih
mniip
Jika saya tidak salah, mesin ini digambarkan sebagai Big Endian, bukan Little Endian.
Hasturkun
@Hasturkun d'oh Saya selalu mengacaukan ini, saya terus berpikir Big Endian singkatan dari "berakhir dengan byte yang lebih besar"
mniip
1
@mniip Big Endian dan Little Endian adalah istilah yang dipinjam dari Gulliver's Travels. Orang-orang kecil Lilliput berperang dengan orang-orang kecil Blefuscu, karena para Lilliputian adalah "Big Endian" yang percaya Anda harus makan ujung besar telur rebus terlebih dahulu, dan Blefuscans percaya sebaliknya. Gulliver's Travels yang asli adalah novel serius karya Jonathan swift. Penulis berkomentar tentang kebodohan pergi berperang karena perbedaan politik dan agama. Gulliver terpaksa pergi setelah dituduh melakukan pengkhianatan karena menolak untuk membantu dalam perang.
Level River St

Jawaban:

6

PHP: 443 416  384 byte

<?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",'])));

* Dirubah lagi *. Sekecil yang saya bisa dapatkan sekarang. Saya menyimpan beberapa variabel di ujung alfabet sehingga regex yang menyisipkan tanda $ tidak memotong-motong konstanta STDIN, jadi inilah sedikit glosarium:

  • U: penunjuk instruksi
  • V: indeks opcode yang saat ini sedang diuji
  • W: kata instruksi saat ini
  • X: 8 register tujuan umum
  • Y: memori utama (setiap blok berbasis 1, karena itulah cara unpack()mengembalikan array)
  • Z: id dari blok memori bebas berikutnya (pada akhirnya akan meluap, tetapi sandmark hanya menggunakan ~ 92 juta)
  • A, B, C adalah register dari instruksi saat ini seperti dalam spesifikasi

Divisi unsigned adalah gangguan halus (the *1 diperlukan untuk memastikan bahwa sejumlah besar dilemparkan kembali ke int yang benar) tetapi sisa aritmatika mudah disimpan 32-bit dengan ORing register aritmatika dengan 0 ( A|=0) setelah setiap instruksi.


Saya menemukan proyek ini benar-benar menarik tetapi berusaha untuk meminimalkan jumlah karakter membuatnya lambat dan tidak elegan, jadi saya juga membuat versi Java yang sederhana (bukan golf), yang dapat menyelesaikan tanda pasir dalam beberapa menit daripada menghabiskan waktu seharian:

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;
                }
            }
        }
    }
}
Boann
sumber
saya tidak berpikir Anda perlu menyesuaikan hasil pembagian menjadi 32 bit karena selalu lebih kecil dari atau sama dengan dividen, yang sudah disesuaikan
mniip
Hanya karena penasaran, seperti apa ungolfed itu?
Tim Seguine
@ mniip Agak sedikit berbeda sekarang, tapi saya harus berhati-hati dengan pembagian karena selama pembagian angka-angka tidak ditandatangani, dan pada setiap saat mereka ditandatangani.
Boann
3

Perl, 407

Sepertinya pertanyaannya mungkin terlihat terlalu rumit, sebenarnya itu sangat sederhana.
Saya masih sangat baru untuk perl, bagaimanapun, ini dia

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].";";}

Ini berjalan sangat lambat, mungkin 800x lebih lambat dari yang x86_64 JITed.
Juga, seorang teman saya membuat referensi implementasi C

mniip
sumber
Apakah ini masalah dalam kode C referensi ?: if(((Memory[++PC]>>28)&15) == 13) { Registers[(Memory[PC]>>25)&7] = (Memory[PC]&0x01ffffff);instruksi tidak di-cache, sehingga opcode yang bukan 13 akan melakukan pra-eksekusi instruksi berikutnya, bukan?
luser droog
2

C, 924 838 825 696 646 623

Saya menyimpan "pointer" (byte-offset) dalam register yang ditunjuk bdalam instruksi, dan menggunakan register apa pun yang menunjuk array dalam pseudocode dengan cara yang sama (atau membalikkan, lebih tepatnya, untuk menyusun kembali pointer) untuk mengakses array itu nanti. Masih perlu mencoba program tes ...

Edit: komentar ditambahkan.

Sunting: instruksi tetap 12. ubah pointer, bukan instruksi di memori. Hitung dengan semua komentar, indentasi, dan baris baru dihapus.

Sunting: Tampaknya sedang berjalan sekarang, dengan asumsi saya menafsirkan hasil dengan benar. :) Realisasi terakhir adalah bahwa 0 array memang direferensikan oleh handle 0, yang dapat ditemukan di register yang tidak diinisialisasi. Mesin kecil yang sangat bengkok! :)

Sunting: menulis ulang alat debugging untuk digunakan writealih-alih printf.... Idenya di sini adalah untuk menghapus bug. :) Edit: putchar() dan getchar()juga no-no dengan sbrk. Sekarang berfungsi, dan muncul cukup cepat.

#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;}}}

Untuk little-endian saja, ada versi 611 karakter.

#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;}}}

Diindentasi dan dikomentari, dengan (diperpanjang) berkomentar alat debugging.

//#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
        }
    }
}
luser droog
sumber
Pegangan array 100% buram. Apa pun yang Anda lewati, program tersebut seharusnya menggunakan nilai yang sama ketika mengakses array. PS saya baru saja mencoba mengkompilasinya, Anda kehilangan pasangan termasuk. PPS apakah Anda pernah mengompilasinya? apa lbreakdan bagaimana Anda bisa unary- *anint
mniip
Iya. Agak terlalu bersemangat. :) Kode yang diperbarui mengkompilasi dengan gcc di Cygwin.
luser droog
@ mniip Jadi hanya array 0 yang ditunjuk oleh "angka"?
luser droog
baru saja dikompilasi, ia hanya menjalankan 2 instruksi dari sandmark: d000108f c0000030dan kemudian keluar
mniip
Saya memperbaiki satu bug. Ini mengeksekusi 7 instruksi sekarang sebelum berhenti.
luser droog