Apakah semantik TeX (sebagai bahasa pemrograman) pernah diformalkan?

Sepertinya saya bahwa bahasa makro yang digunakan oleh mungkin dapat dilihat sebagai semacam sistem penulisan ulang istilah atau semacam bahasa pemrograman dengan pelingkupan panggilan demi nama.$\TeX$

Bahkan implementasi modern dari mesin (mis. ) menafsirkan kode dengan cara yang cukup langsung dan saya tidak mengetahui adanya upaya untuk mengoptimalkan eksekusi (seperti yang dapat dilakukan oleh penerjemah optimisasi modern). Namun, menyusun pengesahan yang benar untuk bahasa seperti akan menjadi sangat sulit karena "aksi di kejauhan" yang dapat dimiliki redefinisi makro, dan kemampuan mendefinisikan-ulang makro dengan memanggilnya dengan nama.X e$\TeX$$\mathit{Xe}\TeX$$\TeX$

Jadi menerapkan juru bahasa pengoptimal hipotesis untuk terdengar masalah yang sangat sulit dalam praktek tetapi juga sangat berguna, karena digunakan di seluruh matematika dan sains dan waktu kompilasi yang lambat adalah kelemahan yang diketahui dari sistem. Perhatikan bahwa sebagian besar waktu dihabiskan untuk menerjemahkan kode, bukan menghitung penyusunan huruf yang sebenarnya, terutama ketika paket-paket yang berat secara komputasi digunakan (seperti ).$\TeX$$\TeX$tikz

Mungkin semantik formal untuk bahasa itu bisa menjadi awal untuk mengatasi masalah tersebut. Jadi apakah semantik bahasa pemrograman pernah diformalkan?$\TeX$

(Dengan permintaan maaf untuk jawaban panjang yang mengarah ke arah yang berbeda dari ruang lingkup situs: terus terang saya terkejut melihat pertanyaan di sini di tempat pertama ....)

TeX dirancang untuk pengaturan huruf, bukan untuk pemrograman; jadi itu yang terbaik "aneh" ketika dianggap sebagai bahasa pemrograman.

- Donald Knuth, Digital Typography, halaman 235

Saya telah membaca banyak selama beberapa tahun terakhir tentang sejarah awal (sekitar 1977) dari TeX, dan banyak dari apa yang ditulis Knuth. Kesimpulan saya adalah bahwa saat kita berbicara tentang "TeX (sebagai bahasa pemrograman)" , ada sesuatu yang salah.

Jika kita melihat "dokumen desain" awal untuk TeX yang ditulis sebelumnya (lihat TEXDR.AFTdan TEX.ONE, diterbitkan dalam Tipografi Digital ), jelas bahwa Knuth sedang merancang sistem yang terutama ditujukan untuk penyusunan huruf The Art of Computer Programming (katanya (misalnya di sini ) bahwa pengguna utama yang ada dalam pikirannya adalah dirinya sendiri dan sekretarisnya), dengan gagasan bahwa, sesuai dimodifikasi, mungkin lebih bermanfaat secara umum. Untuk menghemat pengetikan, untuk hal-hal yang harus dilakukan berulang kali (mis. Setiap kali TAOCP perlu menyertakan kutipan dari penulis, Anda ingin memindahkan secara vertikal dengan jumlah tertentu, mengatur beberapa baris, menggantinya, mengambil font tertentu, mengeset huruf kutipan benar, ambil font lain, ketikkan nama penulis ...), ada makro.

Anda bisa menebak sisanya. Apa yang kita miliki di TeX adalah kasus "Turing-selesai tanpa sengaja" ( lebih ), kecuali bahwa itu terjadi di tengah-tengah komunitas (ilmuwan komputer dan ahli matematika, dan DEK sendiri yang harus "disalahkan" juga) yang (sayangnya) terlalu pintar untuk mengabaikan ini. (Legenda mengatakan bahwa Michael Spivak belum pernah memprogram sebelum dia menemukan TeX, tetapi dia begitu tertarik dengannya sehingga dia akhirnya menulis AMS-TeX, pada saat itu salah satu set makro yang paling rumit yang ada.) Karena TeX ditulis untuk menjadi portabel di sejumlah besar sistem (yang merupakan masalah besar pada saat itu), selalu ada godaan untuk melakukan segalanya di TeX. Selain itu, karena pengalaman menulis kompilernya, Knuth menulis TeX seperti kompiler, dan kadang-kadang menggambarkannya sebagai satu, dan jika program yang bekerja pada input Anda adalah "kompiler", maka pasti Anda sedang pemrograman, bukan?

Anda dapat membaca sedikit lebih banyak tentang bagaimana Knuth tidak bermaksud untuk pemrograman apa pun dilakukan di TeX, dan bagaimana dia “memasukkan banyak fitur pemrograman TeX hanya setelah menendang dan menjerit”, dalam jawaban ini . Apa pun niatnya, seperti yang saya katakan, orang mulai mencari cara untuk (ab) menggunakan sistem makro TeX untuk mencapai prestasi pemrograman yang mengejutkan. Knuth menemukan ini menarik dan (selain menambahkan beberapa fitur ke TeX sendiri) termasuk beberapa dari ini dalam Lampiran D "Trik Kotor" dari TeXbook, tetapi ternyata, terlepas dari namanya, bahwa "sembilan dari sepuluh contoh di dalamnya adalah digunakan dalam implementasi LaTeX ”.

Biar saya katakan lain: LaTeX, sistem makro yang Leslie Lamport tulis di atas TeX, sebagai sebuah ide , adalah yang hebat. Mengarang dokumen dengan cara semantik, terstruktur, berorientasi pada manusia, dan bukannya (Knuth) berorientasi pada halaman TeX, (atau sebagaimana Lamport menyebutnya, logis daripada visual ) adalah cara yang hebat. Tetapi menerapkan sesuatu yang rumit seperti LaTeX menggunakan makro TeX daripada dalam bahasa pemrograman yang "tepat" adalah, dalam pandangan saya dan setidaknya jika itu dilakukan hari ini, di suatu tempat antara kesalahan raksasa dan tindakan kesesatan nakal. Bahkan Knuth terkejut bahwa orang tidak hanya memperpanjang program TeX daripada melakukan semua yang ada di makro TeX.

Saat ini ada banyak cara yang lebih baik untuk melakukan "pemrograman"; Anda dapat menggunakan program eksternal dalam salah satu dari banyak bahasa yang tersedia secara luas di komputer kebanyakan orang, atau Anda dapat menggunakan LuaTeX dan program di Lua (dan melakukan pekerjaan yang lebih baik daripada yang pernah Anda lakukan dengan makro TeX saja, karena Anda dapat memanipulasi struktur internal dan algoritma di tingkat yang tepat). Dan jika Anda melakukannya dengan benar, Anda bisa memiliki program yang bekerja lebih baik atau lebih cepat daripada yang diterapkan di makro TeX.

Tugas membuat program di TeX lebih cepat hampir lucu ketika dilihat dari sudut pandang ini, dan mengingatkan saya pada kata-kata terakhir dari makalah yang menggambarkan bahasa pemrograman "bahasa" lengkap "Turing yang tidak sengaja selesai": bahasa Tom Wildenhain yang indah " Pada Kelengkapan Turing MS PowerPoint ( video ) dari tahun lalu:

Sementara PPTXTM membuktikan kemungkinan teoritis pengembangan PowerPoint, [...]. Pekerjaan juga perlu dilakukan dalam optimasi aplikasi PowerPoint. Ada banyak potensi di sini untuk mengeksploitasi penyangga otomatis slide PowerPoint berikutnya, yang melalui penempatan slide yang cermat dapat digunakan untuk sangat meningkatkan kinerja aplikasi.

The anekdot yang Lipton menjelaskan ilustrasi. Tidak hanya tidak pernah ada semantik formal TeX, ada juga kemungkinan tidak akan ada. Itu terlalu "aneh" sebuah "bahasa" untuk itu, dan (seperti yang saya harap saya jelaskan di atas) itu bahkan tidak dimaksudkan sebagai bahasa. Sebagai contoh, Anda mungkin berpikir Anda sedang menulis makro sebagai fungsi, tetapi memperkenalkan karakter sesat tunggal (bahkan spasi ) di dalamnya, dan TeX segera memperlakukannya sebagai instruksi penyusunan huruf.

Singkatnya: TeX kembali ke pengaturan huruf pada kesempatan yang paling awal, dan ketika memperluas makro, ia melakukannya dengan enggan (tidak sabar untuk mendapatkan karya pengaturan huruf yang "nyata"), dan ekspansi ini sendiri dapat bergantung pada ratusan jenis "negara" di dalam program TeX (nilai-nilai parameter seperti \hsizeatau \baselineskip, isi kotak dan register lainnya ...), itulah sebabnya semantik formal TeX tentu harus menjadi sesuatu yang memperhitungkan seluruh keadaan program dan semua memorinya, hingga kami berakhir dengan sesuatu seperti "makna kode TeX adalah apa pun yang dilakukan TeX", dalam bentuk yang lebih kompleks daripada program TeX itu sendiri.

Sangat bagus, (jika saya sudah meyakinkan Anda) TeX tidak dimaksudkan sebagai bahasa pemrograman dan tidak berfungsi seperti bahasa asli, tidak ada semantik formal, dan ada cara yang lebih baik untuk memprogram hari ini - tetapi semua ini tidak membantu Anda sebenarnya pertanyaan / masalah, yang adalah bahwa dalam prakteknya, banyak dokumen dimaksudkan untuk memproses oleh TeX melakukan penggunaan rumit macro (seperti LaTeX dan TikZ), bangunan-bangunan menakjubkan kompleksitas mengerikan dibangun di atas satu sama lain. Bagaimana kita dapat membuatnya lebih cepat dan menyusun "pass optimasi"?

Anda tidak akan sampai di sana dengan semantik formal IMO. Saya baru-baru ini memikirkan hal ini, dan berikut ini adalah beberapa pemikiran awal.

Kesan saya adalah bahwa Knuth adalah salah satu penulis kompiler berpengalaman pada tahun 1960-an (itulah sebabnya ia diminta untuk menulis buku kompiler yang berubah menjadi The Art of Computer Programming ), dan TeX (dalam banyak hal) menulis dengan cara yang sama seperti kompiler ditulis pada 1970-an, katakanlah. Teknik dan desain kompiler telah meningkat sejak saat itu, dan demikian juga program TeX. Berikut beberapa hal yang bisa dilakukan, dengan cara mempercepat:

• Pada intinya, TeX ditulis seperti "rutin interpretatif", di mana TeX "mata" dan "mulut" (rutinitas inputnya) mengirimkan instruksi ke "perutnya" (rutinitas semantiknya), untuk dieksekusi satu per satu. (Anda dapat melihat daftar di bagian 15 dari program TeX .) Misalnya, ketika mata / mulut TeX bertemu \hfillatau \hskipdalam inputnya, perut mendapat perintah "hskip", yang ditindaklanjuti. Ini mirip dengan apa yang disebut bytecode interpreter hari ini, dan mungkin ada nilai dalam refactoring program TeX untuk memancarkan bytecode / opcode ini secara eksplisit, sehingga kita mungkin dapat menggunakan teknik kompiler yang ada (lebih konvensional saat ini). Atau setidaknya cache mereka untuk menghindari pengerjaan ulang. Tentu saja ada banyak tantangan:

  • Eksekusi perintah di "perut" biasanya masih melibatkan pembacaan input, yaitu pekerjaan rutin input dan rutin semantik tidak terjadi dalam fase terpisah. Misalnya perintah "hskip", jika diberikan \hskip(alih-alih mengatakan \hfill) akan meminta scan_glueuntuk membaca spesifikasi lem dari input, yang pada gilirannya dapat melibatkan perluasan makro dan seterusnya sampai cukup banyak token yang ditemukan untuk lem, meninggalkan tumpukan input dalam keadaan yang sangat berbeda.

  • Mesin seperti eTeX dan pdfTeX dan XeTeX dan LuaTeX memperkenalkan perintah dan primitif baru (primitif eTeX / pdfTex secara praktis digunakan oleh semua orang dalam praktik); Anda harus mendukung mereka juga, bukan hanya mereka yang ada di program TeX Knuth yang asli.

• Kita bisa melakukan sesuatu seperti "eksekusi spekulatif", memproses paragraf di masa depan (mungkin dimulai dari pos pemeriksaan alami seperti bagian atau bab baru) secara paralel (menggunakan beberapa core), melacak semua keadaan internal TeX yang mereka gunakan (bergantung pada), dan melempar menyingkirkan pekerjaan itu (dan mengulanginya) jika nanti kita mengetahui bahwa paragraf sebelumnya akhirnya mengubah beberapa keadaan itu. Saat ini TeX berjalan seluruhnya secara berurutan pada 1 prosesor; perangkat keras tipikal telah bergerak ke arah yang berbeda dan beberapa core tersedia.

• Lebih sederhana lagi, kita hanya bisa men-cache pekerjaan (keadaan TeX apa yang diakses dan dimodifikasi) oleh bagian tertentu dari file input. (Kita bisa melakukan caching ini di tingkat input — hasil bersih dari perluasan semua makro — atau pada tingkat kumpulan kotak yang dirakit, atau semua jalan ke kondisi total program.) Misalnya konten di dalam a \begin{tikzpicture} … \end{tikzpicture}tidak mungkin banyak bergantung pada keadaan TeX seperti penghitung nomor halaman, jadi ketika kita mengkompilasi ulang dokumen TeX kita dapat menggunakan kembali semua pekerjaan - jika kita telah melacak informasi yang cukup untuk mengetahui bahwa itu aman untuk dilakukan. (Tentu saja TikZ memiliki cara untuk mengeksternalisasi ini dan memasukkan hasilnya, tetapi idenya lebih umum.)

• Kita dapat menggunakan teknik (misalnya yang digunakan dalam pemrograman fungsional) untuk melakukan beberapa pemrosesan TeX dengan "hole" - misalnya saat ini, ketika Anda menulis \ref{foo}di LaTeX untuk merujuk ke nomor bagian (katakanlah nanti), ia hanya bekerja dalam dua lompatan kompilasi: pertama seluruh dokumen diproses (semua paragraf mengeset, mengapung diposisikan pada halaman, dll) dengan nomor bagian dituliskan ke file tambahan, kemudian pada lulus kedua semuapekerjaan dilakukan lagi, dengan nomor bagian sebenarnya tersedia saat ini. (Jenis peretasan ini mungkin tidak dapat dihindari pada saat itu, dan saya tahu dampak pada waktu berjalan adalah "hanya faktor konstan", tetapi ....) Sebaliknya, bagaimana jika kita bisa memproses dokumen dengan "lubang" ( sebuah kotak dengan isi yang tidak ditentukan tetapi beberapa lebar diperkirakan) tersisa untuk nomor bagian, lalu pada akhir pemrosesan dokumen mengisi kotak? (Ya, perkiraan lebar kami mungkin salah dan paragraf mungkin perlu diproses ulang dan bahkan halaman, tetapi kami bisa melakukan pekerjaan jika perlu, atau menerima, untuk kecepatan, mode di mana kami akan membiarkan lebar yang salah untuk nomor bagian.)

• Teknik serupa dapat bekerja untuk pengeditan dokumen TeX secara interaktif: ketika Anda mengedit paragraf, dapat diproses "langsung", dengan paragraf berikutnya cukup dipindahkan ke dapur (katakanlah). Kami tahu itu mungkin, karena sudah ada implementasi TeX (komersial) yang melakukan ini, misalnya BaKoMaTeX dan Texpad dan Textures sebelumnya . (Lihat video di halaman beranda BaKoMa-TeX dan juga video TeXpad, misalnya video ini - saya mencoba yang terakhir dan dalam praktiknya kereta itu tidak tertahankan.)

• Tidak bisa diremehkan: nilai menunjukkan sesuatu kepada pengguna, membuat TeX lebih bisa disangkal. Saat ini, pengguna hanya melihat input TeX mereka dan tidak tahu persis apa pekerjaan yang dilakukan TeX, misalnya berapa banyak waktu yang dihabiskan untuk pemecahan garis untuk paragraf, atau pada ekspansi makro (dan makro mana), kotak apa yang dirakit dan membuang, spesial apa yang sedang ditulis oleh paket mana, dll. Saya (mungkin optimis) percaya bahwa ada pengguna yang ingin melihat informasi ini dan akan merasa berguna misalnya untuk mengetahui apakah paket aneh yang mereka gunakan untuk shading persamaan dengan gradien di latar belakang murah (menambahkan sedikit ke waktu pemrosesan) atau tidak. Dengan melihat di mana banyak pekerjaan sia-sia sedang dilakukan, mereka dapat membuang sebagian (setidaknya sampai cetakan terakhir mereka berjalan). (Ini agak seperti kompiler atau alat lain yang memasukkan informasi profil ke dalam program.) Membuat TeX lebih transparan dan dapat ditiadakan mungkin merupakan peningkatan kegunaan yang besar, misalnya. (TeX sudah sangat user-friendly dan dapat ditiadakan untuk IMO waktunya jika kita menggunakan kebanyakan TeX polos dengan makro yang sangat sedikit, tetapi tidak dengan LaTeX atau bagaimana sebagian besar pengguna menjumpainya hari ini.)

Juga, setiap pekerjaan di masa depan mungkin harus mempertimbangkan (membangun) LuaTeX yang merupakan modifikasi terbaik dari TeX yang kami miliki saat ini.

Semua ini hanyalah pemikiran kosong (saya belum mengimplementasikannya, untuk mengetahui upaya yang diperlukan atau berapa banyak peningkatan yang akan kita peroleh), tapi saya harap ini bisa menjawab pertanyaan Anda atau memberi Anda ide untuk arah di masa depan. .

Tidak, setahu saya belum ada upaya untuk memformalkan TeX dari jenis yang Anda minati.

(Berikut ini adalah komentar subjektif dan pribadi). Saya pikir itu adalah ide yang menarik dan berpose bagus, dan motivasi Anda untuk menggunakannya untuk melakukan optimasi terdengar masuk akal - pertanyaan lain yang terkait adalah apakah Anda dapat menentukan format bytecode untuk mempercepat interpretasi. Di sisi lain, idenya memiliki dua kelemahan.

Pertama, tidak jelas bagi saya bahwa ada potensi besar untuk optimasi (misalnya, jenis transformasi pelestarian program apa yang dapat dilakukan seseorang untuk mempercepat perhitungan?), Karena mungkin semantik bahasa terkait erat dengan penguraian aliran karakter, dan dengan demikian tidak terlalu akomodatif dengan desain representasi perantara yang ramah-optimasi.

Kedua, kebutuhan untuk perbaikan dalam kecepatan interpretasi TeX tidak mapan: kecepatan pembangunan kecepatan batch tetap masuk akal berkat perbaikan perangkat keras. Kasus-kasus di mana speedup dapat diterima adalah paket grafik yang kompleks (presentasi beamer dapat memakan waktu cukup lama untuk dibuat), paket yang menyertakan perhitungan kaya (tapi kemudian bahasa lain mungkin lebih tepat), dan kasus-kasus penggunaan yang membutuhkan pembangunan kembali yang cepat untuk umpan balik pengguna instan (tetapi kemudian incrementality, daripada optimisasi, mungkin adalah intinya; semantik formal pasti akan membantu alasan tentang implementasi inkremental juga).

Artinya: ini terdengar seperti topik yang menyenangkan dan instruktif, tetapi tidak jelas bagi saya bahwa pembenaran praktis untuk melakukan pekerjaan itu kuat. Jika seseorang tertarik untuk melakukannya karena penasaran, itu terdengar seperti petualangan yang luar biasa, tetapi sebaliknya mungkin ada cara lain untuk menggunakan skillet yang sama yang pengaruhnya akan lebih dicari oleh pengguna akhir.