Quine logis

8

Tantangan

Cukup tulis sebuah program yang mengeluarkan kode sumbernya sendiri.

Tidak lebih dari quine biasa.

Masalah

Kami tidak memiliki komputer sehingga kami harus menjalankan program pada perangkat logika yang dapat diprogram (seperti FPGA, CPLD, gerbang array ...).

Aturan

  • Perangkat apa pun yang tersedia di pasar (seperti printer yang terhubung melalui port Centronics, layar LED, terminal RS232 ...) yang terhubung ke perangkat logika dapat digunakan untuk menampilkan program.
  • Jika Anda menggunakan segala jenis perangkat yang dapat diprogram sebagai perangkat keluaran, Anda tidak diizinkan untuk memasukkan logika program apa pun di sana!

    Contoh: Jika Anda menggunakan RS232 untuk mengirim data ke komputer, komputer harus melakukan apa pun selain menampilkan data yang diterima dari RS232. Namun Anda diperbolehkan untuk mengaktifkan opsi RS232 seperti menggemakan kembali data ke perangkat logika jika ada program terminal yang ada memiliki fitur ini.

  • Pengkodean "standar" apa pun (terkini atau bersejarah) (ASCII, UNICODE, EBCDIC, kode Morse ...) dapat digunakan.

  • Program hanya perlu mengeluarkan kode sumbernya sendiri. File hanya berisi pemetaan antara VHDL / Verilog / ... "kabel" dan pin I / O yang sebenarnya, file yang berisi pengaturan kompiler dan file serupa tidak dianggap sebagai "kode sumber" dan tidak perlu ditulis.
  • Anda memiliki satu pin input jam dengan frekuensi pilihan Anda (jika Anda membutuhkannya).
  • Unit on-chip (seperti SRAM on-chip atau pengganda on-chip) tidak boleh digunakan.
  • Untuk menguji kode Anda dapat mensimulasikan perangkat output menggunakan kode tambahan; tentu saja Anda dapat mensimulasikan perangkat logika juga (jika Anda tidak memiliki yang asli).
  • Celah standar berlaku.

Pemenang

  • Untuk menghitung ukuran program diasumsikan bahwa perangkat output nyata (misalnya printer) terhubung ke beberapa pin I / O dari perangkat logika.
  • Kode yang membutuhkan sel "LE" paling sedikit pada FPGA saya (Altera EP2C20F484C7) menang.
  • Jika FPGA saya terlalu kecil (= tidak cukup besar untuk solusi terkecil) kami mengkompilasi untuk yang terbesar memiliki sel tipe "LE" (EP4CGX150DF31I7).
  • Jika itu masih belum cukup, kami mencoba yang terbesar yang didukung oleh kompiler bebas biaya (EP2AGX260FF35I5).
  • Jika perangkat itu masih terlalu kecil ukuran kode sumber diperhitungkan.

Catatan

Mencari "quine VHDL" di Google, saya menemukan setidaknya tiga quine yang ditulis dalam VHDL di halaman pertama!

Sayangnya tidak satupun dari mereka akan bekerja pada perangkat logika nyata tetapi hanya di emulator karena output standar (dari emulator) digunakan.

Semoga berhasil!

Martin Rosenau
sumber

Jawaban:

6

Verilog, dioptimalkan untuk area, 130 gerbang LE

Quine itu sendiri (file aktual dikodekan dalam DEC SIXBIT ):

module q(s,d);inout s,d;wire[0:1023]v=1024'b0110111100101001011001111110110110010110100100001111011010010111010101110101010110010110111100101001011001111110110100100110100100001111011010100111010101110110111000011100111100111010011001111011100000001001000111011010100111000101100111111010100111010111010100100110101101101110111010011111010110111000011011001101111000011110011100111000000010001100001011111100111001011001001001111001010000001100110010011010011001100010001010100111100101010010011000101001011001111010011011100000001010010111011010010010110100010110111010100111011010100001100100011111100000011010010111110101110110100100010110111001011011101001000000001001011011001100111001010000001010100111011010100010110100010110111001011011101001001011011011111001001101011011001001010000000000000000101101101111100100110101101100100101000000110001001000110011001100100100001001011011101001101110101111110101110100000000110011001100100100011011110111101001110010100101111011010000011010010001010000010010010011111101110110011101010001010000010010010100000111100010;reg[9:0]i=759;reg[2:0]j=7;assign d=j<6?j==2:v[i];always@(posedge s)if(j>5)begin i=i+1;j=j&1^!i?7:1;end else j=j+1;endmodule

Versi yang dapat dibaca dengan komentar dan testbench:

module q(s,d);
   // Declare the ports. Making them both "inout" is shortest.
   inout s,d;
   // Data storage for the program.
   wire[0:1023]v=1024'b{DATA GOES HERE};
   // i is the current bit number within the program.
   // This is relative to the /end of the data storage/ (not to the start
   // of the program), so it starts at a nonzero value so that the output
   // starts at the start of the program.
   reg[9:0]i=759;
   // When expanding bits to (6-bit) bytes, j is the bit number within
   // the expansion, from 1 for the first bit up to 6 for the last.
   // When not expanding, j is always 7.
   // DEC SIXBIT encoding for 0 is (from MSB to LSB) 010 000.
   // DEC SIXBIT encoding for 1 is (from MSB to LSB) 010 001.
   // We use SSI encoding for the output, so the MSB is sent first.
   reg[2:0]j=7;
   assign d=j<6?j==2:v[i];
   // When we get a strobe:
   always@(posedge s)
     // If we just output a bit, move onto the next bit.
     // We may also need to reset j.
     if(j>5)
       begin 
          i=i+1;
          j=j&1^!i?7:1;
       end 
     else 
       // If we're inside a bit, continue to output that bit.
       j=j+1;
endmodule
// {TESTBENCH BELOW HERE}

`timescale 10ns / 1ns
module testbench();
   reg clock = 0;
   wire data, strobe;

   always
     #1 clock <= !clock;
   initial
     #14304 $finish;

   assign strobe = clock;
   q testquine(.s(strobe),.d(data));

   always @(negedge strobe)
      $display("%d", data);

endmodule // testbench

Penggunaan Verilog memberi saya kontrol lebih besar atas detail tingkat rendah daripada yang saya miliki dengan Verity. Secara khusus, ini memungkinkan saya mengontrol jam dan mengatur ulang aturan sendiri. Program ini ditujukan untuk koneksi serial sinkron dengan input strobo sdan output datad. Meskipun masing-masing hanya digunakan dalam satu arah, saya menyatakan keduanya sebagai dua arah untuk menghemat beberapa byte; Saya harus golf bagian-bagian non-data program ke 1024 bit untuk dapat menggunakan gerbang logika 10-bit secara internal (bit ekstra akan lebih mahal di daerah), dan itu hanya goresan di bawah pada 1008, jadi penghematan seperti ini penting. Untuk menyimpan sejumlah besar kode, saya mengandalkan sirkuit reset perangkat keras FPGA daripada menambahkan sendiri, dan saya menggabungkan input strobo dan jam (yang merupakan trik lama yang agak disukai saat ini karena membuatnya sulit untuk menjaga pohon jam seimbang pada kecepatan tinggi, tapi ini berguna untuk bermain golf.) Saya harap itu dapat disintesis; Saya tidak tahu seberapa baik synthesizer Verilog mengatasi menggunakan port dua arah sebagai jam.

Sumber dikodekan dalam DEC SIXBIT (Saya mengasumsikan di sini bahwa kami menafsirkan alfabet tunggal huruf sebagai huruf kecil; sebuah synthesizer Verilog tidak memiliki alasan untuk menggunakan interpretasi huruf besar). Saya menggunakan karakter enam-bit yang ditetapkan secara internal dalam solusi saya yang lain, kemudian membuang-buang byte untuk mengubahnya; lebih baik menggunakan rangkaian karakter yang "alami" dengan lebar enam bit sehingga tidak perlu konversi. Saya memilih rangkaian karakter enam-bit khusus ini karena 0dan 1hanya berbeda dalam bit paling tidak signifikan mereka, dan hanya memiliki satu set bit lain, yang berarti bahwa rangkaian untuk mengubah digit biner ke DEC SIXBIT (yaitu "melarikan diri" string) bisa sangat sederhana. Menariknya, karakter yang diatur dalam pertanyaan tidak memiliki karakter baris baru; program aslinya semua dalam satu baris bukan hanyauntuk membuatnya lebih mudah untuk dibuat, tetapi untuk membuatnya mungkin untuk dikodekan! Untung Verilog tidak terlalu peduli dengan spasi putih.

Protokol untuk mengirim data ke host didasarkan pada Synchronous Serial Interface. Saya mengambilnya karena sudah di-clock (memungkinkan saya untuk menggunakan trik jam / strobo, dan juga memungkinkan saya untuk menulis program portabel yang tidak bergantung pada perangkat timing on-chip), dan karena itu sangat sederhana (jadi saya tidak harus membuang banyak kode untuk mengimplementasikannya). Protokol ini tidak menentukan metode untuk menentukan di mana pesan berakhir (tuan rumah seharusnya tahu); dalam kasus khusus ini, saya mengisi output hingga kelipatan 1024 bit dengan nol bit (total 16 bit padding), setelah itu (seperti yang dipersyaratkan oleh SSI) pesan restart. (Saya tidak menerapkan timer mode siaga; tujuannya adalah untuk menentukan apakah akan mengirim pesan baru atau apakah akan mengulangi pesan sebelumnya, dan karena program ini selalu mengirimkan kode sumber sendiri sebagai pesan, perbedaannya tidak terlihat. Anda dapat menganggapnya panjang 0,

Dalam hal logika aktual, hal yang paling menarik adalah cara saya membagi variabel untuk mengurangi jumlah area yang dibutuhkan pada chip. i, register yang lebih besar, menyimpan "alamat" saat ini dalam data program, dan hanya pernah diubah melalui penambahannya; ini berarti bahwa logikanya dapat disintesis menggunakan konstruksi setengah penambah (yang, seperti namanya, menggunakan hanya setengah sumber daya yang dilakukan penambah; ini sebagian besar hanya masalah pada FPGA terkecil, yang lebih besar akan menggunakan 3-input atau bahkan LUT 4-input yang cukup kuat sehingga mereka akan memiliki banyak kapasitas terbuang mensintesis setengah penambah). Register yang lebih kecil,j, pada dasarnya adalah keadaan mesin negara dan dengan demikian menangani sebagian besar logika kompleks program. Ini cukup kecil sehingga dapat ditangani sepenuhnya melalui tabel pencarian pada FPGA yang lebih besar (membuat logika pada dasarnya hilang); dalam hal program disintesis untuk FPGA kecil, saya memilih pengkodeannya sedemikian rupa sehingga beberapa bagian dari kode peduli tentang ketiga bit sekaligus.

Ini juga perlu dicatat bahwa saya secara siklus mengijinkan penyimpanan data. Kita bisa mulai imenunjuk ke mana saja di dalamnya, tidak harus di awal. Dengan pengaturan yang terlihat di sini, kita dapat mencetak dari nilai awal ihingga akhir secara langsung, lalu mencetak seluruh larik, kemudian mencetak dari awal hingga nilai awal i, untuk mencetak semua bagian data di tempat yang tepat tanpa perlu menyimpan dan mengembalikan nilai i. (Trik ini mungkin berguna untuk quines dalam bahasa lain juga.)

Sumbernya panjangnya 1192 6-bit, setara dengan 894 8-bit. Agak memalukan bahwa ini mengandung sumber byte lebih sedikit daripada pengiriman Verity saya, meskipun dioptimalkan untuk sesuatu yang sama sekali berbeda; ini sebagian besar karena Verilog memiliki string dan Verity tidak, yang berarti bahwa meskipun saya telah menyandikan program dalam biner daripada oktal (yang secara substansial kurang efisien dalam hal ukuran kode sumber), saya dapat menyandikan setiap byte program menggunakan enam karakter enam-bit (satu untuk setiap bit) daripada delapan karakter delapan-bit (empat untuk setiap digit oktal). Pengajuan Verilog yang mengkodekan program dalam oktal mungkin akan lebih kecil dalam hal ukuran kode sumber, tetapi hampir pasti akan lebih besar di daerah tersebut.

Saya tidak tahu berapa banyak area yang akan digunakan oleh program ini; itu sangat tergantung pada seberapa kuat pengoptimal dalam Verilog synthesizer Anda (karena masalah minimalisasi mengubah data yang disimpan menjadi satu set gerbang logika adalah sesuatu yang dilakukan dalam synthesizer itu sendiri; melemparkan pekerjaan ke synthesizer membuat kode sumber itu sendiri membuat kode sumber itu sendiri jauh lebih pendek, dan dengan demikian mengurangi area yang dibutuhkan untuk menyimpannya). Seharusnya memiliki kompleksitas O (n log n), dan karenanya jauh lebih kecil daripada O (n²) dari program lain. Saya tertarik melihat OP mencoba menjalankannya di FPGA mereka. (Mungkin butuh beberapa waktu untuk mensintesis; ada beberapa langkah yang dapat Anda ambil untuk mengoptimalkan program untuk waktu kompilasi, tetapi saya tidak mengambilnya di sini karena akan menyebabkan program yang lebih besar = area yang lebih besar.)


sumber
1
Menjalankan kompiler pertama mengatakan bahwa hanya 130 LE gerbang digunakan. Karena gerbang LE hanya dapat menyimpan 2 bit data dan Anda menggunakan aliran data ~ 750 bit ini dapat berarti bahwa kompilator mengompresi data atau ada yang tidak beres saat kompilasi. Besok pagi saya akan memverifikasi apakah hasil kompiler sudah benar.
Martin Rosenau
Dengan konstruksi ini, banyak data disimpan dalam pola koneksi antara gerbang daripada gerbang itu sendiri, jadi saya bisa percaya bahwa 130 gerbang LE benar. (Synthesizer pada dasarnya adalah brute-forcing formula yang memetakan indeks 10-bit ke nilai 1-bit; Saya menentukan rumus dalam program Verilog menggunakan tabel pencarian dengan 1024 entri, tetapi synthesizer sangat mungkin menggunakan yang lebih representasi efisien berdasarkan pada sesuatu seperti minimisasi K-peta.)
Oh, Anda mungkin juga harus memeriksa untuk memastikan bahwa kompiler belum mengoptimalkan bagian dari kode ke dalam blok RAM atau blok ROM (tidak diizinkan oleh pertanyaan). Saya tidak meminta satu, dan belum menulis kode dalam bentuk yang akan menyiratkan satu (saya berhati-hati untuk membuat kombinasi tabel pencarian), tetapi kadang-kadang optimasi kompiler melakukan hal-hal aneh. Jika ada optimasi yang mengganggu itu, Anda harus mematikan optimasi.
1
Baik. Saya mengelola masalah dengan pin sekarang. Kode itu tampaknya berfungsi dengan baik. Luar biasa. Hanya 130 sel tipe-LE! RAM, ROM dll tidak digunakan. Saya pikir kompiler melakukan beberapa optimasi mirip dengan diagram KV untuk "memampatkan" data.
Martin Rosenau
1
Kamu menang! Selamat.
Martin Rosenau
3

Verity 0.10, dioptimalkan untuk ukuran kode sumber (1944 byte)

Saya awalnya salah membaca pertanyaan dan menafsirkannya sebagai . Itu mungkin yang terbaik, karena jauh lebih mudah untuk menulis quine dengan kode sumber pendek daripada kode objek pendek di bawah batasan dalam pertanyaan; yang membuat pertanyaan itu cukup mudah sehingga saya merasa bisa menghasilkan jawaban yang masuk akal, dan mungkin berfungsi sebagai batu loncatan dalam perjalanan menuju jawaban yang lebih baik. Itu juga mendorong saya untuk menggunakan bahasa tingkat yang lebih tinggi untuk input, yang berarti bahwa saya perlu sedikit mengekspresikan dalam program itu sendiri. Saya tidak membuat Verity sebagai bahasa golf untuk perangkat keras (saya sebenarnya disewa untuk membuatnya beberapa waktu yang lalu dalam konteks yang sama sekali berbeda), tetapi ada sedikit kenangan di sana (misalnya tingkat yang jauh lebih tinggi daripada HDL biasa, dan itu memiliki boilerplate jauh lebih sedikit; ini juga jauh lebih portabel daripada HDL khas).

Saya cukup yakin bahwa solusi yang tepat untuk kode objek pendek melibatkan penyimpanan data dalam beberapa jenis struktur pohon, mengingat bahwa pertanyaannya melarang penggunaan ROM blok, yang biasanya Anda simpan dalam program praktis; Saya mungkin harus menulis program yang menggunakan prinsip ini (tidak yakin bahasa apa, mungkin Verity, mungkin Verilog; VHDL memiliki terlalu banyak boilerplate yang cenderung optimal untuk masalah semacam ini) di beberapa titik. Itu berarti Anda tidak perlu meneruskan setiap bit kode sumber ke setiap bit "ROM yang dibuat secara manual". Namun, kompiler Verity saat ini mensintesis struktur output berdasarkan prioritas dan asosiatif input, yang berarti bahwa itu secara efektif mewakili pointer instruksi (dengan demikian indeks ke tabel pencarian) di unary,

Program itu sendiri:

import <print>new x:=0$1296in(\p.\z.\a.new y:=(-a 5-a 1-a 1-a 2-a 4-a 2-a 3-a 2-a 6-a 2-a 0-a 3-a 0-a 4-a 4-a 7-a 4-a 2-a 6-a 2-a 5-a 1-a 2-a 2-a 0-a 3-a 6-a 7-a 2-a 2-a 1-a 1-a 3-a 3-a 0-a 4-a 4-a 3-a 2-a 7-a 5-a 7-a 0-a 6-a 4-a 4-a 1-a 6-a 2-a 6-a 1-a 7-a 6-a 6-a 5-a 1-a 2-a 2-a 0-a 5-a 0-a 0-a 4-a 2-a 6-a 5-a 0-a 0-a 6-a 3-a 6-a 5-a 0-a 0-a 5-a 0-a 6-a 5-a 2-a 2-a 1-a 1-a 3-a 3-a 0-a 4-a 5-a 3-a 2-a 7-a 5-a 7-a 0-a 5-a 5-a 5-a 1-a 4-a 4-a 3-a 1-a 5-a 5-a 1-a 2-a 2-a 0-a 4-a 3-a 3-a 4-a 1-a 5-a 1-a 0-a 2-a 1-a 1-a 1-a 4-a 4-a 3-a 6-a 7-a 0-a 6-a 0-a 1-a 3-a 2-a 0-a 5-a 4-a 2-a 0-a 5-a 5-a 1-a 2-a 1-a 0-a 4-a 6-a 3-a 4-a 7-a 3-a 6-a 2-a 6-a 0-a 3-a 4-a 1-a 1-a 1-a 2-a 2-a 0-a 4-a 6-a 3-a 3-a 5-a 1-a 7-a 2-a 6-a 1-a 1-a 0-a 2-a 7-a 2-a 1-a 1-a 0-a 4-a 6-a 3-a 1-a 5-a 3-a 7-a 5-a 1-a 2-a 1-a 0-a 4-a 6-a 3-a 5-a 7-a 5-a 7-a 4-a 6-a 5-a 6-a 0-a 3-a 4-a 1-a 1-a 1-a 2-a 2-a 0-a 4-a 3-a 3-a 4-a 1-a 5-a 1-a 0-a 2-a 1-a 1-a 1-a 4-a 5-a 3-a 6-a 7-a 0-a 6-a 0-a 1-a 3-a 2-a 0-a 5-a 4-a 2-a 0-a 4-a 1-a 7-a 7-a 6-a 3-a 7-a 4-a 2-a 0-a 4-a 3-a 6-a 2-a 6-a 3-a 7-a 4-a 2-a 0-a 5-a 4-a 6-a 0-a 7-a 2-a 0-a 1-a 4-a 5-a 3-a 4-a 4-a 4-a 4-a 3-a 6-a 4-a 4-a 4-a 4-a 3-a 6-a 2-a 6-a 1-a 5-a 3-a 7-a 4-a 2-a 0-a 4-a 4-a 6-a 5-a 6-a 3-a 7-a 5-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 5-a 3-a 6-a 7-a 6-a 7-a 3-a 6-a 1-a 5-a 1-a 1-a 0-a 2-a 7-a 2-a 1-a 1-a 0-a 4-a 7-a 2-a 7-a 1-a 5-a 1-a 4-a 2-a 3-a 7-a 4-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 4-a 3-a 6-a 7-a 6-a 7-a 6-a 6-a 1-a 5-a 1-a 5-a 4-a 2-a 6-a 2-a 5-a 1-a 2-a 2-a 0-a 3-a 0-a 5-a 1-a 4-a 4-a 3-a 4-a 4-a 4-a 4-a 6-a 6-a 4-a 4-a 4-a 4-a 3-a 6-a 2-a 6-a 1-a 5-a 0-a 5-a 0-a 0-a 0-a 1-a 6-a 5-a 4-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 4-a 3-a 6-a 7-a 6-a 7-a 3-a 6-a 2-a 0-a 0-a 1-a 4-a 7-a 4-a 7-a 1-a 6-a 2-a 6-a 1-a 7-a 3-a 6-a 3-a 7-a 0-a 6-a 1-a 5-!x)in while!x>0do(p(if z<32then z+92else z);if z==45then while!y>0do(p 97;p 32;p(48^!y$$3$$32);p 45;y:=!y>>3)else skip;x:=!x>>6))print(!x$$6$$32)(\d.x:=!x>>3^d<<1293;0)

Lebih mudah dibaca:

import <print>
new x := 0$1296 in
(\p.\z.\a.
  new y := (-a 5-a 1-
            # a ton of calls to a() omitted...
            -a 1-a 5-!x) in
  while !x>0 do (
    p(if z<32 then z+92 else z);
    if z==45
    then while !y>0 do (
      p 97;
      p 32;
      p(48^!y$$3$$32);
      p 45;
      y:=!y>>3 )
    else skip;
    x:=!x>>6
  )
)(print)(!x$$6$$32)(\d.x:=!x>>3^d<<1293;0)

Ide dasarnya adalah bahwa kita menyimpan seluruh data dalam variabel x. (Seperti biasa untuk quine, kami memiliki bagian kode dan bagian data; data menyandikan teks kode, dan juga dapat digunakan untuk membuat ulang teks data.) Sayangnya, Verity saat ini tidak mengizinkan sangat besar konstanta ditulis dalam kode sumber (menggunakan integer OCaml selama kompilasi untuk mewakili integer dalam sumber, yang jelas tidak benar dalam bahasa yang mendukung tipe integer lebar sewenang-wenang) - dan selain itu, konstanta tidak memungkinkan konstanta menjadi ditentukan dalam oktal - jadi kami menghasilkan nilai xsaat runtime melalui panggilan berulang ke suatu fungsia. Kami dapat membuat fungsi void dan menyebutnya berulang kali sebagai pernyataan terpisah, tetapi itu akan menyulitkan untuk mengidentifikasi di mana mulai mengeluarkan teks dari bagian data. Jadi sebagai gantinya, saya membuat amengembalikan bilangan bulat, dan menggunakan aritmatika untuk menyimpan data (Verity menjamin bahwa aritmatika mengevaluasi dari kiri ke kanan). Bagian data dikodekan xmenggunakan -tanda tunggal ; ketika ini ditemui pada saat run time, itu diperluas ke penuh -a 5-a 1-, dll, melalui penggunaan y.

Menginisialisasi ysebagai salinan xcukup halus di sini. Karena amengembalikan nol secara khusus, sebagian besar jumlahnya hanya nol minus nol minus ... dan membatalkannya sendiri. Kita akhiri dengan !x(yaitu "nilai x"; di Verity, seperti pada OCaml, nama variabel bekerja lebih seperti penunjuk daripada yang lainnya, dan Anda harus melakukan dereferensi secara eksplisit untuk mendapatkan nilai variabel). Aturan Verity untuk unary minus sedikit rumit - minus unary vditulis sebagai (-v)- dengan demikian (-0-0-0-!x)diuraikan sebagai (-(0-0-0-!x)), yang sama dengan !x, dan kami akhirnya menginisialisasi ysebagai salinan x. (Perlu juga dicatat bahwa Verity tidakcall-by-value, tetapi lebih memungkinkan fungsi dan operator untuk memilih urutan mereka mengevaluasi sesuatu; -akan mengevaluasi argumen kiri sebelum argumen kanan, dan khususnya, jika argumen kiri memiliki efek samping, mereka akan terlihat ketika argumen kanan dievaluasi.)

Setiap karakter kode sumber direpresentasikan menggunakan dua digit oktal. Ini berarti bahwa kode sumber terbatas pada 64 karakter yang berbeda, jadi saya harus membuat codepage saya sendiri untuk penggunaan internal. Keluaran dalam ASCII, jadi saya perlu mengkonversi secara internal; ini untuk apa (if z<32 then z+92 else z). Inilah rangkaian karakter yang saya gunakan dalam representasi internal, dalam urutan numerik (mis. \Memiliki codepoint 0, ?memiliki codepoint 63):

\]^_`abcdefghijklmnopqrstuvwxyz{ !"#$%&'()*+,-./0123456789:;<=>?

Kumpulan karakter ini memberi kita sebagian besar karakter yang penting untuk Verity. Karakter yang hilang adalah }(artinya kita tidak dapat membuat blok menggunakan {}, tetapi untungnya semua pernyataan adalah ekspresi sehingga kita dapat menggunakannya ()sebagai gantinya); dan |(inilah sebabnya saya harus menggunakan yang eksklusif daripada inklusif ATAU ketika membuat nilai x, artinya saya perlu menginisialisasi ke 0; namun, saya perlu menentukan seberapa besar ukurannya). Beberapa karakter penting yang ingin saya pastikan ada dalam rangkaian karakter adalah <>(untuk impor, juga bergeser), ()(sangat sulit untuk menulis program yang dapat diuraikan tanpa ini), $(untuk segala sesuatu yang berkaitan dengan bitwidth), dan \( untuk lambdas, secara teori kita bisa mengatasi inilet…in tetapi akan jauh lebih verbose).

Untuk membuat program sedikit lebih pendek, saya membuat singkatan untuk printdan untuk !x$$6$$32(yaitu, "6 bit terbawah !x, dilemparkan agar dapat digunakan ke printperpustakaan) melalui mengikat sementara mereka ke argumen lambda.

Akhirnya, ada masalah output. Verity menyediakan printperpustakaan yang dimaksudkan untuk hasil debug. Pada simulator, ini mencetak kode ASCII ke output standar, yang dapat digunakan untuk menguji program. Pada papan sirkuit fisik, itu tergantung pada printperpustakaan yang telah ditulis untuk chip tertentu dan papan di sekitarnya; ada printperpustakaan di distribusi Verity untuk papan evaluasi yang saya punya akses untuk mencetak output pada tampilan tujuh-segmen. Mengingat bahwa perpustakaan pada akhirnya akan mengambil ruang pada papan sirkuit yang dihasilkan, mungkin ada baiknya menggunakan bahasa yang berbeda untuk solusi yang dioptimalkan untuk masalah ini sehingga kami dapat menampilkan bit-bit output langsung pada kabel.

Omong-omong, program ini adalah O (n²) pada perangkat keras, artinya jauh lebih buruk pada simulator (saya curiga O (n⁴); meskipun tidak yakin, tetapi cukup sulit untuk mensimulasikan bahwa sepertinya tidak mungkin bahkan kubik , dan berdasarkan pada bagaimana waktu bereaksi terhadap perubahan saya ketika saya menulis program, fungsinya tampaknya berkembang sangat cepat). Kompilator Verity membutuhkan 436 pass optimasi (yang jauh, jauh lebih banyak daripada biasanya) untuk mengoptimalkan program, dan bahkan setelah itu, mensimulasikan itu sangat sulit untuk laptop saya. Proses kompilasi-dan-simulasi lengkap membutuhkan waktu berikut:

real  112m6.096s
user  105m25.136s
sys   0m14.080s

dan memuncak pada 2740232 kibiby memori. Program ini membutuhkan total siklus 213646 untuk dijalankan. Tapi itu berhasil!

Bagaimanapun, jawaban ini tidak benar-benar memenuhi pertanyaan karena saya mengoptimalkan untuk hal yang salah, tetapi melihat karena belum ada jawaban lain, ini adalah yang terbaik secara default (dan itu menyenangkan untuk melihat seperti apa palu golf akan terlihat seperti di bahasa perangkat keras). Saat ini saya tidak yakin apakah saya akan bekerja pada suatu program yang bertujuan untuk menghasilkan ouptut yang lebih optimal pada chip. (Kemungkinan akan jauh lebih besar dalam hal sumber, karena O (n) pengkodean data akan lebih kompleks daripada yang terlihat di sini.)


sumber
Berapa skor untuk kriteria utama (gerbang LE yang digunakan pada FPGA yang ditentukan)?
Mego
Tidak, maksud saya, skor apa yang dicapai solusi ini?
Mego
@Mego Saya hanya mencoba untuk mendapatkan kompiler dari veritygos.orguntuk memeriksa ...
Martin Rosenau
@Mego: Tidak tahu; Verity sendiri adalah bahasa portabel, tetapi implementasi Verity mungkin tidak memiliki tingkat atas yang sudah diterapkan untuk chip tertentu yang ditentukan, dan lagi pula saya tidak memiliki synthesizer FPGA untuk diberikan saat ini. Simulator saya mengatakan ada 6328084 sinyal yang digerakkan; yang seharusnya memiliki hubungan linier dengan jumlah gerbang LE yang dibutuhkan, tapi saya tidak tahu apa faktor konstannya. (Secara umum, memiliki kriteria yang ditentukan dalam hal sesuatu yang dapat diperiksa secara objektif pada simulator akan membuat segalanya lebih mudah di sini.)
1
Sintesis kehabisan memori - yang tidak berarti bahwa itu tidak akan berhasil. Namun file VHDL menengah yang dihasilkan oleh kompiler Verity memiliki ukuran> 1MB sedangkan solusi Verilog Anda hanya berukuran 2KB jadi saya ragu solusi Verity memerlukan lebih sedikit sel logika daripada solusi Verity.
Martin Rosenau