Tulis Penerjemah Shift

10

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 fungsi fdan nilai xdari tumpukan, dan berlaku funtuk x. Jika fmemiliki arity 1, daftar f(x)ditambahkan ke bagian depan tumpukan. Jika memiliki arity n > 1, (n-1)fungsi -ary baru gdidorong ke stack. Dibutuhkan input dan pengembalian .x1,x2,...,xn-1f(x,x1,x2,...,xn-1)
  • ?( kosong ) mendorong yang kosong ke tumpukan.
  • +( klon ) mendorong ke stack fungsi yang tidak xdikenal yang menggandakan inputnya: nilai apa pun dipetakan ke [x,x].
  • >( shift ) mendorong ke stack fungsi unary yang mengambil nfungsi -ary f, dan mengembalikan (n+1)fungsi -ary gyang mengabaikan argumen pertamanya x, memanggil fyang tersisa, dan mengetuk xdi depan hasilnya. Misalnya, shift(clone)adalah fungsi biner yang mengambil input a,bdan mengembalikan [a,b,b].
  • /( fork ) mendorong ke stack fungsi terner yang mengambil tiga input a,b,c, dan mengembalikan [b]jika akosong, dan [c]sebaliknya.
  • $( Panggilan ) dorongan untuk stack fungsi biner yang muncul fungsi fdan nilai x, dan berlaku funtuk xpersis seperti !yang dilakukannya.
  • .( rantai ) mendorong ke stack fungsi biner yang muncul dua fungsi fdan g, dan mengembalikan komposisi mereka: fungsi hyang memiliki arity yang sama dengan f, dan yang mengambil inputnya secara normal, berlaku funtuk mereka, dan kemudian sepenuhnya berlaku guntuk hasil (panggilan) sebanyak yang ditentukan arity), dengan item yang tidak digunakan dari output yang ftersisa dalam hasil h. Sebagai contoh, anggap itu fadalah fungsi biner yang mengkloning argumen keduanya, dan gadalah panggilan . Jika tumpukan berisi [f,g,a,b,c]dan kami lakukan .!!, maka berisi [chain(f,g),a,b,c]; jika kita lakukan !!selanjutnya, maka fpertama kali diterapkan a,b, berproduksi[a,b,b], kemudian gditerapkan 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 mencetak 0jika itu kosong, dan 1jika 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 0s atau 1s 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 0s dan 1s. 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 nkarakter 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 adan 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,xinput 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 1s selalu bertambah satu:

@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!

Repositori berisi versi beranotasi.

Zgarb
sumber
Saya agak bingung di sini. Ketika Anda menulis "menerima" seperti pada perintah shift, apakah maksud Anda muncul atau apakah maksud Anda diterapkan oleh perintah yang berlaku?
tecywiz121
1
Juga, saya benar-benar tidak yakin dari spek Anda bagaimana rantai seharusnya bekerja. Bisakah Anda menjelaskannya dengan contoh?
tecywiz121
@ tecywiz121 Ini adalah bagaimana saya memahaminya: katakanlah Anda memiliki dua fungsi di bagian atas tumpukan, f(x1, x2, ..., xn)dan g(y1, y2, ..., ym). Memanggil .muncul keduanya dan mendorong suatu fungsi h(z1, z2, ..., zn). Sekarang Anda bisa makan semua argumen itu dengan secara bertahap menyentuhnya !. Setelah naplikasi seperti itu, fungsi yang tersisa hanya memiliki satu argumen, dan pada saat itu ia menghitung f(z1, z2, ..., zn)(yaitu fditerapkan pada semua argumen yang Anda curry), yang mendorong beberapa nilai baru, dan kemudian segera mengkonsumsi mnilai dari stack dan memanggilnya g.
Martin Ender
@ MartinBüttner Jika Zgarb menganggapnya sesuai dengan aturan, Anda dapat menggunakan parameter input kedua yang menentukan ukuran maksimal dari output. Ini juga akan menjadi solusi untuk masalah evaluasi malas.
randomra
@ tecywiz121 .bekerja persis seperti yang dijelaskan Martin, kecuali jika fmengembalikan daftar kurang dari mnilai, hasilnya tidak terdefinisi (komposisinya arity n, sehingga tidak dapat memakan lebih banyak argumen dari tumpukan). Pada dasarnya, output fdigunakan sebagai tumpukan sementara, yang gdidorong dan diterapkan mkali menggunakan !, dan hasilnya ditambahkan ke tumpukan utama.
Zgarb

Jawaban:

12

Python 2, 752 667 534 506 445 436 427 404 398 393 byte

Ini 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.

k,d=[],[]
u=k.append
def z(f,a=1):f.a=a;return f
exec "i=!x:x(*map(k.pop,[-1]*x.a)));e=dict(zip('?+>/$.@',[0,!x:u(x)<u(x)),!x:u(!a,*_:x(*_)<u(a),x.a+1))),!x,y,z:u((z,y)[x<1]),3),!x,y:u(!*_:x(y,*_),x.a-1))if x.a>1 else x(y),2),!x,y:u(!*_:x(*_)<i(y),x.a)),2),!x:d.append(`+(x>0)`)<u(x))]))".replace('!',"z(lambda ")
for _ in raw_input():
 try:[i,u][_ in e](e.get(_,e['$']))
 except:break
print d

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:

stack = []
push = stack.append

def arity(func,a=1): #give each of our functions an arity
    func.arity = a
    return func

def do(func): ##pop the args off the stack, then call the function
    args = map(stack.pop,[-1]*func.arity)
    func(*args)

def call(func,arg): #apply is just do(call)
    if func.arity == 1:
        func(arg)
    else:
        def curried(*a): #a quick little currier
            func(arg, *a)
        curried = arity(curried, func.arity - 1)
        push(curried)

def clone(arg):
    push(arg)
    push(arg)

def shift(func):
    def shifted(a, *arg):
        func(*arg)
        push(a)
    shifted = arity(shifted, func.arity + 1)
    push(shifted)

def fork(a, b, c):
    if a == 0:
        push(b)
    else:
        push(c)

def chain(func, gunc):
    def composition(*args):
        func(*args)
        do(gunc)
    composition = arity(composition, func.arity)
    push(composition)

def say(arg):
    print '10'[arg == 0],
    push(arg)

commands = {'?': 0,
            '+': arity(clone),
            '>': arity(shift),
            '/': arity(fork, 3),
            '$': arity(call, 2),
            '.': arity(chain, 2),
            '@': arity(say)}

def interpret(input_string):
    for command in input_string:
        try:
            if command == '!':
                do(call)
            else:
                push(commands[command])
        except RuntimeError: #this handles max recursion depth errors
            break            # for infinite programs
    print

if __name__ == "__main__":
    interpret(raw_input())

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 @usebagai dekorator untuk mendorong fungsi (tidak lagi!).

Karena 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 atribut dekorator .

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:

>>> tests
['?@!@@!', '$+.!!+!!', '?@$..!!+.!!+>!.!!!!+?/!!!@!@>!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!!!!', '@?/!@>!.!!??/!!>!.!!+.!!.+>!.!!$$.!!$.!!$.!!+.!!$>!>!.!!$>!>!.!!+>!.!!$>!>!>!.!!+>!>!.!!///!!>!>!>!.!!+!!!!!']
>>> for t in tests: m(t)
0 1

0 0 1 0
0
0 0
0 0 0
0 0 0 0
0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sirpercival
sumber
1
Reaksi pertama saya: @ _ @ Serius, kerja bagus - meletakkan fungsi aktual di stack adalah solusi yang sangat rapi. Beberapa tips: 1) Operator ternary biasanya dapat disingkat . 2) Anda bisa menggantinya ['1','0'][...]dengan adil '10'[...]. 3) Mengapa x is 0dan tidak x==0(atau x<1)? 4) Jangan repot-repot menentukan RuntimeError, cukup exceptlakukan. 5) Karena Anda menggunakan Python 2, tab dan spasi dihitung sebagai level indentasi yang berbeda - jelek, tetapi seharusnya menghemat ~ 25 byte.
DLosc
1
Anda harus dapat memotongnya 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 menggunakan x.a-1sebagai kondisi (0 / false jika xadalah 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 ...; ^))
DLosc
1
Setelah mengalami masalah yang sama dengan saya, saya mengerti apa yang gagal sekarang - jika x.a==1benar tetapi x(y)mengembalikan sesuatu yang salah, ia mencoba untuk mengevaluasi u(...)juga. Tapi sepertinya Anda tidak perlu menyimpan 3 byte yang sangat sedikit yang akan memberi Anda! Saya mengakui, tuan: Anda telah melampaui saya.
DLosc
1
Hanya satu berdalih: format output yang ditentukan tidak memiliki spasi - Anda dapat menyelesaikannya dengan berbagai strategi , tidak yakin yang mana yang terpendek. Tentu saja, program Anda menangani RuntimeErrorsaat saya hanya meminta pengguna untuk mengarahkan ulang stderr ... jadi kami mungkin bahkan berdalih. ; ^)
DLosc
1
Untuk apa *_dalam lambda?
mbomb007
4

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 !.

/switch {
    /y exch def
    /x exch def
    {x} {y} ifelse
} bind def

/unwrap {
    dup type (arraytype) eq {aload pop} if
} bind def

/! { % IN: <x> <f> OUT: <g>|<f(x)>
    [ 3 1 roll unwrap] cvx %prefix argument into function
    dup /fun exch def %bind

    [ count 1 roll ] { %run the function sandboxed so it can't take any additional args
        2 dict begin
        /=only {} def % suppress output
            {
                fun
            } stopped /err exch def clear err
        end
    } .runandhide


    exch {
        $error /errorname get
        (stackunderflow) ne {
            handleerror
        } if

        $error /newerror false put

        unwrap
    } {
        unwrap exec
    } ifelse
} def

/? 0 def
/+ {{dup}} def
/_ {{/f exch def pop f}} def % using _ instead of >
/: {{? ne 3 1 roll switch}} def % using : instead of /
/$ {{!}} def
/. {{/g exch def exec g}} def 
/@ {{dup ? eq {0}{1} ifelse =only}} def

Cara !kerja sederhana: Pertama, ia menambahkan argumen xuntuk fdengan awalan xdengan isi f, mendorong kembali di stack, dan penamaan salinan hasilnya fun.

Kemudian membungkus seluruh tumpukan sebagai array. .runandhideadalah ekstensi Ghostscript untuk menjalankan kode sandboxed, menyembunyikan konten array sebelumnya dari prosedur itu dipanggil. The dictperintah mendorong kamus baru pada stack dict, mempersempit ruang lingkup nama ditetapkan dalam sampai endmuncul itu mundur. Itu juga menggantikan =only(operator keluaran saya gunakan dalam @) dengan yang dummy, menekan output selama uji coba. stoppedadalah setara PostScript dari trypernyataan yang ditemukan dalam bahasa lain, dan itu mengembalikan true jika prosedurnya melemparkan kesalahan, dan salah jika berlari ke penyelesaian.

Setelah uji coba funselesai, program mengembalikan tumpukan asli dari array tersembunyi, dan jika funselesai tanpa kesalahan, ia kemudian menjalankannya secara nyata, menjaga hasilnya.

AJMansfield
sumber
2

Python3, 685 670 634 633 byte

Saya 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!

from re import*
E,*k="E"
P="e(k.pop(),k.pop())"
def H(a,b):global k;k+=list(a)+[N(b)];exec("k+=%s;"%P*Z(N(b)));return[]
def e(a,b):a=sub("(?<!\d)0",repr(N(b,1)).replace("\\",r"\\"),a,1);return Z(a)and[a]or list(eval(a))
D=list(zip("ilhydsSNZ",[3,2,2]+[1]*6,sub("A","N(a)",',b,c:[N([b,c][a>E])]|,b:e(A,N(b))|,b:["H(%s,%s)"%(A,repr(b))]|:print(0+(a>E),end="")or[A]|:[A]*2|:["S(0,%s)"%A]|,b:b+[A]|,b=-1:sub("\d+",lambda m:str(int(m.group())+b),a)|:len(split("\D0",a))-1').split("|")))
for n,r,f in D:exec(n+"=lambda a"+f)
F=dict(zip("/$.@+>?!",D))
for z in input():n,r,f=F[z];k+=z!="!"and[[n+"(%s)"%",".join("0"*r),E][z=="?"]]or eval(P)

kadalah 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 akan repr'd dan semua angka bertambah: "h('h(1,1)',0)". Setelah semua 0s diganti dalam suatu fungsi, semuanya dilewatkan ke eval, dengan demikian memanggil fungsi Python yang sesuai - sebagian besar adalah fungsi lambda yang dihasilkan dari string besar di baris 6 dengan execdi 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:

from re import *
E="E"
stack=[]

clone=lambda a:[unnest(a)]*2
shift=lambda a:["shifted(0,%s)"%unnest(a)]
fork=lambda a,b,c:[unnest(c if a!=E else b)]
call=lambda a,b:apply(unnest(a),unnest(b))
chain=lambda a,b:["chained(%s,%s)"%(unnest(a),repr(b))]
def say(a):
 print(1 if a!=E else 0,end="")
 return [unnest(a)]

shifted=lambda a,b:b+[unnest(a)]
def chained(a,b):
 global stack
 stack+=list(a)+[unnest(b)]
 exec("stack+=apply(stack.pop(),stack.pop());"*zeros(unnest(b)))
 return []

nest=lambda a,direction:sub("\d+",lambda m:str(int(m.group())+direction),a)
unnest=lambda a:nest(a,-1)
zeros=lambda a:len(split("\D0",a))-1
def apply(a,b):
 a=sub("(?<!\d)0",repr(nest(b,1)).replace("\\",r"\\"),a,1)
 return [a] if zeros(a) else list(eval(a))

functions=dict(zip("+>/$.@",zip(["clone","shift","fork","call","chain","say"],[1,1,3,2,2,1])))

for cmd in input():
 if"!"==cmd:
  stack+=apply(stack.pop(),stack.pop())
 elif"?"==cmd:
  stack+=[E]
 else:
  name,arity=functions[cmd]
  stack+=[name+"(%s)"%",".join("0"*arity)]

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.

DLosc
sumber
Bisakah Anda menulis program yang menghasilkan program di atas dan kemudian menjalankannya? Anda memiliki banyak kode berulang yang harus dapat dikompresi seperti lambda adan k.pop().
mbomb007
@ mbomb007 ... Saya pikir otak saya akan meledak. (Tapi lihat hasil edit terakhir - saya membuat k.pop()situasi sedikit kurang berulang.)
DLosc
dapatkah kamu melakukan trik eksekutif menerjemahkan untuk semua lambda itu? tempel semuanya dalam satu string?
sirpercival
satu komentar lain: Saya ragu Anda dapat mengandalkan fungsi nesting <= 9 dengan bahasa ini
sirpercival
@sirpercival Ya, saya berpikir untuk mencobanya. Dan tidak, saya kira tidak. : ^ P
DLosc
1

Ceylon, 1167 1057 1031

Saya 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):

import ceylon.language.meta.model {
    N=Function
}
import ceylon.collection {
    H=HashMap
}
//↑ Import of stuff we need – with a shorter alias.
// (The comment is down here due to a bug in my comment and space
//  remover – it doesn't remove a comment if it is the first token
//  at all.)

// Our data items are either functions or blanks.
interface D of F | b {}

// There is no point in having many blanks – so here a singleton.
object b satisfies D {}

// The function class. Our functions take a number of data items,
// and return a number of data items.
// We know the arity a, and have also an actual function f, and a number
// or already collected arguments.
class F(shared Integer a, [D+](D+) f, [D*] c = [])
        satisfies D {
    // apply once (= collect one parameter). Returns either the result,
    // or a function with arity one less.
    shared [D+] o(D i) {
        [D+] s = [i].prepend(c);
        return a == 1 then f(*s) else [F(a - 1, f, s)];
    }
    // apply fully (= with all needed parameters).
    // The input size should equal the arity.
    shared [D+] y([D+] i) {
        // merge collected and input arguments.
        return f(*i.prepend(c));
    }
}
// creates a shift function from a ceylon function,
// deriving the arity using reflection.
F m<A>(N<[D+],A> f)
        given A satisfies [D+]
        => F(f.parameterTypes.size, (D+ i) => f.apply(*i));

//
// clone: a unary function that duplicates its input: any value x is mapped to [x,x].
//
[D, D] e(D x) => [x, x];

//
// shift: a unary function that takes in an n-ary function f, and returns an
// (n+1)-ary function g that ignores its first argument x, calls f on the
// remaining ones, and tacks x in front of the result. For example,
// shift(clone) is a binary function that takes inputs a,b and returns [a,b,b].
//
[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)];
}

//
// fork: a ternary function that takes three inputs a,d,c, and returns [d] if a is a blank,
// and [c] otherwise.
//
[D] k(D a, D d, D c) => a == b then [d] else [c];

//
// call: a binary function that pops a function f and a value x,
//        and applies f to x exactly as ! does.
//
[D+] l(F a, D x) => a.o(x);

//
// chain:  a binary function that pops two functions f and g, and returns their composition:
//         a function h that has the same arity as f, and which takes its inputs normally, applies
//         f to them, and then fully applies g to the result (calls it as many times as its arity
//         dictates), with unused items from the output of f remaining in the result of h. For
//         example, suppose that f is a binary function that clones its second argument, and
//         g is call. If the stack contains [f,g,a,b,c] and we do .!!, then it contains
//         [chain(f,g),a,b,c]; if we do !! next, then f is first applied to a,b, producing
//         [a,b,b], then g is applied to the first two elements of that since its arity is 2,
//         producing [a(b),b], and the stack will finally be [a(b),b,c].
//
[F] n(F f, F g) {
    [D+] h(D+ i) {
        // call f, remember the results.
        [D+] r = f.y(i);
        // first some results from f are the arguments to g:
        assert (is [D+] d = r[0:g.a]);
        // remaining results from f are passed back directly, with the results from g.
        return g.y(d).append(r[g.a...]);
    }
    return [F(f.a, h)];
}

//
// say: a unary function that simply returns its input, and prints 0 if it was a blank,
//      and 1 if it was a function.
// 
[D] y(D x) {
    process.write(x == b then "0" else "1");
    return [x];
}

//
// Interpreter class, which manages the stack and interprets the commands.
// Just call the r method with the individual command characters.
//
class I() {
    // The stack. The only variable in the whole program.
    variable D[] s = [];

    // a hash map of items to be pushed by commands, most build using the m function.
    // The apply command is not here, this is handled separately by the interpreter. 
    value c = H {
        '?'->b,
        '+'->m(`e`),
        '>'->m(`t`),
        '/'->m(`k`),
        '$'->m(`l`),
        '.'->m(`n`),
        '@'->m(`y`)
    };

    // Interprets one command, indicated by a character.
    // Will throw an AssertionError for unknown commands.
    shared void r(Character i) {
        if (i == '!') {
            assert (
                is F f = s[0],
                is D x = s[1]);
            // apply f on x, push the result onto a shortened version of the stack.
            s = f.o(x).append(s[2...]);
        } else {
            assert (is D d = c[i]);
            // push d on top of the stack.
            s = [d].append(s);
        }
    }
}

shared void z() {
    process.readLine()?.collect(I().r);
}

Fungsi mengkloning e, menggeser t, garpu k, memanggil l, mengatakan ydan rantai nmenggunakan 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 nama blankmenjadi b, ini pecah, karena sekarang membandingkan parameter adan bsebagai gantinya adengan kosong. Butuh beberapa waktu untuk debug.)

The zFungsi dibagi karena IDE saya berjalan fungsi-fungsi - alat baris perintah juga dapat menjalankan yang non-berbagi.

Paŭlo Ebermann
sumber
Versi perulangan sebenarnya akan melempar StackOverflowError di beberapa titik, menyelesaikannya kemudian. JVM tidak memiliki optimisasi stack rekursi (atau setidaknya tidak ada yang akan bekerja untuk program saya).
Paŭlo Ebermann