Tantangannya adalah menulis penerjemah untuk kalkulus lambda yang tidak diketik dalam karakter sesedikit mungkin. Kami mendefinisikan kalkulus lambda yang tidak diketik sebagai berikut:
Sintaksis
Ada tiga jenis ekspresi berikut:
Ekspresi lambda memiliki bentuk di
(λ x. e)
manax
bisa berupa nama variabel hukum dane
ekspresi hukum apa pun. Di sinix
disebut parameter dane
disebut fungsi tubuh.Demi kesederhanaan, kami menambahkan batasan lebih lanjut bahwa tidak boleh ada variabel dengan nama yang sama seperti
x
saat ini dalam ruang lingkup. Suatu variabel mulai berada dalam cakupan ketika namanya muncul di antara(λ
dan.
dan berhenti berada dalam lingkup pada yang bersangkutan)
.- Aplikasi fungsi memiliki bentuk di
(f a)
manaf
dana
merupakan ekspresi hukum. Di sinif
disebut fungsi dana
disebut argumen. - Variabel memiliki bentuk di
x
manax
nama variabel hukum.
Semantik
Suatu fungsi diterapkan dengan mengganti setiap kemunculan parameter di badan fungsi dengan argumennya. Lebih formal ekspresi dari bentuk ((λ x. e) a)
, di mana x
adalah nama variabel dan e
dan a
adalah ekspresi, mengevaluasi (atau mengurangi) untuk ekspresi e'
di mana e'
merupakan hasil dari penggantian setiap kemunculan x
di e
dengan a
.
Bentuk normal adalah ungkapan yang tidak dapat dievaluasi lebih lanjut.
Tantangan
Misi Anda, jika Anda memilih untuk menerimanya, adalah untuk menulis seorang juru bahasa yang mengambil sebagai input ekspresi dari kalkulus lambda yang tidak diketik yang tidak mengandung variabel bebas dan menghasilkan sebagai output bentuk normal ekspresi (atau ekspresi alpha-kongruen dengan itu) . Jika ekspresi tidak memiliki bentuk normal atau itu bukan ekspresi yang valid, perilaku tidak terdefinisi.
Solusi dengan jumlah karakter terkecil menang.
Beberapa catatan:
- Input dapat dibaca dari stdin atau dari nama file yang diberikan sebagai argumen baris perintah (Anda hanya perlu mengimplementasikan satu atau yang lain - tidak keduanya). Output menuju ke stdout.
- Atau Anda dapat mendefinisikan fungsi yang mengambil input sebagai string dan mengembalikan output sebagai string.
- Jika karakter non-ASCII bermasalah untuk Anda, Anda dapat menggunakan karakter backslash (
\
) alih-alih λ. - Kami menghitung jumlah karakter, bukan byte, jadi meskipun file sumber Anda dikodekan sebagai unicode, λ dihitung sebagai satu karakter.
- Nama variabel legal terdiri dari satu atau lebih huruf kecil, yaitu karakter antara a dan z (tidak perlu mendukung nama alfanumerik, huruf besar atau huruf non-latin - meskipun hal itu tidak akan membatalkan solusi Anda, tentu saja).
- Sejauh menyangkut tantangan ini, tidak ada tanda kurung opsional. Setiap ekspresi lambda dan setiap aplikasi fungsi akan dikelilingi oleh tepat sepasang kurung. Tidak ada nama variabel yang akan dikelilingi oleh tanda kurung.
- Gula sintaksis seperti menulis
(λ x y. e)
untuk(λ x. (λ y. e))
tidak perlu didukung. - Jika kedalaman rekursi lebih dari 100 diperlukan untuk mengevaluasi suatu fungsi, perilaku tidak terdefinisi. Itu harus lebih dari cukup rendah untuk diimplementasikan tanpa optimasi dalam semua bahasa dan masih cukup besar untuk dapat mengeksekusi sebagian besar ekspresi.
- Anda juga dapat mengasumsikan bahwa spasi akan seperti dalam contoh, yaitu tidak ada spasi di awal dan akhir input atau sebelum
λ
atau.
dan tepat satu spasi setelah a.
dan antara fungsi dan argumennya dan setelah aλ
.
Input dan Output Sampel
Memasukkan:
((λ x. x) (λ y. (λ z. z)))
Keluaran:
(λ y. (λ z. z))
Memasukkan:
(λ x. ((λ y. y) x))
Keluaran:
(λ x. x)
Memasukkan:
((λ x. (λ y. x)) (λ a. a))
Keluaran:
(λ y. (λ a. a))
Memasukkan:
(((λ x. (λ y. x)) (λ a. a)) (λ b. b))
Keluaran:
(λ a. a)
Memasukkan:
((λ x. (λ y. y)) (λ a. a))
Keluaran:
(λ y. y)
Memasukkan:
(((λ x. (λ y. y)) (λ a. a)) (λ b. b))
Keluaran:
(λ b. b)
Memasukkan:
((λx. (x x)) (λx. (x x)))
Keluaran: apa saja (Ini adalah contoh ekspresi yang tidak memiliki bentuk normal)
Memasukkan:
(((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))
Output:
(λ a. a)
(Ini adalah contoh ekspresi yang tidak menormalkan jika Anda mengevaluasi argumen sebelum pemanggilan fungsi, dan sayangnya contoh yang gagal diupayakan solusi saya)Memasukkan:
((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))
Keluaran:
`(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))
Ini menghitung 2 ^ 3 dalam angka Gereja.
(\y. a)
.Jawaban:
Terbaru:
Saya telah memerasnya menjadi 644 karakter , saya memasukkan beberapa bagian cOll ke dalam cOpy dan Par; cache panggilan ke sel dan cdr ke variabel lokal sementara, dan memindahkan variabel-variabel lokal ke global dalam fungsi "terminal" (mis. non-rekursif). Juga, konstanta desimal lebih pendek dari karakter literal dan bisnis yang buruk ini ...
... mengidentifikasi huruf kecil dengan benar (dengan asumsi ASCII), tetapi juga menerima salah satu dari `{|} ~. (Pengamatan yang sama tentang ASCII ini dibuat dalam video yang luar biasa ini tentang UTF-8 .)
Et viola: |
Sebelumnya:
Bisakah saya mendapatkan beberapa suara untuk usaha? Saya telah bekerja pada siang dan malam ini selama seminggu. Saya menggali kertas McCarthy asli dan diganggu oleh bug di kertas itu sendiri sampai saya membaca lampiran untuk The Roots of Lisp karya Paul Graham . Saya sangat terganggu sehingga saya mengunci diri dari rumah saya, kemudian benar-benar lupa sampai tiba di rumah lagi malam itu pukul 12:30 (sedikit terlambat untuk memanggil manajer bangunan yang tinggal jauh di county), dan harus menghabiskan malam di rumah nenek saya (meretas hingga baterai laptop saya kering).
Dan setelah semua itu, bahkan tidak dekat dengan entri pemenang!
Saya tidak yakin bagaimana membuat ini lebih pendek; dan saya telah menggunakan semua trik kotor yang dapat saya pikirkan! Mungkin tidak bisa dilakukan dalam C.
Dengan kedermawanan dalam penghitungan (chunk pertama mengambil string dan mencetak hasilnya), itu
778770709694 karakter. Tetapi untuk membuatnya berdiri sendiri, ia harus memilikisbrk
panggilan itu. Dan untuk menangani ekspresi yang lebih rumit, perlusignal
handler juga. Dan tentu saja itu tidak dapat dibuat menjadi modul dengan kode apa pun yang mencoba untuk digunakanmalloc
.Jadi, sayang, ini dia:
Inilah blok tepat sebelum reduksi akhir. Trik di sini adalah kursor integer alih-alih pointer (mengambil keuntungan dari perilaku 'implisit int'), dan penggunaan 'memori awal':
char*n
adalah pointer 'baru' atau 'berikutnya' ke ruang kosong. Tetapi kadang-kadang saya menulis string ke dalam memori, kemudian memanggil strlen dan increment n; menggunakan memori secara efektif dan kemudian mengalokasikannya, setelah ukuran lebih mudah untuk dihitung. Anda dapat melihat itu hampir langsung dari makalah McCarthy, dengan pengecualiancell()
antarmuka antara fungsi dan representasi string data.sumber
sprintf(n,...);n+=strlen(n)+1;
lebih baik sebagain+=sprintf(n,...)+1;
pembalikan sintaks arrayx[m]
daripadam[x]
memungkinkan saya untuk mengganti semua tipuan dengan makro 'postfix'#define M [m]
...x M
yang menyimpan 1 char dan memberikan garis "bebas" baris karena spasi diperlukan untuk memisahkan token.// um ...
adalah perulangan melalui string dan menghitung tanda kurung sampai menemukan paren dekat yang sesuai pada tingkat bersarang yang benar.Binary Lambda Calculus 186
Program ditunjukkan dalam hex dump di bawah ini
tidak cukup menerima format yang Anda usulkan. Sebaliknya, ia mengharapkan istilah lambda dalam format kalkulus binda lambda (blc). Namun, itu menunjukkan setiap langkah dalam pengurangan bentuk normal, menggunakan tanda kurung minimal.
Contoh: menghitung 2 ^ 3 dalam angka Gereja
Simpan hex dump di atas dengan xxd -r> symbolic.Blc
Dapatkan juru bahasa blc dari http://tromp.github.io/cl/uni.c
Karena hexdump agak tidak dapat dibaca, ini adalah versi "dibongkar"
mengganti 00 (lambda) dengan \ dan 01 (aplikasi) dengan @ Sekarang hampir bisa dibaca seperti brainfuck :-)
Juga lihat http://www.ioccc.org/2012/tromp/hint.html
sumber
Haskell,
342323317305 karakterPada tulisan ini, ini adalah satu-satunya solusi yang mengevaluasi ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))) dengan hasil yang benar (λ x. (Λ z. x)) daripada (λ x. (λ x. x)). Implementasi yang benar dari kalkulus lambda membutuhkan penggantian yang menghindari penangkapan , bahkan di bawah jaminan penyederhanaan masalah ini bahwa tidak ada variabel yang menaungi variabel lain dalam cakupannya. (Program saya kebetulan bekerja bahkan tanpa jaminan ini.)
Catatan:
Versi tidak dikoleksi dengan dokumentasi.
sumber
Python -
321320Inilah upaya saya (diperbaiki):
sumber
Ruby 254 karakter
Dapat digunakan seperti
Solusinya belum sepenuhnya golf tetapi sudah hampir tidak dapat dibaca.
sumber
Sunting: periksa jawaban saya di bawah untuk 250 di bawah JavaScript murni.
2852243 karakter menggunakan LiveScript (Tidak Ada Regex! Tidak sepenuhnya golf - bisa ditingkatkan)Uji:
Yaitu
3^2=9
, sebagaimana dinyatakan pada OP.Jika ada yang ingin tahu, ini adalah versi yang diperluas dengan beberapa komentar:
sumber
Waterhouse Arc - 140 karakter
sumber
C 1039 byte
Variabel memungkinkan sebagai input menggunakan huruf kecil [dari a..z] sistem dapat menghasilkan variabel menggunakan huruf besar [dari A..Z] jika perlu dalam output ... Asumsikan konfigurasi karakter ascii.
sumber
Haskell 456 C
Ini bisa menjadi jauh lebih pendek jika fitur evaluasi malas dari Haskell sepenuhnya digunakan. Sayangnya, saya tidak tahu bagaimana cara melakukannya.
Juga, banyak karakter terbuang pada langkah penguraian.
Versi tidak disatukan
sumber
Mendapat 231 dengan JavaScript / tanpa Regex
Menerima array 2-elemen.
1
singkatanλ
dan 2 berarti variabel indeks bruijn.Uji:
sumber
Python: 1266 karakter (diukur menggunakan wc)
Bukan yang terpendek oleh tembakan panjang, tapi itu benar menangani alpha-renaming dan semua contoh yang tercantum dalam pos OP.
sumber
except NameError
dengan adilexcept
? (3) Nama fungsi dua karakter dapat diubah namanya menjadi nama satu karakter. (4) Ada beberapa tempat di mana Anda memiliki tugas yang memiliki ruang di sekitar=
. (5)if t[0]=='c'
dapat diganti denganif'c'==t[0]
.C ++ (gcc) ,
782766758731 byteCobalah online!
Ide dasar di sini adalah bahwa kode menggunakan representasi internal berdasarkan pada gagasan de Bruijn indeks - kecuali bahwa saya membalikkan indeks untuk menunjukkan lambda mendalam tentang pengikatan variabel disebut. Dalam kode:
E::t
mewakili jenis simpul - 0 untuk simpul daun variabel, 1 untuk simpul lambda, dan 2 untuk simpul aplikasi fungsi. (Dipilih sehingga bertepatan dengan arity dari node, yang kebetulan mungkin terjadi.) LaluE::l
danE::r
apakah anak-anak sesuai (hanyaE::l
untuk simpul lambda), danE::i
merupakan indeks kedalaman lambda untuk simpul daun variabel.E::E(E&o,int d,int e)
mengkloning subekspresi yang awalnya di kedalaman lambdad
untuk menempel ke lokasi baru di kedalaman lambdad+e
. Ini melibatkan mempertahankan variabel di kedalaman lambda kurang darid
sementara meningkatkan variabel di kedalaman lambda setidaknyad
olehe
.E::s
melakukan substitusi subexpression yangv
menjadi variabel jumlahd
di*this
saat decrementing nomor variabel lebih besar darid
(dane
adalah detail internal yang melacak kenaikan lambda mendalam untuk saat dibutuhkan untuk panggilanE::c
).E::R
mencari pengurangan beta tunggal untuk melakukan, lebih memilih instance paling atas atau paling kiri menurut pencarian pre-order melalui AST. Ini mengembalikan nol jika ditemukan pengurangan untuk melakukan atau nol jika tidak ditemukan.E::u
adalahto_string
tipe operasi yang menyusun kembali string "dapat dibaca manusia" menggunakan nama sintetis untuk variabel. (Perhatikan bahwa karena golf sedikit dariV
fungsi pembantu itu hanya akan menghasilkan nama yang mengandunga
melaluii
.)E::E(int d, std::map<std::string, int> m, char*&s)
melakukan parsing dari string inputs
ke ekspresi AST berdasarkan pemetaanm
nama variabel yang saat ini terikat ke indeks kedalaman lambda.f
adalah fungsi utama menjawab pertanyaan.(Seperti yang Anda lihat di link TIO, kode tidak nama variabel menangani dengan beberapa karakter, dan juga mendapat jawaban yang benar dari
(\ a. (\ b. a))
untuk((\ f. (\ x. (f x))) (\ y. (\ x. y)))
. Ini juga kebetulan bahwa kode parsing dapat menangani variabel membayangi tanpa biaya tambahan.)-16 byte sebagian karena ide oleh ceilingcat (yang juga saya buat sendiri), dan sebagian karena berubah
E*a=new E;
menjadiE&a=*new E;
dan kemudian berubaha->
menjadia.
-8 byte lebih karena komentar lain oleh ceilingcat (faktor penugasan dari
a.t
dari ternary)-27 byte dari pengonversi parser dan klon menjadi konstruktor
E
sumber
C 637 byte
Versi ini tidak menggunakan variabel bantu (jadi ini tidak mengikuti 100% apa yang dikatakan kalkulus lambda ... karena banyak lainnya di sini ...). Setiap variabel harus sepanjang 1 karakter (seperti beberapa lainnya di sini). Kode uji:
hasil:
ini adalah semi ungolf:
sumber