Zaimplementuj emulator Universal Machine

13

Celem jest napisanie pełnego programu, który emuluje Universal Machine z ICFP 2006 z najkrótszym kodem. Uniwersalna maszyna posiada bardzo prosty zestaw instrukcji wyjaśniono tutaj . Emulator musi odczytać nazwę pliku z argumentu wiersza poleceń i uruchomić plik jako program, więc twój język musi obsługiwać argumenty wiersza poleceń i w jakiś sposób stdin / out. Emulator musi ukończyć test w rozsądnym czasie (nie dekadach). Oto krótkie wyjaśnienie zestawu instrukcji:

Maszyna ma osiem rejestrów, z których każdy zawiera 32-bitową liczbę całkowitą bez znaku.
Maszyna przechowuje indeksowany zestaw tablic 32-bitowych komórek całkowitych bez znaku.
Krótko mówiąc, instrukcja alokacji zwraca nieprzezroczysty 32-bitowy uint, który jest uchwytem utworzonej tablicy, która ma rozmiar statyczny i zawiera 32-bitowe elementy uint.
0-ta tablica oznacza program. Jest ładowany z pliku big-endian przy uruchomieniu.
Istnieje również wskaźnik instrukcji, który wskazuje komórkę w tablicy 0.
Na każdym kroku odczytywana jest instrukcja z komórki, na którą wskazuje Wskaźnik, a wskaźnik jest zwiększany, zanim cokolwiek zostanie zrobione.
4 najbardziej znaczące bity reprezentują kod operacji.
Jeżeli kodem operacji jest 13, to kolejne 3 bity reprezentują rejestr, a pozostałe 25 reprezentuje liczbę zapisaną w tym rejestrze.
W przeciwnym razie 9 najmniej znaczących bitów reprezentuje trzy rejestry, powiedzmy A, B i C, gdzie C jest reprezentowane przez 3 najmniej znaczące bity.
Następnie, w zależności od kodu operacji, następują:
0. A = B, chyba że 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 kończy
8. B = alokuje (C)
9. dezalokuje (C)
10. wypisuje znak z C na standardowe wyjście
11. wprowadza znak ze standardowego na C
12. skopiuj tablicę B do tablicy 0 i ustaw Wskaźnik na C

Napisałem niepotrzebnie złożoną, ale całkowicie szybką implementację (ab) przy użyciu zespolonego zespołu x86_64 (zabawa zaczyna się w emit ()) , co z pewnością pomoże ci, jeśli źle zrozumiesz niektóre aspekty Maszyny.

mniip
źródło
Musisz zdecydować, czy powinien to być konkurs golfa czy popularności. Są ekskluzywne.
Howard
@Howard Rozumiem, dzięki
mniip
Jeśli się nie mylę, maszynę określa się jako Big Endian, a nie Little Endian.
Hasturkun
@Hasturkun d'oh Zawsze to robię, ciągle myślę, że Big Endian oznacza „kończenie większego bajtu”
mniip 15.01.2014
1
@mniip Big Endian i Little Endian są warunkami zapożyczonymi z Guliwera. Mali ludzie z Lilliput prowadzili wojnę z małymi mieszkańcami Blefuscu, ponieważ Lilliputianie byli „Wielkimi Endianami”, którzy wierzyli, że najpierw powinniście zjeść duży koniec gotowanego jajka, a Blefuscans wierzyli w drugą stronę. Oryginalna podróż Guliwera była poważną powieścią Jonathana Swift. Autor komentował głupotę prowadzenia wojny z powodu różnic politycznych i religijnych. Guliwer został zmuszony do odejścia po oskarżeniu go o zdradę stanu za odmowę udzielenia pomocy w wojnie.
Level River St

Odpowiedzi:

6

PHP: 443 416  384 bajtów

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

* Ponownie odnowiony *. Jest tak mały, jak tylko mogę go teraz zdobyć. Trzymałem niektóre zmienne na drugim końcu alfabetu, aby wyrażenie regularne wstawiające znaki $ nie zmieniało stałej STDIN, więc oto mały słownik:

  • U: wskaźnik instrukcji
  • V: indeks testowanego kodu operacyjnego
  • W: aktualne słowo instrukcji
  • X: 8 rejestrów ogólnego przeznaczenia
  • Y: pamięć główna (każdy blok jest oparty na 1, ponieważ w ten sposób unpack()zwraca tablice)
  • Z: id następnego wolnego bloku pamięci (ostatecznie się przepełni, ale znak zużywa tylko ~ 92 miliony)
  • A, B, C są rejestrami bieżącej instrukcji jak w specyfikacji

Dzielenie bez podpisu jest subtelną uciążliwością ( *1jest to konieczne, aby duże liczby zostały zwrócone z powrotem do poprawnej liczby całkowitej), ale reszta arytmetyki jest łatwa do zachowania 32-bitowego poprzez ORing rejestru arytmetycznego za pomocą 0 ( A|=0) po każdej instrukcji.


Uważam ten projekt za naprawdę interesujący, ale dążenie do zminimalizowania liczby znaków sprawiło, że jest on powolny i nieelegancki, dlatego stworzyłem również prostą (nie golfową) wersję Java, która może ukończyć testowanie w kilka minut zamiast zajmować cały dzień:

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
źródło
nie sądzę, żebyś musiał dopasować wynik podziału do 32 bitów, ponieważ zawsze jest on mniejszy niż lub równy dywidendie, która jest już dostosowana
mniip
Z ciekawości, jak to wygląda bez golfa?
Tim Seguine
@mniip Teraz jest trochę inaczej, ale muszę uważać na podział, ponieważ podczas podziału liczby są niepodpisane i za każdym razem są podpisywane.
Boann
3

Perl, 407

Wygląda na to, że pytanie może wydawać się zbyt skomplikowane, w rzeczywistości jest bardzo proste.
Nadal jestem jednak bardzo nowy w Perlu, w każdym razie tutaj jest

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

Działa naprawdę wolno, prawdopodobnie 800 razy wolniej niż JITed x86_64.
Również mój przyjaciel dokonał referencyjnej implementacji C.

mniip
źródło
Czy jest to problem w referencyjnym kodzie C ?: if(((Memory[++PC]>>28)&15) == 13) { Registers[(Memory[PC]>>25)&7] = (Memory[PC]&0x01ffffff);instrukcja nie jest buforowana, więc wszelkie kody inne niż 13 wstępnie wykonałyby następną instrukcję, nie?
luser droog
2

DO, 924 838 825 696 646 623

Przechowuję „wskaźnik” (offset bajtowy) w rejestrze wskazanym bw instrukcji i używam dowolnego rejestru oznaczającego tablicę w pseudokodzie w ten sam sposób (lub odwrotnie, aby odtworzyć wskaźnik), aby uzyskać dostęp do tej tablicy później. Nadal musisz wypróbować program testowy ...

Edytuj: dodano komentarze.

Edycja: poprawiona instrukcja 12. zmień wskaźnik, a nie instrukcję w pamięci. Liczba jest usuwana z wszystkich komentarzy, wcięć i znaków nowej linii.

Edycja: Wygląda na to, że działa teraz, zakładając, że poprawnie interpretuję wyniki. :) Ostateczną realizacją było to, że do tablicy 0 rzeczywiście odnosi się uchwyt 0, który można znaleźć w niezainicjowanym rejestrze. Bardzo pokręcona mała maszyna! :)

Edycja: przepisałem aparat do debugowania, aby go używać writezamiast printf… Chodzi tutaj o usunięcie błędów. :) Edycja: putchar() i getchar()również nie są nosicielami sbrk. Teraz działa i wydaje się dość szybki.

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

Tylko dla little-endian dostępna jest wersja 611 znaków.

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

Wcięte i komentowane, z (rozszerzonym) komentowanym aparatem do debugowania.

//#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
źródło
Uchwyty tablic są w 100% nieprzezroczyste. Bez względu na to, co przekażesz, program powinien używać tej samej wartości podczas uzyskiwania dostępu do tablic. PS Właśnie próbowałem go skompilować, brakuje Ci kilku zestawów. PPS, czy kiedykolwiek go skompilowałeś? co lbreaki jak można unary- *sięint
mniip
Tak. Trochę zbyt chętny. :) Zaktualizowany kod kompiluje się z gcc na Cygwin.
luser droog
@mniip Czyli tylko tablica 0 jest oznaczona „liczbą”?
luser droog
właśnie go skompilowałem, wykonuje tylko 2 instrukcje poza piaskownicą: d000108f c0000030a następnie wychodzi
mniip
Naprawiłem jeden błąd. Wykonuje teraz 7 instrukcji przed zatrzymaniem.
luser droog