EDIT: Seperti yang Anda duga, ada bug pada penerjemah resmi: urutan komposisi .
terbalik. Saya memiliki dua versi penerjemah, dan menggunakan yang salah di sini. Contoh-contoh juga ditulis untuk versi yang salah ini. Saya telah memperbaiki juru bahasa di repositori, dan contoh-contoh di bawah ini. Penjelasannya >
juga agak ambigu, jadi saya sudah memperbaikinya. Juga, permintaan maaf untuk ini sudah begitu lama, saya terjebak dalam beberapa hal kehidupan nyata.
EDIT2: Penerjemah saya memiliki bug dalam implementasi .
yang tercermin dalam contoh (mereka bergantung pada perilaku yang tidak ditentukan). Masalahnya sekarang sudah diperbaiki.
pengantar
Shift adalah bahasa pemrograman fungsional esoteris yang saya buat beberapa tahun yang lalu, tetapi diterbitkan hari ini. Ini berbasis stack, tetapi juga memiliki currying otomatis seperti Haskell.
Spesifikasi
Ada dua tipe data di Shift:
- Fungsi, yang memiliki arity positif sewenang-wenang (jumlah input), dan yang mengembalikan daftar output. Misalnya, fungsi yang menggandakan inputnya hanya memiliki arity 1, dan fungsi yang menukar kedua inputnya memiliki arity 2.
- Kosong, yang semuanya identik dan tidak memiliki tujuan selain tidak berfungsi.
Program Shift terdiri dari nol atau lebih perintah , yang masing-masing merupakan karakter ASCII tunggal. Total ada 8 perintah:
!
( berlaku ) memunculkan fungsif
dan nilaix
dari tumpukan, dan berlakuf
untukx
. Jikaf
memiliki arity 1, daftarf(x)
ditambahkan ke bagian depan tumpukan. Jika memiliki arityn > 1
,(n-1)
fungsi -ary barug
didorong ke stack. Dibutuhkan input dan pengembalian .x1,x2,...,xn-1
f(x,x1,x2,...,xn-1)
?
( kosong ) mendorong yang kosong ke tumpukan.+
( klon ) mendorong ke stack fungsi yang tidakx
dikenal yang menggandakan inputnya: nilai apa pun dipetakan ke[x,x]
.>
( shift ) mendorong ke stack fungsi unary yang mengambiln
fungsi -aryf
, dan mengembalikan(n+1)
fungsi -aryg
yang mengabaikan argumen pertamanyax
, memanggilf
yang tersisa, dan mengetukx
di depan hasilnya. Misalnya,shift(clone)
adalah fungsi biner yang mengambil inputa,b
dan mengembalikan[a,b,b]
./
( fork ) mendorong ke stack fungsi terner yang mengambil tiga inputa,b,c
, dan mengembalikan[b]
jikaa
kosong, dan[c]
sebaliknya.$
( Panggilan ) dorongan untuk stack fungsi biner yang muncul fungsif
dan nilaix
, dan berlakuf
untukx
persis seperti!
yang dilakukannya..
( rantai ) mendorong ke stack fungsi biner yang muncul dua fungsif
dang
, dan mengembalikan komposisi mereka: fungsih
yang memiliki arity yang sama denganf
, dan yang mengambil inputnya secara normal, berlakuf
untuk mereka, dan kemudian sepenuhnya berlakug
untuk hasil (panggilan) sebanyak yang ditentukan arity), dengan item yang tidak digunakan dari output yangf
tersisa dalam hasilh
. Sebagai contoh, anggap ituf
adalah fungsi biner yang mengkloning argumen keduanya, dang
adalah panggilan . Jika tumpukan berisi[f,g,a,b,c]
dan kami lakukan.!!
, maka berisi[chain(f,g),a,b,c]
; jika kita lakukan!!
selanjutnya, makaf
pertama kali diterapkana,b
, berproduksi[a,b,b]
, kemudiang
diterapkan pada dua elemen pertama itu karena aritynya adalah 2, menghasilkan[a(b),b]
, dan tumpukan akhirnya akan[a(b),b,c]
.@
( katakanlah ) mendorong fungsi unary yang hanya mengembalikan inputnya, dan mencetak0
jika itu kosong, dan1
jika itu adalah fungsi.
Perhatikan bahwa semua perintah kecuali !
hanya mendorong nilai ke tumpukan, tidak ada cara untuk melakukan input, dan satu-satunya cara untuk menghasilkan apa pun adalah dengan menggunakan @
. Suatu program ditafsirkan dengan mengevaluasi perintah satu per satu, mencetak 0
s atau 1
s setiap kali "katakan" dipanggil, dan keluar. Perilaku apa pun yang tidak diuraikan di sini (menerapkan blank, menerapkan stack dengan panjang 0 atau 1, memanggil "chain" pada blank, dll.) Tidak terdefinisi: penerjemah mungkin macet, gagal dalam diam, meminta input, atau apa pun.
Tugas
Tugas Anda adalah menulis juru bahasa untuk Shift. Ini harus mengambil dari STDIN, baris perintah, atau argumen fungsi program Shift untuk ditafsirkan, dan mencetak ke STDOUT atau mengembalikan hasil yang dihasilkan (mungkin tak terbatas) dari 0
s dan 1
s. Jika Anda menulis suatu fungsi, Anda harus dapat mengakses keluaran panjang tak terbatas dengan beberapa cara (generator dengan Python, daftar malas di Haskell, dll). Atau, Anda dapat mengambil input lain, nomor n
, dan mengembalikan setidaknya n
karakter dari output jika lebih lama dari n
.
Hitungan byte terendah menang, dan celah standar tidak diizinkan.
Uji Kasus
Program Shift ini mencetak 01
:
?@!@@!
Mulai dari kiri: dorong kosong, dorong say , lalu terapkan say ke kosong. Ini output 0
. Kemudian, mendorong mengatakan dua kali, dan menerapkan kedua mengatakan yang pertama. Ini output 1
.
Program ini berulang selamanya, tanpa menghasilkan output:
$+.!!+!!
Tekan panggilan dan klon , lalu terapkan rantai ke mereka (kita perlu dua !
s karena rantai adalah fungsi biner). Sekarang stack berisi fungsi yang mengambil satu argumen, menggandakannya, dan memanggil salinan pertama pada argumen kedua. Dengan +!!
, kami menduplikasi fungsi ini dan memanggilnya sendiri.
Program ini mencetak 0010
:
?@$.++>!.!!.!!.!!!!+?/!!!@!@>!!!
Dorong kosong dan katakan . Kemudian, buat fungsi biner yang menyalin argumen kedua b
, lalu salin yang pertama a
dan buat dengan sendirinya, lalu terapkan komposisi ke salinan b
, kembali [a(a(b)),b]
. Terapkan untuk berkata dan kosongkan, lalu terapkan katakan pada dua elemen yang tersisa di tumpukan.
Program ini mencetak 0
. Untuk setiap !!!
yang Anda tambahkan, ia mencetak tambahan 0
.
?@+$>!>!+>!///!!>!>!.!!.!!.!!+!!!!
Dorong kosong dan katakan . Kemudian, buat fungsi terner yang mengambil f,g,x
input dan pengembalian [f,f,g,g(x)]
. Kloning fungsi itu, dan terapkan pada dirinya sendiri, katakanlah , dan kosong. Aplikasi ini tidak mengubah tumpukan, jadi kita dapat menerapkan fungsi lagi sebanyak yang kita inginkan.
Program ini mencetak urutan tanpa batas 001011011101111...
, di mana jumlah 1
s selalu bertambah satu:
@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!
Repositori berisi versi beranotasi.
sumber
f(x1, x2, ..., xn)
dang(y1, y2, ..., ym)
. Memanggil.
muncul keduanya dan mendorong suatu fungsih(z1, z2, ..., zn)
. Sekarang Anda bisa makan semua argumen itu dengan secara bertahap menyentuhnya!
. Setelahn
aplikasi seperti itu, fungsi yang tersisa hanya memiliki satu argumen, dan pada saat itu ia menghitungf(z1, z2, ..., zn)
(yaituf
diterapkan pada semua argumen yang Anda curry), yang mendorong beberapa nilai baru, dan kemudian segera mengkonsumsim
nilai dari stack dan memanggilnyag
..
bekerja persis seperti yang dijelaskan Martin, kecuali jikaf
mengembalikan daftar kurang darim
nilai, hasilnya tidak terdefinisi (komposisinya arityn
, sehingga tidak dapat memakan lebih banyak argumen dari tumpukan). Pada dasarnya, outputf
digunakan sebagai tumpukan sementara, yangg
didorong dan diterapkanm
kali menggunakan!
, dan hasilnya ditambahkan ke tumpukan utama.Jawaban:
Python 2,
752667534506445436427404398393 byteIni tidak berarti singkat ... tapi saya melakukan yang terbaik. Setiap saran bermain golf akan sangat dihargai ...
EDIT6: Ini sekarang skrip bukan fungsi. Simpan ke file (shift.py, forex), lalu jalankan dengan
$ python shift.py '<my_input>'
. Pastikan untuk memasukkan input dalam tanda kutip tunggal, atau bash akan menjadi gila dengan karakter input.EDIT7: Aaaaaa dan ... itu tidak dapat dibaca lagi. Tapi saya menghilangkan 23 byte lagi, jadi itu bagus, saya kira? Saya akan memposting versi yang tidak serigala juga.
EDIT8: Satu golf lagi, terima kasih kepada @Zgarb.
EDIT: terima kasih kepada @DLosc atas bantuan golfnya! Berhasil menguranginya hingga 85 byte.
EDIT2: memotong satu ton pembungkus yang tidak perlu, dan menjatuhkan 133 byte lagi!
EDIT3: ... dan 28 lainnya berkat @ Sp3000 dan @orlp dalam obrolan!
EDIT4: dengan bantuan dari @orlp & @ Sp3000, menghapus semua dekorator dan sekarang lebih pendek 61 byte.
EDIT5: bantu akuuuu, aku tidak bisa berhenti bermain golf ini .... 9 byte lagi hilang. Menyingkirkan pernyataan cetak akhir akan menghemat 7 lainnya, tetapi kemudian jika Anda menjalankan m () dalam satu lingkaran, semua output berada pada baris yang sama ... apakah itu oke?
Berikut ini adalah versi yang tidak dipisahkan:
Ide dasarnya adalah bahwa daftar python berfungsi dengan sangat baik sebagai tumpukan, dan dengan menyimpan
u=k.append
, saya tidak hanya menyimpan karakter,tetapi saya juga dapat menggunakan(tidak lagi!).@u
sebagai dekorator untuk mendorong fungsiKarena beberapa fungsi yang bekerja pada fungsi n-arity harus dapat menerima sejumlah argumen yang berubah-ubah, saya harus menggunakan
*args
, yang berarti bahwa rencana awal saya untuk melacak f.func_code.co_argcount harus diganti oleh arity atributdekorator.Dalam hal menangani program tak terbatas, interpreter berjalan hingga mencapai kedalaman rekursif maksimal; penangan RuntimeError di bagian bawah telah keluar dengan tenang pada saat itu, dan kemudian mencetak string keluaran saat ini.
Kasus uji:
sumber
['1','0'][...]
dengan adil'10'[...]
. 3) Mengapax is 0
dan tidakx==0
(ataux<1
)? 4) Jangan repot-repot menentukanRuntimeError
, cukupexcept
lakukan. 5) Karena Anda menggunakan Python 2, tab dan spasi dihitung sebagai level indentasi yang berbeda - jelek, tetapi seharusnya menghemat ~ 25 byte.x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))
- operator logis masih mengalami hubungan arus pendek, tetapi menggunakan lebih sedikit karakter daripada ternary. Kemudian simpan byte lain dengan menggunakanx.a-1
sebagai kondisi (0 / false jikax
adalah 1, nol / true sebaliknya) dan menukar 'kemudian' dan 'lain' ekspresi:x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y)
. (Harus punya tambang lagi sekarang setelah kamu melewati saya ...; ^))x.a==1
benar tetapix(y)
mengembalikan sesuatu yang salah, ia mencoba untuk mengevaluasiu(...)
juga. Tapi sepertinya Anda tidak perlu menyimpan 3 byte yang sangat sedikit yang akan memberi Anda! Saya mengakui, tuan: Anda telah melampaui saya.RuntimeError
saat saya hanya meminta pengguna untuk mengarahkan ulang stderr ... jadi kami mungkin bahkan berdalih. ; ^)*_
dalam lambda?Ghostscript
Belum bermain golf, karena saya masih harus mengerjakan fungsi parsing.
Implementasi ini menggunakan
_
dan:
bukannya>
dan/
, dan mengharuskan semua karakter program dipisahkan dengan spasi. Ini karena>
dan/
bukan nama yang valid di Postscript, dan operator tidak membatasi sendiri, tetapi ini akan diperbaiki ketika saya menulis parser.Bagian pertama dari kode harus cukup transparan, karena hanya mengulangi definisi fungsi operator. Keajaiban terjadi dalam definisi
!
.Cara
!
kerja sederhana: Pertama, ia menambahkan argumenx
untukf
dengan awalanx
dengan isif
, mendorong kembali di stack, dan penamaan salinan hasilnyafun
.Kemudian membungkus seluruh tumpukan sebagai array.
.runandhide
adalah ekstensi Ghostscript untuk menjalankan kode sandboxed, menyembunyikan konten array sebelumnya dari prosedur itu dipanggil. Thedict
perintah mendorong kamus baru pada stack dict, mempersempit ruang lingkup nama ditetapkan dalam sampaiend
muncul itu mundur. Itu juga menggantikan=only
(operator keluaran saya gunakan dalam@
) dengan yang dummy, menekan output selama uji coba.stopped
adalah setara PostScript daritry
pernyataan yang ditemukan dalam bahasa lain, dan itu mengembalikan true jika prosedurnya melemparkan kesalahan, dan salah jika berlari ke penyelesaian.Setelah uji coba
fun
selesai, program mengembalikan tumpukan asli dari array tersembunyi, dan jikafun
selesai tanpa kesalahan, ia kemudian menjalankannya secara nyata, menjaga hasilnya.sumber
Python3,
685670634633 byteSaya cukup yakin ini adalah hal terpanjang yang pernah saya mainkan. Ini digunakan untuk menjadi agak mudah dibaca, tapi berikut @ saran sirpercival telah dieliminasi bahwa kelemahan!
k
adalah stack, yang berisi fungsi yang direpresentasikan sebagai string seperti"h(0,0)"
(yang merupakan c h ain ). Ketika fungsi dilewatkan sebagai argumen ke fungsi lain, itu akanrepr
'd dan semua angka bertambah:"h('h(1,1)',0)"
. Setelah semua0
s diganti dalam suatu fungsi, semuanya dilewatkan keeval
, dengan demikian memanggil fungsi Python yang sesuai - sebagian besar adalah fungsi lambda yang dihasilkan dari string besar di baris 6 denganexec
di baris 7.Mendapatkan beberapa tingkat fungsi bersarang bertambah, dikutip, dan lolos dengan benar adalah sakit kepala terbesar. Saya bisa menghemat sedikit lebih banyak pada operasi regex jika saya bisa berasumsi bahwa fungsi nesting tidak akan berjalan lebih dari 9 level, tetapi seperti yang ditunjukkan dalam komentar yang mungkin bukan asumsi yang aman.
Versi kode sebelumnya yang tidak digabungkan:
Satu kelemahan potensial dari implementasi ini adalah ia menggunakan rekursi, sehingga program-program yang seharusnya tidak terbatas mencapai kedalaman rekursi maksimum dengan cukup cepat. (Anda mungkin ingin mengarahkan ulang stderr ketika Anda menjalankan program tanpa batas - jika tidak, tumpukan jejak akan membanjiri output aktual.) Selain itu, semuanya tampaknya berfungsi.
sumber
lambda a
dank.pop()
.k.pop()
situasi sedikit kurang berulang.)Ceylon,
116710571031Saya tidak mengerti sesingkat versi python yang diketik satu ...
import ceylon.language.meta.model{N=Function}import ceylon.collection{H=HashMap}interface D of F|b{}object b satisfies D{}class F(shared Integer a,[D+](D+)f,[D*]c=[])satisfies D{shared[D+]o(D i){[D+]s=[i].prepend(c);return a==1then f(*s)else[F(a-1,f,s)];}shared[D+]y([D+]i){return f(*i.prepend(c));}}F m<A>(N<[D+],A>f)given A satisfies[D+]=>F(f.parameterTypes.size,(D+i)=>f.apply(*i));[D,D]e(D x)=>[x,x];[F]t(F f){[D+]g(D+i){assert(is[D+]r=i.rest);return[i[0],*f.y(r)];}return[F(f.a+1,g)];}[D]k(D a,D d,D c)=>a==b then[d]else[c];[D+]l(F a,D x)=>a.o(x);[F]n(F f,F g){[D+]h(D+i){[D+]r=f.y(i);assert(is[D+]d=r[0:g.a]);return g.y(d).append(r[g.a...]);}return[F(f.a,h)];}[D]y(D x){process.write(x==b then"0"else"1");return[x];}class I(){variable D[]s=[];value c=H{'?'->b,'+'->m(`e`),'>'->m(`t`),'/'->m(`k`),'$'->m(`l`),'.'->m(`n`),'@'->m(`y`)};shared void r(Character i){if(i=='!'){assert(is F f=s[0],is D x=s[1]);s=f.o(x).append(s[2...]);}else{assert(is D d=c[i]);s=[d].append(s);}}}shared void z(){process.readLine()?.collect(I().r);}
Berikut ini adalah versi yang diformat (dan dikomentari) dari kode yang sama (dengan spasi / baris baru / komentar menjadi 4867 byte):
Fungsi mengkloning
e
, menggesert
, garpuk
, memanggill
, mengatakany
dan rantain
menggunakan huruf terakhir dari nama untuk versi yang disingkat, karena itu memberikan sedikit tabrakan. (Trivia: fork awalnya didefinisikan dengan cara ini:[Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c];
- ketika saya berganti namablank
menjadib
, ini pecah, karena sekarang membandingkan parametera
danb
sebagai gantinyaa
dengan kosong. Butuh beberapa waktu untuk debug.)The
z
Fungsi dibagi karena IDE saya berjalan fungsi-fungsi - alat baris perintah juga dapat menjalankan yang non-berbagi.sumber