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.
źródło
Odpowiedzi:
PHP:
443 416384 bajtów* 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:
unpack()
zwraca tablice)Dzielenie bez podpisu jest subtelną uciążliwością (
*1
jest 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ń:
źródło
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
Działa naprawdę wolno, prawdopodobnie 800 razy wolniej niż JITed x86_64.
Również mój przyjaciel dokonał referencyjnej implementacji C.
źródło
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?DO,
924838825696646623Przechowuję „wskaźnik” (offset bajtowy) w rejestrze wskazanym
b
w 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ć
write
zamiastprintf
… Chodzi tutaj o usunięcie błędów. :) Edycja:putchar()
igetchar()
również nie są nosicielamisbrk
. Teraz działa i wydaje się dość szybki.Tylko dla little-endian dostępna jest wersja 611 znaków.
Wcięte i komentowane, z (rozszerzonym) komentowanym aparatem do debugowania.
źródło
lbreak
i jak można unary-*
sięint
d000108f c0000030
a następnie wychodzi