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.
sumber
Jawaban:
PHP:
443 416384 byte* 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:
unpack()
mengembalikan array)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:
sumber
Perl, 407
Sepertinya pertanyaannya mungkin terlihat terlalu rumit, sebenarnya itu sangat sederhana.
Saya masih sangat baru untuk perl, bagaimanapun, ini dia
Ini berjalan sangat lambat, mungkin 800x lebih lambat dari yang x86_64 JITed.
Juga, seorang teman saya membuat referensi implementasi C
sumber
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?C,
924838825696646623Saya menyimpan "pointer" (byte-offset) dalam register yang ditunjuk
b
dalam 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
write
alih-alihprintf
.... Idenya di sini adalah untuk menghapus bug. :) Edit:putchar()
dangetchar()
juga no-no dengansbrk
. Sekarang berfungsi, dan muncul cukup cepat.Untuk little-endian saja, ada versi 611 karakter.
Diindentasi dan dikomentari, dengan (diperpanjang) berkomentar alat debugging.
sumber
lbreak
dan bagaimana Anda bisa unary-*
anint
d000108f c0000030
dan kemudian keluar