Kiat penyimpanan dalam bahasa golf

Saya menulis bahasa golf.

Apakah Anda menyarankan variabel, tumpukan, kaset, register, dll untuk penyimpanan dalam bahasa kode-golf? Bagaimana dengan input implisit?

Definisi kasar:

• Sebuah variabel hanyalah sebuah nama (biasanya satu karakter panjang dalam bahasa golf) yang nilai dapat ditugaskan untuk, dan kemudian diambil dengan nama itu.
• Sebuah mendaftar adalah seperti variabel, tetapi memiliki sendiri (biasanya single-byte) yang perintah untuk pengaturan / mendapatkan nilai.
• Sebuah tumpukan adalah variabel-panjang array / daftar nilai, di mana nilai-nilai yang paling baru ditambahkan (nilai "di atas") adalah orang-orang yang sedang dimodifikasi.
• Sebuah antrian seperti stack, kecuali nilai-nilai "pada bagian bawah " adalah orang-orang yang sedang dimodifikasi.
• Sebuah rekaman adalah array / list statis nilai-nilai di mana setiap nilai memiliki indeks. Perbedaan utama antara tumpukan dan pita adalah bahwa nilai pada pita dimodifikasi di tempat.

Saya akan sangat menghargai mengetahui kelebihan dan kekurangan dari setiap opsi untuk skenario yang berbeda, dan secara keseluruhan. Harap hindari opini, dan buat pernyataan cadangan dengan alasan.

Semua tipe penyimpanan melibatkan penyimpanan sesuatu pada satu titik dan mengambilnya nanti. Untuk melakukan ini hanya dalam satu operasi, Anda harus melakukan penyimpanan atau pengambilan secara otomatis, dan tentukan posisi nilai yang disimpan dalam operasi lainnya.

Yaitu, untuk penyimpanan eksplisit, Anda dapat membuat operator untuk mengambil nilai yang dihitung sebelum operasi ini, atau mengembalikan nilai saat ini setelah operasi. Atau, Anda dapat menggunakan posisi absolut dari awal program, atau melakukan lebih banyak hal seperti menghapus beberapa elemen secara otomatis setelah beberapa operasi (seperti dalam tumpukan). Anda juga dapat membuat beberapa operator, mengambil dari berbagai salinan penyimpanan dengan atau tanpa operasi otomatis ini. Dan Anda harus mencoba membuat jumlah maksimum yang diperlukan untuk menentukan dalam operasi yang cukup kecil, sehingga Anda dapat menetapkan satu operator untuk setiap nomor.

Tetapi dalam kebanyakan kasus, Anda bahkan tidak memerlukan operator dan bahasa akan melakukan ini secara implisit. Saat itulah Anda perlu mempertimbangkan model yang lebih standar seperti tumpukan atau antrian. Yang paling sukses untuk saat ini tampaknya adalah pemrograman diam-diam, yang bahkan tidak menyebutkan penyimpanan secara langsung.

Jika Anda ingin mendesain model seperti itu, Anda dapat mencoba memperluas evaluasi sebagai barang, dan cobalah memikirkan barang bawaan jika tidak ada yang ditentukan. Kemungkinan besar, defaultnya hanya sebuah pohon, kecuali untuk beberapa daun yang dapat dihubungkan ke input yang sama. Misalnya Anda dapat menggunakan antrian untuk pohon seimbang, atau tumpukan untuk pohon yang dalam di mana daun sebagian besar konstan, atau sesuatu seperti Jelly untuk pohon yang dalam di mana daun sebagian besar merupakan salinan dari input.

Tetapi perhatikan bahwa, Anda bisa menyandikan bentuk pohon biner hanya dalam 2 bit per operator. Jadi, jika bahasa Anda memiliki kurang dari 64 operator, Anda mungkin benar-benar mengabaikan model tradisional dan hanya meng-encode pohon lengkap dalam bit cadangan (sebut saja flag kombinasi_pihak dan di bawah_bawah). Bahkan jika ada lebih banyak operator, Anda bisa membuat default yang cukup bagus (seperti model Jelly) dan 3 pengubah untuk mengubahnya.

Anda dapat menggunakan model yang sama untuk penyimpanan implisit dan eksplisit untuk kenyamanan, tetapi Anda tidak harus melakukannya. Misalnya, Anda bisa menggunakan tumpukan untuk penyimpanan implisit, tetapi jangan muncul elemen dalam penyimpanan eksplisit (atau penyimpanan eksplisit lain selain yang implisit). Kemungkinan itu tidak akan disebut tumpukan di dokumentasi akhir, tetapi Anda mendapatkan idenya.

Untuk referensi, ukuran pengkodean sempurna dari pohon biner adalah logaritma angka Catalan . Dan ukuran penyandian sempurna dari "binary" dag adalah logaritma A082161 , tetapi jelas tidak praktis. Ini mengasumsikan operator dengan argumen berbeda memesan dua operator yang berbeda, menambahkan bit lain ketika tidak.

Kadang-kadang Anda mungkin masih menginginkan variabel untuk loop. Dimungkinkan untuk menulis ulang loop dengan cara lain. Tetapi jika Anda benar-benar membutuhkannya, jangan gunakan konstruk 1-byte selain nama untuk mendefinisikan variabel. kecuali Anda hanya menggunakan nilai yang diinisialisasi, biasanya lebih efisien menggunakan flag 1-bit untuk menentukan apakah Anda membaca atau menulis variabel ini.

Saya sarankan mereka semua!

Lebih serius lagi, mereka semua berguna beberapa saat, dan semakin banyak semakin baik! Masukan implisit tidak pernah buruk , cukup beri tanda untuk mematikannya. Variabel sangat membantu sehingga mereka tidak perlu ditemukan di tumpukan atau kaset; sama dengan register. Stack sangat membantu untuk menyimpan data, dan juga kaset. Saya sarankan mencoba mengimplementasikan beberapa, katakan stack dan register, atau stack dan variabel, seperti GolfScript. Jika Anda dapat membuat setiap fungsi satu byte, maka bahasa Anda mungkin akan efektif dalam bermain golf, karena Anda dapat menggunakan kelebihan masing-masing.

Sebuah contoh:

• Katakanlah saya ingin mengambil dua angka sebagai input, dan menambahkan panjang string mereka
• Variabel mungkin lebih baik untuk ini (tumpukan mungkin tidak)

• Kode contoh dalam GolfScript (dengan input implisit):

  ~,\,+
  ~ # Eval input (e.g. "1 2" > 1, 2)
  , # Take Length
  \ # Reverse items on the stack
  , # Take Length
  + # Add
    # Implicit output
  

  Namun, dengan variabel (saya tahu ini lebih lama, tidak perlu bertukar tempat di stack):

  ~,:a;,:b;ab+
  ~ # Eval input
  , # Get length
  :a# Store in "a"
  ; # Discard value left on stack
  , # Length
  :b# Store in "b"
  ; # Discard
  a # Recall a
  b # Recall b
  + # Add
    # Implicit output
  

Kelebihan

Hal lain yang dapat membantu adalah kelebihan beban. Misalnya, jika Anda memiliki fungsi penyimpanan variabel, mungkin itu dapat digunakan sebagai monad (fungsi satu-input; Saya tidak yakin dengan istilah sisi luar J / K / APL) untuk ditambahkan ke tumpukan atau pita.

Contoh:

c12 # Stores "1" into register 2
c1] # Pushes "1" onto the stack ("]" is used to denote the end of the monad)

Saya sarankan memiliki beberapa penyimpanan yang dapat digunakan dengan cepat (dari yang diberikan - tape, antrian, tumpukan) dan beberapa penyimpanan permanen (variabel, register) untuk hal-hal yang tidak menghalangi ketika program sedang melakukan sesuatu yang tidak terkait. Saya akan mengatakan bahwa lebih banyak jarang akan memberikan apa pun dan membiarkan lebih banyak karakter gratis untuk instruksi 1-byte lagi.

Dari definisi yang diberikan, yang saya pikir akan bekerja yang terbaik adalah tumpukan dan register.
Tumpukan, karena kaset harus menggunakan fungsi hanya untuk menyimpan hal baru di dalamnya, sementara tumpukan harus memiliki fungsi push dan pop yang sederhana (biasanya dibangun pada perintah). Register, karena mereka mengambil kurang dari biasanya dibandingkan dengan variabel dan jika Anda perlu menyimpan lebih dari 2-4 hal yang berbeda untuk sesuatu, Anda melakukan sesuatu yang salah.

Jangan membatasi fungsi mereka hanya pada apa yang disarankan oleh nama atau definisi mereka - beberapa fungsi seperti put the 1st thing of the stack on top of the stackpasti dapat membantu.

Pada dasarnya ada dua jenis penyimpanan yang perlu ditangani secara berbeda; akses ke nilai yang baru dihasilkan dan / atau input; dan penyimpanan jangka panjang.

Untuk penyimpanan jangka panjang, variabel tampaknya berfungsi paling baik; apa pun dengan sejumlah opsi terbatas tidak berskala (meskipun bahasa dengan properti ini, seperti Jelly, tetap dapat melakukannya dengan cukup baik bahkan pada tugas berukuran sedang). Namun, tidak perlu memberikan nama variabel saat menyimpan variabel, sebagian besar waktu; hanya memiliki perintah untuk menyimpan nilai dalam variabel, dan membuat nama secara otomatis sesuai dengan pola yang dapat diprediksi sehingga menyimpan dan mengambil nilai dapat menjadi satu perintah masing-masing dalam kasus sederhana. (Misalnya, Anda dapat memiliki perintah untuk mengembalikan variabel yang paling baru ditugaskan, yang kedua baru-baru ini, yang ketiga baru-baru ini, dan seterusnya, hingga sejumlah kecil, ditambah perintah umum yang mengambil argumen.)

Untuk penyimpanan jangka pendek, Anda ingin sebanyak mungkin implisit. Hampir semua bahasa golf yang saya lihat menghubungkan output dari satu perintah ke input berikutnya, secara default; cara persisnya yang dilakukan berbeda dari bahasa ke bahasa tetapi biasanya sampai pada hal yang sama. Namun, input kedua untuk perintah 2-input lebih menarik. Mengambilnya dari tumpukan bekerja dengan baik dalam kasus di mana nilai hanya digunakan sekali, tetapi tidak skala dengan baik saat menggunakan kembali nilai. (Cobalah untuk menghindari manipulasi tumpukan primitif; jika Anda harus menggunakan mereka, Anda membuang banyak byte.) Atau, menggunakan input pengguna atau variabel yang baru ditugaskan karena argumen kedua implisit cenderung memberikan penghematan beberapa byte pada program sederhana, meskipun Anda

Dalam bahasa golf yang sedang saya kerjakan saat ini, saya menggunakan kombinasi mekanisme yang sangat murah (satu bit ) untuk menentukan bentuk pohon parse, secara otomatis mengisi argumen yang hilang dari input pengguna secara default, dan checkpointing pendekatan yang memungkinkan untuk menetapkan default untuk argumen yang hilang ke sesuatu yang lain (ditambah banyak kasus khusus). Pada titik tertentu saya mungkin akan menambahkan variabel untuk mengkomunikasikan informasi jarak yang lebih jauh di sepanjang program.

Saya sarankan kaset dan register.

Saya lebih suka kaset daripada tumpukan karena kaset cenderung memiliki elemen lebih sedikit, membuat manipulasi mereka mudah. Juga, dapat menempatkan elemen dalam rekaman di register dan sebaliknya membuat kode pendek mudah.