TypeScript Ternyata Cukup Oke untuk Implementasi Kompiler

 (matklad.github.io)
8 poin oleh GN⁺ 2023-08-20 | 1 komentar | Bagikan ke WhatsApp
  • Bahasa implementasi untuk alat bergaya kompiler secara tradisional terbagi antara OCaml dan C++, tetapi untuk eksperimen bahasa kecil, TypeScript bisa menjadi pilihan yang ringan seperti bahasa keluarga ML
  • Rust menggabungkan kelebihan ML dan C++ serta menyediakan multithreading aman, tetapi karena perlu memodelkan tata letak fisik data, ia bisa terasa berat untuk prototipe kecil
  • Deno membantu memulai eksperimen bahasa dengan TypeScript dengan cepat berkat biner tunggal, linting dan formatting bawaan, tanpa tahap kompilasi, serta task runner dan mode watch
  • Type checker contoh menggabungkan AST generik, tagged union, visitor, dan transform bottom-up untuk mengubah Expr<void> menjadi Expr<Type>, serta memasukkan TypeError sebagai nilai tipe guna mengurangi error berantai
  • TypeScript bisa produktif sebagai alat untuk eksperimen bahasa kecil berkat autocompletion, sistem tipe yang fleksibel, dan karakteristik runtime yang memungkinkan kita beralih ke pendekatan dinamis saat diperlukan

Pola lama dalam memilih bahasa implementasi

  • Saat membuat alat berbentuk kompiler, secara umum ada dua arus besar dalam pemilihan bahasa implementasi
  • Untuk pekerjaan yang berpusat pada implementasi dan perlu kesiapan produksi, C++ sering dipilih
    • LLVM, clang, v8, dan HotSpot semuanya berbasis C++
  • Rust secara langsung dipengaruhi oleh ML dan C++, menggabungkan kelebihan keduanya, dan juga menawarkan kekuatan khasnya sendiri seperti multithreading yang aman
    • Namun, dalam spektrum ini Rust lebih condong ke sisi kesiapan produksi
    • Sistem build yang “langsung jalan” memang membantu untuk prototyping, tetapi ikut membawa kompleksitas tambahan karena kita harus memodelkan tata letak fisik data

Kelebihan pendekatan indeks di Rust dan bebannya untuk kode kecil

  • Saran umum saat membuat kompiler dengan Rust adalah menghindari pointer dan menggunakan indeks
  • Indeks memiliki berbagai kelebihan pada codebase besar
    • Side table bisa ditempatkan di dalam modul terkait sehingga coupling lebih rendah
    • Indeks berupa u32 dan mendorong tata letak struct-of-arrays yang menguntungkan untuk performa
    • Mudah diserialisasi atau dihubungkan ke framework incremental compilation sehingga strategi komputasi lebih fleksibel
  • Namun, dalam pemrograman skala kecil, pendekatan indeks itu sendiri bisa merepotkan, dan untuk eksperimen hobi beban ini bisa menjadi fatal
  • OCaml masih terasa agak kuno, dan dalam konteks ini dipertimbangkan apakah TypeScript dapat dipakai sebagai alternatif yang setara dengan ML

Lingkungan eksperimen cepat dari Deno dan TypeScript

  • deno digunakan sebagai lingkungan awal
    • Ia memberikan pengalaman langsung pakai untuk TypeScript
    • Di OCaml bagian ini merupakan titik sakit, dan meski Rust lebih baik daripada OCaml atau C++, Deno tetap memberi pengalaman yang lebih sederhana daripada Rust
  • Pengalaman pengembangan di Deno sangat cocok untuk hacking PLT skala kecil
    • Biner tunggal
    • Linting dan formatting bawaan
    • Tidak ada tahap kompilasi terpisah
    • Ada task runner dan mode watch bawaan
  • TypeScript sendiri menyediakan sistem tipe yang cukup fleksibel sambil tetap ringan dari sisi beban sintaks

Pola TypeScript yang terlihat dari contoh type checker kecil

  • AST dimulai dari ekspresi yang memiliki informasi lokasi file
    • Location memiliki file, line, column
    • Di TypeScript, string tetap hanya string, angka tetap hanya number, jadi tidak perlu memikirkan pembedaan seperti usize dan u32
  • Ekspresi dipisahkan antara lokasi dan kind, lalu belakangan data terkait digenerikkan menjadi bentuk Expr<T>
    • Ekspresi tepat setelah parsing memiliki data void
    • Ekspresi yang telah diproses type checker memiliki data Type
    • Fungsi inferensi tipe menerima ast.Expr<void> dan mengembalikan ast.Expr<Type>
  • Karena TypeScript tidak otomatis menambahkan perilaku runtime, untuk melakukan matching pada union type kita perlu memasukkan informasi tipe runtime sendiri
    • Field seperti tag: "binary", tag: "if" menjalankan peran ini
    • tag: "binary" berarti pada runtime nilai tersebut hanya bisa berupa string "binary"
  • Literal boolean dan literal int hampir berbentuk sama sehingga diabstraksikan sebagai ExprLiteral<T, V, Tag>
    • ExprBool<T> adalah ExprLiteral<T, boolean, "bool">
    • ExprInt<T> adalah ExprLiteral<T, number, "int">
  • Nilai tipe dipisah menjadi TypeBool, TypeInt, dan nilai singleton juga disediakan dengan nama yang sama
    • TypeScript menghapus tipe sepenuhnya, sehingga nama terkait tipe dan nama terkait nilai berada di namespace terpisah
    • Karakteristik ini memungkinkan kita mendefinisikan tipe dan nilai dengan nama yang sama

Visitor, transform, tipe error, desugaring

  • switch di TypeScript adalah statement, bukan expression, jadi untuk menangani kind ekspresi dengan nyaman didefinisikan visitor
    • Metode bool, int, binary, if masing-masing menangani kind terkait
    • Autocompletion editor membantu baik untuk case switch maupun implementasi visitor
  • transform<U, V> adalah fungsi traversal umum yang mengubah Expr<U> menjadi Expr<V>
    • Transformasi dijalankan secara bottom-up
    • Saat mengunjungi node internal, subekspresi sudah lebih dulu ditransformasi, sehingga tipe visitor menjadi Visitor<V, V>, bukan Visitor<U, V>
  • Dengan memanfaatkan sifat TypeScript sebagai bahasa bertipe dinamis, kita juga bisa membuat traversal yang lebih umum dengan Object.keys
    • Bahkan dalam kasus ini, signature fungsi statis tetap bisa dipertahankan
    • Pada contoh hal ini tidak wajib, tetapi bila perlu ada ruang untuk turun ke pendekatan dinamis
  • Error tipe tidak dikumpulkan ke array sebagai efek samping, melainkan direpresentasikan dengan tipe TypeError
    • Type menjadi TypeBool | TypeInt | TypeError
    • TypeError memiliki tag: "Error", location, message
    • type_equal mengembalikan true jika salah satu sisi adalah Error untuk mencegah kegagalan berantai
  • Type checker akhir memeriksa binary dan if
    • Jika tipe operand kiri dan kanan pada ekspresi binary berbeda, ia mengembalikan error "binary expression operands have different types"
    • Jika kondisi pada ekspresi if bukan boolean, ia mengembalikan error "if condition is not a boolean"
    • Jika tipe branch then dan else berbeda, ia mengembalikan error "if branches have different types"
  • Hasil akhirnya memang tetap memerlukan sedikit penulisan tipe, tetapi sangat dibantu oleh autocompletion, terasa lebih sedikit “berkelahi dengan bahasa”, dan cocok secara alami dengan bentuk masalahnya
  • Alasan TypeScript produktif sebagai alat untuk eksperimen bahasa kecil diringkas menjadi tiga hal
    • Deno adalah runtime scripting yang kecil, tertutup, kuat, dan dioptimalkan untuk workflow pengembangan yang efektif
    • Tooling TypeScript membuat IDE berguna dan produktif, dan berkat Deno tidak memerlukan konfigurasi
    • Bahasanya kuat baik di runtime maupun compile time, mampu mengekspresikan hal yang cukup canggih lewat tipe, tetapi tetap memungkinkan beralih ke pendekatan dinamis bila perlu
  • Sebagai ide tambahan, banyak syntactic sugar juga bisa di-desugar dengan aman secara tipe
    • Expr dan ExprKind diparameterkan secara rekursif terhadap keseluruhan ExprKind, bukan terhadap data terkait
    • ExprKindCore merepresentasikan himpunan ekspresi dasar
    • ExprKindSugar mencakup ekspresi dasar atau ekspresi yang bisa di-desugar ke ekspresi dasar
    • desugar(expr: ExprSugar): ExprCore mereduksi ekspresi syntactic sugar menjadi ekspresi inti
    • desugar_one(expr: ExprKindSugar<ExprCore>): ExprKindCore<ExprCore> melakukan transformasi satu langkah saat subekspresi sudah berada dalam keadaan ter-desugar

Bacaan terkait

1 komentar

 
GN⁺ 2023-08-20
Opini Hacker News

  • TypeScript secara keseluruhan adalah bahasa yang bagus, dan fakta bahwa fungsi adalah objek yang bisa memiliki properti/metode masih kurang diapresiasi
    Anda bisa menjalankan array fungsi seperti perintah, lalu belakangan menambahkan deskripsi seperti help, atau menambahkan state dengan closure/partial application, sehingga tidak perlu buru-buru mendefinisikan kelas seperti Command
    Dalam pemrograman berorientasi objek, memberi nama terlalu dini sering menimbulkan banyak konflik, dan menurut saya lebih natural mengoper nilai yang diperlukan ke fungsi daripada struktur seperti VideoCompressor#compress()

    • Tepatnya, ini lebih merupakan fitur JavaScript daripada TypeScript
      Bahasa lain yang mendukung objek yang bertindak seperti fungsi dirangkum di https://en.wikipedia.org/wiki/Function_object
    • Di Go, fungsi juga bisa diberi metode, dan pada dasarnya itu bisa dilakukan pada tipe apa pun
      Seperti handler di net/http, sebuah struct bisa mengimplementasikan metode serve, atau sebuah fungsi handler bisa memanggil dirinya sendiri untuk memenuhi interface
      Di Clojure, metadata bisa ditempelkan pada var fungsi untuk menangani hal serupa, dan karena ini Lisp, hampir apa pun bisa dilakukan dengan makro
      Selain itu, kanal CSP di core/async memisahkan eksekusi dan komunikasi sehingga membantu menghindari masalah warna fungsi seperti callback/promise/async/await, dan perintah dapat bertindak seperti produsen yang mengirim hasil ke kanal
    • Efek serupa juga bisa dicapai dengan single-method interface di Java
      Apa pun nama metodenya, ia bisa digunakan dalam konteks fungsi, dan tidak perlu merujuk nama metode konkretnya
      Namun, saya tidak suka jika fungsi memiliki properti untuk memuat state sehingga perilakunya bisa berubah meski dipanggil dengan argumen yang sama. Menurut saya salah satu keunggulan besar pemrograman fungsional adalah menjauh dari state ala OOP
    • Python mendukung arah seperti ini dengan baik karena semuanya adalah objek
    • Di C#, fungsi yang memiliki nilai balik dapat direpresentasikan dengan Func, dan fungsi tanpa nilai balik dengan Action, dengan cara yang mirip
      Ekspresi lambda JavaScript cukup mirip dengan C#, dan signature fungsi TypeScript dan C# juga cukup serupa
      Ada juga repositori kecil yang menunjukkan kemiripan JavaScript, TypeScript, dan C#: https://github.com/CharlieDigital/js-ts-csharp
      Screenshot yang menampilkan logika yang sama dalam JS/TS/C# berdampingan: https://github.com/CharlieDigital/js-ts-csharp/blob/main/js-...

  • Tidak terlalu mengejutkan. Menurut saya TypeScript pada akhirnya juga merupakan satu lagi bahasa yang dengan susah payah mengadopsi cukup banyak fitur keluarga ML
    Karena tidak ada pattern matching sungguhan, ia lebih merepotkan daripada OCaml, tetapi jika dibandingkan dengan kelompok seperti C#, Swift, Dart, dan Kotlin, levelnya masih cukup lumayan

    • Ini perbandingan yang hanya dilihat dari level terlalu tinggi. Rasa pemakaian nyatanya cukup berbeda
      TypeScript punya sistem tipe yang kuat, tetapi standard library dasarnya dan bahasanya sendiri terasa kurang memuaskan, dan tidak ada pattern matching/switch expression
      Dart memiliki model objek yang tertutup sehingga kebebasan dinamisnya rendah, sistem tipe dan ekspresinya juga lebih lemah, dan hampir tidak ada fasilitas metaprogramming, sehingga harus bergantung pada boilerplate gaya Java dan generator kode
      C# adalah yang paling dekat dengan fitur ML di antara bahasa yang disebutkan, tetapi tidak seperti TypeScript, ia tidak memiliki sum type, sehingga banyak hal menjadi lebih merepotkan
    • Dulu, pada compiler pembelajaran bergaya Pascal-C yang dibuat dengan Haskell, parser combinator memungkinkan tata bahasa diekspresikan langsung dalam kode dengan bentuk mirip BNF
      Misalnya, parser yang mengenali { ... } bisa dikombinasikan dengan parser lain, dan statement dapat didefinisikan sebagai salah satu dari control flow/deklarasi/assignment
      Pemrosesan list dan pattern matching ala ML sangat ekspresif saat menangani representasi antara
    • Saat membutuhkan pattern matching di TypeScript, saya sering memakai library ini: https://github.com/gvergnaud/ts-pattern
    • Sulit untuk mengatakan bahwa TypeScript mengambil sebagian besar fitur ML
      Di artikel utama pun, karena switch bukan expression, mereka harus memutar lewat visitor pattern, dan dukungan iterator JavaScript juga anehnya kurang
      .map() memang ada, tetapi hanya bekerja pada array dan tidak bisa langsung diterapkan pada iterator umum
    • Jika memakai TypeScript dan kotlin-js, kedua bahasa itu terasa cukup dekat
      Ada banyak perbedaan, tetapi transisinya tidak sulit, dan secara pribadi saya lebih menyukai Kotlin, meski keduanya bisa digunakan
      Saya bertanya-tanya bagaimana jadinya jika TypeScript lepas dari kompatibilitas JavaScript dan dikompilasi ke WASM. Kotlin sedang menambahkan compiler WASM dan sudah memiliki transpiler JS, tetapi kode yang sama lebih kecil dan lebih cepat dimuat di WASM
      JavaScript di browser bukan target kompilasi yang baik, dan karena makin banyak proyek baru dimulai langsung dengan TypeScript sejak awal, alasan bahwa harus mudah bermigrasi dari JavaScript lama juga makin melemah

  • Saat berpindah-pindah antara Rust dan TypeScript, sangat jelas terasa betapa hilangnya fitur seperti tagged enum
    Proposal enum ADT tampaknya berhenti, jadi saya penasaran apakah ada upaya lain: https://github.com/Jack-Works/proposal-enum/discussions/19

    • Untuk kegunaan serupa, menurut saya discriminated union bekerja cukup baik

  • Sistem tipe TypeScript memang menarik, tetapi jadi penasaran seberapa jauh lebih cepat jika compilernya ditulis dalam bahasa yang dikompilasi
    Tentu saja perlu prasyarat besar berupa “implementasi yang baik”

    • swc dan esbuild bukan pembanding yang bagus. Sebagian besar peningkatan kecepatannya berasal dari menghapus sintaks khusus TypeScript untuk menghasilkan JavaScript
      tsc cenderung lambat hanya pada eksekusi pertama, dan jika memakai flag incremental atau mode watch --transpile-only, waktu kompilasi biasanya turun di bawah 100 ms sehingga hampir tidak terasa berbeda dari SWC atau ESBuild
    • Ada jawaban dari tim TypeScript: https://twitter.com/drosenwasser/status/1260723846534979584
      Intinya, jika pemeriksaan tipe pada program berukuran menengah memakan waktu 20 detik, biasanya itu bukan karena JS, melainkan karena tipenya menyebabkan ledakan kombinatorial
      Runtime lain bisa memberi keuntungan dalam paralelisme atau waktu startup, tetapi katanya mereka belum melihat benchmark berpusat CPU yang mendukung peningkatan kecepatan total 20 kali lipat
    • Sistem tipe itu menarik sampai benar-benar dimanfaatkan semaksimal mungkin pada generic
      Lalu setelah seharian men-debug 5 baris logika tipe, kita akan bertanya-tanya bagaimana bisa sampai sejauh ini
    • Tidak perlu lagi hanya membayangkan: https://github.com/dudykr/stc
      Ini proyek yang ditulis dalam Rust oleh pengembang utama SWC; SWC mengompilasi TS ke JS, sedangkan STC memeriksa tipe TS
    • Performa compiler TypeScript belakangan ini sudah jauh membaik
      isolated declaration mode yang akan datang disebut bisa memangkas waktu kompilasi hingga 75%: https://github.com/microsoft/TypeScript/pull/53463#issuecomm...

  • Untuk orang yang baru mulai belajar compiler, saya merekomendasikan buku ini: https://keleshev.com/compiling-to-assembly-from-scratch/
    Penulisnya menjelaskan cara membuat compiler assembly ARM 32-bit dengan subset TypeScript, dan bentuknya hampir seperti pseudocode sehingga mudah didekati

    • Crafting Interpreters juga sangat direkomendasikan: https://craftinginterpreters.com/
      Bukunya terbagi menjadi dua bagian; bagian pertama membuat interpreter bahasa dengan Java, dan bagian kedua mengompilasi bahasa yang sama ke bytecode lalu mengimplementasikan VM bytecode dalam C
      Setiap baris kode implementasinya dirujuk di dalam buku

  • Jika ingin menghindari visitor pattern, bisa memakai switch bergaya IIFE dengan fungsi utilitas run
    Caranya, gunakan switch di dalam fungsi yang langsung dieksekusi dan biarkan tipe kembaliannya diinferensi

    • Saya pernah menulis tentang pola ini: https://maxgreenwald.me/blog/do-more-with-run
    • Sebenarnya itu pun tidak perlu; cukup panggil fungsi secara langsung, maka tipe kembaliannya akan diinferensi
      Jika ingin menghindari IIFE karena tidak suka () di akhir, definisikan saja fungsinya secara terpisah lalu panggil

  • Saya sedang menulis compiler dengan TypeScript, dan setuju bahwa ini tidak seburuk yang dibayangkan
    Awalnya saya mulai dengan Deno seperti penulis, tetapi akhirnya pindah ke Bun; meski masih ada bagian yang kasar, saya lebih puas dibanding Deno dan performanya sangat cepat
    Untuk frontend parser generator standar, Ohm-js cukup nyaman: https://ohmjs.org/
    Compiler resmi tsc terlalu besar sehingga tidak saya sarankan untuk dibaca; untuk melihat cara kerja tsc, mini-typescript lebih bagus: https://github.com/sandersn/mini-typescript/
    Khususnya branch centi-typescript cukup membantu: https://github.com/sandersn/mini-typescript/tree/centi-types...
    Saya menantikan GC dan akses DOM tersedia di WASM

    • Penasaran apa alasan pindah ke Bun

  • Saya kira TypeScript akan punya overhead tambahan karena interface, jadi ini cukup di luar dugaan
    Jadi penasaran apakah bisa diterapkan ke bidang lain juga, misalnya apakah cocok untuk parsing bahasa

    • Pada runtime, overhead interface adalah 0
      Interface sepenuhnya hilang pada proses kompilasi

  • Hasilnya tidak terlalu mengejutkan. Karena compiler TypeScript sendiri ditulis dalam TypeScript
    TypeScript sebagai ML sudah divalidasi setiap hari di lingkungan produksi yang berat

  • Saya pernah menulis compiler dengan C#, dan yang tampak istimewa di sini kira-kira hanya union type
    Secara pribadi saya memilih menghindari verbositas visitor pattern, dan sedang menunggu fitur enum tertutup untuk pemeriksaan kelengkapan pada waktu kompilasi

    • Kalau memakai bahasa tanpa union type atau enum ala Rust, fitur itu sangat terasa dirindukan
      Alternatifnya biasanya canggung. Entah memakai kelas untuk merepresentasikan satu sum type dengan N properti nullable dan mengandalkan syarat dalam dokumentasi bahwa “selalu hanya satu yang non-null”, atau membuat beberapa kelas mewarisi kelas bersama; keduanya terasa berat
      Untuk membuat beberapa union type yang saling tumpang tindih, kedua cara itu membutuhkan duplikasi atau kombinasi yang cerdik