Ini adalah pertanyaan teoretis - pertanyaan yang tidak memberikan jawaban mudah dalam hal apa pun, bahkan tidak untuk yang sepele.

Di Game of Life Conway, ada konstruksi seperti metapixel yang memungkinkan Game of Life untuk mensimulasikan sistem aturan Game-of-Life lainnya juga. Selain itu, diketahui bahwa Game of Life adalah Turing-complete.

Tugas Anda adalah membangun otomat seluler menggunakan aturan permainan Conway tentang kehidupan yang memungkinkan Anda memainkan permainan Tetris.

Program Anda akan menerima input dengan secara manual mengubah keadaan otomat pada generasi tertentu untuk mewakili interupsi (misalnya memindahkan potongan ke kiri atau ke kanan, menjatuhkannya, memutarnya, atau secara acak membuat potongan baru untuk ditempatkan di grid), menghitung sejumlah generasi tertentu sebagai waktu tunggu, dan menampilkan hasilnya di suatu tempat di otomat. Hasil yang ditampilkan harus tampak seperti kisi Tetris yang sebenarnya.

Program Anda akan dinilai berdasarkan hal-hal berikut, secara berurutan (dengan kriteria yang lebih rendah bertindak sebagai tiebreak untuk kriteria yang lebih tinggi):

• Bounding box size - kotak persegi panjang dengan area terkecil yang sepenuhnya berisi solusi yang menang.

• Perubahan yang lebih kecil untuk input - sel paling sedikit (untuk kasus terburuk dalam otomat Anda) yang perlu disesuaikan secara manual untuk kemenangan interupsi.

• Eksekusi tercepat - generasi paling sedikit untuk maju satu centang dalam simulasi menang.

• Hitungan sel hidup awal - jumlah kemenangan yang lebih kecil.

• Pertama ke posting - posting sebelumnya menang.

Ini dimulai sebagai pencarian tetapi berakhir sebagai pengembaraan.

Quest for Tetris Processor, 2.940.928 x 10.295.296

File pola, dengan segala kejayaannya, dapat ditemukan di sini , dapat dilihat di dalam browser di sini .

Proyek ini adalah puncak dari upaya banyak pengguna selama 1 & 1/2 tahun terakhir. Meskipun komposisi tim bervariasi dari waktu ke waktu, para peserta pada saat penulisan adalah sebagai berikut:

• PhiNotPi
• El'endia Starman
• K Zhang
• Blue (Muddyfish)
• Sapi dukun (Kritixi Lithos)
• Mego
• Kuartata

Kami juga ingin menyampaikan terima kasih kepada 7H3_H4CK3R, Conor O'Brien , dan banyak pengguna lain yang telah berupaya mengatasi tantangan ini.

Karena ruang lingkup kolaborasi ini yang belum pernah terjadi sebelumnya, jawaban ini dibagi menjadi beberapa bagian dari beberapa jawaban yang ditulis oleh anggota tim ini. Setiap anggota akan menulis tentang sub-topik tertentu, kira-kira sesuai dengan bidang proyek di mana mereka paling terlibat.

Silakan bagikan semua upvote atau hadiah di semua anggota tim.

Daftar Isi

1. Gambaran
2. Metapixels dan VarLife
3. Perangkat keras
4. QFTASM dan Cogol
5. Majelis, Terjemahan, dan Masa Depan
6. Bahasa dan Kompiler Baru

Juga pertimbangkan untuk memeriksa organisasi GitHub kami tempat kami telah meletakkan semua kode yang telah kami tulis sebagai bagian dari solusi kami. Pertanyaan dapat diarahkan ke ruang obrolan pengembangan kami .

Bagian 1: Ikhtisar

Ide dasar dari proyek ini adalah abstraksi . Daripada mengembangkan game Tetris dalam Life secara langsung, kami perlahan-lahan menggerakkan abstraksi dalam serangkaian langkah. Pada setiap lapisan, kita semakin menjauh dari kesulitan Hidup dan lebih dekat dengan pembangunan komputer yang semudah diprogram seperti yang lainnya.

Pertama, kami menggunakan OTCA metapixels sebagai dasar komputer kami. Metapixels ini mampu meniru aturan "seperti hidup". Komputer Wireworld dan Wireworld berfungsi sebagai sumber inspirasi penting untuk proyek ini, jadi kami berupaya membuat konstruksi yang mirip dengan metapixels. Meskipun tidak mungkin untuk meniru Wireworld dengan OTCA metapixels, dimungkinkan untuk menetapkan metapixels yang berbeda dengan aturan yang berbeda dan untuk membangun pengaturan metapixel yang berfungsi sama dengan kabel.

Langkah selanjutnya adalah membangun berbagai gerbang logika dasar untuk berfungsi sebagai dasar untuk komputer. Sudah pada tahap ini kita berhadapan dengan konsep yang mirip dengan desain prosesor dunia nyata. Berikut adalah contoh gerbang OR, setiap sel dalam gambar ini sebenarnya adalah seluruh metapixel OTCA. Anda dapat melihat "elektron" (masing-masing mewakili sedikit data) masuk dan keluar dari gerbang. Anda juga dapat melihat semua jenis metapixel yang kami gunakan di komputer: B / S sebagai latar belakang hitam, B1 / S berwarna biru, B2 / S berwarna hijau, dan B12 / S1 berwarna merah.

Dari sini kami mengembangkan arsitektur untuk prosesor kami. Kami menghabiskan banyak upaya untuk mendesain arsitektur yang non-esoterik dan semudah mungkin diimplementasikan. Sedangkan komputer Wireworld menggunakan arsitektur yang dipicu transportasi yang belum sempurna, proyek ini menggunakan arsitektur RISC yang jauh lebih fleksibel lengkap dengan beberapa opcode dan mode pengalamatan. Kami menciptakan bahasa rakitan, yang dikenal sebagai QFTASM (Quest for Tetris Assembly), yang memandu pembangunan prosesor kami.

Komputer kami juga tidak sinkron, artinya tidak ada jam global yang mengendalikan komputer. Sebaliknya, data disertai dengan sinyal jam saat mengalir di sekitar komputer, yang berarti kita hanya perlu fokus pada waktu global tetapi bukan waktu global komputer.

Berikut adalah ilustrasi arsitektur prosesor kami:

Dari sini hanya masalah penerapan Tetris di komputer. Untuk membantu mencapai hal ini, kami telah mengerjakan beberapa metode mengkompilasi bahasa tingkat lebih tinggi ke QFTASM. Kami memiliki bahasa dasar yang disebut Cogol, bahasa kedua yang lebih maju dalam pengembangan, dan akhirnya kami memiliki backend GCC yang sedang dibangun. Program Tetris saat ini ditulis dalam / dikompilasi dari Cogol.

Setelah kode QFTASM Tetris final dibuat, langkah-langkah terakhir adalah mengumpulkan dari kode ini ke ROM yang sesuai, dan kemudian dari metapixels ke Game of Life yang mendasarinya, menyelesaikan konstruksi kami.

Menjalankan Tetris

Bagi mereka yang ingin bermain Tetris tanpa bermain-main dengan komputer, Anda dapat menjalankan kode sumber Tetris pada juru bahasa QFTASM . Atur alamat tampilan RAM ke 3-32 untuk melihat seluruh permainan. Berikut ini adalah permalink untuk kenyamanan: Tetris di QFTASM .

Fitur permainan:

• Semua 7 tetromino
• Gerakan, rotasi, tetesan lembut
• Garis bersih dan skor
• Pratinjau cuplikan
• Input pemain menyuntikkan keacakan

Tampilan

Komputer kami mewakili papan Tetris sebagai kisi di dalam memorinya. Alamat 10-31 menampilkan papan, alamat 5-8 menampilkan potongan pratinjau, dan alamat 3 berisi skor.

Memasukkan

Input ke permainan dilakukan dengan mengedit secara manual isi alamat RAM 1. Menggunakan penerjemah QFTASM, ini berarti melakukan penulisan langsung ke alamat 1. Cari "Direct write to RAM" pada halaman penerjemah. Setiap gerakan hanya membutuhkan pengeditan sedikit RAM, dan register input ini secara otomatis dihapus setelah event input telah dibaca.

value     motion
   1      counterclockwise rotation
   2      left
   4      down (soft drop)
   8      right
  16      clockwise rotation

Sistem penilaian

Anda mendapatkan bonus untuk menghapus beberapa baris dalam satu giliran.

1 row    =  1 point
2 rows   =  2 points
3 rows   =  4 points
4 rows   =  8 points

Bagian 2: OTCA Metapixel dan VarLife

OTCA Metapixel

( Sumber )

The OTCA Metapixel adalah membangun di Game Conway of Life yang dapat digunakan untuk mensimulasikan setiap selular automata Hidup-seperti. Seperti yang LifeWiki (ditautkan di atas),

OTCA metapixel adalah sel unit 2048 × 2048 35328 yang dibangun oleh Brice Due ... Ia memiliki banyak keuntungan ... termasuk kemampuan untuk mengemulasi setiap otomat seluler yang menyerupai kehidupan dan fakta bahwa, ketika diperbesar keluar, ON dan sel OFF mudah dibedakan ...

Apa yang dimaksud dengan automata seluler yang hidup di sini pada dasarnya adalah bahwa sel dilahirkan dan sel bertahan hidup sesuai dengan berapa banyak dari delapan sel tetangga mereka yang hidup. Sintaks untuk aturan-aturan ini adalah sebagai berikut: a B diikuti oleh jumlah tetangga yang hidup yang akan menyebabkan kelahiran, kemudian garis miring, kemudian S yang diikuti oleh jumlah tetangga yang hidup yang akan membuat sel tetap hidup. Sedikit bertele-tele, jadi saya pikir contoh akan membantu. Permainan Kehidupan kanonik dapat diwakili oleh aturan B3 / S23, yang mengatakan bahwa sel mati dengan tiga tetangga hidup akan menjadi hidup dan setiap sel hidup dengan dua atau tiga tetangga hidup akan tetap hidup. Kalau tidak, sel mati.

Meskipun merupakan sel 2048 x 2048, metapixel OTCA sebenarnya memiliki kotak pembatas dari 2058 x 2058 sel, alasannya adalah bahwa ia tumpang tindih oleh lima sel di setiap arah dengan tetangganya yang diagonal . Sel yang tumpang tindih berfungsi untuk mencegat glider - yang dipancarkan untuk memberi sinyal pada tetangga metacell bahwa ia aktif - sehingga mereka tidak mengganggu metapixel lain atau terbang tanpa batas. Aturan kelahiran dan kelangsungan hidup dikodekan dalam bagian khusus sel di sisi kiri metapixel, dengan ada atau tidaknya pemakan dalam posisi tertentu di sepanjang dua kolom (satu untuk kelahiran, yang lain untuk bertahan hidup). Adapun untuk mendeteksi keadaan sel tetangga, inilah yang terjadi:

Aliran 9-LWSS kemudian bergerak searah jarum jam di sekitar sel, kehilangan LWSS untuk setiap sel 'on' yang berdekatan yang memicu reaksi honeybit. Jumlah LWSS yang hilang dihitung dengan mendeteksi posisi LWSS depan dengan menabrak LWSS lain ke dalamnya dari arah yang berlawanan. Tabrakan ini melepaskan glider, yang memicu satu atau dua reaksi honeybit lain jika pemakan yang menunjukkan bahwa kondisi kelahiran / bertahan hidup tidak ada.

Diagram yang lebih terperinci dari setiap aspek metapixel OTCA dapat ditemukan di situs web aslinya: Bagaimana Cara Kerjanya? .

VarLife

Saya membuat simulator daring seperti aturan hidup di mana Anda bisa membuat sel berperilaku sesuai dengan aturan seperti apa pun dan menyebutnya "Variasi Kehidupan". Nama ini telah disingkat menjadi "VarLife" agar lebih ringkas. Berikut screenshot-nya (tautan ke sini: http://play.starmaninnovations.com/varlife/BeeHkfCpNR ):

Fitur-fitur penting:

• Beralih sel antara hidup / mati dan cat papan dengan aturan berbeda.
• Kemampuan untuk memulai dan menghentikan simulasi, dan melakukan satu langkah pada satu waktu. Juga dimungkinkan untuk melakukan sejumlah langkah tertentu secepat mungkin atau lebih lambat, pada tingkat yang ditetapkan dalam kotak ticks per detik dan milidetik-per-centang.
• Kosongkan semua sel hidup atau setel ulang papan sepenuhnya ke keadaan kosong.
• Dapat mengubah ukuran sel dan papan, dan juga memungkinkan pembungkus toroidal secara horizontal dan / atau vertikal.
• Permalinks (yang menyandikan semua informasi di url) dan url pendek (karena terkadang ada terlalu banyak info, tapi tetap bagus).
• Rule set, dengan spesifikasi B / S, warna, dan keacakan opsional.
• Dan yang terakhir tapi pasti tidak kalah pentingnya, rendering gif!

Fitur render-to-gif adalah favorit saya baik karena butuh banyak pekerjaan untuk diimplementasikan, jadi itu benar-benar memuaskan ketika saya akhirnya memecahkannya pada jam 7 pagi, dan karena membuatnya sangat mudah untuk membagikan konstruksi VarLife dengan yang lain .

Sirkuit VarLife Dasar

Secara keseluruhan, komputer VarLife hanya membutuhkan empat tipe sel! Delapan negara bagian dalam semua menghitung keadaan mati / hidup. Mereka:

• B / S (hitam / putih), yang berfungsi sebagai penyangga antara semua komponen karena sel B / S tidak pernah hidup.
• B1 / S (biru / cyan), yang merupakan tipe sel utama yang digunakan untuk menyebarkan sinyal.
• B2 / S (hijau / kuning), yang terutama digunakan untuk kontrol sinyal, memastikan tidak mundur.
• B12 / S1 (merah / oranye), yang digunakan dalam beberapa situasi khusus, seperti sinyal persimpangan dan menyimpan sedikit data.

Gunakan url singkat ini untuk membuka VarLife dengan aturan-aturan ini yang telah disandikan: http://play.starmaninnovations.com/varlife/BeeHkfCpNR .

Kabel

Ada beberapa desain kawat yang berbeda dengan karakteristik yang berbeda-beda.

Ini adalah kawat termudah dan paling dasar di VarLife, strip biru yang dibatasi oleh strip hijau.

Url pendek: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Kawat ini searah. Artinya, itu akan membunuh sinyal yang mencoba melakukan perjalanan ke arah yang berlawanan. Ini juga satu sel lebih sempit dari kawat dasar.

Url pendek: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

Kabel diagonal juga ada tetapi tidak digunakan sama sekali.

Url pendek: http://play.starmaninnovations.com/varlife/kJotsdSXIj

Gates

Sebenarnya ada banyak cara untuk membangun setiap gerbang individu, jadi saya hanya akan menunjukkan satu contoh dari masing-masing jenis. Gif pertama ini menunjukkan masing-masing gerbang AND, XOR, dan OR. Gagasan dasar di sini adalah bahwa sel hijau bertindak seperti AND, sel biru bertindak seperti XOR, dan sel merah bertindak seperti OR, dan semua sel lain di sekitarnya hanya ada untuk mengendalikan aliran dengan benar.

Url pendek: http://play.starmaninnovations.com/varlife/EGTlKktmeI

Gerbang AND-NOT, disingkat "Gerbang ANT", ternyata merupakan komponen vital. Ini adalah gerbang yang melewati sinyal dari A jika dan hanya jika tidak ada sinyal dari B. Oleh karena itu, "A AND NOT B".

Url pendek: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Meskipun bukan gerbang , genteng kawat masih sangat penting dan berguna untuk dimiliki.

Url pendek: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

Kebetulan, tidak ada gerbang TIDAK di sini. Itu karena tanpa sinyal masuk, output konstan harus dihasilkan, yang tidak bekerja dengan baik dengan variasi waktu yang diperlukan perangkat keras komputer saat ini. Lagipula, kami baik-baik saja tanpa itu.

Juga, banyak komponen yang sengaja dirancang agar sesuai dengan kotak pembatas 11 oleh 11 ( ubin ) di mana dibutuhkan sinyal 11 tick dari memasuki ubin untuk meninggalkan ubin. Ini membuat komponen lebih modular dan lebih mudah untuk menampar bersama sesuai kebutuhan tanpa harus khawatir menyesuaikan kabel baik untuk jarak atau waktu.

Untuk melihat lebih banyak gerbang yang ditemukan / dibangun dalam proses mengeksplorasi komponen sirkuit, lihat posting blog ini oleh PhiNotPi: Blok Bangunan: Gerbang Logika .

Komponen Penundaan

Dalam proses mendesain perangkat keras komputer, KZhang merancang beberapa komponen penundaan, seperti ditunjukkan di bawah ini.

Penundaan 4-tick: Url pendek: http://play.starmaninnovations.com/varlife/gebOMIXxdh

5-tick delay: Url pendek: http://play.starmaninnovations.com/varlife/JItNjJvnUB

Delay 8-tick (tiga titik masuk berbeda): Url pendek: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

Penundaan 11-tick: Url pendek: http://play.starmaninnovations.com/varlife/kfoADussXA

12-tick delay: Url pendek: http://play.starmaninnovations.com/varlife/bkamAfUfud

14-tick delay: Url pendek: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Penundaan 15-tick (diverifikasi dengan membandingkan dengan ini ): Url pendek: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Nah, itu saja untuk komponen sirkuit dasar di VarLife! Lihat pos perangkat keras KZhang untuk sirkuit utama komputer!

Bagian 3: Perangkat Keras

Dengan pengetahuan kita tentang gerbang logika dan struktur umum prosesor, kita dapat mulai mendesain semua komponen komputer.

Demultiplexer

Demultiplexer, atau demux, adalah komponen penting untuk ROM, RAM, dan ALU. Ini merutekan sinyal input ke salah satu dari banyak sinyal output berdasarkan pada beberapa data pemilih yang diberikan. Ini terdiri dari 3 bagian utama: konverter serial ke paralel, pemeriksa sinyal dan pemecah sinyal jam.

Kami mulai dengan mengubah data pemilih serial menjadi "paralel". Ini dilakukan dengan memisahkan dan menunda data secara strategis sehingga bit data paling kiri memotong sinyal clock di kotak 11x11 paling kiri, bit data berikutnya memotong sinyal clock di square 11x11 berikutnya, dan seterusnya. Meskipun setiap bit data akan dikeluarkan dalam setiap persegi 11x11, setiap bit data akan berpotongan dengan sinyal clock hanya sekali.

Selanjutnya, kami akan memeriksa untuk melihat apakah data paralel cocok dengan alamat yang telah ditetapkan. Kami melakukan ini dengan menggunakan gerbang AND dan ANT pada jam dan data paralel. Namun, kita perlu memastikan bahwa data paralel juga dikeluarkan sehingga dapat dibandingkan lagi. Inilah gerbang yang saya buat:

Akhirnya, kami hanya membagi sinyal clock, menumpuk sekelompok checker sinyal (satu untuk setiap alamat / output) dan kami memiliki multiplexer!

ROM

ROM seharusnya mengambil alamat sebagai input dan mengirimkan instruksi pada alamat tersebut sebagai hasilnya. Kami mulai dengan menggunakan multiplexer untuk mengarahkan sinyal jam ke salah satu instruksi. Selanjutnya, kita perlu menghasilkan sinyal menggunakan beberapa penyeberangan kawat dan gerbang OR. Penyeberangan kawat memungkinkan sinyal jam untuk melakukan perjalanan ke semua 58 bit instruksi, dan juga memungkinkan sinyal yang dihasilkan (saat ini dalam paralel) untuk bergerak turun melalui ROM yang akan dikeluarkan.

Selanjutnya kita hanya perlu mengubah sinyal paralel ke data serial, dan ROM selesai.

ROM saat ini dihasilkan dengan menjalankan skrip di Golly yang akan menerjemahkan kode perakitan dari clipboard Anda ke ROM.

SRL, SL, SRA

Tiga gerbang logika ini digunakan untuk bit shift, dan mereka lebih rumit daripada AND, OR, XOR, dll. Untuk membuat gerbang ini bekerja, pertama-tama kita akan menunda sinyal jam jumlah waktu yang tepat untuk menyebabkan "shift" dalam data. Argumen kedua yang diberikan kepada gerbang ini menentukan berapa banyak bit yang harus diganti.

Untuk SL dan SRL, kita perlu

1. Pastikan bahwa 12 bit paling signifikan tidak aktif (jika tidak, outputnya hanya 0), dan
2. Tunda data jumlah yang benar berdasarkan pada 4 bit paling tidak signifikan.

Ini bisa dilakukan dengan sekelompok gerbang AND / ANT dan multiplexer.

SRA sedikit berbeda, karena kita perlu menyalin bit tanda selama shift. Kami melakukan ini dengan ANDing sinyal jam dengan bit tanda, dan kemudian menyalin output yang beberapa kali dengan kawat splitter dan gerbang OR.

Kait Set-Reset (SR)

Banyak bagian dari fungsi prosesor bergantung pada kemampuan untuk menyimpan data. Dengan menggunakan 2 sel B12 / S1 merah, kita dapat melakukan hal itu. Kedua sel itu dapat saling menjaga, dan juga bisa tetap bersama. Menggunakan beberapa set tambahan, reset, dan membaca sirkuit, kita dapat membuat kait SR sederhana.

Sinkronisasi

Dengan mengonversi data serial menjadi data paralel, lalu mengatur sekelompok kait SR, kita dapat menyimpan seluruh kata data. Kemudian, untuk mengeluarkan data lagi, kita bisa membaca dan mereset semua kait, dan menunda datanya. Ini memungkinkan kami untuk menyimpan satu (atau lebih) kata data sambil menunggu yang lain, memungkinkan dua kata data tiba pada waktu yang berbeda untuk disinkronkan.

Baca Penghitung

Perangkat ini melacak berapa kali lagi perlu alamat dari RAM. Ini melakukan ini menggunakan perangkat yang mirip dengan kait SR: kegagalan flip T. Setiap kali flipflop menerima input, ia berubah status: jika itu aktif, mati, dan sebaliknya. Ketika flip flop T dibalik dari aktif ke mati, ia mengirimkan pulsa output, yang dapat dimasukkan ke flip flop T lain untuk membentuk penghitung 2 bit.

Untuk membuat Read Counter, kita perlu mengatur penghitung ke mode pengalamatan yang sesuai dengan dua gerbang ANT, dan menggunakan sinyal output penghitung untuk memutuskan di mana mengarahkan sinyal jam: ke ALU atau ke RAM.

Baca Antrian

Antrian baca perlu melacak penghitung baca yang mengirim input ke RAM, sehingga dapat mengirim output RAM ke lokasi yang benar. Untuk melakukan itu, kami menggunakan beberapa kait SR: satu kait untuk setiap input. Ketika sinyal dikirim ke RAM dari penghitung baca, sinyal jam dibagi dan mengatur kait SR penghitung. Output RAM kemudian ANDed dengan kait SR, dan sinyal jam dari RAM me-reset kait SR.

ALU

Fungsi ALU mirip dengan antrian baca, dalam hal itu menggunakan kait SR untuk melacak di mana mengirim sinyal. Pertama, kait SR dari rangkaian logika yang sesuai dengan opcode instruksi diatur menggunakan multiplexer. Selanjutnya, nilai argumen pertama dan kedua adalah ANDed dengan kait SR, dan kemudian diteruskan ke sirkuit logika. Sinyal jam me-reset kait saat melewati sehingga ALU dapat digunakan lagi. (Sebagian besar sirkuit diturunkan, dan satu ton manajemen penundaan didorong masuk, sehingga terlihat seperti sedikit berantakan)

RAM

RAM adalah bagian paling rumit dari proyek ini. Untuk itu diperlukan kontrol yang sangat spesifik atas setiap kait SR yang menyimpan data. Untuk membaca, alamat dikirim ke multiplexer dan dikirim ke unit RAM. Unit RAM menampilkan data yang mereka simpan secara paralel, yang dikonversi menjadi serial dan dikeluarkan. Untuk penulisan, alamat dikirim ke multiplexer yang berbeda, data yang akan ditulis dikonversi dari serial ke paralel, dan unit RAM menyebarkan sinyal ke seluruh RAM.

Setiap unit RAM 22x22 metapixel memiliki struktur dasar ini:

Menyatukan seluruh RAM, kami mendapatkan sesuatu yang terlihat seperti ini:

Menyatukan semuanya

Menggunakan semua komponen ini dan arsitektur komputer umum yang dijelaskan dalam Ikhtisar , kita dapat membangun komputer yang berfungsi!

Unduhan: - Komputer Jadi Tetris - Skrip pembuatan ROM, komputer kosong, dan komputer temuan utama

Bagian 4: QFTASM dan Cogol

Tinjauan Arsitektur

Singkatnya, komputer kita memiliki arsitektur RISC Harvard asinkron 16-bit. Saat membangun prosesor dengan tangan, arsitektur RISC ( komputer dengan instruksi terbatas ) praktis merupakan persyaratan. Dalam kasus kami, ini berarti jumlah opcode kecil dan, yang jauh lebih penting, bahwa semua instruksi diproses dengan cara yang sangat mirip.

Sebagai referensi, komputer Wireworld menggunakan arsitektur yang dipicu transportasi , di mana satu-satunya instruksi adalah MOVdan perhitungan dilakukan dengan menulis / membaca register khusus. Meskipun paradigma ini mengarah pada arsitektur yang sangat mudah diimplementasikan, hasilnya juga batas tidak dapat digunakan: semua operasi aritmatika / logika / kondisional memerlukan tiga instruksi. Jelas bagi kami bahwa kami ingin menciptakan arsitektur yang jauh lebih esoteris.

Agar prosesor kami tetap sederhana sekaligus meningkatkan kegunaan, kami membuat beberapa keputusan desain penting:

• Tidak ada register. Setiap alamat dalam RAM diperlakukan sama dan dapat digunakan sebagai argumen untuk operasi apa pun. Dalam arti tertentu, ini berarti semua RAM dapat diperlakukan seperti register. Ini berarti tidak ada instruksi pemuatan / penyimpanan khusus.
• Dalam nada yang sama, pemetaan memori. Segala sesuatu yang dapat ditulis atau dibaca dari berbagi skema pengalamatan terpadu. Ini berarti bahwa penghitung program (PC) adalah alamat 0, dan satu-satunya perbedaan antara instruksi reguler dan instruksi aliran kontrol adalah bahwa instruksi aliran kontrol menggunakan alamat 0.
• Data bersifat serial dalam transmisi, paralel dalam penyimpanan. Karena sifat "elektron" berbasis komputer kita, penambahan dan pengurangan secara signifikan lebih mudah untuk diterapkan ketika data ditransmisikan dalam bentuk serial little-endian (bit paling signifikan pertama). Selain itu, data serial menghilangkan perlunya bus data yang rumit, yang keduanya sangat lebar dan tidak praktis waktu (agar data tetap bersama, semua "jalur" bus harus mengalami keterlambatan perjalanan yang sama).
• Arsitektur Harvard, artinya pembagian antara memori program (ROM) dan memori data (RAM). Meskipun ini mengurangi fleksibilitas prosesor, ini membantu dengan optimasi ukuran: panjang program jauh lebih besar dari jumlah RAM yang kita perlukan, jadi kita dapat membagi program menjadi ROM dan kemudian fokus pada mengompresi ROM , yang jauh lebih mudah bila hanya baca.
• Lebar data 16-bit. Ini adalah kekuatan terkecil dari dua yang lebih luas dari papan Tetris standar (10 blok). Ini memberi kami rentang data -32768 hingga +32767 dan panjang program maksimum 65536 instruksi. (2 ^ 8 = 256 instruksi sudah cukup untuk hal-hal paling sederhana yang mungkin kita inginkan pengolah mainan, tetapi tidak Tetris.)
• Desain asinkron. Daripada memiliki jam pusat (atau, setara, beberapa jam) yang menentukan waktu komputer, semua data disertai dengan "sinyal jam" yang bergerak secara paralel dengan data saat mengalir di sekitar komputer. Jalur tertentu mungkin lebih pendek dari yang lain, dan sementara ini akan menimbulkan kesulitan untuk desain jam pusat, desain asinkron dapat dengan mudah menangani operasi variabel-waktu.
• Semua instruksi berukuran sama. Kami merasa bahwa arsitektur di mana setiap instruksi memiliki 1 opcode dengan 3 operan (nilai tujuan) adalah pilihan yang paling fleksibel. Ini mencakup operasi data biner serta gerakan bersyarat.
• Sistem mode pengalamatan sederhana. Memiliki berbagai mode pengalamatan sangat berguna untuk mendukung hal-hal seperti array atau rekursi. Kami berhasil menerapkan beberapa mode pengalamatan penting dengan sistem yang relatif sederhana.

Ilustrasi arsitektur kami terdapat di pos ikhtisar.

Fungsi dan Operasi ALU

Dari sini, itu adalah masalah menentukan fungsi apa yang harus dimiliki prosesor kami. Perhatian khusus diberikan pada kemudahan implementasi serta fleksibilitas dari setiap perintah.

Gerakan Bersyarat

Gerakan bersyarat sangat penting dan berfungsi sebagai aliran kontrol skala kecil dan besar. "Skala kecil" mengacu pada kemampuannya untuk mengontrol pelaksanaan pemindahan data tertentu, sementara "skala besar" mengacu pada penggunaannya sebagai operasi lompatan bersyarat untuk mentransfer aliran kontrol ke setiap bagian kode yang sewenang-wenang. Tidak ada operasi lompatan khusus karena, karena pemetaan memori, gerakan bersyarat dapat menyalin data ke RAM biasa dan menyalin alamat tujuan ke PC. Kami juga memilih untuk tidak menggunakan gerakan tak bersyarat dan lompatan tak bersyarat untuk alasan yang sama: keduanya dapat diimplementasikan sebagai gerakan bersyarat dengan kondisi yang sulit diubah ke TRUE.

Kami memilih untuk memiliki dua jenis gerakan bersyarat: "bergerak jika tidak nol" ( MNZ) dan "bergerak jika kurang dari nol" ( MLZ). Secara fungsional, MNZjumlah untuk memeriksa apakah bit dalam data adalah 1, sedangkan MLZjumlah untuk memeriksa apakah bit tanda adalah 1. Mereka berguna untuk persamaan dan perbandingan, masing-masing. Alasan kami memilih dua ini lebih dari yang lain seperti "bergerak jika nol" ( MEZ) atau "bergerak jika lebih besar dari nol" ( MGZ) adalah yang MEZmemerlukan pembuatan sinyal BENAR dari sinyal kosong, sementara itu MGZadalah pemeriksaan yang lebih kompleks, yang membutuhkan tanda bit menjadi 0 sementara setidaknya satu bit lainnya menjadi 1.

Hitung

Instruksi terpenting berikutnya, dalam hal memandu desain prosesor, adalah operasi aritmatika dasar. Seperti yang saya sebutkan sebelumnya, kami menggunakan data serial little-endian, dengan pilihan endianness ditentukan oleh kemudahan operasi penjumlahan / pengurangan. Dengan meminta bit terkecil datang terlebih dahulu, unit aritmatika dapat dengan mudah melacak carry bit.

Kami memilih untuk menggunakan representasi komplemen 2 untuk angka negatif, karena ini membuat penambahan dan pengurangan lebih konsisten. Perlu dicatat bahwa komputer Wireworld menggunakan komplemen 1.

Penambahan dan pengurangan adalah sejauh mana dukungan aritmatika asli komputer kami (selain pergeseran bit yang akan dibahas nanti). Operasi lain, seperti multiplikasi, terlalu rumit untuk ditangani oleh arsitektur kita, dan harus diimplementasikan dalam perangkat lunak.

Operasi Bitwise

Prosesor kami memiliki AND,, ORdan XORinstruksi yang melakukan apa yang Anda harapkan. Daripada memiliki NOTinstruksi, kami memilih untuk memiliki instruksi "dan-tidak" ( ANT). Kesulitan dengan NOTinstruksi itu lagi bahwa ia harus membuat sinyal dari kurangnya sinyal, yang sulit dengan automata seluler. The ANTinstruksi mengembalikan 1 hanya jika bit argumen pertama adalah 1 dan bit argumen kedua adalah 0. Jadi, NOT xini setara dengan ANT -1 x(serta XOR -1 x). Selain itu, ANTserbaguna dan memiliki keuntungan utama dalam menutupi: dalam hal program Tetris kami menggunakannya untuk menghapus tetromino.

Pergeseran Bit

Operasi bit-shifting adalah operasi paling kompleks yang ditangani oleh ALU. Mereka mengambil dua input data: nilai untuk digeser dan jumlah untuk digeser. Terlepas dari kerumitannya (karena jumlah pergeseran yang bervariasi), operasi ini sangat penting untuk banyak tugas penting, termasuk banyak operasi "grafis" yang terlibat dalam Tetris. Pergeseran bit juga akan berfungsi sebagai dasar untuk algoritma multiplikasi / divisi yang efisien.

Prosesor kami memiliki tiga operasi shift bit, "shift left" ( SL), "shift right logical" ( SRL), dan "shift arithmetic right" ( SRA). Dua bit pertama bergeser ( SLdan SRL) mengisi bit baru dengan semua nol (artinya angka negatif yang bergeser ke kanan tidak akan lagi menjadi negatif). Jika argumen kedua dari pergeseran berada di luar kisaran 0 hingga 15, hasilnya adalah nol, seperti yang Anda harapkan. Untuk bit shift terakhir SRA,, bit shift mempertahankan tanda input, dan karenanya bertindak sebagai pembagian yang benar oleh dua.

Instruksi Pipelining

Sekarang saatnya berbicara tentang beberapa detail arsitektur yang rumit. Setiap siklus CPU terdiri dari lima langkah berikut:

1. Ambil instruksi saat ini dari ROM

Nilai PC saat ini digunakan untuk mengambil instruksi yang sesuai dari ROM. Setiap instruksi memiliki satu opcode dan tiga operan. Setiap operan terdiri dari satu kata data dan satu mode pengalamatan. Bagian-bagian ini terpisah satu sama lain karena dibaca dari ROM.

Opcode adalah 4 bit untuk mendukung 16 opcode unik, yang 11 ditugaskan:

0000  MNZ    Move if Not Zero
0001  MLZ    Move if Less than Zero
0010  ADD    ADDition
0011  SUB    SUBtraction
0100  AND    bitwise AND
0101  OR     bitwise OR
0110  XOR    bitwise eXclusive OR
0111  ANT    bitwise And-NoT
1000  SL     Shift Left
1001  SRL    Shift Right Logical
1010  SRA    Shift Right Arithmetic
1011  unassigned
1100  unassigned
1101  unassigned
1110  unassigned
1111  unassigned

2. Tulis hasil (jika perlu) dari instruksi sebelumnya ke RAM

Bergantung pada kondisi instruksi sebelumnya (seperti nilai argumen pertama untuk gerakan bersyarat), penulisan dilakukan. Alamat penulisan ditentukan oleh operan ketiga dari instruksi sebelumnya.

Penting untuk dicatat bahwa menulis terjadi setelah instruksi mengambil. Ini mengarah pada pembuatan slot penundaan cabang di mana instruksi segera setelah instruksi cabang (operasi apa pun yang menulis ke PC) dieksekusi sebagai pengganti instruksi pertama pada target cabang.

Dalam kasus tertentu (seperti lompatan tanpa syarat), slot cabang penundaan dapat dioptimalkan jauh. Dalam kasus lain tidak bisa, dan instruksi setelah cabang harus dibiarkan kosong. Selanjutnya, jenis slot tunda ini berarti bahwa cabang harus menggunakan target cabang yang 1 alamat kurang dari instruksi target yang sebenarnya, untuk memperhitungkan kenaikan PC yang terjadi.

Singkatnya, karena output instruksi sebelumnya ditulis ke RAM setelah instruksi berikutnya diambil, lompatan bersyarat harus memiliki instruksi kosong setelah mereka, atau PC tidak akan diperbarui dengan benar untuk lompatan.

3. Baca data untuk argumen instruksi saat ini dari RAM

Seperti disebutkan sebelumnya, masing-masing dari tiga operan terdiri dari kata data dan mode pengalamatan. Kata data adalah 16 bit, sama lebarnya dengan RAM. Mode pengalamatan adalah 2 bit.

Mode pengalamatan dapat menjadi sumber kompleksitas yang signifikan untuk prosesor seperti ini, karena banyak mode pengalamatan dunia nyata melibatkan perhitungan multi-langkah (seperti menambahkan offset). Pada saat yang sama, mode pengalamatan serbaguna memainkan peran penting dalam kegunaan prosesor.

Kami berusaha untuk menyatukan konsep menggunakan angka hard-kode sebagai operan dan menggunakan alamat data sebagai operan. Ini mengarah pada pembuatan mode pengalamatan berbasis counter: mode pengalamatan sebuah operan hanyalah angka yang menunjukkan berapa kali data harus dikirim di sekitar loop pembacaan RAM. Ini mencakup pengalamatan langsung, langsung, tidak langsung, dan tidak langsung ganda.

00  Immediate:  A hard-coded value. (no RAM reads)
01  Direct:  Read data from this RAM address. (one RAM read)
10  Indirect:  Read data from the address given at this address. (two RAM reads)
11  Double-indirect: Read data from the address given at the address given by this address. (three RAM reads)

Setelah dereferencing ini dilakukan, tiga operan instruksi memiliki peran yang berbeda. Operan pertama biasanya argumen pertama untuk operator biner, tetapi juga berfungsi sebagai kondisi ketika instruksi saat ini adalah gerakan bersyarat. Operan kedua berfungsi sebagai argumen kedua untuk operator biner. Operan ketiga berfungsi sebagai alamat tujuan untuk hasil instruksi.

Karena dua instruksi pertama berfungsi sebagai data sementara yang ketiga berfungsi sebagai alamat, mode pengalamatan memiliki interpretasi yang sedikit berbeda tergantung pada posisi mana mereka digunakan. Misalnya, mode langsung digunakan untuk membaca data dari alamat RAM tetap (karena satu RAM diperlukan), tetapi mode langsung digunakan untuk menulis data ke alamat RAM tetap (karena tidak ada RAM yang diperlukan).

4. Hitung hasilnya

Opcode dan dua operan pertama dikirim ke ALU untuk melakukan operasi biner. Untuk operasi aritmatika, bitwise, dan shift, ini berarti melakukan operasi yang relevan. Untuk gerakan bersyarat, ini berarti mengembalikan operan kedua.

Opcode dan operan pertama digunakan untuk menghitung kondisi, yang menentukan apakah akan menulis hasilnya atau tidak ke memori. Dalam kasus gerakan kondisional, ini berarti menentukan apakah bit dalam operan adalah 1 (untuk MNZ), atau menentukan apakah bit tanda adalah 1 (untuk MLZ). Jika opcode bukan gerakan bersyarat, maka penulisan selalu dilakukan (kondisinya selalu benar).

5. Tambahkan penghitung program

Akhirnya, penghitung program dibaca, ditambahkan, dan ditulis.

Karena posisi kenaikan PC antara membaca instruksi dan instruksi menulis, ini berarti bahwa instruksi yang menambah PC oleh 1 adalah no-op. Instruksi yang menyalin PC ke dirinya sendiri menyebabkan instruksi berikutnya dieksekusi dua kali berturut-turut. Tetapi, berhati-hatilah, banyak instruksi PC secara berurutan dapat menyebabkan efek kompleks, termasuk perulangan tak terbatas, jika Anda tidak memperhatikan pipa instruksi.

Quest for Tetris Assembly

Kami menciptakan bahasa rakitan baru bernama QFTASM untuk prosesor kami. Bahasa assembly ini berkorespondensi 1-ke-1 dengan kode mesin dalam ROM komputer.

Setiap program QFTASM ditulis sebagai serangkaian instruksi, satu instruksi per baris. Setiap baris diformat seperti ini:

[line numbering] [opcode] [arg1] [arg2] [arg3]; [optional comment]

Daftar Opcode

Seperti dibahas sebelumnya, ada sebelas opcode yang didukung oleh komputer, yang masing-masing memiliki tiga operan:

MNZ [test] [value] [dest]  – Move if Not Zero; sets [dest] to [value] if [test] is not zero.
MLZ [test] [value] [dest]  – Move if Less than Zero; sets [dest] to [value] if [test] is less than zero.
ADD [val1] [val2] [dest]   – ADDition; store [val1] + [val2] in [dest].
SUB [val1] [val2] [dest]   – SUBtraction; store [val1] - [val2] in [dest].
AND [val1] [val2] [dest]   – bitwise AND; store [val1] & [val2] in [dest].
OR [val1] [val2] [dest]    – bitwise OR; store [val1] | [val2] in [dest].
XOR [val1] [val2] [dest]   – bitwise XOR; store [val1] ^ [val2] in [dest].
ANT [val1] [val2] [dest]   – bitwise And-NoT; store [val1] & (![val2]) in [dest].
SL [val1] [val2] [dest]    – Shift Left; store [val1] << [val2] in [dest].
SRL [val1] [val2] [dest]   – Shift Right Logical; store [val1] >>> [val2] in [dest]. Doesn't preserve sign.
SRA [val1] [val2] [dest]   – Shift Right Arithmetic; store [val1] >> [val2] in [dest], while preserving sign.

Mengatasi Mode

Setiap operan berisi nilai data dan gerakan pengalamatan. Nilai data dijelaskan oleh angka desimal dalam kisaran -32768 hingga 32767. Mode pengalamatan dijelaskan oleh awalan satu huruf ke nilai data.

mode    name               prefix
0       immediate          (none)
1       direct             A
2       indirect           B
3       double-indirect    C 

Kode Contoh

Urutan Fibonacci dalam lima baris:

0. MLZ -1 1 1;    initial value
1. MLZ -1 A2 3;   start loop, shift data
2. MLZ -1 A1 2;   shift data
3. MLZ -1 0 0;    end loop
4. ADD A2 A3 1;   branch delay slot, compute next term

Kode ini menghitung urutan Fibonacci, dengan alamat RAM 1 yang berisi istilah saat ini. Dengan cepat meluap setelah 28657.

Kode abu-abu:

0. MLZ -1 5 1;      initial value for RAM address to write to
1. SUB A1 5 2;      start loop, determine what binary number to covert to Gray code
2. SRL A2 1 3;      shift right by 1
3. XOR A2 A3 A1;    XOR and store Gray code in destination address
4. SUB B1 42 4;     take the Gray code and subtract 42 (101010)
5. MNZ A4 0 0;      if the result is not zero (Gray code != 101010) repeat loop
6. ADD A1 1 1;      branch delay slot, increment destination address

Program ini menghitung kode Gray dan menyimpan kode dalam alamat berurutan mulai dari alamat 5. Program ini menggunakan beberapa fitur penting seperti pengalamatan tidak langsung dan lompatan bersyarat. Ini berhenti setelah kode Gray yang dihasilkan 101010, yang terjadi untuk input 51 di alamat 56.

Penerjemah Online

El'endia Starman telah menciptakan juru bahasa online yang sangat berguna di sini . Anda dapat melangkah melalui kode, mengatur breakpoints, melakukan penulisan manual ke RAM, dan memvisualisasikan RAM sebagai tampilan.

Cogol

Setelah arsitektur dan bahasa assembly didefinisikan, langkah selanjutnya pada sisi "perangkat lunak" proyek adalah penciptaan bahasa tingkat yang lebih tinggi, sesuatu yang cocok untuk Tetris. Jadi saya membuat Cogol . Namanya adalah plesetan dari "COBOL" dan akronim untuk "C of Game of Life", meskipun perlu dicatat bahwa Cogol adalah untuk C seperti apa komputer kita dengan komputer yang sebenarnya.

Cogol ada pada level di atas bahasa assembly. Secara umum, sebagian besar baris dalam program Cogol masing-masing sesuai dengan satu baris perakitan, tetapi ada beberapa fitur penting dari bahasa ini:

• Fitur dasar termasuk variabel bernama dengan penugasan dan operator yang memiliki sintaks yang lebih mudah dibaca. Misalnya, ADD A1 A2 3menjadi z = x + y;, dengan variabel pemetaan kompiler ke alamat.
• Konstruksi perulangan seperti if(){}, while(){}, dan do{}while();sehingga compiler menangani bercabang.
• Array satu dimensi (dengan aritmatika pointer), yang digunakan untuk papan Tetris.
• Subrutin dan tumpukan panggilan. Ini berguna untuk mencegah duplikasi potongan kode besar, dan untuk mendukung rekursi.

Kompiler (yang saya tulis dari awal) sangat mendasar / naif, tetapi saya telah mencoba mengoptimalkan beberapa konstruksi bahasa untuk mencapai panjang program yang dikompilasi.

Berikut ini beberapa ikhtisar singkat tentang bagaimana berbagai fitur bahasa bekerja:

Tokenisasi

Kode sumber tokenized secara linear (single-pass), menggunakan aturan sederhana tentang karakter mana yang boleh berdekatan dalam token. Ketika karakter ditemukan yang tidak dapat berdekatan dengan karakter terakhir dari token saat ini, token saat ini dianggap selesai dan karakter baru memulai token baru. Beberapa karakter (seperti {atau ,) tidak dapat berdekatan dengan karakter lain dan karenanya merupakan token mereka sendiri. Lainnya (seperti >atau =) hanya boleh berdekatan dengan karakter lain dalam kelas mereka, dan dengan demikian dapat membentuk token seperti >>>, ==, atau >=, tapi tidak seperti =2. Karakter spasi putih memaksa batas antara token tetapi tidak sendiri termasuk dalam hasil. Karakter yang paling sulit untuk dipatahkan adalah- karena keduanya bisa mewakili pengurangan dan negasi unary, dan dengan demikian memerlukan beberapa casing khusus.

Parsing

Parsing juga dilakukan secara single-pass. Compiler memiliki metode untuk menangani setiap konstruksi bahasa yang berbeda, dan token dikeluarkan dari daftar token global karena mereka dikonsumsi oleh berbagai metode kompiler. Jika kompiler pernah melihat token yang tidak diharapkan, itu menimbulkan kesalahan sintaksis.

Alokasi Memori Global

Kompiler memberikan setiap variabel global (kata atau larik) alamat RAM yang ditunjuknya sendiri. Kita perlu mendeklarasikan semua variabel menggunakan kata kunci mysehingga kompiler tahu untuk mengalokasikan ruang untuk itu. Jauh lebih keren daripada variabel global bernama adalah manajemen memori alamat awal. Banyak instruksi (terutama kondisional dan banyak akses array) memerlukan alamat "awal" sementara untuk menyimpan perhitungan menengah. Selama proses kompilasi, kompiler mengalokasikan dan tidak mengalokasikan alamat awal yang diperlukan. Jika kompilator membutuhkan lebih banyak alamat awal, ia akan mendedikasikan lebih banyak RAM sebagai alamat awal. Saya percaya ini tipikal untuk program yang hanya membutuhkan beberapa alamat awal, meskipun setiap alamat awal akan digunakan berkali-kali.

IF-ELSE Pernyataan

Sintaks untuk if-elsepernyataan adalah bentuk C standar:

other code
if (cond) {
  first body
} else {
  second body
}
other code

Ketika dikonversi ke QFTASM, kode tersebut diatur seperti ini:

other code
condition test
conditional jump
first body
unconditional jump
second body (conditional jump target)
other code (unconditional jump target)

Jika tubuh pertama dieksekusi, tubuh kedua dilewati. Jika tubuh pertama dilewati, tubuh kedua dieksekusi.

Dalam perakitan, tes kondisi biasanya hanya pengurangan, dan tanda hasilnya menentukan apakah akan melakukan lompatan atau mengeksekusi tubuh. Sebuah MLZinstruksi digunakan untuk menangani ketidaksetaraan seperti >atau <=. Sebuah MNZinstruksi yang digunakan untuk menangani ==, karena melompat di atas tubuh ketika perbedaan tersebut tidak nol (dan oleh karena itu ketika argumen tidak sama). Persyaratan multi-ekspresi saat ini tidak didukung.

Jika elsepernyataan dihilangkan, lompatan tanpa syarat juga dihilangkan, dan kode QFTASM terlihat seperti ini:

other code
condition test
conditional jump
body
other code (conditional jump target)

WHILE Pernyataan

Sintaks untuk whilepernyataan juga merupakan bentuk C standar:

other code
while (cond) {
  body
}
other code

Ketika dikonversi ke QFTASM, kode tersebut diatur seperti ini:

other code
unconditional jump
body (conditional jump target)
condition test (unconditional jump target)
conditional jump
other code

Pengujian kondisi dan lompatan bersyarat berada di akhir blok, yang berarti mereka dieksekusi kembali setelah setiap eksekusi blok. Ketika kondisi dikembalikan palsu tubuh tidak diulang dan loop berakhir. Selama awal eksekusi loop, aliran kontrol melompati body loop ke kode kondisi, sehingga tubuh tidak pernah dieksekusi jika kondisinya salah saat pertama kali.

Sebuah MLZinstruksi digunakan untuk menangani ketidaksetaraan seperti >atau <=. Tidak seperti selama ifpernyataan, MNZinstruksi digunakan untuk menangani !=, karena ia melompat ke tubuh ketika perbedaannya tidak nol (dan karena itu ketika argumen tidak sama).

DO-WHILE Pernyataan

Satu-satunya perbedaan antara whiledan do-whileadalah bahwa do-whilebadan loop pada awalnya tidak dilewati sehingga selalu dieksekusi setidaknya sekali. Saya biasanya menggunakan do-whilepernyataan untuk menyimpan beberapa baris kode assembly ketika saya tahu loop tidak perlu dilewati sepenuhnya.

Array

Array satu dimensi diimplementasikan sebagai blok memori yang berdekatan. Semua array adalah panjang tetap berdasarkan deklarasi mereka. Array dinyatakan seperti ini:

my alpha[3];               # empty array
my beta[11] = {3,2,7,8};   # first four elements are pre-loaded with those values

Untuk array, ini adalah pemetaan RAM yang memungkinkan, menunjukkan bagaimana alamat 15-18 dicadangkan untuk array:

15: alpha
16: alpha[0]
17: alpha[1]
18: alpha[2]

Alamat berlabel alphadiisi dengan pointer ke lokasi alpha[0], jadi dalam kasus ini alamat 15 berisi nilai 16. alphaVariabel dapat digunakan di dalam kode Cogol, mungkin sebagai penunjuk tumpukan jika Anda ingin menggunakan array ini sebagai tumpukan .

Mengakses elemen-elemen dari array dilakukan dengan array[index]notasi standar . Jika nilai indexkonstanta, referensi ini secara otomatis diisi dengan alamat absolut elemen itu. Kalau tidak, ia melakukan beberapa aritmatika pointer (hanya tambahan) untuk menemukan alamat absolut yang diinginkan. Dimungkinkan juga untuk mengindeks sarang, seperti alpha[beta[1]].

Subrutin dan Memanggil

Subrutin adalah blok kode yang dapat dipanggil dari berbagai konteks, mencegah duplikasi kode dan memungkinkan untuk pembuatan program rekursif. Berikut adalah program dengan subrutin rekursif untuk menghasilkan angka Fibonacci (pada dasarnya algoritma paling lambat):

# recursively calculate the 10th Fibonacci number
call display = fib(10).sum;
sub fib(cur,sum) {
  if (cur <= 2) {
    sum = 1;
    return;
  }
  cur--;
  call sum = fib(cur).sum;
  cur--;
  call sum += fib(cur).sum;
}

Subrutin dideklarasikan dengan kata kunci sub, dan subrutin dapat ditempatkan di mana saja di dalam program. Setiap subrutin dapat memiliki banyak variabel lokal, yang dideklarasikan sebagai bagian dari daftar argumennya. Argumen ini juga bisa diberi nilai default.

Untuk menangani panggilan rekursif, variabel lokal dari subrutin disimpan di stack. Variabel statis terakhir dalam RAM adalah penunjuk tumpukan panggilan, dan semua memori setelah itu berfungsi sebagai tumpukan panggilan. Ketika subrutin dipanggil, ia membuat bingkai baru di tumpukan panggilan, yang mencakup semua variabel lokal serta alamat return (ROM). Setiap subrutin dalam program ini diberikan alamat RAM statis tunggal untuk berfungsi sebagai pointer. Pointer ini memberikan lokasi panggilan "saat ini" dari subrutin dalam tumpukan panggilan. Referensi variabel lokal dilakukan menggunakan nilai pointer statis ini ditambah offset untuk memberikan alamat variabel lokal tertentu. Juga terdapat dalam tumpukan panggilan adalah nilai sebelumnya dari penunjuk statis. Sini'

RAM map:
0: pc
1: display
2: scratch0
3: fib
4: scratch1
5: scratch2
6: scratch3
7: call

fib map:
0: return
1: previous_call
2: cur
3: sum

Satu hal yang menarik tentang subrutin adalah mereka tidak mengembalikan nilai tertentu. Sebaliknya, semua variabel lokal dari subrutin dapat dibaca setelah subrutin dilakukan, sehingga berbagai data dapat diekstraksi dari panggilan subrutin. Ini dilakukan dengan menyimpan pointer untuk panggilan spesifik dari subrutin, yang kemudian dapat digunakan untuk memulihkan variabel lokal dari dalam frame stack (baru-baru ini deallocated).

Ada beberapa cara untuk memanggil subrutin, semuanya menggunakan callkata kunci:

call fib(10);   # subroutine is executed, no return vaue is stored

call pointer = fib(10);   # execute subroutine and return a pointer
display = pointer.sum;    # access a local variable and assign it to a global variable

call display = fib(10).sum;   # immediately store a return value

call display += fib(10).sum;   # other types of assignment operators can also be used with a return value

Sejumlah nilai dapat diberikan sebagai argumen untuk panggilan subrutin. Setiap argumen yang tidak disediakan akan diisi dengan nilai standarnya, jika ada. Argumen yang tidak disediakan dan tidak memiliki nilai default tidak dihapus (untuk menyimpan instruksi / waktu) sehingga berpotensi mengambil nilai apa pun di awal subrutin.

Pointer adalah cara mengakses beberapa variabel lokal dari subrutin, walaupun penting untuk dicatat bahwa pointer hanya sementara: data yang ditunjuk oleh pointer akan dihancurkan ketika panggilan subrutin lain dibuat.

Label debugging

Setiap {...}blok kode dalam program Cogol dapat didahului dengan label deskriptif multi-kata. Label ini dilampirkan sebagai komentar dalam kode perakitan yang dikompilasi, dan dapat sangat berguna untuk debugging karena memudahkan untuk menemukan potongan kode tertentu.

Optimalisasi Slot Cabang Delay

Untuk meningkatkan kecepatan kode yang dikompilasi, kompiler Cogol melakukan beberapa optimasi slot keterlambatan yang sangat mendasar sebagai umpan akhir atas kode QFTASM. Untuk lompatan tak bersyarat apa pun dengan slot tunda cabang kosong, slot tunda dapat diisi dengan instruksi pertama di tujuan lompat, dan tujuan lompatan bertambah satu untuk menunjuk ke instruksi berikutnya. Ini umumnya menghemat satu siklus setiap kali lompatan tanpa syarat dilakukan.

Menulis kode Tetris di Cogol

Program Tetris terakhir ditulis dalam Cogol, dan kode sumber tersedia di sini . Kode QFTASM yang dikompilasi tersedia di sini . Untuk kenyamanan, permalink disediakan di sini: Tetris di QFTASM . Karena tujuannya adalah untuk golf kode perakitan (bukan kode Cogol), kode Cogol yang dihasilkan sulit digunakan. Banyak bagian dari program biasanya terletak di subrutin, tetapi subrutin tersebut sebenarnya cukup pendek sehingga duplikasi kode menyimpan instruksi di atascallpernyataan. Kode akhir hanya memiliki satu subrutin selain kode utama. Selain itu, banyak array telah dihapus dan diganti dengan daftar variabel individual yang panjangnya setara, atau dengan banyak angka yang dikodekan dalam program. Kode QFTASM terakhir yang dikompilasi berada di bawah 300 instruksi, meskipun hanya sedikit lebih panjang dari sumber Cogol itu sendiri.

Bagian 5: Majelis, Terjemahan, dan Masa Depan

Dengan program perakitan kami dari kompiler, saatnya untuk merakit ROM untuk komputer Varlife, dan menerjemahkan semuanya menjadi pola GoL yang besar!

Majelis

Merakit program perakitan ke dalam ROM dilakukan dengan cara yang hampir sama seperti dalam pemrograman tradisional: setiap instruksi diterjemahkan ke dalam setara biner, dan itu kemudian digabungkan menjadi gumpalan biner besar yang kita sebut executable. Bagi kami, satu-satunya perbedaan adalah, bahwa gumpalan biner perlu diterjemahkan ke dalam rangkaian Varlife dan dilampirkan ke komputer.

K Zhang menulis CreateROM.py , skrip Python untuk Golly yang melakukan perakitan dan terjemahan. Ini cukup mudah: dibutuhkan program perakitan dari clipboard, merakitnya menjadi biner, dan menerjemahkan biner itu ke sirkuit. Berikut ini contoh dengan tester primality sederhana yang disertakan dengan skrip:

#0. MLZ -1 3 3;
#1. MLZ -1 7 6; preloadCallStack
#2. MLZ -1 2 1; beginDoWhile0_infinite_loop
#3. MLZ -1 1 4; beginDoWhile1_trials
#4. ADD A4 2 4;
#5. MLZ -1 A3 5; beginDoWhile2_repeated_subtraction
#6. SUB A5 A4 5;
#7. SUB 0 A5 2;
#8. MLZ A2 5 0;
#9. MLZ 0 0 0; endDoWhile2_repeated_subtraction
#10. MLZ A5 3 0;
#11. MNZ 0 0 0; endDoWhile1_trials
#12. SUB A4 A3 2;
#13. MNZ A2 15 0; beginIf3_prime_found
#14. MNZ 0 0 0;
#15. MLZ -1 A3 1; endIf3_prime_found
#16. ADD A3 2 3;
#17. MLZ -1 3 0;
#18. MLZ -1 1 4; endDoWhile0_infinite_loop

Ini menghasilkan biner berikut:

0000000000000001000000000000000000010011111111111111110001
0000000000000000000000000000000000110011111111111111110001
0000000000000000110000000000000000100100000000000000110010
0000000000000000010100000000000000110011111111111111110001
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011110100000000000000100000
0000000000000000100100000000000000110100000000000001000011
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000110100000000000001010001
0000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000001010100000000000000100001
0000000000000000100100000000000001010000000000000000000011
0000000000000001010100000000000001000100000000000001010011
0000000000000001010100000000000000110011111111111111110001
0000000000000001000000000000000000100100000000000001000010
0000000000000001000000000000000000010011111111111111110001
0000000000000000010000000000000000100011111111111111110001
0000000000000001100000000000000001110011111111111111110001
0000000000000000110000000000000000110011111111111111110001

Ketika diterjemahkan ke sirkuit Varlife, tampilannya seperti ini:

ROM kemudian dihubungkan dengan komputer, yang membentuk program yang berfungsi penuh di Varlife. Tapi kita belum selesai ...

Terjemahan ke Game of Life

Selama ini, kami telah bekerja di berbagai lapisan abstraksi di atas dasar Game of Life. Tapi sekarang, saatnya untuk menarik kembali tirai abstraksi dan menerjemahkan pekerjaan kita menjadi pola Game of Life. Seperti yang disebutkan sebelumnya, kami menggunakan OTCA Metapixel sebagai basis untuk Varlife. Jadi, langkah terakhir adalah mengubah setiap sel di Varlife menjadi metapixel di Game of Life.

Untungnya, Golly dilengkapi dengan skrip ( metafier.py ) yang dapat mengubah pola dalam aturan berbeda ke pola Game of Life melalui OTCA Metapixel. Sayangnya, ini hanya dirancang untuk mengubah pola dengan satu aturan global, sehingga tidak berfungsi di Varlife. Saya menulis versi modifikasi yang membahas masalah itu, sehingga aturan untuk setiap metapixel dihasilkan berdasarkan sel per sel untuk Varlife.

Jadi, komputer kita (dengan Tetris ROM) memiliki kotak pembatas 1,436 x 5,082. Dari 7.297.752 sel dalam kotak itu, 6.075.811 adalah ruang kosong, meninggalkan jumlah populasi aktual 1.221.941. Masing-masing sel tersebut perlu diterjemahkan ke dalam metapixel OTCA, yang memiliki kotak pembatas 2048x2048 dan populasi 64.691 (untuk metapixel ON) atau 23.920 (untuk metapixel OFF). Itu berarti produk akhir akan memiliki kotak pembatas dari 2.940.928 x 10.407.936 (ditambah beberapa ribu tambahan untuk batas metapixels), dengan populasi antara 29.228.828.720 dan 79.048.585.231. Dengan 1 bit per sel hidup, itu antara 27 dan 74 GiB diperlukan untuk mewakili seluruh komputer dan ROM.

Saya memasukkan perhitungan itu di sini karena saya lalai menjalankannya sebelum memulai skrip, dan sangat cepat kehabisan memori di komputer saya. Setelah killperintah panik , saya membuat modifikasi pada skrip metafier. Setiap 10 baris metapixels, polanya disimpan ke disk (sebagai file RLE yang di-gzip), dan kisi-kisinya memerah. Ini menambahkan runtime tambahan ke terjemahan dan menggunakan lebih banyak ruang disk, tetapi menjaga penggunaan memori dalam batas yang dapat diterima. Karena Golly menggunakan format RLE yang diperluas yang mencakup lokasi pola, ini tidak menambah kerumitan pada pemuatan pola - cukup buka semua file pola pada lapisan yang sama.

K Zhang membangun dari karya ini, dan menciptakan skrip metafier yang lebih efisien yang menggunakan format file MacroCell, yang memuat lebih efisien daripada RLE untuk pola besar. Skrip ini berjalan jauh lebih cepat (beberapa detik, dibandingkan dengan beberapa jam untuk skrip metafier asli), menciptakan output yang jauh lebih kecil (121 KB dibandingkan 1,7 GB), dan dapat mem-metaf seluruh komputer dan ROM dalam sekali gerakan tanpa menggunakan jumlah besar memori. Itu mengambil keuntungan dari fakta bahwa file MacroCell mengkodekan pohon yang menggambarkan pola. Dengan menggunakan file templat khusus, metapixels sudah dimuat sebelumnya ke dalam tree, dan setelah beberapa perhitungan dan modifikasi untuk deteksi tetangga, pola Varlife dapat dengan mudah ditambahkan.

File pola seluruh komputer dan ROM di Game of Life dapat ditemukan di sini .

Masa Depan Proyek

Sekarang kita sudah membuat Tetris, sudah selesai, kan? Bahkan tidak dekat. Kami memiliki beberapa tujuan lagi untuk proyek ini yang sedang kami upayakan:

• muddyfish dan Lithos Kritixi terus bekerja pada bahasa tingkat tinggi yang mengkompilasi ke QFTASM.
• El'endia Starman bekerja pada peningkatan ke penerjemah QFTASM online.
• quartata sedang mengerjakan backend GCC, yang akan memungkinkan kompilasi kode C dan C ++ yang berdiri sendiri (dan berpotensi bahasa lain, seperti Fortran, D, atau Objective-C) ke dalam QFTASM melalui GCC. Ini akan memungkinkan program yang lebih canggih untuk dibuat dalam bahasa yang lebih akrab, meskipun tanpa perpustakaan standar.
• Salah satu rintangan terbesar yang harus kita atasi sebelum kita dapat membuat lebih banyak kemajuan adalah kenyataan bahwa alat kita tidak dapat memancarkan kode bebas posisi (misalnya lompatan relatif). Tanpa PIC, kami tidak dapat melakukan penautan, jadi kami kehilangan keuntungan yang didapat karena dapat menautkan ke perpustakaan yang ada. Kami sedang berusaha mencari cara untuk melakukan PIC dengan benar.
• Kami sedang mendiskusikan program berikutnya yang ingin kami tulis untuk komputer QFT. Saat ini, Pong terlihat seperti tujuan yang bagus.

Bagian 6: Kompiler Baru untuk QFTASM

Meskipun Cogol cukup untuk implementasi Tetris yang belum sempurna, itu terlalu sederhana dan terlalu rendah untuk pemrograman tujuan umum pada tingkat yang mudah dibaca. Kami mulai mengerjakan bahasa baru pada September 2016. Kemajuan bahasa lambat karena sulit untuk memahami bug dan juga kehidupan nyata.

Kami membangun bahasa tingkat rendah dengan sintaksis yang mirip dengan Python, termasuk sistem tipe sederhana, subrutin yang mendukung rekursi dan operator inline. Kompiler dari teks ke QFTASM dibuat dengan 4 langkah: tokeniser, pohon tata bahasa, kompilator level tinggi dan kompilator level rendah.

Tokeniser itu

Pengembangan dimulai menggunakan Python menggunakan pustaka tokeniser bawaan, yang berarti langkah ini cukup sederhana. Hanya beberapa perubahan pada output default yang diperlukan, termasuk stripping komentar (tetapi tidak #includes).

Pohon tata bahasa

Pohon tata bahasa dibuat agar mudah diperluas tanpa harus mengubah kode sumber apa pun.

Struktur pohon disimpan dalam file XML yang mencakup struktur node yang dapat membentuk pohon dan bagaimana mereka dibuat dengan node dan token lainnya.

Tata bahasa yang diperlukan untuk mendukung simpul yang diulang serta yang opsional. Ini dicapai dengan memperkenalkan meta tag untuk menggambarkan bagaimana token dibaca.

Token yang dihasilkan kemudian diuraikan melalui aturan tata bahasa sehingga output membentuk pohon elemen tata bahasa seperti subs dan generic_variables, yang pada gilirannya mengandung elemen tata bahasa dan token lainnya.

Kompilasi menjadi kode tingkat tinggi

Setiap fitur bahasa harus dapat dikompilasi ke dalam konstruksi tingkat tinggi. Ini termasuk assign(a, 12) dan call_subroutine(is_prime, call_variable=12, return_variable=temp_var). Fitur seperti inlining elemen dieksekusi di segmen ini. Ini didefinisikan sebagai operators dan khusus di mana mereka digarisbawahi setiap kali operator seperti +atau %digunakan. Karena itu, mereka lebih dibatasi daripada kode biasa - mereka tidak dapat menggunakan operator mereka sendiri atau operator yang bergantung pada kode yang ditentukan.

Selama proses inlining, variabel internal diganti dengan yang dipanggil. Ini ternyata berlaku

operator(int a + int b) -> int c
    return __ADD__(a, b)
int i = 3+3

ke

int i = __ADD__(3, 3)

Namun perilaku ini dapat merusak dan rawan bug jika variabel input dan variabel output menunjuk ke lokasi yang sama dalam memori. Untuk menggunakan perilaku 'lebih aman', unsafekata kunci menyesuaikan proses kompilasi sehingga variabel tambahan dibuat dan disalin ke dan dari inline sesuai kebutuhan.

Variabel awal dan operasi kompleks

Operasi matematika seperti a += (b + c) * 4tidak dapat dihitung tanpa menggunakan sel memori tambahan. Kompilator tingkat tinggi berurusan dengan ini dengan memisahkan operasi menjadi beberapa bagian:

scratch_1 = b + c
scratch_1 = scratch_1 * 4
a = a + scratch_1

Ini memperkenalkan konsep variabel awal yang digunakan untuk menyimpan informasi antara perhitungan. Mereka dialokasikan sesuai kebutuhan dan dialokasikan ke kolam renang umum setelah selesai. Ini mengurangi jumlah lokasi memori awal yang diperlukan untuk digunakan. Variabel awal dianggap global.

Setiap subrutin memiliki VariableStore sendiri untuk menyimpan referensi ke semua variabel yang digunakan subrutin serta tipenya. Pada akhir kompilasi, mereka diterjemahkan ke dalam offset relatif dari awal toko dan kemudian diberi alamat aktual dalam RAM.

Struktur RAM

Program counter
Subroutine locals
Operator locals (reused throughout)
Scratch variables
Result variable
Stack pointer
Stack
...

Kompilasi tingkat rendah

Satu-satunya hal compiler tingkat rendah harus berurusan dengan adalah sub, call_sub, return, assign, ifdan while. Ini adalah daftar tugas yang jauh berkurang yang dapat diterjemahkan ke dalam instruksi QFTASM dengan lebih mudah.

sub

Ini menempatkan awal dan akhir dari subrutin bernama. Kompiler level rendah menambahkan label dan dalam kasus mainsubrutin, menambahkan instruksi keluar (lompat ke ujung ROM).

if dan while

Baik interpreter tingkat rendah whiledan ifcukup sederhana: mereka mendapatkan pointer ke kondisi mereka dan melompat tergantung pada mereka. whileloop sedikit berbeda karena mereka dikompilasi

...
condition
jump to check
code
condition
if condtion: jump to code
...

call_sub dan return

Tidak seperti kebanyakan arsitektur, komputer yang kita kompilasi tidak memiliki dukungan perangkat keras untuk mendorong dan keluar dari tumpukan. Ini berarti mendorong dan melompat dari tumpukan membutuhkan dua instruksi. Dalam hal muncul, kami mengurangi penunjuk tumpukan dan menyalin nilai ke alamat. Dalam hal mendorong, kami menyalin nilai dari alamat ke alamat di penunjuk tumpukan saat ini dan kemudian bertambah.

Semua penduduk setempat untuk subrutin disimpan di lokasi tetap dalam RAM yang ditentukan pada waktu kompilasi. Untuk membuat rekursi berfungsi, semua penduduk setempat untuk suatu fungsi ditempatkan ke tumpukan pada awal panggilan. Kemudian argumen ke subrutin disalin ke posisi mereka di toko lokal. Nilai dari alamat pengirim dimasukkan ke stack dan subrutin dijalankan.

Ketika sebuah returnpernyataan ditemukan, bagian atas tumpukan muncul dan penghitung program diatur ke nilai itu. Nilai-nilai untuk penduduk setempat dari panggilan subrutin adalah muncul dari tumpukan dan ke posisi sebelumnya.

assign

Tugas variabel adalah hal termudah untuk dikompilasi: mereka mengambil variabel dan nilai dan mengkompilasi ke dalam satu baris: MLZ -1 VALUE VARIABLE

Menetapkan target lompatan

Akhirnya, kompiler menentukan target lompatan untuk label yang dilampirkan pada instruksi. Posisi absolut label ditentukan dan kemudian referensi ke label tersebut diganti dengan nilai-nilai itu. Label sendiri dihapus dari kode dan akhirnya nomor instruksi ditambahkan ke kode yang dikompilasi.

Contoh kompilasi langkah demi langkah

Sekarang kita telah melalui semua tahapan, mari kita pergi melalui proses kompilasi yang sebenarnya untuk program yang sebenarnya, langkah demi langkah.

#include stdint

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, cukup sederhana. Ini harus jelas bahwa pada akhir program, a = 8, b = 12, c = 96. Pertama, mari sertakan bagian-bagian yang relevan dari stdint.txt:

operator (int a + int b) -> int
    return __ADD__(a, b)

operator (int a - int b) -> int
    return __SUB__(a, b)

operator (int a < int b) -> bool
    bool rtn = 0
    rtn = __MLZ__(a-b, 1)
    return rtn

unsafe operator (int a * int b) -> int
    int rtn = 0
    for (int i = 0; i < b; i+=1)
        rtn += a
    return rtn

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, sedikit lebih rumit. Mari kita beralih ke tokeniser dan melihat apa yang keluar. Pada tahap ini, kita hanya akan memiliki aliran token linier tanpa bentuk struktur apa pun

NAME NAME operator
LPAR OP (
NAME NAME int
NAME NAME a
PLUS OP +
NAME NAME int
NAME NAME b
RPAR OP )
OP OP ->
NAME NAME int
NEWLINE NEWLINE
INDENT INDENT     
NAME NAME return
NAME NAME __ADD__
LPAR OP (
NAME NAME a
COMMA OP ,
NAME NAME b
RPAR OP )
...

Sekarang semua token dimasukkan melalui pengurai tata bahasa dan menampilkan pohon dengan nama masing-masing bagian. Ini menunjukkan struktur tingkat tinggi yang dibaca oleh kode.

GrammarTree file
 'stmts': [GrammarTree stmts_0
  '_block_name': 'inline'
  'inline': GrammarTree inline
   '_block_name': 'two_op'
   'type_var': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'a'
    '_global': False

   'operator': GrammarTree operator
    '_block_name': '+'

   'type_var_2': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'b'
    '_global': False
   'rtn_type': 'int'
   'stmts': GrammarTree stmts
    ...

Struktur tata bahasa ini mengatur informasi untuk diuraikan oleh kompiler tingkat tinggi. Ini termasuk informasi seperti jenis struktur dan atribut dari suatu variabel. Pohon tata bahasa kemudian mengambil informasi ini dan menetapkan variabel yang diperlukan untuk subrutin. Pohon itu juga memasukkan semua inline.

('sub', 'start', 'main')
('assign', int main_a, 8)
('assign', int main_b, 12)
('assign', int op(*:rtn), 0)
('assign', int op(*:i), 0)
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'start', 1, 'for')
('call_sub', '__ADD__', [int op(*:rtn), int main_a], int op(*:rtn))
('call_sub', '__ADD__', [int op(*:i), 1], int op(*:i))
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'end', 1, global bool scratch_2)
('assign', int main_c, int op(*:rtn))
('sub', 'end', 'main')

Selanjutnya, kompiler level rendah harus mengubah representasi level tinggi ini menjadi kode QFTASM. Variabel ditetapkan lokasi dalam RAM seperti:

int program_counter
int op(*:i)
int main_a
int op(*:rtn)
int main_c
int main_b
global int scratch_1
global bool scratch_2
global int scratch_3
global int scratch_4
global int <result>
global int <stack>

Instruksi sederhana kemudian dikompilasi. Akhirnya, nomor instruksi ditambahkan, menghasilkan kode QFTASM yang dapat dieksekusi.

0. MLZ 0 0 0;
1. MLZ -1 12 11;
2. MLZ -1 8 2;
3. MLZ -1 12 5;
4. MLZ -1 0 3;
5. MLZ -1 0 1;
6. MLZ -1 0 7;
7. SUB A1 A5 8;
8. MLZ A8 1 7;
9. MLZ -1 15 0;
10. MLZ 0 0 0;
11. ADD A3 A2 3;
12. ADD A1 1 1;
13. MLZ -1 0 7;
14. SUB A1 A5 8;
15. MLZ A8 1 7;
16. MNZ A7 10 0;
17. MLZ 0 0 0;
18. MLZ -1 A3 4;
19. MLZ -1 -2 0;
20. MLZ 0 0 0;

Sintaksnya

Sekarang kita memiliki bahasa yang telanjang, kita harus benar-benar menulis sebuah program kecil di dalamnya. Kami menggunakan indentasi seperti yang dilakukan Python, memecah blok logis dan mengontrol aliran. Ini berarti spasi putih penting untuk program kami. Setiap program lengkap memiliki mainsubrutin yang bertindak seperti main()fungsi dalam bahasa C-like. Fungsi dijalankan di awal program.

Variabel dan tipe

Ketika variabel didefinisikan pertama kali, mereka harus memiliki tipe yang terkait dengannya. Tipe yang didefinisikan saat ini adalah intdan booldengan sintaks untuk array yang ditentukan tetapi bukan kompiler.

Perpustakaan dan operator

Pustaka yang disebut stdint.txttersedia yang mendefinisikan operator dasar. Jika ini tidak termasuk, bahkan operator sederhana tidak akan ditentukan. Kita dapat menggunakan perpustakaan ini dengan #include stdint. stdintmendefinisikan operator seperti +, >>dan bahkan *dan %, yang keduanya bukan opcode QFTASM langsung.

Bahasa ini juga memungkinkan opcode QFTASM langsung dipanggil dengan __OPCODENAME__.

Penambahan dalam stdintdidefinisikan sebagai

operator (int a + int b) -> int
    return __ADD__(a, b)

Yang mendefinisikan apa yang dilakukan +operator ketika diberikan dua ints.