Juru Bahasa Penafsir Mandiri

25

Berdasarkan komentar oleh George Edison untuk pertanyaan ini , tulislah juru penterjemah mandiri terkecil.

  • Anda dapat menggunakan bahasa yang Anda pilih.
  • Bahasa kosong tidak masuk hitungan. Panjang program Anda harus minimal dua karakter.
  • Program ini tidak perlu menginterpretasikan seluruh bahasa, hanya subset lengkap fitur bahasa Turing (yang berisi penerjemah).
  • Quines tidak masuk hitungan.
  • Jangan gunakan evalfungsi bawaan bahasa Anda atau yang setara. Sama berlaku untuk apply, dll.
Hoa Long Tam
sumber
1
(Hmm .. aku harus melakukan sesuatu dengan /usr/bin/cat) bagaimana dengan Turing-kelengkapan?
Ming-Tang
@ SHiNKiROU: Terima kasih, saya tidak menganggap itu sebagai ujian. Diperbarui.
Hoa Long Tam
Terkait: Bahasa dengan penerjemah terkecil yang ditulis sendiri di Stack Overflow, meskipun ada beberapa (hanya satu?) Jawaban yang benar-benar mematuhi aturan yang diberikan di sini.
dmckee
1
Apakah kita harus menulis ulang parser Skema sexp itu, atau bisakah kita menganggap bahasa host tidak masalah?
JB
@JB: Utilitas pemrosesan string bahasa baik-baik saja, termasuk sexpparser.
Hoa Long Tam

Jawaban:

19

CI - 260

,(1p0(2d())(41(2d())('#((1p0()(10()(1d,1p$)=)<)$2d,1p$)(40(1d,1c$^)(''(1d,^)('0
'9('0-(,'0'9('0-2p10*+1p$)(!1d)~)$^)(0($)'$(^)'^(&)'&(c)'c(p)'p(d)'d(=)'=(<)'<(
>)'>(~)'~(.)'.(,)',(!)'!(+)'+(-)'-(*)'*(/)'/(%)'%()38p(1p3p0(3d)((2)(3)=p1d1p$)
=)$)~)=)=,2p$&)=)=)<)$$

320 → 260: Dorong pemetaan karakter-ke-instruksi sederhana, lalu lipat. Ini membagi dua ukuran kode per kas (ada 18 kas), tetapi biaya 30 karakter untuk melakukan lipat.

Ini adalah salah satu dari bahasa saya yang dikonstruksi, (juru bahasa dasar yang dihosting di Gist ). Ini unik karena bahasa tersebut mengubah fragmen kode. Artinya, string instruksi dalam bahasa berbasis stack ini digunakan untuk efek yang sama dengan struktur data atau penutupan dalam bahasa lain:

1^      # Push a 1, and "lift" it to be a code literal.
(5 +)   # Define a code literal.
&       # Join the two code literals, forming (1 5 +)
$       # Execute the code literal.

Penerjemah membangun fragmen kode dari seluruh program sebelum menjalankannya, sehingga ia juga dapat dianggap sebagai kompiler. Karena itu, penumpukan juru bahasa tidak menghasilkan overhead run-time eksponensial.

Juru bahasa memperoleh semua operatornya secara langsung dari juru bahasa induk. Namun, ia melakukan parsing dengan sendirinya, sehingga sebagian besar kode hanyalah urutan yang menerjemahkan karakter ke dalam literal kode masing-masing. Ini tidak sama dengan menggunakan eval, tetapi ia mengungkapkan betapa tergantungnya implementasi bahasa pemrograman pada semantik bahasa host / arsitekturnya.


Referensi bahasa:

Dapatkan penerjemahnya di sini

Blok

  • ( ... )

    Buat "blok", yang secara efektif adalah daftar instruksi tanpa konteks. Secara internal, itu bahkan bisa menjadi kode mesin.

  • blok $

    Panggil satu blok. Callee diberikan tumpukan global, yang termasuk blok dipanggil.

  • nilai ^

    Angkat nilai. Yaitu, ubah menjadi blok yang mendorong nilai itu.

    Contoh :

       1 ^
    == (1)
    
  • block1 block2 &

    Bergabunglah dua blok, membentuk satu yang menjalankan keduanya secara berurutan.

    Contoh :

       (1) (2) &
    == (1 2)
    

Manipulasi tumpukan

  • n c

    Salin nilai n stack.

    Contoh :

       5 4 3 2 1 0 3c
    == 5 4 3 2 1 0 3
    
  • n p

    Ambil nilai n stack (lepaskan, dan bawa ke depan).

    Contoh :

       5 4 3 2 1 0 3p
    == 5 4 2 1 0 3
    
  • n d

    Jatuhkan n nilai dari tumpukan. 0dadalah no-op.

    Contoh :

       5 4 3 2 1 0 3d
    == 5 4 3
    

Operator relasional

  • ab (on_true) (on_false) =

    Tes jika a sama dengan b. Konsumsi semua kecuali argumen pertama, dan panggil on_true atau on_false. Jika satu argumen nol dan yang lainnya adalah tipe lainnya, hasilnya akan salah. Kalau tidak, a dan b harus bilangan bulat.

    Contoh :

       3 3 ('0+ .) (1d) =
    == 3 '0+ .
    
  • ab (on_true) (on_false) <

    Tes jika a kurang dari b. a dan b harus berupa bilangan bulat.

    Contoh :

       3 5 (1d 5) () <
    == 3 1d 5
    == 5
    
  • ab (on_true) (on_false) >

    Uji apakah a lebih besar dari b. a dan b harus berupa bilangan bulat.

    Contoh :

       3 5 (1d 5) () >
    == 3
    
  • a lo hi (on_true) (on_false) ~

    Tes jika lo <= a <= hai. a, lo, dan hai harus bilangan bulat.

    Contoh :

       3 0 10 ('0+ .) (1d) ~
    == 3 '0+ .
    

I / O

  • c .

    Masukkan karakter c (mengkonsumsinya dari tumpukan).

  • ,

    Dapatkan karakter dan dorong ke tumpukan. Jika akhir file telah tercapai, -1 didorong.

  • c !

    Tidak mendapatkan karakter. Sama seperti ungetc di C, hanya satu pushback yang diizinkan.

Literal integer

  • 'c

    Dorong karakter c.

  • [0-9] +

    Dorong bilangan bulat desimal.

Hitung

  • ab +
  • ab -
  • ab *

    Tambahkan / kurangi / gandakan dua angka.

    Contoh :

       3 5 + 7 3 + *
    == 80
    
  • ab /

  • ab %

    Pembagian dan modulus. Tidak seperti di C, putaran ini menuju infinity negatif.

Lain-lain

  • #komentar kode

    The #karakter komentar segala sesuatu ke akhir baris.

  • )

    Digunakan untuk mengakhiri blok. Dapat digunakan untuk mengakhiri seluruh program juga.

  • Semua karakter lain diabaikan.

Joey Adams
sumber
24

Binary Lambda Calculus, 232 bits (29 bytes)

0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010

Lihat http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding untuk detail

John Tromp
sumber
2
Mengapa ini bukan jawaban yang diterima D: BLC luar biasa!
kucing
Bisakah Anda menjelaskannya sama sekali?
PyRulez
1
Sayangnya, Wikipedia menghapus halaman Binary Lambda Calculus. Halaman tromp.github.io/cl/cl.html saya menghubungkan ke salinan yang disimpan dan ke kertas yang saya tulis menjelaskan cara kerja penerjemah.
John Tromp
13

Saya tidak dapat mengambil kredit untuk yang ini , tetapi saya pikir saya akan membagikan yang menakjubkan ini:

Brainf *** (423)

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]
Peter Olson
sumber
10

BlockScript - 535

{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

BlockScript adalah setumpuk spaghetti sepele- bahasa yang saya buat khusus untuk tantangan ini. Penerjemah dasar adalah blockscript.c .

Program sampel (mencetak 15 angka Fibonacci pertama):

{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

Interpreter membaca kode sumber dan input program dari input standar, dalam urutan itu. Ini berarti bahwa untuk menjalankan juru bahasa dalam juru bahasa dalam sebuah juru bahasa, cukup salin dan tempel:

# Level 1
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 2
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 3
{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

Seperti film Inception , Anda tidak dapat mencapai lebih dari tiga level. Ini bukan masalah waktu, tetapi ruang. BlockScript sangat banyak kebocoran memori, dan ini ada hubungannya dengan bagaimana bahasa itu sendiri dirancang.


Referensi bahasa:

Dapatkan penerjemahnya di sini

Dalam BlockScript, "tumpukan" bukan array yang ditimpa oleh operasi selanjutnya seperti Anda mungkin terbiasa. Ini sebenarnya diimplementasikan sebagai daftar tertaut yang tidak dapat diubah, dan tumpukan tetap ada selama durasi program. Juga, tidak ada operator (kecuali@ ) yang menghapus nilai dari stack. Namun, modifikasi tumpukan hanya mempengaruhi blok tempat terjadinya.

Seleksi nilai

  • a melalui z

    Ambil item 0-25 dari tumpukan, dan dorong ke tumpukan. amengacu pada kepala, atau item yang paling baru didorong, dari tumpukan.

  • A melalui Z

    Ambil item 0-25 dari frame saat ini, dan dorong ke stack.

  • [

    Buka "bingkai" untuk memilih item dari referensi tumpukan (lihat di bawah) di kepala tumpukan. [tidak memerlukan pencocokan ], tetapi bingkai dibatasi secara leksikal. Dalam BlockScript, "lingkup" ditentukan oleh tanda kurung ( {... }) yang membentuk blok. Dengan demikian, membuka bingkai di dalam blok tidak akan berpengaruh pada kode di luar blok.

  • ]

    Tutup frame saat ini, kembali ke frame sebelumnya (jika ada).

Blok

  • { ... }

    Buat "blok", dan dorong ke tumpukan. Di dalam blok, tumpukan akan mulai seperti sebelum blok, kecuali tumpukan penelepon akan didorong di atas. Tumpukan gigih dan tidak berubah dalam BlockScript, jadi blok adalah penutup. Ungkapan tersebut {[berarti membuka blok, lalu membuka bingkai untuk mulai memilih argumen (menggunakan Amelalui Z). Nilai kembali blok adalah kepala tumpukan saat }tercapai.

    Contoh:

    '3 '2 '1 {[ b. d. f. B. C. D. A! } 'D 'C 'B d!;
    

    Ini mencetak 123BCD123DCB123BCD123DCB…. Huruf kecil mengacu pada nilai stack, sedangkan huruf besar merujuk pada argumen (karena frame diatur ke tumpukan pemanggil). A!mengambil kepala penelepon (yang dijamin menjadi blok yang dipanggil) dan memanggilnya. Jika Anda bertanya-tanya mengapa pembalikan terjadi BCDsetiap saat, itu karena B. C. D.mendorong argumen tersebut dalam urutan terbalik tepat sebelum blokir memanggil dirinya sendiri.

  • !

    Panggil satu blok. Dorong nilai kembali ke tumpukan.

Referensi tumpukan

  • &

    Buat referensi tumpukan, dan dorong ke tumpukan. Anggap ini sebagai "super-kontra", karena secara efektif mengeluarkan setiap item di stack dan membentuk "tuple" darinya. Idiom &[berarti bahwa apa pun a, b,c disebut sebelum sekarang dapat diakses dengan A, B, C(untuk sisa blok atau sampai ]ditemui).

    Sebagian karena & menangkap lebih banyak nilai daripada biasanya, BlockScript membocorkan memori dengan desain.

  • @

    Beralih ke tumpukan yang ditunjuk oleh referensi tumpukan a. Operator ini agak aneh, tetapi penerjemah mandiri BlockScript menggunakannya beberapa kali untuk menghindari keharusan mendorong argumen yang sama dua kali. Efek dari@ (atau operasi stack, dalam hal ini) terbatas pada blok di mana ia dipanggil. Selain itu, frame tidak terpengaruh oleh @, sehingga frame dapat digunakan untuk mengambil nilai yang Anda butuhkan setelah beralih tumpukan.

Ekspresi bersyarat

  • ? <Benar> : <on false>

    Ekspresi bersyarat, sama seperti operator ternary dalam C. Artinya, jika a"benar" (yaitu, tidak sama dengan nol bilangan bulat), maka lakukan <pada true> , jika tidak lakukan <pada false> .

I / O

Catatan: Input dan output dilakukan dalam UTF-8. "Karakter" adalah bilangan bulat yang sesuai dengan indeks Unicode.

  • ,

    Dapatkan karakter input berikutnya, dan dorong ke tumpukan. Jika akhir input tercapai, tekan -1.

  • .

    Keluarkan karakter di kepala tumpukan.

Literal integer / karakter

Catatan: Integer dan karakter adalah hal yang sama di BlockScript.

  • 'c

    Dorong karakter c.

  • [0-9] +

    Dorong bilangan bulat desimal.

Hitung

Operator ini hanya bekerja pada nilai integer.

  • +Compute b+ a(mendorong hasilnya, tetapi tidak membuang salah satu nilai).
  • -Hitung b- a.
  • *Hitung b* a.
  • /Hitung b/ a(pembagian bilangan bulat; putaran menuju infinity negatif).
  • %Hitung b% a(bilangan bulat modulus; putaran ke arah infinity negatif).

Operator relasional

Operator ini hanya bekerja pada nilai integer.

  • <Jika bkurang dari a, tekan 1, jika tidak tekan 0.
  • >
  • =

Lain-lain

  • # Komentar ke akhir baris
  • Program harus diakhiri dengan ;
  • Semua karakter lain diabaikan.
Joey Adams
sumber
2
Kristus. Ingin membagikan spek seperti yang Anda lakukan untuk CI?
Casey
@Casey: Menambahkan referensi.
Joey Adams
1
Apakah Anda tertarik mengetahui bahwa Anda sedang bermimpi? ... Di level 4.
Mateen Ulhaq
3

Zozotez LISP : 414

linefeeds yang ditambahkan untuk mendapatkan blok yang bagus tidak diperlukan dan tidak dihitung.

((\(E V A L)(E(r)'(())))(\(x e)(?(s x)(V x e)((\(b j)(?(= b ")(a j)(?(= b \)x
(?(= b ?)(?(E(a j)e)(E(a(d j))e)(E(a(d(d j)))e))(?(s b)(A b(E(a j)e)(E(a(d j)
)e))(E(a(d(d b)))(L(a(d b))j e)))))))(E(a x)e)(d x))))(\(x g)(? g(?(= x(a(a
g)))(d(a g))(V x(d g)))x))(\(f h v)(?(= f r)(r)(?(= f p)(p h)(?(= f s)(s h)(?
(= f a)(a h)(?(= f d)(d h)(?(= f =)(= h v)(c h v))))))))(\(k v i)(? k(L(d k)(
d v)(c(c(a k)(E(a v)i))i))i)))

Secara teori seharusnya bisa menjalankan sendiri, tetapi karena penerjemah asli adalah biner BrainFuck dan itu sendiri penerjemah saya hanya bisa menguji setiap bagian. Ketika diberikan sendiri dan ekspresi sederhana, (p p)saya pikir itu membutuhkan lebih banyak waktu daripada 40 menit saya telah menunggu sejauh ini dan saya menggunakan puasa sayajitbf untuk menjalankannya yang (salah) menggunakan Perl Inline-C untuk menjalankan kode C dengan cepat.

Tidak mungkin untuk mengimplementasikan seluruh Zozotez di Zozotez karena tidak memiliki cara untuk bermutasi kontra dan :(setq / define) memerlukan itu untuk memperbarui binding. Saya juga tidak menerapkan argumen begin / progn or & rest, makro dan argumen pencetakan khusus karena saya tidak menggunakannya dalam juru bahasa. Saya memang memasukkanp (mencetak) meskipun saya tidak menggunakannya sehingga program perlu mencetak kalkulasi mereka secara eksplisit seperti juru bahasa asli.

Yang ungolfed sama:

;; A stand alone Zozotez script need to be
;; contained in one expression, here with
;; all functions provided as arguments to
;; get them bound in the dynamic environment
((\ (E V A L)
  (E(r)'(())))
 ;; E (EVAL)
 (\ (x e)
   (? (s x)
      (V x e)
      ((\ (b j)
         (? (= b ") (a j)
         (? (= b \) x
         (? (= b ?) (? (E(a j)e) (E(a(d j))e) (E(a(d(d j)))e))
         (? (s b)
            (A b (E(a j)e) (E (a(d j))e))
            (E (a(d(d b))) (L(a(d b))j e)))))))
       (E (a x) e)(d x))))
 ;; V (VALUE / symbol->value)
 (\ (x g)
   (? g
      (? (= x (a (a g)))
         (d (a g))
         (V x (d g)))
      x))
 ;; A (APPLY) but just for primitives
 (\ (f h v)
   (? (= f r) (r)
   (? (= f p) (p h)
   (? (= f s) (s h)
   (? (= f a) (a h)
   (? (= f d) (d h)
   (? (= f =)
      (= h v)
      (c h v))))))))
 ;; L ( joint evLis / extend-env)
 (\ (k v i)
   (? k
      (L (d k) 
         (d v)
     (c (c (a k) 
           (E (a v) i)) 
        i))
      i)))
Sylwester
sumber
0

CHIQRSX9 + (mungkin tidak bersaing), 2 byte

+I

Tidak ada cara untuk menulis interpreter interpretasi mandiri dalam bahasa berbasis HQ9 + ini tanpa menggunakan I, yang menjalankan interpreter internal yang memproses STDIN.

pengguna8397947
sumber
1
Tidak ada dalam aturannya yang mengatakan bahwa penafsir diri bawaan dilarang. Dikatakan untuk eval, yang untuk ekspresi, bukan program.
Erik the Outgolfer
Bagaimana cara menghitung bilangan prima dalam bahasa ini?
pppery
@ppperry Xseharusnya membuat bahasa Turing-complete (dengan demikian dapat menghitung bilangan prima) dengan cara yang bergantung pada implementasi.
user8397947
Menurut halaman Esolang, Xperintah penerjemah Perl secara acak mengganggu program dan mengeksekusinya, yang berarti bahwa seseorang tidak dapat menggunakan selain perintah untuk secara perhitungan menghitung bilangan prima. Bisakah Anda memberi saya contoh penerjemah yang memungkinkan Anda menggunakan Xdengan cara yang Anda tentukan?
pppery
@ppperry Ternyata penerjemah yang ditulis dalam Perl adalah satu-satunya penerjemah, jadi tidak. Juga, bagaimana jika ada program yang menghitung bilangan prima ketika "diacak" dengan nilai tertentu?
user8397947
0

Concurrent Filesystem Befunge 98 - 53 \ 18 bytes (hampir pasti curang)

Interpreter 53 byte penuh tanpa batasan (walaupun saya belum menguji interaksi waktu yang rumit yang melibatkan pemisahan IP dan pembungkus):

v ;;;;;;;;
>]390'ai@
 t;;;;;;;;
;>zzzzz#;

Membaca input dari file bernama a dan menjalankannya. Itu tidak ditentukan dalam aturan bahwa kita tidak dapat menggunakan kode modifikasi diri.

Interpreter 18 byte yang tidak memungkinkan pembungkus (IP bergerak dari satu sisi kode dan mulai dari sisi yang berlawanan):

]210'ai@
t
><
pppery
sumber